Applying go methods to other games

Monte Carlo Tree Search
jhouse
Posts: 3
Joined: Tue Feb 12, 2008 5:47 pm

Applying go methods to other games

Post by jhouse » Tue Feb 12, 2008 6:23 pm

Remi wrote (on computer go mailing list):
> I expect checkers and abalone to be very easy to attack with MC methods.
I am not so sure. Of course it is easy to write a MC program for any
game. But I do not expect that it would be competitive with the
classical approach for Abalone. Checkers is solved, anyway.

MC seems to be working already for Hex and Amazons, since, as you wrote
in your other post, they are so similar to Go. I talked with Julien
Kloetzer in Hakone, who is working on applying MC algorithms to Amazons.
I know some Hex programmers have successful experiments with MC methods too.
I was probably mistaken about checkers. Kings may really mess things up. Abalone seems doable, but I definitely agree that Hex and Amazons are way easier to do with MC methods.

Would the programmers you know be open to a cgos style of interface? I'd love to see a simple gtp-like client-side interface and a basic server for testing. If someone standardized that stuff and wrote the viewer (like cgosview), I'd definitely code up a module for my bot to compete on those servers.

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Universal protocol

Post by Rémi Coulom » Tue Feb 12, 2008 6:42 pm

jhouse wrote:Would the programmers you know be open to a cgos style of interface? I'd love to see a simple gtp-like client-side interface and a basic server for testing. If someone standardized that stuff and wrote the viewer (like cgosview), I'd definitely code up a module for my bot to compete on those servers.
I am not sure that these less popular games could have enough programmers to provide sustained activity on a CGOS-like server. But standardizing a protocol for use in servers and tournaments looks like a useful idea.

Rémi

Russell Reagan
Posts: 1
Joined: Tue Feb 12, 2008 7:35 pm

Re: Applying go methods to other games

Post by Russell Reagan » Tue Feb 12, 2008 8:13 pm

jhouse wrote:Remi wrote (on computer go mailing list):
> I expect checkers and abalone to be very easy to attack with MC methods.
I am not so sure. Of course it is easy to write a MC program for any
game. But I do not expect that it would be competitive with the
classical approach for Abalone. Checkers is solved, anyway.

MC seems to be working already for Hex and Amazons, since, as you wrote
in your other post, they are so similar to Go. I talked with Julien
Kloetzer in Hakone, who is working on applying MC algorithms to Amazons.
I know some Hex programmers have successful experiments with MC methods too.
I was probably mistaken about checkers. Kings may really mess things up. Abalone seems doable, but I definitely agree that Hex and Amazons are way easier to do with MC methods.

Would the programmers you know be open to a cgos style of interface? I'd love to see a simple gtp-like client-side interface and a basic server for testing. If someone standardized that stuff and wrote the viewer (like cgosview), I'd definitely code up a module for my bot to compete on those servers.
MC stands for Monte Carlo, I assume? I've known about monte carlo methods used in poker playing programs, but how are they used in go, hex, or amazons?

At least personally, I am familiar with chess programming techniques, and I have been interested in other games, but I never spent much time on them (beyond writing a basic program capable of playing legal hex and amazons). There was never the infrastructure in place that computer chess had (standards, protocols, interfaces, servers, forums, etc).

I think it would be helpful if there was a quick way to get "up to speed" on the current state of the different games being discussed here. I would like to know what techniques are used in other games, like hex and amazons, and how they are different from chess. Even just a few lines discussing the general ideas would be great. I see we're off to a good start by posting some good links :)

I would also like to know what infrastructure is available for each game (standards, protocols, interfaces, servers, etc). I think it's an important area to consider in order to improve interest in other games.

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Applying go methods to other games

Post by Rémi Coulom » Tue Feb 12, 2008 9:11 pm

Russell Reagan wrote:MC stands for Monte Carlo, I assume? I've known about monte carlo methods used in poker playing programs, but how are they used in go, hex, or amazons?
Monte Carlo algorithms are a new family of search algorithms, that completely revolutionized computer Go. In one year of time, between the Computer Olympiad of Italy (2006) and the Computer Olympiad of Amsterdam (2007), 9x9 Go programs have improved by about 600 Elo points thanks to this method. Monte-Carlo algorithms is now the dominating approach to Go, on 9x9, and 19x19 as well.

If you understand the rules of Go, these slides should be an easy introduction:
http://remi.coulom.free.fr/Hakone2007/
The paper that started the current MC trend is this one:
http://remi.coulom.free.fr/CG2006/
Several significant improvements have been made since then. Some important papers are:
http://www.machinelearning.org/proceedi ... rs/387.pdf
http://hal.inria.fr/inria-00117266
http://remi.coulom.free.fr/Amsterdam2007/
http://www.math-info.univ-paris5.fr/~bo ... S-2007.pdf

The last paper of this list has a very nice description of MC tree search, with figures that explain how it works very clearly.
I would also like to know what infrastructure is available for each game (standards, protocols, interfaces, servers, etc). I think it's an important area to consider in order to improve interest in other games.
Besides those that I mentioned in other posts, an important standard is sgf:
http://www.red-bean.com/sgf/

Rémi

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Applying go methods to other games

