MCTS in Computer Chess?

[hbj]

Hello,

Monte-Carlo Tree Search (MCTS) has been successfully used in several games, but seems less popular in computer chess so far. Is there some news about MCTS in chess? Anyway, even if it failed to generate strong engines, there should have been reports about this failure, right?

[Uly]

The only use that MonteCarlo has had in chess is Fortress Positions, in where common methods of chess engines give a high evaluation because the draw is out of their horizon, but when MonteCarlo forces the moves is becomes evident that all plans fail and the right evaluation is 0.

It's also useful for the opposite problem, in where the engines think a position is drawn, because the winning path is very thin and out of the horizon, after enough games have been played with MonteCarlo, the winning line is found and it can be seen that there's no move to refute it, so the right evaluation should be much higher.

The problem is that these situations are very uncommon on games, so that it's not practical to spend so much resources in it, those resources are better applied increasing the engine's horizon, which is the most effective thing that can be done in the most common positions.

It has been suggested that after you have enough hardware to hit diminishing results, that you use the extra resources to run MonteCarlo, and the special MC modules would be used to modify the standard evaluations and scores (Not only to correctly evaluate fortress positions or win positions that are currently scored as draws, but to avoid the former and aim for the latter positions before they happen, scoring better against engines without a MC module).

The resources needed to do this seem significantly higher than what is currently available, and standard methods haven't yet hit a plateau, with returns that are still very high, so MC for chess is an idea that will need to be explored in the distant future, I wouldn't call it a failure yet.

[hbj]

those resources are better applied increasing the engine's horizon, which is the most effective thing that can be done in the most common positions.

Is there any experiments/trials to support this conclusion? I would appreciate it if you could give some pointers to related reports. Actually I am just considering the situation where MCTS is used as the primary strategy, rather than as a backup strategy as you've described. Is there some engine that seriously optimizes the Monte-Carlo approach particularly for chess and plays against state-of-art engines with the standard algorithms?

Both MCTS and the standard approach (let's say, PV-search) look ahead in the gaming tree, and both of them play better as the size of the explored sub-tree grows. So one possible way to compare their performance is to measure the winning rate when both are allowed to explore/evaluate the same number of tree nodes for each move.

[Uly]

Is there any experiments/trials to support this conclusion?

No, there's only anecdotal evidence. MonteCarlo was implemented in the Rybka engine, what it does is playing thousands of games against itself, which requires playing them at very low depth, which still provides relatively good results due to good evaluation at small depths. The engine takes special care in avoiding to play moves that were already played in any previous games, making all games unique to avoid any bias in statistics towards the most common played move. The efficiency comes in that the engine already avoids playing moves that are known to be losing, so they are pruned and more resources can be spent on the unclear moves.

It can be argued that this isn't really "Monte Carlo", as there is nothing random about it (the moves are tried in the way that the engine prefers them), but it's the state of the art implementation of Monte Carlo in Chess engines.

It was also found that you could get basically random samples by setting the engine to play the games at depth 1, in such case you had a result that was much bigger in game amount than at higher depths, but this produced much poorer results. As the depth decreases and the randomness goes up, the critical moves are pruned, and so, in a winning branch, the winning move was pruned every time (in all the resulting branches that now would wrongly end in draw), or in a drawing branch, the saving move would not be played in any of the games (wrongly setting this branch as lost, and avoiding it in future games).

To avoid this one needs to use MonteCarlo at higher depth, which reduces the number of games that can be played, and accuracy.

With this implementation, the results are good enough to inform you how "drawish" is the position (by draw percentage, low one indicates sharp continuations), or whether one side or the other is winning. However, it's not good at telling you what move to play.

Suppose it was run on a position with 3 playable (non-transposing) moves, for 9000 games, you could get:

Move 1: 1000 games won, 1000 games drawn, 1000 games lost.
Move 2: 500 games won, 2000 games drawn, 500 moves lost.
Move 3: 1400 games won, 200 games drawn, 1400 games lost.

Then, what move to play depends on the player's goal. If the player only needs a draw to secure first place on a tournament, move 2 is best. If the player needs to win at all costs (and doesn't mind losing), move 3 is best. And in a common scenario, move 1 is best.

A standard approach wouldn't have this dilemma, either it would have a very high evaluation for the third move (and spend most of its time in it, pruning the other two), or a very low evaluation of it, pruning it and then, picking among the other two depending of if they evaluated its own position as better (pruning move 2 with score 0.00) or worse (picking move 2 as the best it can do is draw).

So while this implementation of MC would spend 33% of the resources on each move, a standard approach would spend most of the resources on the move it thinks is more favorable.

The end result was that even though this implementation would give realistic end results percentages for the current position, the move with the best performance percentage would be a poor one, so a standard approach would easily defeat MC, and that's why very few people use MC to analyze their games or pick their moves.

If this approach doesn't convince you, then I'd say a true MCTS has not been implemented yet on a chess engine, but the random nature of it would lead me to believe that it would perform worse than current "MC" implementation.

[hbj]

Hi Uly,

Thank you for your comments. The Monte-Carlo module you described is more like an evaluation function, rather than a tree searching algorithm. Actually the "tree searching" part of the MCTS paradigm can involve zero randomness, such as the UCT algorithm, which is a totally deterministic policy that tends to generate a highly skewed tree.

[Dismas]

We don't yet have computer programs that play go as well as a decent amateur player, unfortunately. They say that playing too much against programs will build bad habit because programs have different systematic weaknesses from human players. I would recommend you try playing online on KGS against both stronger players and other beginners - check out the Beginner's Room. As far as doing go problems try something like goproblems.com or the problem pages at Sensei's Library.