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
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
> >> 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.
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.
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
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?
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.
>>> ... (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