Monte Carlo chess

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Rob

Monte Carlo chess

Post by Rob » Sun Jul 22, 2007 5:47 pm

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.

User avatar
Mike S.
Posts: 1480
Joined: Thu Mar 09, 2006 4:33 am

Re: Monte Carlo chess

Post by Mike S. » Sun Jul 22, 2007 6:27 pm

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.
Regards, Mike

bob
Posts: 20358
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Monte Carlo chess

Post by bob » Sun Jul 22, 2007 6:44 pm

Rob wrote: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.

User avatar
Zach Wegner
Posts: 1922
Joined: Wed Mar 08, 2006 11:51 pm
Location: Earth
Contact:

Re: Monte Carlo chess

Post by Zach Wegner » Sun Jul 22, 2007 7:20 pm

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
Posts: 405
Joined: Mon Apr 24, 2006 6:06 pm
Contact:

Re: Monte Carlo chess

Post by Rémi Coulom » Mon Jul 23, 2007 10:12 am

Zach Wegner wrote: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
Posts: 405
Joined: Mon Apr 24, 2006 6:06 pm
Contact:

Re: Monte Carlo chess

Post by Rémi Coulom » Mon Jul 23, 2007 10:15 am

bob wrote: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

Post Reply