Monte Carlo algoritm?

[Klaas van der Laan]

In 2006 and 2007 a new breakthrough algorithm for computer go (Monte Carlo Tree Search), was developed in France. This new approach plays thousands of pseudorandom games each second, and collects statistics on the moves to choose where to play. With very little go knowledge, this algorithm can beat any of the traditional, knowledge-based, go programs. However the playing style of this new algorithm is strange.
Is this algoritm also good for draughtsprograms?

[Rein Halbersma]

In 2006 and 2007 a new breakthrough algorithm for computer go (Monte Carlo Tree Search), was developed in France. This new approach plays thousands of pseudorandom games each second, and collects statistics on the moves to choose where to play. With very little go knowledge, this algorithm can beat any of the traditional, knowledge-based, go programs. However the playing style of this new algorithm is strange.
Is this algoritm also good for draughtsprograms?

Hi Klaas,

I don't know for draughts, but there was a (heated as usual) discussion on the chess forum Talkchess.com last year. http://talkchess.com/forum/viewtopic.ph ... 34&t=26945

Apparently modern versions of alpha-beta with heavy truncations and selective extensions already behave quite similar to Monte Carlo methods such as UCT. This is indeed a surprising result. On the other hand, MTD(f) and SSS* search were shown to be equivalent even though the first is a best-first and the latter a depth-first algorithm.

Rein

[Klaas van der Laan]

In 2006 and 2007 a new breakthrough algorithm for computer go (Monte Carlo Tree Search), was developed in France. This new approach plays thousands of pseudorandom games each second, and collects statistics on the moves to choose where to play. With very little go knowledge, this algorithm can beat any of the traditional, knowledge-based, go programs. However the playing style of this new algorithm is strange.
Is this algoritm also good for draughtsprograms?

Hi Klaas,

I don't know for draughts, but there was a (heated as usual) discussion on the chess forum Talkchess.com last year. http://talkchess.com/forum/viewtopic.ph ... 34&t=26945

Apparently modern versions of alpha-beta with heavy truncations and selective extensions already behave quite similar to Monte Carlo methods such as UCT. This is indeed a surprising result. On the other hand, MTD(f) and SSS* search were shown to be equivalent even though the first is a best-first and the latter a depth-first algorithm.

Rein

Hi mate,

I like the basic idea that a random algoritm is much more better then all science (of 5000 years Go) together. Of course with smart extensions it becomes yet even more stronger. But it shows the relativity of human's wisdom.
Draughts with 8piece-endgame is much smaller and easyer then Go, so you can get even much more statistics for strong moves I think.

With greetings,
Klaas.

[Rein Halbersma]

In 2006 and 2007 a new breakthrough algorithm for computer go (Monte Carlo Tree Search), was developed in France. This new approach plays thousands of pseudorandom games each second, and collects statistics on the moves to choose where to play. With very little go knowledge, this algorithm can beat any of the traditional, knowledge-based, go programs. However the playing style of this new algorithm is strange.
Is this algoritm also good for draughtsprograms?

Hi Klaas,

I don't know for draughts, but there was a (heated as usual) discussion on the chess forum Talkchess.com last year. http://talkchess.com/forum/viewtopic.ph ... 34&t=26945

Apparently modern versions of alpha-beta with heavy truncations and selective extensions already behave quite similar to Monte Carlo methods such as UCT. This is indeed a surprising result. On the other hand, MTD(f) and SSS* search were shown to be equivalent even though the first is a best-first and the latter a depth-first algorithm.

Rein

Hi mate,

I like the basic idea that a random algoritm is much more better then all science (of 5000 years Go) together. Of course with smart extensions it becomes yet even more stronger. But it shows the relativity of human's wisdom.
Draughts with 8piece-endgame is much smaller and easyer then Go, so you can get even much more statistics for strong moves I think.

With greetings,
Klaas.

It's a bit more subtle than "Monte Carlo = random algorithm > humans". The plain Monte Carlo with purely random playouts is not nearly competitive with any human or other program. Only by strongly biasing the search and lots of other enhancements does it become possible to get a competitive algorithm. This is familiar from chess & draughts: purely naive minimax searches half the depth in the same time as clever alpha-beta with lots of enhancements based on decades of experiments.

My view is the one of Deep Blue author Feng - Hsiung Hsu: it's not a competition of man vs machine, but rather of "man the player" vs "man the toolmaker". Interestingly, Hsu is now also active in the Go arena: http://spectrum.ieee.org/computing/software/cracking-go