Re: computer-go: Programming the capturing game

["Tristan Cazenave" <cazenave@xxxxxxxxxxxxxxxxx>]

great!

I also used iterative deepening and transposition tables,
but I did not use the history heuristic and the killer
moves.
I will try with these heuristics in both alpha beta and
AGPS and see how they compare...
Do you have other move ordering heuristics ?
(I start with the liberties of the string that has the
less liberties...)

You wrote your solution is depth 15, and the shortest one
I found was depth 17... I am quite interested in seeing
your solution...

So the next challenge is solving the empty 6x6 board ?
Is it harder than the 8x8 board with a cross cut ?

Tristan Cazenave.


----- Original Message -----
From: Erik van der Werf <E.vanderWerf@xxxxxxxxxxxxxxxxx>
To: <computer-go@xxxxxxxxxxxxxxxxx>
Sent: Tuesday, February 05, 2002 3:46 PM
Subject: Re: computer-go: Programming the capturing game


> 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
>