Re: computer-go: Programming the capturing game

[Bruno Bouzy <Bruno.Bouzy@xxxxxxxxxxxxxxxxxxxxxxxx>]

Tristan Cazenave wrote:
> You wrote your solution is depth 15, and the shortest
> one
> I found was depth 17... I am quite interested in seeing
> your solution...
I carefully read your AGPS paper which is very interesting.
AGPS algorithm seems to be a too selective search to me because, if
my reading is correct,
the diagonal move on the 6x6 cross-cut position leads to a13 ply capture
sequence.
:-|

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
>

-- 
---------------------------------------------------------------------
        Bruno Bouzy
        C.R.I.P.5 - UFR de mathematiques et d'informatique
        Universite Rene Descartes (Paris V) 
        45, rue des Saints-Peres 75270 Paris Cedex 06 FRANCE
        tel: (33) (0)1 44 55 35 58 fax: (33) (0)1 44 55 35 35
        e-mail: bouzy@xxxxxxxxxxxxxxxxx 
        http://www.math-info.univ-paris5.fr/~bouzy/
---------------------------------------------------------------------