Monte Carlo chess

[Rob]

In go programming they're having success with the monte carlo method,
where you evaluate by playing a great number of random games and looking at the
win/loss ratio. I've adapted my chess engine to do something similar
by playing 1000 random games per rootmove and then choosing the move with the highest
score. With the 300 WinAtChess positions it scored on a very slow VIA C3 700MHz:

random:...............7
Monte Carlo:......46 (took about 6 hours)
Normal:...............250 (1 second per position)

I think this is an interesting result, certainly higher that I expected.
This method is embarrassingly parallel. I wonder how many processors are needed
to catch up with a strong normally searching engine.

[Mike S.]

I wonder if it's possible to use this method with a 2 ply search within reasonable time... or would that be too time consuming already? Maybe 200 2 ply-games give better results than 1,000 with rootmoves. I can only guess.

(Is my assumption correct that 'rootmove' means, move selection by best eval after 1 ply, and without quiescence search?)

Also, positions like WAC, although mostly easy, often require (short or less short) sacrifice combos... I guess the Monte Carlo method will perform relatively better in 'silent' positions where the challenge is to find a promising or at least reasonable positional decision.

[bob]

In go programming they're having success with the monte carlo method,
where you evaluate by playing a great number of random games and looking at the
win/loss ratio. I've adapted my chess engine to do something similar
by playing 1000 random games per rootmove and then choosing the move with the highest
score. With the 300 WinAtChess positions it scored on a very slow VIA C3 700MHz:

random:...............7
Monte Carlo:......46 (took about 6 hours)
Normal:...............250 (1 second per position)

I think this is an interesting result, certainly higher that I expected.
This method is embarrassingly parallel. I wonder how many processors are needed
to catch up with a strong normally searching engine.

would seem to me that this would get crushed by a strong tactical program since the depth of those 1000 games would be so shallow.

[Zach Wegner]

This should probably go in the programming subforum. Anyways, I've experimented with it a bit, but in a different way. I replaced my qsearch with a loop that plays a certain number of moves for each side a certain number of times and averages out the eval after each sequence. The moves are also obtained by the normal move sorting, with a 50% chance of the first move being taken, 25% the next, and so on. (This is simple to do with taking successive bits of a random number) I ran a test with moves=2 and games=10 on wac at 1 sec per position and came up with 62/300.

I think some promise may lie in UCT. Pure MC in go seems to be very weak. I want to implement UCT in chess, but I'd like to do it in my go program first.

[Rémi Coulom]

I think some promise may lie in UCT. Pure MC in go seems to be very weak. I want to implement UCT in chess, but I'd like to do it in my go program first.

Right, "pure" MC is not efficient in Go either. You have to do UCT (no alpha-beta), use a clever non-uniform random move selection mechanism, and also use domain knowledge to bias the tree growth, with priors or progressive widening.

Rémi

[Rémi Coulom]

would seem to me that this would get crushed by a strong tactical program since the depth of those 1000 games would be so shallow.

I don't believe it is possible to make a strong MC chess program. But I would find it very interesting. I expect it would have a very original playing style, and would not be materialistic at all. I am a little bit tempted to try it, but I prefer to focus my efforts on Go.

Rémi