Is Risk a computationally difficult game

Question

I have a free Risk app on my phone. I am amazed by how bad the AI plays even on the highest setting. Is Risk a computationally challenging game to implement in AI or is the app just bad?

Answer 1

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?

Answer 2

Yes and no. Every AI will have strategies that it uses, and some will be better than others. The combination of that and how many turns deep you're willing to execute your AI to decide on a move, and how thorough those turns are (do you roll the dice 5 times and branch each time? Or do you use every possible die roll and branch all 40 something times? etc...) will determine how long the turns take to compute and how "good" they are.

However what is more likely is the developers want to make sure you still win most of the time. Me personally I'm more than happy to have my behind handed to me by a game because I know I'm being challenged and I'm learning. Most people want to win. It's a common thread in games - winning is more fun, and more fun leads to more sales. This is true in online and offline games.

So yes, Risk can be computationally expensive. But it doesn't have to be. and if you make it expensive, it will be less fun for the more casual audience.

Answer 3

State of the art AIs are beating humans, but require more processing power is available on your phone. Here are some good background stories regarding the state of the art:
https://en.wikipedia.org/wiki/AlphaGo_Zero
https://www.pokernews.com/news/2017/10/artificial-intelligence-poker-history-implications-29117.htm

Chess AIs do really well even with modest processing power. So far, I have been unable to beat my MacBook Pro's Chess implementation allowing it only 1 second of thinking time. It is easily beat if only allowed to think 3 moves ahead. Poker and bridge are other games where AIs are doing well at a practical level. I think that the main reason Risk AIs are weak is that there is not much incentive for anyone to build a very strong AI. Risk does present some computational challenges when compared to these other games.

Here are some key factors that make an strong AI "computationally challenging":
1. Number of available choices per turn.
2. Number of opponents in the game.
3. Number of turns a game is expected to last.
4. Imperfect information, e.g. not knowing other player's cards in poker or bridge.

Let's compare Risk's complexity in these areas to the other games with Strong AIs.
Generally you have fewer choices about your very next action in Risk when compared to Chess. Probably less than 20 possible attacks most of the time. However, your choice for an overall turn involves the entire set attacks you might make. An even bigger computational challenge would be to estimate the likely results of all of the opposing moves. Much more can happen in Risk while you wait for your next turn when compared to these other games. The fact that Risk is likely to complete in fewer turns helps offset the fact that each Risk turn involves more choices.
Chess and Go are perfect information games as you know every choice available for your opponents next move when you make yours. This is unlike card games where you don't know your opponent's cards which greatly effect their choices. With imperfect information a strong AI has to account what for what each player might have AND also the choices in each case. Risk is much more like chess as most information is available to all players, so this helps reduce the amount of computing needed to consider all possibilities.
The truly hidden information in risk is the collected cards. The key information from card holdings is the likelihood of a set which is easy to compute.
Another source of imperfect information in Risk is not knowing how the dice will fall. While the exact results are known, statistics provides solutions for computers to estimate the results far more easily than the even very good human players.
Other responses to this question imply that it is not possible for an AI to understand what alliances are in place. Alliances are normally a big part of most Risk games, but the risk rules themselves don't specify how these should work. My preference is that alliances/agreements between players is open information. Players can make any agreements they want (which they are equally free to break) but must do so publicly. When I host, all agreements must be discussed in the room where the game is being played. The online site MajorCommand implements something similar making established agreements public information. Understanding such agreements and the human propensity for honoring (or not honoring) the agreements would be similar to estimating the likelihood of that a poker player is bluffing. Assuming that the information is made available to the computer in a fair fashion as is done in Major Command, I believe that a good AI should be able to make as use of the information as well as human player.
The main reason good AIs need a great deal of computational power is to look ahead many moves into the future. With Chess, I expect state of the art systems to solve the game within my kids lifetime. Today there are good systems without the need to compute 50+ moves ahead. However there are many shortcuts that provide reasonably good play with moderate computing. A key short cut is a board evaluator which assigns points based the pieces and there position on the board. AIs then consider the possibilities N moves into the future, picking the path that leads to the best scoring board. Risk is well suited for such a point system. Some of the obvious items to award points for are total armies, territories occupied, expected income including continents, and number of Risk cards. Some less obvious but import items to consider odds of being able to eliminate an opponent, and odds of being able to conquer territories to and continue collecting risk cards. Since Risk is well suited to this type of evaluation, a good-enough Risk AI would not need to think many turns into the future. Evaluating the likely moves of each player until its next turn would be enough.
In conclusion, a Risk AI has more complicated turns to evaluate but does not need to evaluate as many turns into the future compared to other games. To be effective it should evaluate the next turn of every player in the game, which is where your Risk AI is probably falling short.

Disclaimer: I am a professional programmer, but the last time I worked on a AI game engine was a hearts project in college 20+ years ago.

Answer 4

Yes and no. If the players all played independently, then the AI ought to be able to play well. Realistically this isn't how RISK is played. Players form and break alliances. So pals Al and Frank would team up on Ben. Al might just sacrifice himself so that Frank could win against Ben. The point is that Al and Frank might even do this without any open negotiation. An AI wouldn't have a preferred friend. Adding negotiating would be an additional level of complexity which would reasonable seem to require some knowledge of the players.