[Computer-go] longest 3x3 game
John Tromp
john.tromp at gmail.com
Wed Feb 17 18:39:39 PST 2016
dear Go researchers,
Finding the maximum length of a Go game, if we measure length
by number of (non-pass) moves, is equivalent to finding the longest
simple path in the game graph.
For 2x2 this can easily be brute forced, and one finds a maximum
length of 48 moves (so a single game can visit at most 49 of the 57
legal positions).
For 3x3 brute-force is already out of the question. The game graph
has 12675 nodes (the number of legal positions).
The longest I've been able to find, by more or less random sampling,
is only 521 moves, which leads me to think the longest must
be well under a thousand.
The longest path problem is not only NP complete, but also
hard to approximate, so we may never know when we get close
to the longest.
(see also https://en.wikipedia.org/wiki/Longest_path_problem)
For now I will just leave you with a challenge:
who can find the longest 3x3 game?
Assume the logical rules of Go, so that's with positional
superko, and suicide allowed, although these probably have
only minimal, if any, effect on the answer.
regards,
-John
More information about the Computer-go
mailing list