RobertJasiek/LongestSuperkoCycle

Sub-page of RobertJasiek

2013-11-02

Dear ...,

if you are the person having requested this information, please send me an email 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 is 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.

[ext] http://en.wikipedia.org/wiki/Bipartite_graph [ext] http://en.wikipedia.org/wiki/Hall%27s_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
[Diagram]

---------------------------------------


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


RobertJasiek/LongestSuperkoCycle last edited by RobertJasiek on November 15, 2013 - 13:12
RecentChanges · StartingPoints · About
Edit page ·Search · Related · Page info · Latest diff
[Welcome to Sensei's Library!]
RecentChanges
StartingPoints
About
RandomPage
Search position
Page history
Latest page diff
Partner sites:
Go Teaching Ladder
Goproblems.com
Login / Prefs
Tools
Sensei's Library