Risk compared to Backgammon

[premio53]

I have played Backgammon for many years and realize how strong computers have come vs humans by simply knowing dice probabality. Would it be possible for someone to create a Risk program on any one specific map that would play beyond any human's ability? A computer program that would take into account dice probability along with strategy on a specific map? I believe it would be very much possible.

[premio53]

I might add for those who aren't familiar with Backgammon that computers don't win every game but over a series of games (called matches) computers will almost always win even against the top human players. I don't see why the same thing couldn't happen on a given map on Conquer Club that is obviously more complicated than Doodle.

[TeeGee]

It's not only possible, it has been done a few times, there are a few "risk" programs out there with various levels of artificial intelligence.

[Metsfanmax]

I started coding one for the Classic map a couple years back, but lost interest before I finished it. It's fairly simple to code in principle, and the Classic map is small enough that you should be able to brute force it on a 1v1.

[Army of GOD]

Little do you know that I am an actual computer.

[premio53]

It's not only possible, it has been done a few times, there are a few "risk" programs out there with various levels of artificial intelligence.

I have "RisK II" but it is far from world class as far as playing strength in my opinion. "GnuBackgammon" and "Snowie" are a couple of world class programs that will beat even the human World Backgammon Champion in matches. If there was a comparable program for Risk I believe it would get some kind of recognition.

[Kaskavel]

Little do you know that I am an actual computer.

Lol...
Seriously now...
For a very strong program in strategy games, we typically need a strong sponsor to support the procudure. It is not a coincidence that most money have been invented in chess programs, then in checkers, othello, go and backgammon and then for others. I imagine we will not find out soon how strong can a computer in RISK, because the world influence of the game is not so big as other games (it is, but not as much as the other games I mentioned). A program created by an amateur will definitely be interesting, but probably not the maximum our technology can do.

[frankiebee]

The problem with Risk is that it is most of the times more than 2 players. In 6 players games responding on the opponents strategy is as important as your own strategy. This would make it hard for a computer to get a significant advantage...

[Metsfanmax]

The problem with Risk is that it is most of the times more than 2 players. In 6 players games responding on the opponents strategy is as important as your own strategy. This would make it hard for a computer to get a significant advantage...

Game-playing algorithms don't really know about strategy to begin with. If you can brute force your way through all the possible scenarios, it doesn't matter what your opponent's strategy is; you're still going to be making the best objective move. The problem is that with six players, it becomes increasingly more computationally demanding to sort out all the possible plays.

[Chariot of Fire]

Interestingly if you take perhaps the most complex game (chess) with its myriad of strategies and permutations, you only have 20 possible options on your opening move. Thereafter it becomes exponential as the board opens up. Risk on the other hand has many many more options on your opening move, but thereafter those options remain pretty constant (even diminishing oft times). Factor in the dice - not applicable in chess - and you could easily see how much better a program could be than a human at quickly determining the odds for each possible move. It's very interesting to read about Deep Blue if you're not already familiar with its history (and its rather sad demise when IBM dismantled it). It nevertheless would always require human intervention between games, otherwise a set sequence of moves would always be met by the same response - thus revealing more and more about Deep Blue's programming and ways of countering it.

Disagree with Mets statement re algorithms 'knowing strategy' to some extent (but then I know nothing of technology but everything to do with strategy games) as every game-playing program has a catalogue of strategies from which it adopts at the opening. It will play one strategy, recognise the opponent's strategy and immediately compute whether it will win or lose if it sticks to its original gambit and respond accordingly.

Tech today would make for a far more efficient (and formidable) computer than Deep Blue, whose real strength lay in its ability to compute 200 million moves per second (an extraordinary advantage in tourney-playing conditions under the clock) rather than its software.

Back on topic....Risk & Backgammon....I'd have thought a backgammon program would be much simpler to perfect. Anyone thoroughly proficient at the game realises that there are standard 'best' moves for every roll and that when two players of equal ability face one another then it really does come down to simple luck of the dice.