Post by Rémi Coulom » Wed Apr 09, 2008 2:04 pm

This paper presents an application of Monte Carlo search to Othello:
http://www.wfg.csse.uwa.edu.au/publicat ... G2007g.pdf

Rémi

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Applying go methods to other games

Post by Rémi Coulom » Tue May 06, 2008 4:44 pm

Application to Same Game:
http://www.cs.unimaas.nl/maarten.schadd ... GameCG.pdf

Title: Single-Player Monte-Carlo Tree Search

Abstract. Classical methods such as A* and IDA* are a popular and
successful choice for one-player games. However, they fail without an
accurate admissible evaluation function. In this paper we investigate
whether Monte-Carlo Tree Search (MCTS) is an interesting alternative
for one-player games where A* and IDA* methods do not perform
well. Therefore, we propose a new MCTS variant, called Single-Player
Monte-Carlo Tree Search (SP-MCTS). The selection and backpropagation
strategy in SP-MCTS are different from standard MCTS. Moreover,
SP-MCTS makes use of a straightforward Meta-Search extension. We
tested the method on the puzzle SameGame. It turned out that our SPMCTS
program gained the highest score so far on the standardised test
set.

luke_g
Posts: 29
Joined: Sun Feb 17, 2008 9:52 am

Re: Applying go methods to other games

Post by luke_g » Thu May 08, 2008 6:26 am

Rémi Coulom wrote:Application to Same Game:
http://www.cs.unimaas.nl/maarten.schadd ... GameCG.pdf

Title: Single-Player Monte-Carlo Tree Search

Abstract. Classical methods such as A* and IDA* are a popular and
successful choice for one-player games. However, they fail without an
accurate admissible evaluation function. In this paper we investigate
whether Monte-Carlo Tree Search (MCTS) is an interesting alternative
for one-player games where A* and IDA* methods do not perform
well. Therefore, we propose a new MCTS variant, called Single-Player
Monte-Carlo Tree Search (SP-MCTS). The selection and backpropagation
strategy in SP-MCTS are different from standard MCTS. Moreover,
SP-MCTS makes use of a straightforward Meta-Search extension. We
tested the method on the puzzle SameGame. It turned out that our SPMCTS
program gained the highest score so far on the standardised test
set.
So, basically this paper says UCT does well in single-player games, or at least SameGame.

I'm not sure why the focus on A* as a comparable algorithm. A* is for when you need to find optimal solutions, while MC will never guarantee it. I think I must be misunderstanding something, because they list results for an A* algorithm that clearly aren't optimal ?

(Unrelatedly) Is SameGame a common benchmark for search techniques?

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Applying go methods to other games

Post by Rémi Coulom » Thu May 08, 2008 12:31 pm

luke_g wrote:I'm not sure why the focus on A* as a comparable algorithm. A* is for when you need to find optimal solutions, while MC will never guarantee it. I think I must be misunderstanding something, because they list results for an A* algorithm that clearly aren't optimal ?
In their experiments they compare to IDA* (approximate A*, not optimal), and the current best program by Billings.
(Unrelatedly) Is SameGame a common benchmark for search techniques?
I don't know. I suppose they chose SameGame because it has nice properties that allow Monte-Carlo search to work: it is possible to select moves at random and finish the game. That would not work at all for Numbrosia, for instance.

Tristan Cazenave also applied a kind of single-player MC search to "Morpion Solitaire":
http://www.ai.univ-paris8.fr/~cazenave/reflexmc.pdf

Rémi

spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: Applying go methods to other games

Post by spurious_ai » Thu May 08, 2008 8:45 pm

JT's Blocks on Yahoo is like Same Game but on a 9 x 14 grid also with 5 colors. Even on the smaller grid it would be hard to find the optimal solution using A* in a reasonable time (36 moves on average). The branching factor does decrease quickly, but starts very high.

I used my JT's Blocks program as the starting point for my Numbrosia program. It does not guarantee the optimal solution, but in Numbrosia it found many optimal solutions in a few minutes that took the optimal programs many orders of magnitude longer. Run time is linear based on the number of moves.

luke_g, your solution for 20+ move Numbrosia puzzles take over a day, how long would a 30 move puzzle take? At some point you have to abandon the idea of optimal, and find a method that gives you the best solution possible in a reasonable amount of time.

I think some form of MC could work for Numbrosia. Would it fail for Numbrosia because 2 consecutive ( opposite )moves do nothing?

Remi, are you still working on your Go program or off in some other research?
Last edited by spurious_ai on Thu May 08, 2008 9:10 pm, edited 1 time in total.

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: Applying go methods to other games

Post by Rémi Coulom » Thu May 08, 2008 8:56 pm

spurious_ai wrote:I think some form of MC could work for Numbrosia. Would it fail for Numbrosia because 2 consecutive ( opposite )moves do nothing?
As I wrote in my previous message, the main problem of MC for Numbrosia is that playing moves at random will never finish. It looks difficult to make random playouts intelligent enough so that they solve the problem.
spurious_ai wrote:Remi, are you still working on your Go program or off in some other research?
I am currently working on rating systems:
http://remi.coulom.free.fr/WHR/

Rémi

Post Reply