![]() |
5x5 GO IS SOLVED | ![]() |
![]() |
Subject: computer-go: 5x5 Go is solved Date: Sun, 20 Oct 2002 15:27:04 -0100 From: Erik van der Werf To: COMPUTER GO MAILING LISTYesterday 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.
![]() Optimal play for opening at b2 |
![]() Mistake at 11 |
![]() Optimal play for opening at c2 |
![]() Mistake at 6 (Even Cho Chikun missed this one) |
![]() Optimal in the center, boring :-) |