[Computer-go] longest 3x3 game

95 views
Skip to first unread message

John Tromp

unread,
Feb 17, 2016, 9:39:45 PM2/17/16
to computer-go
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
_______________________________________________
Computer-go mailing list
Compu...@computer-go.org
http://computer-go.org/mailman/listinfo/computer-go

John Tromp

unread,
Feb 20, 2016, 2:36:20 PM2/20/16
to computer-go
> The longest I've been able to find, by more or less random sampling,
> is only 521 moves,

Found a 582 move 3x3 game...

Darren Cook

unread,
Feb 20, 2016, 3:06:14 PM2/20/16
to compu...@computer-go.org
>> The longest I've been able to find, by more or less random sampling,
>> is only 521 moves,
>
> Found a 582 move 3x3 game...

Again by random sampling?

Are there certain moves(*) that bring games to an end earlier, or
certain moves(*) that make games go on longer? Would weighting them
appropriately in your random playouts help?

*: or move sequences. E.g. playing a stone in atari that the opponent
then does not capture. (No idea if that makes a game longer or shorter,
just meaning it as an example.)

Darren

grok

unread,
Feb 20, 2016, 3:39:57 PM2/20/16
to compu...@computer-go.org

As the smoke cleared, Darren Cook <dar...@dcook.org>
mounted the barricade and roared out:

> >> The longest I've been able to find, by more or less random sampling,
> >> is only 521 moves,
> >
> > Found a 582 move 3x3 game...

Is AlphaGo 'aware' of this database..?

-- grok.

"Ingo Althöfer"

unread,
Feb 21, 2016, 11:33:43 AM2/21/16
to compu...@computer-go.org
Hi John,

very interesting. Is it allowed for players
to pass in between? Do these passes count like
normal moves?

> Found a 582 move 3x3 game...

Can you give us sgf?


My intuition says that there should be a constant
delta > 0 such that for all board sizes m x n (with
m > 1, n > 1) there exist games of length
at least (1 + delta)^(m*n).
And also for m x 1 boards (so, only one "long" streak)
there should exist games with length above
(1 + delta)^m (they might be constructed by doing some
pseudo-counting, starting at one end of the board).

************************
Might neural nets help to find (very) long games
for given board size?

Cheers, Ingo.

John Tromp

unread,
Feb 21, 2016, 1:55:13 PM2/21/16
to computer-go
dear Darren, Ingo,

> Again by random sampling?

Yes, nothing fancy.

> Are there certain moves(*) that bring games to an end earlier, or
> certain moves(*) that make games go on longer? Would weighting them
> appropriately in your random playouts help?

You could try to weigh moves by how likely they lead to revisiting previous
positions. I think that's the only thing that makes moves worse.


> very interesting. Is it allowed for players
> to pass in between? Do these passes count like
> normal moves?

Yes, passes are implied whenever two consecutively played stones
are of the same color.

> > Found a 582 move 3x3 game...
> Can you give us sgf?

I took the effort of trying to format the 582 game in a more insightful way.
I ended up with lines of positions that mostly add stones, only starting
a new line when a capture of more than 1 stone left at most 4 stones:
The result is attached. I think there is clearly
room for improvement, i.e. make this game much longer.

> My intuition says that there should be a constant
> delta > 0 such that for all board sizes m x n (with
> m > 1, n > 1) there exist games of length
> at least (1 + delta)^(m*n).

This is true, and a delta > 2 follows from a Theorem in an
upcoming paper by Matthieu Walraet and myself.

> And also for m x 1 boards (so, only one "long" streak)
> there should exist games with length above
> (1 + delta)^m (they might be constructed by doing some
> pseudo-counting, starting at one end of the board).

We already have a lower bound of 2^{n+1}-4
as Theorem 9 in our combinatorics paper.

> Might neural nets help to find (very) long games
> for given board size?

