Is Risk a computationally difficult game
Disclaimer: I have some programming background but haven't ever actually tried to make a Risk AI, so this isn't 100% definitive.

Although making a "perfect" Risk AI might be, it seems like it wouldn't in theory. At the end of the day, Risk is a resource management game, and that's something a computer can do.

For starters, the combat mechanism is fairly straightforward. There's only 6 basic types of fights (1-1,2-1,3-1,1-2,2-2,3-2), and everything else is just an extension of those parameters. The average value and variance of these can easily be hard-coded, so it's simple for the computer to calculate the probabilities. And one of those, the 3-2, is the most common by far. I would imagine the average advantage of an attacker in that fight (quick Google search showed 0.158 men per roll) would be an important number in Risk strategy as a whole. The only other source of luck, the cards, can be estimated as well. 

After that, there's the risk-reward decisions. What's the value in holding territory, vs. the risk of over-extending? Well, the value is the armies, and that can be calculated. There's 0.33 for the territory, some large number for the card if it's the first attack, some amount for the inroads to a continent, and some amount for the possibility of a elimination and the cards that could come with it. The value of the cards can be determined (but I imagine that it would be large enough to turn into "Always take over something if it's even remotely possible, and if there's a good chance of taking someone out without completely destroying the current defensive position go for it, especially if a set is guaranteed.") The continent effect can also be easily calculated by determine the probability of wiping the continent (which is just a bunch of battles that are already well defined.)

The risk of being overrun would be along the lines of "this is how many armies my opponent is mustering. If he puts them all on his front line what happens to my income?" and uses that to determine what sized defense force is good enough. In a situation where continents aren't a thing, it might be far more reasonable to not worry about defense and focus on attacks (since the attacker has the advantage in all situations with more than 3 armies.)

The map positioning would be a bit more difficult, but I'm sure that it can be solved, even with just simulations worst case.

The problem with a Risk AI is two fold:

1) A computer will not be able to perform effective diplomacy. Regardless of how much player history the game remembers, there's still a human element of "who has the target on their back" that a computer will just not be able to match. Especially in games with multiple humans and multiple bots, the bots don't "know" if the humans are in an alliance or not. It'll see weakly defended borders and think "Well, as long as my borders are bigger, they'll go for the easier prey instead" without knowing that it's because of a mutual agreement.

2) What's the value in it? Thought it might not be 100% be "winning humans are happy humans, let the humans win," I'm sure that a minor part of it. However, the bigger question is the luck vs. skill curve. Unless or until a game becomes 100% luckless, there will eventually be a point where further thought or processing just doesn't make sense. Especially in a situation where the human using the device just wants to get to their next turn. Especially in Risk, where variance is high and there's little way of being able to mitigate it, it doesn't make sense to make a bot that does the "perfect move every time" because the advantage gained is dwarfed by the variance. Especially when the computer can just as easily manipulate said variance ever so slightly.....

I remember playing an old PC Risk game where the computer would Ping-Pong between 4 different battles, as it re-calculates after each roll what the most profitable attack would be. So they do exist. But I would imagine that for most apps out there AI is just tacked on. Heck, there's a non zero chance the difficulty just determines how much the computer "cheats" and the actual AI decision making is just always the same (I'm sure some manager eventually determined that a "high-end Risk bot" would not increase revenue enough to warrant the development time.) 

At the end of the day, Risk is NOT a game where people at the end of it will think "Wow, the AI in this game was remarkable! They're always able to find ways to hit weak points, and have just enough people on defense to prevent mass invasions. I was beaten hands down by tactics alone, and the computer didn't cheat at all!" Why, then, bother with making a really difficult bot?