Applying go methods to other games

[jhouse]

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]

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]

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]

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]

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]

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]

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]

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]

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?

[Rémi Coulom]

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.

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