Monte Carlo chess engines

[Peteshnick]

So I know Rybka has a monte carlo analysis tool, but does anyone know of any chess engines that purely work via Monte Carlo (i.e. just pick the move that leads to the highest winning percentage in random games?)

Thanks,
Pete

[CRoberson]

So I know Rybka has a monte carlo analysis tool, but does anyone know of any chess engines that purely work via Monte Carlo (i.e. just pick the move that leads to the highest winning percentage in random games?)

Thanks,
Pete

Your terminology is a bit spread. So, I am going to state multiple possibilities.

1) Build a book based on a large number of "random games" that you collected and have the program play completely from that book. Yeah, been done. Problem is that very few games will stay in book.

2) A real Monte Carlo engine would sample the state space randomly. It would at any given position, randomly pick which moves it will search, then make those moves and recursively repeat the random pick of which moves it will search at the new position.

Sure, it can be done. Some engines have random modes (they randomly choose a move without search). The full Monte Carlo technique that I described wouldn't perform well due to unintelligent/random forward pruning.

How is that different from Monte Carlo analysis? Rybka doesn't randomly pick at all search plies.

3) This leads to another possible Monte Carlo player: it randomly chooses which moves to search at the root node and searches each move normally picking the best of those moves at the end of the search period.

There are many ways to create a Monte Carlo player; those mentioned are just a few. Notice that 2 & 3 don't use previously played games.

[lmader]

So I know Rybka has a monte carlo analysis tool, but does anyone know of any chess engines that purely work via Monte Carlo (i.e. just pick the move that leads to the highest winning percentage in random games?)

Thanks,
Pete

Your terminology is a bit spread. So, I am going to state multiple possibilities.

1) Build a book based on a large number of "random games" that you collected and have the program play completely from that book. Yeah, been done. Problem is that very few games will stay in book.

2) A real Monte Carlo engine would sample the state space randomly. It would at any given position, randomly pick which moves it will search, then make those moves and recursively repeat the random pick of which moves it will search at the new position.

Sure, it can be done. Some engines have random modes (they randomly choose a move without search). The full Monte Carlo technique that I described wouldn't perform well due to unintelligent/random forward pruning.

How is that different from Monte Carlo analysis? Rybka doesn't randomly pick at all search plies.

3) This leads to another possible Monte Carlo player: it randomly chooses which moves to search at the root node and searches each move normally picking the best of those moves at the end of the search period.

There are many ways to create a Monte Carlo player; those mentioned are just a few. Notice that 2 & 3 don't use previously played games.

From what I know, the idea for using Monte Carlo techniques in board games is similar to your option #2 above. Randomly play out a given position to the conclusion of the game, thousands of times, and use the outcomes of all of these thousands of games to choose the move that had the best outcome.

It has had good results for Go programs (programs that play the game of Go, aka Wei Chi). Don't know much about how useful it has been for chess, given that current search/eval techniques for chess are so successful.

[Peteshnick]

From what I know, the idea for using Monte Carlo techniques in board games is similar to your option #2 above. Randomly play out a given position to the conclusion of the game, thousands of times, and use the outcomes of all of these thousands of games to choose the move that had the best outcome.

It has had good results for Go programs (programs that play the game of Go, aka Wei Chi). Don't know much about how useful it has been for chess, given that current search/eval techniques for chess are so successful.

Yeah this is exactly what I was thinking. Does anyone have any links to (free) engines that do this? Thanks!

[CRoberson]

From what I know, the idea for using Monte Carlo techniques in board games is similar to your option #2 above. Randomly play out a given position to the conclusion of the game, thousands of times, and use the outcomes of all of these thousands of games to choose the move that had the best outcome.

It has had good results for Go programs (programs that play the game of Go, aka Wei Chi). Don't know much about how useful it has been for chess, given that current search/eval techniques for chess are so successful.

Yeah this is exactly what I was thinking. Does anyone have any links to (free) engines that do this? Thanks!

Why do you want such a program? It would play chess weakly if not poorly. The domain in which this could work are domains where the search space is very large and there aren't good predictors on the worth of a position. In Chess, we have some good predictors for the value of a position without having to search to the end of the game.

[CRoberson]

From what I know, the idea for using Monte Carlo techniques in board games is similar to your option #2 above. Randomly play out a given position to the conclusion of the game, thousands of times, and use the outcomes of all of these thousands of games to choose the move that had the best outcome.

It has had good results for Go programs (programs that play the game of Go, aka Wei Chi). Don't know much about how useful it has been for chess, given that current search/eval techniques for chess are so successful.

Yes, #2 would be a likely method, but it I see other ways to do it that are likely better.

[Peteshnick]

Why do you want such a program? It would play chess weakly if not poorly. The domain in which this could work are domains where the search space is very large and there aren't good predictors on the worth of a position. In Chess, we have some good predictors for the value of a position without having to search to the end of the game.

Well, for one thing, I play chess pretty weakly myself, so it might not be so bad for me . Seriously, I like the idea of these because they are unbiased with respect to current chess knowledge - i.e. they don't use any subjective heuristics. Perhaps some new fundamental insight about chess can be discovered by such analysis (the current knowledge may be a local maximum, but not global..)

Mainly though, I'm just curious to see how it plays.

[Eastendboy]

From what I know, the idea for using Monte Carlo techniques in board games is similar to your option #2 above. Randomly play out a given position to the conclusion of the game, thousands of times, and use the outcomes of all of these thousands of games to choose the move that had the best outcome.

It has had good results for Go programs (programs that play the game of Go, aka Wei Chi). Don't know much about how useful it has been for chess, given that current search/eval techniques for chess are so successful.

Yeah this is exactly what I was thinking. Does anyone have any links to (free) engines that do this? Thanks!

Why do you want such a program? It would play chess weakly if not poorly. The domain in which this could work are domains where the search space is very large and there aren't good predictors on the worth of a position. In Chess, we have some good predictors for the value of a position without having to search to the end of the game.

In general, I think Monte Carlo could be very useful for endgame analysis.

One of the first scenarios that comes to mind is coping with tree explosions. This happens quite a lot in complex near endgame positions where knowledge and evaluation lock horns. When faced with a plethora of moves with more or less the same evaluation, engines have a tendency to get lost in the weeds. Monte Carlo might help make sense of the chaos. In such positions, every bit of information helps and playing the game out could help resolve situations where the engine is overly optimistic in positions where it's unwarranted.

For example, the unstoppable pawn scenario in the Programming forum is the kind of position where Monte Carlo might be extremely useful. Here's a link to the topic:
http://www.talkchess.com/forum/viewtopic.php?t=34879

[svchbe]

yes writing a chess engine based on a monte carlo approach is possible.
But it wouldn't be possible to get it strong...
That's because chess is a drawish game.
Go has in 99.999% a winner there are some positions that are drawn, but the only occur so rarely or even only in theory... so they are always neglected...
anyway if you would montecarlo search in the chess startposition you end up with no clear move... basicly you get something around ~70% draw and inconclusive results for the winning percentages...
so you end up doing classic chess eval on the moves that are in the ballpark of each other considering the associated error bars...
so it's an inefficient way to do pruning