Re: computer-go: Programming the capturing game

[Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxx>]

Tristan Cazenave wrote:
> 
> > Has anyone written a program that will play the capturing game?  It would
> > seem, from my naive perspective, to be a rather trivial task for those who
> > have written engines to play the 'real' game of go.  Assuming that it has
> > not already been done, could I interest anyone in doing so?  Or, failing
> > that, could someone point me in the direction of some suitable starting
> > point for algorithms which would be useful in developing a program whose
> > goal is merely to be the first to capture a stone?
> >
> 
> I have written such a program. I solved AtariGo 6x6 with a crosscut in
> the
> center. Win for the first player.
> 
> I published a paper about it last month. You can have a look at it at:
> 
> http://www.ai.univ-paris8.fr/~cazenave/AGPS-RFIA.pdf
> 

Interesting, you seem to claim that alpha-beta would take years. I just
tested the 6x6 with cross-cut and solved the problem in 543 seconds (on
a P3 with several other running processes). My program used alpha-beta
with standard search enhancements such as itt.deepening, history
heuristic, killer moves and a transposition table.

It seems that the cross-cut is much easier than the empty board. The
cross-cut is solved by my alpha-beta at depth 15. For the empty 6x6
board I once ran a process for several weeks till at depth 23 someone
was so kind to create a short circuit :-( The solution is at least at 24
but probably even deeper...

Erik