Longest Superko Cycle
2013-11-02
Dear ...,
if
you are the person having requested this information, please send me an
email to <jasiek@snafu.de> from an email address different from
<...@daum.net> and <...@paran.com>, whose providers currently refuse to receive my emails to
you.
> the number of variation of 4 straight Ko is about 19million.
This
information was not on my homepage, but available in newsgroup
archives. The citation is below. It relies on a few mathematical
proofs, of which a part belongs to the field mathematics called "graph
theory" and is related to the Marriage Theorem applicable to Bipartite
graphs.
http://en.wikipedia.org/wiki/Bipartite_graph
http://en.wikipedia.org/wiki/Hall's_marriage_theorem
(There is a chance that I find time for the Korean Rules during the following days.)
****************************************************************************
Robert Jasiek
25.04.01
Bruno Wolff III wrote:
> >Do you know any Go problems with more plies?
> You might find "Mathematical Go: Chilling gets the last point" interesting.
> It provides some very complicated endgame positions that can be solved
> use combanatorial game theory. They are exactly like your ladder situations
> and you may not be looking for that kind of problem.
Go with a prohibition of repeated positions can have quite long
problems: (use a fixed width font)
X X X X X X X X X X X X X X X X X X X X to play and prepare
O X O X . X . X . X . X . X . X X X X against O's toughest
. O . O X O X O X O X O X O X O O O O (i.e. longest) perfect
O O O O O O O O O O O O O O O O O O O play resistance
X X X X X X X X X X X X X X X X X X X
O O O O O O O O O O O O O O O O X X .
. O . O X O X O X O X O X O X O X X X
O X O X . X . X . X . X . X . X O O .
X X X X X X X X X X X X X X X X O O O
O O O O O O O O O O O O O O O O O O O
X X X X X X X X X X X X X X X X O O O
O X O X . X . X . X . X . X . X O O .
. O . O X O X O X O X O X O X O X X X
O O O O O O O O O O O O O O O O X X .
X X X X X X X X X X X X X X X X X X X
O O O O O O O O O O O O O O O O O O O
. O . O X O X O X O X O X O X O O O O
O X O X . X . X . X . X . X . X X X X
X X X X X X X X X X X X X X X X X X X
There are 4 8-tuple-kos on the board. According to the proof
for the theorem by Bill Spight, which relies on concepts
proposed by James Davies and John Rickard and is attached inline,
X can destroy exactly one 8-tuple-ko-coexistence after, if I have
understood the proof correctly after quickly skimming through it,
at most 2 * (8*7)^4 = 19.668.992 plays on the board because
within each 8-tuple-ko there are 8*7 defensive positions with
exactly two O ko stones, because the number of 8-tuple-kos is 4,
and because defensive and attacking positions alternate giving
the factor 2.
X wants to win one of the two biggest 8-tuple-kos while O
wants to keep them. If all four would be equally big, then
O could pass at move 19.668.992. (If you can set up 4 equally
big 8-tuple-kos on a 19x19-board, then calculation is easier.)
However, O will pass earlier, namely the last time when X can
attack a small 8-tuple-ko. I am not sure, which such last time
moment is the earliest for X? Anyway, it will be fewer than
19.668.992 moves until one of the 4 8-tuple-kos is dissolved.
Then I suppose there to be an endgame ko fight about 4 points
(or about even more?). O should be able to turn at least one
standard ko within the remaining 3 8-tuple-kos from an X to a
O ko stone. Does this take only a few moves or many moves?
How long is this problem really in case of O's toughest
resistance while still following perfect play? It looks like
many millions of moves or have I made severe mistakes while
applying the proof? What is the correct komi?
--
robert jasiek
Subject: Re: Two quad-kos and more
Date: Sat, 27 Sep 1997 03:49:47 -0400 (EDT)
From: BillSpight@aol.com
To: go-rules@lists.io.com
All:
Before I said that James Davies' note on two quadruple kos
was excellent. Let me amend that. It is most excellent!!!!!
I did not understand Davies' method at first. But when I
did, I realized that it shows that enough basic n-tuple kos allow
the attacker to break the final standoff under superko rules, and
tells the attacker how to play.
Definitions:
Basic multiple ko. A superko comprised of simple ko mouths
in which, if either player has a stone in all of the ko mouths,
he captures all of the opponent's stones, and neither player can
capture any stones except single ko stones otherwise.
Attack position. 1. A position in a basic multiple ko in
which one player (the attacker) has stones in all but one of the
ko mouths.
2. A position in a superko comprised of basic multiple kos
in which one of the multiple kos is in an attack position.
Standoff position. 1. A position in a basic multiple ko in
which one player (the attacker) has stones in all but two of the
ko mouths. This is said to be a standoff favoring the attacker.
2. A position in a superko comprised of basic multiple kos
in which all of the multiple kos are in standoff positions
favoring the attacker.
Break the standoff. Reach an attack position from which the
defender is barred from returning to a standoff position by the
superko rule.
Proposition:
Given int(n/2) n-tuple kos (n > 2) (the superko) in standoff
position favoring the attacker (and given that the last play was
not a play by the defender in the superko), the attacker to move
can break the standoff.
Davies' method:
For each standoff position determine an attack position
which the attacker can reach by one move. Then from each
standoff position the attacker may move to the corresponding
attack position without repeating a prior superko position (if
the attacker was the first to play from the initial superko
position). Since the defender can move to at most all but one of
the standoff positions from the attack positions without
repeating a superko position, and the attacker has a
non-repeating move from each of these, the defender must run out
of legal plays in the multiple n-tuple ko before the attacker
does.
How to determine the corresponding attack positions:
Definition:
Order of a standoff position:
Represent a ko mouth occupied by the attacker by X and one
occupied by the defender by O. For the standoff position arrange
the ko mouths in a circle. Given this arrangement, the order of
the standoff position is the minimum number of Xs between the Os.
Examples:
In a 7-tuple ko the order of the following position is 2.
X X O X X O X.
In an 11-tuple ko the order of the following position is 4.
X X O X X X X X O X X (the last X is adjacent to the first
in the circle).
For a given circular arrangement, each standoff position in
an n-tuple ko has possible orders from 0 to int(n/2) - 1.
Phase 1: For each n-tuple ko standoff position determine an
attack position.
For the circle representing the standoff position identify a
direction and a "leftmost point". We may write the circle as a
line in which the direction is left to right except from the
rightmost point, where the direction is to the leftmost point.
For a position of order r replace the O which has r Xs to its
left between it and the other O. Order n/2 - 1 is ambiguous.
For it replace the rightmost O in the line.
Phase 2: Given the standoff positions and attack positions
of each of the n-tuple kos, determine an attack position for each
standoff position in the superko.
Number the individual n-tuple kos from 0 to int(n/2) - 1.
Add the orders of the standoff positions modulo int(n/2).
The attack position in the n-tuple ko with the same number as the
sum, along with the standoff positions is the superko attack
position.
That is it!
I realize that that may not look too much like what Davies
did, but it comes to the same thing.
To demonstrate that, here is how the method as I describe it
applies to 2 quadruple kos.
Order 0 standoff positions and corresponding attack
positions:
OOXX OXXX
XOOX XOXX
XXOO XXOX
OXXO XXXO
Order 1 standoff positions and corresponding attack
positions:
OXOX OXXX
XOXO XOXX
Next the method I describe differs slightly from what Davies
did, but the difference is minor. He divided the positions
equally, instead of by orders.
Let the right quadruple ko have number 0 and the left have
number 1. Then if both individual standoff positions have order
0, the sum is 0, so the attacker should play in the right
quadruple ko. If one individual standoff position has order 0
and the other has order 1, the sum is 1, and the attacker should
play in the left quadruple ko. If both standoff positions have
order 1, the sum is 1 + 1 = 0 (mod 2), so the attacker should
play in the right quadruple ko.
Now let's look at 4 9-tuple kos:
Order 0
OOXXXXXXX OXXXXXXXX
XOOXXXXXX XOXXXXXXX
. . . . . .
OXXXXXXXO XXXXXXXXO
Order 1
OXOXXXXXX OXXXXXXXX
XOXOXXXXX XOXXXXXXX
. . . . . .
XOXXXXXXO XXXXXXXXO
Order 2
OXXOXXXXX OXXXXXXXX
XOXXOXXXX XOXXXXXXX
. . . . . .
XXOXXXXXO XXXXXXXXO
Order 3
OXXXOXXXX OXXXXXXXX
XOXXXOXXX XOXXXXXXX
. . . . . .
XXXOXXXXO XXXXXXXXO
Orders of 9-tuple kos Number of 9-tuple ko in which to play
0 + 0 + 0 + 0 = 0 (mod 4)
0 + 0 + 0 + 1 = 1 (mod 4)
. .
. ...
0 + 0 + 1 + 1 = 2 (mod 4)
. .
. ...
1 + 2 + 3 + 0 = 2 (mod 4)
. .
. ...
3 + 1 + 1 + 2 = 3 (mod 4)
. . .
= ...
3 + 3 + 3 + 3 = 0 (mod 4)
You can see that each attack position is different. Given
the orders of three of the 9-tuple kos, the order of the fourth
uniquely determines which of the kos to play in.
Many thanks, James!
Bill Spight
****************************************************************************
Best wishes,
--
robert jasiek