computer-go: 5x5 Go is solved

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

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

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)

The main reason why my search was able to solve 5x5 is Benson's
algorithm which reduced the depth where a proven full-board-win is
detected by at least 6 plies (compared to by old implementation which
had to play many things out).

Only the simple (japanese) ko-rule was used, so the result is
independent of any superko-rule. This does not mean that super-ko is
irrelevant, just that from the empty 5x5 board there is a forced line
that avoids all long cycles. 

I'm currently trying some other small board variants too and I'd like to
use the situational super-ko rule. My current implementation for
detecting situational super-ko seems to have no problem with the empty
5x5 board (it's giving the same result, which is obvious) but I have a
nagging feeling that something is not completely ok. Basically the
problem is that some positions can be evaluated without actually making
the moves because they has been examined and stored in the transposition
table. Now if a transposition is found with a different history, the
value can (at least in principle) be different due to the different
history. This problem is known as (or at least related to) the Graph
History Interaction (GHI) problem. In principle it can be solved by
storing the history of each position in the table, this however is not
very practical since it would slow down the search and enormously
decrease the amount of transpositions. If anyone has an efficient
solution for this, or could convince me that it cannot occur in practise
I'd be grateful.

Erik.


PS. David, nice prediction ;-)