Solving 6x6 Go

The NWO-funded Go for Go project hereby applies for 60,000 hours of processor time on Huygens or at least equivalent super-computing machinery for solving 6x6 Go starting between June and August 2007. Go is a partisan two-player, perfect-information game of no chance. Today, Go remains an open challenge for Artificial Intelligence. Solving 6x6 Go is a cornerstone in meeting this challenge. Due to the search space complexity, solving 6x6 Go can only be achieved by means of a super-computing facility. In 2003, Erik van der Werf et al. [1] earned well-deserved acknowledgement beyond the computer-game community by solving 5x5 Go [2]. Up to now, this achievement is outstanding. No solution for larger game boards has been accomplished since. The next Go board awaiting its solution is 6x6. While solving 5x5 Go was still possible on a single CPU, the search space of 6x6 Go exceeds the computational power of any single core architecture. For a comparison it suffices to omit various complications and only point out that the number of legal game states grows by a factor larger than 100,000 from ca. 4·1011 in 5x5 Go to ca. 6·1016 in 6x6 Go [3]. Thus, the problem of solving 6x6 Go can only be achieved by state-of-the-art parallel machinery and algorithmic methodology. Estimates indicate a requirement of ca. 60,000 CPU hours on 3.0 GHz CPUs. The memory requirements for various look-up tables depend on the architecture but are estimated to ca. 4 GB per computational node. A large shared memory is essential for solving this task.