Neural nets are not the best way to deal with avoiding superko:-(

regards,
-John
attach.582

Petr Baudis

unread,
Feb 21, 2016, 3:01:04 PM2/21/16
to compu...@computer-go.org
Hi!

On Sun, Feb 21, 2016 at 01:55:05PM -0500, John Tromp wrote:
> > very interesting. Is it allowed for players
> > to pass in between? Do these passes count like
> > normal moves?
>
> Yes, passes are implied whenever two consecutively played stones
> are of the same color.

I'm wondering if there's some framework for studying combinatoric
aspects of games that are not only technically Go, but also actually
resemble real Go games played by competent players?

This research doesn't touch my heart very deeply because it seems
that the astonishing numbers rise up only while exploiting "loopholes"
in the technical rules formulation rather than their intention - passing
while you still have moves that'd improve your score, putting
whole-board groups in self-atari instead of capturing enemy groups
in atari, etc.

How would the results change if we approximated more realistic games
by introducing just the same basic restriction that we use in Monte
Carlo simulations - (i) filling your own true eye is invalid move,
(ii) do not pass if a move is avilable.

Naybe on 3x3, the games could still end up potentially quite long, but
perhaps more interesting. And is there some way to quantify how harmful
that restriction is, besides the famous example of forcing a bulky five
(and how much that one matters at least on small boards like 5x5)? How
often do 3x3 positions arise in random games that require filling your
own eye to win?

> > > Found a 582 move 3x3 game...
> > Can you give us sgf?
>
> I took the effort of trying to format the 582 game in a more insightful way.
> I ended up with lines of positions that mostly add stones, only starting
> a new line when a capture of more than 1 stone left at most 4 stones:
> The result is attached. I think there is clearly
> room for improvement, i.e. make this game much longer.

This was quite instructive, thank you very much for that!

--
Petr Baudis
If you have good ideas, good data and fast computers,
you can do almost anything. -- Geoffrey Hinton

Petr Baudis

unread,
Feb 21, 2016, 3:09:45 PM2/21/16
to compu...@computer-go.org
On Sun, Feb 21, 2016 at 09:00:54PM +0100, Petr Baudis wrote:
> I'm wondering if there's some framework for studying combinatoric
> aspects of games that are not only technically Go, but also actually
> resemble real Go games played by competent players?
>
> This research doesn't touch my heart very deeply because it seems
> that the astonishing numbers rise up only while exploiting "loopholes"
> in the technical rules formulation rather than their intention - passing
> while you still have moves that'd improve your score, putting
> whole-board groups in self-atari instead of capturing enemy groups
> in atari, etc.
>
> How would the results change if we approximated more realistic games
> by introducing just the same basic restriction that we use in Monte
> Carlo simulations - (i) filling your own true eye is invalid move,
> (ii) do not pass if a move is avilable.

Maybe a more formal way to express my concern: it should be easy to
come up with (of course ugly or expensive to verify) rule modifications
that would still allow >99.9% or more pro games to be valid, but
invalidate games proving these results in just a few moves. Can we
reach some results (re longest games, number of games, etc.) that
don't have this property?

"Ingo Althöfer"

unread,
Feb 22, 2016, 10:55:50 AM2/22/16
to compu...@computer-go.org
Dear John,

thanks for the explanations (and paper announcement).


>> ... (1 + delta)^(m*n).


>
> This is true, and a delta > 2 follows from a Theorem in an
> upcoming paper by Matthieu Walraet and myself.

Do you mean (1+delta) > 2, or really (1+delta) > 3?


> > Might neural nets help to find (very) long games
> > for given board size?
>
> Neural nets are not the best way to deal with avoiding superko:-(

I had some special way to use them in mind - but too complicated
to explain it here.

Please let us know when a preprint is available on ArXiv or some other place.

Cheers, Ingo.

PS. I am just a guest of Richard Lorentz in LA. He met you only once
(back in Summer 2002 in Maastricht). Richard still remembers vividly your
research energy! Keep it alive.

John Tromp

unread,
Feb 22, 2016, 11:09:44 AM2/22/16
to computer-go
dear Ingo,

>>> ... (1 + delta)^(m*n).
>>
>> This is true, and a delta > 2 follows from a Theorem in an
>> upcoming paper by Matthieu Walraet and myself.
>
> Do you mean (1+delta) > 2, or really (1+delta) > 3?

Oops; I mean delta >= 1, so the base of the exponent is at least 2.

(1+delta) is necessarily bounded by the base of liberties of 2.975734192...

> Please let us know when a preprint is available on ArXiv or some other place.

The original write-up by Matthieu is available at
http://matthieuw.github.io/go-games-number/GoGamesNumber.pdf

Our CG2016 submission both simplifies and improves on that,
but that write-up should already convince you of how to achieve delta 1.

regards,
-John

John Tromp

unread,
Mar 9, 2016, 2:08:10 PM3/9/16
to computer-go
dear Go researchers,

>> > Found a 582 move 3x3 game...
>> Can you give us sgf?
>
> I took the effort of trying to format the 582 game in a more insightful way.
> I ended up with lines of positions that mostly add stones, only starting
> a new line when a capture of more than 1 stone left at most 4 stones:
> The result is attached. I think there is clearly
> room for improvement, i.e. make this game much longer.

Gunnar Farnebäck took up my challenge and took a giant leap from 582
to 1808 moves, using a UCT oriented search with maximum playout length
as the score.

That led me to implement a so-called beam search,
in which we keep a set of W (the beam width) games at the same depth
D, and for each one, play some number B (branching factor) of random
playouts.
We then keep the W longest of these W*B playouts, truncated at depth D+1,
and repeat the process, until no more playouts are possible (all moves
being superko violations).

I ran a dozen beam searches with W=16384 and B=1024, and the best one
reached a record 2900 moves. See the attached sgf.

It's quite mesmerizing to load this sgf in your favorite go editor and just
cycle through all the moves at a rapid pace...

The rules should really be TT (Tromp/Taylor) instead of NZ (New Zealand),
but unfortunately Cgoban doesn't support TT.

regards,
-John
2900.sgf
Reply all
Reply to author
Forward
0 new messages