Re: computer-go: 5x5 Go is solved

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

Andrew Derrick Balsa wrote:
> 
> Hi Erik,
> 
> Congratulations!
> 
> On Sun, 20 Oct 2002 15:27:04 -0100, "Erik van der Werf"
> <E.vanderWerf@xxxxxxxxxxxxxxxxx> said:
> > Yesterday my program solved 5x5 Go starting with the first move in the
> > centre. As was expected it is a win for the first player with 25 points
> > (the whole board belongs to black).
> >
> > I used an iterative deepening Alpha-beta search (PVS) with:
> > - Transposition tables (2-deep replacement scheme, 2 x 2^24 entries)
> > - Enhanced transposition cut-offs
> > - Symmetry lookups in the Transposition table
> > - 2 killer moves
> > - History heuristic
> > - Benson's algorithm for unconditional live (extended with unconditional
> > territory)
> > - Heuristic evaluation for positions that are not fixed by benson
> 
> Could you please expand on each of these?

I'm planning to write a paper on this, however for the time being you'll
have to do with an older paper I wrote about solving Ponnuki-Go. It can
be found at :

http://www.cs.unimaas.nl/~vanderwerf/pubdown/Solving_Ponnuki-Go_BNAIC2002.pdf

Many things of the techniques I used are already discussed there. The
new things are Benson and checking for symmetrical positions. For Benson
I'd suggest reading his original work, or easier Martin Müller's paper
at:

http://games.cs.ualberta.ca/~mmueller/ps/gpw97.ps.gz

Symmetry lookups in the Transposition table means that I check if a
mirrored or rotated version of a position has already been examined. If
this is the case the result can be re-used to narrow bounds, or directly
return the score.


> >
> > The solution was found at 22 ply deep (23 for the empty
> > board).(searching 4.472.000.000 nodes in about 4 hours on a P4 2.0Ghz)
> 
> That gives us 310k nps, or one node every 3 microseconds; very efficient
> coding. In what language did you code your program? Do you plan to
> release it?

C. No plans yet.


> It would be nice to have the complete solution in the form of a table,
> that one could download for future use.

How do you picture this? Should I just save my complete transposition
table? The search only generates a small fraction of all the possible
legal states on a 5x5 board. I'm not sure how usefull it is to have this
in a table. Further, there may be a practical problem with storage and
download capacity (my network is quite slow :-( ).

Erik.