[Metsfanmax]

Disagree with Mets statement re algorithms 'knowing strategy' to some extent (but then I know nothing of technology but everything to do with strategy games) as every game-playing program has a catalogue of strategies from which it adopts at the opening. It will play one strategy, recognise the opponent's strategy and immediately compute whether it will win or lose if it sticks to its original gambit and respond accordingly.

It only does that for games like chess because you can't brute force the whole game, so those opening catalogs are important for saving on calculation time. But even so, what's really going on is that certain lines are given more weight than others. Now, there is some subjectivity to it when you can't brute force fully, because you have to come up with a way to score certain positions, but that's not computer 'strategy', that's just a way to make the calculation possible.

Tech today would make for a far more efficient (and formidable) computer than Deep Blue, whose real strength lay in its ability to compute 200 million moves per second (an extraordinary advantage in tourney-playing conditions under the clock) rather than its software.

Well, modern software like Rybka is really only a few hundred ELO points above Deep Blue (better than any human, of course). The algorithms have gotten much more efficient for a given processing time, for sure.

[pickleofdoom]

AIs will have no great problems with the dice probabilities. But there is also a traveling salesman type problem which arises when making a sweep, to path all the kills efficiently. This is the kind of thing where the human mind might be expected to work better than computers.

[premio53]

I didn't realize it but there have been entire books written on developing Artificial Intelligence for the game of Risk. Here is an excerpt of one conclusion reached.

http://www.google.com/url?sa=t&rct=j&q= ... kvQ4QCpzhQ

Risk is a very complex game, with both infinite game-state and game-tree complexities.
Even calculating a good approximation of the average complexity of the game proves to
be complex.

My work has shown that it is crucial in Risk to combine several actions to achieve a
high-level goal. The addition of just a single pre-defined high-level goal paired with the
means to combine several actions to achieve it, has increased the probability to win a
game by more than 60 times (Section 7.3.2), while the addition of just a high-level goal
has increased the probability by almost 20 times.

I believe that the key to building very strong Risk players are dynamic plans. Instead
of having three pre-defined high-level goals, the player would have to define reasonable
goals1 on its own using the evaluation function. Then a plan would have to be created
that would connect the actions of the player in a way that provides the highest probability
of achieving that goal. Of course, after each decision the situation would have to be re-
evaluated, though that might prove to be infeasible.

If the evaluation function determined for which high-level goal a plan would be made,
the evaluation function, and subsequently TD learning, too, would have a major effect on the playing strength.

[Funkyterrance]

Little do you know that I am an actual computer.

*flips over AoG*
Yup, says right here: "Made in Bangladesh".

[Haggis_McMutton]

The problem with Risk is that it is most of the times more than 2 players. In 6 players games responding on the opponents strategy is as important as your own strategy. This would make it hard for a computer to get a significant advantage...

Game-playing algorithms don't really know about strategy to begin with. If you can brute force your way through all the possible scenarios, it doesn't matter what your opponent's strategy is; you're still going to be making the best objective move. The problem is that with six players, it becomes increasingly more computationally demanding to sort out all the possible plays.

Well, first of all, with 6 players it seems extremely intractable. Assuming a ridiculously small branching factor of 3. it would take you 3^6 branches to go to depth 1. Assuming again a ridiculously low 10 rounds maximum game length, that gives you 3^60 branches in the complete game tree, which is of course absurd. Yeah, pruning will help but still it's way off.

Secondly, now that min-max fails you have to derive a evaluation function for intermediate nodes. This seems to me EXTREMELY more difficult to do in 6 player risk than in chess. For instance, is it a good thing to have 30% of the armies with all of the 6 players still alive? Or does it mean they will now gang up on you ?
Is it a good thing to have a large bonus? Or does it's size assure that you'll lose it before your next turn.
How does the relative capability of the opponents factor into these kinds of decisions? What about diplomacy, should you be able to offer truces?

I think a world-class Risk AI (in multiple player games) is way off. We don't even have world class poker AIs yet.