Computer Go algorithms applied to other games?

Question

Fairly recently, Computer Go programs became able to compete with humans using Monte-Carlo Search trees:

A Monte Carlo (MC) go program plays random games and easily evaluates the terminal position (win or loss). A MC program searches for moves that have high win rates, calculated from playing out at least a few hundred random games.

(This is a very simplified description. In practice one want to explore interesting branches with higher priority, so the randomness has to be controlled in some way using collected results. To play go at a reasonable level several millions of random games still have to be played out. But, hopefully it's quite fast to play randomly…)

I feel like a lot more games could be “addressed” using this method, and that could include maybe a vast majority of board games…

Two questions:

• Has the Monte Carlo method already been applied to other games? (Are there concrete implementations available?)

• For which kind of games, among those that have clearly stated rules and won't rely on complex communication between players, this method can be expected to fail?

Answer 1

Has the Monte Carlo method already been applied to other games? (Are there concrete implementations available?

Yes. This Grad paper might be of interest to you. It covers Backgammon, Bridge, Go, Scrabble, and Clobber.

• Backgammon, implementation TD-gammon.
• Bridge, implementation Bridge Barron. Probably outclassed these days by other computer implementations.
• Scrabble, implementation MAVEN.

For which kind of games, among those that have clearly stated rules and won't rely on complex communication between players, this method can be expected to fail?

Actually, Monte Carlo methods don't do very well with end games in general. You will find that many computer implementations that use Monte Carlo methods employ different algorithms when playing the endgame.

• MAVEN uses B* search algorithms during the endgame (no more tile to draw).
• MoGo uses 3x3 patterns to help identify "interesting" moves, and Upper Confidence applied to Trees (UCT) to help prune less optimal random moves from consideration and speed up searching.

While Monte Carlo methods are a useful tool in playing board games, they aren't a perfect solution. Computer Go programs using MCTS, are still unable to beat the best players on 19x19 boards without significant handicaps. Computer Bridge programs are no match for expert players. Monte Carlo methods will only approach perfect game with infinite time/space.

Answer 2

First, one needs to understand the differences between Chess and Go from a game complexity standpoint. Next, one must understand the differences between the two types of AI algorithms, and why one works for Chess and the other doesn't.

Both chess and Go are perfect information games with no stochastic elements. This means you can always see the full state of the game, and there is no chance or luck involved (no dice to roll, no unlucky card draws).

The difference between the games can thus be distilled to the number of possible moves each turn (# of decisions or choices) and the length of the game. I'm skipping a more formal analysis of search tree sizes, state space sizes, etc., in order to provide a more intuitive understanding of the differences.

For chess, the average number of possible moves at a typical point in the game is about 30 different moves. A typical game lasts about 40 moves. For Go, there are about 250 choices per move and the game lasts about 150 moves.

What this means is that there is much, much more evaluation of possible moves, far farther into the future with Go than with Chess.

However, what makes it possible for human to play is that in Go the pieces are all alike, we can target patterns instead of positions.

A traditional chess AI uses something called an Evaluation Function which uses shortcuts (like assigning more points for queens than for pawns) to evaluate a board and say that a state of the game is better or worse for one player than the other. With Go, it's very difficult to come up with an evaluation function, since the pieces are the same and territory is not set in stone until nearly the end of the game. This is why the traditional chess-AI approach to Go has failed, the larger decision and state spaces are impossible to prune, so the search is ineffective.

Now, let's flip the problem and see why using Monte Carlo on chess might be a bad idea. Since random play doesn't distinguish between 'good moves' and 'bad moves', a large majority of the random plays will be exploring obviously bad game trees. For example, sacrificing your queen for no advantage, or making it vulnerable and having the opponent not exploit it. Little information is gained by averaging in the results of individual bad moves. This type of AI will work, but it would require much more computation than the usual evaluative approach.

In short, much more of the winning/losing is evident by looking at the pieces in Chess than it is by Go.

So, why does Monte Carlo work for Go (i.e. can beat humans)? It works because both humans and computers are very bad at playing Go (compared to theoretical perfect play). Monte Carlo random play sampling works because no higher-level of understanding of patterns is necessary than can be obtained in a computationally efficient manner.

So, how do other board games compare? Let's ask ourselves these questions:

1. Can the board situation be easily evaluated?
2. How many decisions/moves are possible each turn?
3. How many decisions need to be made in a typical game?
4. How predictable are the outcomes of each move?

Most board games will show characteristics that make them far closer to chess than Go for the first 3 questions. This is highly suggestive that a chess style-AI will be easier, faster, and more effective.

Since #4 is different for both Chess and Go, let's see how it affects the two algorithms.

If we had a random factor, let's say, drawing a card from a stack of 60, each decision to draw a card will branch the game into 60 possible outcomes. Depending on what other players draw, their choices will change, which again puts us in the position of sampling many states are are highly unlikely or impossible (arguing against Monte Carlo). Meanwhile, an evaluation function can easily be written to give values to each card (combined with the state of the board).

I have not seen Monte Carlo applied to other board game AIs, and the above are some of the reasons why. Those are also the reasons why it's expected to fail. When it fails it can fail spectacularly in that it's doing boneheaded, obvious bad moves because the 'random' outcomes from the samples just happened to be irrational far down the future random choices.

If you want to read more, I suggest these sites:

http://aaai.org/AITopics/

http://beej.us/blog/data/monte-carlo-method-game-ai/

http://www.aihorizon.com/essays/chessai/intro.htm

Answer 3

Ok, I did a little bit of research. Quoting this paper:

In the last few years, several Monte-Carlo based techniques emerged in the field of computer games. They have already been applied successfully to many games, including POKER (Billings et al. 2002) and SCRABBLE (Sheppard 2002). Monte-Carlo Tree Search (MCTS), a Monte-Carlo based technique that was first established in 2006, is implemented in top-rated GO programs. These programs defeated for the first time professional GO players on the 9 × 9 board. However, the technique is not specific to GO or classical-board games, but can be generalized easily to modern board-games or video games. Furthermore, its implementation is quite straightforward. In the proposed demonstration, we will illustrate that MCTS can be applied effectively to

1. classic board-games (such as GO)
2. modern board-games (such as SETTLERS OF CATAN), and
3. video games (such as the SPRING RTS game).

So, it seems that it was already applied to some other games. And they mention explicit implementations, but don't provide links to them.