Re: [gnugo-devel] Half and false eye with ko.

[Gunnar Farneback]

Dan wrote:
> I think there is an arithmetic with 1/4 eyes in Howard Landsman's
> paper.

That one is quite different and does not involve ko. He does have some
discussion about ko eyes, but those are numerically 1/3 eyes.

> The following table converts diagonal sums to
> 1/4-fractional eyes. The total number of eyes to live would be
> 2. For example, a group with 8 quarter eyes should be alive, the
> example at the end shows. If at any point B takes a ko, W just takes
> some other one.

Your example is faulty. 8 "quarter eyes" do indeed live
unconditionally, but so do 6.

Trevor wrote:
> I think Gunnar's original message had the topology values for
> diagrams a & b off by 1.

Almost all details were wrong in my previous messages, but it seems
the idea was good enough to shine through all the mist. :-)

> So I don't think the analysis is messy, but rather quite clean.
> (I'm not sure though, that 1/2 is the best value to assign to the
> ko.  1/3 or 2/3 might be more appropriate - more later on this).

I've been thinking in this direction too. 1/2 is definitely not good
enough, but 2/3 also has drawbacks. Below follows a much more thorough
analysis. Notice that I have switched the cases (a) and (b) to get a
more systematic analysis.

=========================================

Eye topology without ko:
------------------------
We are examining the diagonal properties of an O eyespace. If no ko is
involved we have the following. 

Diagonal values:
0 - O has control of the vertex (or vertex off corner)
1 - either color can take control over the vertex (or vertex off edge)
2 - X has control of the vertex

Topological eye values (sum of the four diagonal values)
2 or less - proper eye
3         - half eye
4 or more - false eye


Diagonal ko values:
-------------------
We distinguish between a ko in O's favor and one in X's favor:

.?O?   good for O
OO.O
O.O?
XOX.
.X..

.?O?   good for X
OO.O
OXO?
X.X.
.X..

Preliminarily we give the former the symbolic diagonal value a and the
latter the diagonal value b. We should clearly have 0 < a < 1 < b < 2.
Letting e be the topological eye value (still the sum of the four
diagonal values), we want to have the following properties:

e <= 2     - proper eye
2 < e < 3  - worse than proper eye, better than half eye
e = 3      - half eye
3 < e < 4  - worse than half eye, better than false eye
e >= 4     - false eye


Analysis of typical cases of ko contingent topological eyes:
------------------------------------------------------------

      .X..      (slightly) better than proper eye
(a)   ..OO          e < 2
      OO.O
      O.OO      e = 1 + a
      XOX.
      .X..

      
      .X..      better than half eye, worse than proper eye
(a')  ..OO      2 < e < 3
      OO.O
      OXOO      e = 1 + b
      X.X.
      .X..

      
      .X..      better than half eye, worse than proper eye
(b)   .XOO      2 < e < 3
      OO.O
      O.OO      e = 2 + a
      XOX.
      .X..

      
      .X..      better than false eye, worse than half eye
(b')  .XOO      3 < e < 4
      OO.O
      OXOO      e = 2 + b
      X.X.
      .X..

      
      .X..
      XOX.      (slightly) better than proper eye
(c)   O.OO          e < 2
      OO.O
      O.OO      e = 2a
      XOX.
      .X..


      .X..
      XOX.      proper eye, some aji
(c')  O.OO      e ~ 2
      OO.O
      OXOO      e = a + b
      X.X.
      .X..


      .X..
      X.X.      better than half eye, worse than proper eye
(c'') OXOO      2 < e < 3
      OO.O
      OXOO      e = 2b
      X.X.
      .X..


      .X...
      XOX..     better than half eye, worse than proper eye
(d)   O.O.X     2 < e < 3
      OO.O.
      O.OO.     e = 1 + 2a
      XOX..
      .X...


      .X...
      XOX..     half eye, some aji
(d')  O.O.X     e ~ 3
      OO.O.
      OXOO.     e = 1 + a + b
      X.X..
      .X...


      .X...
      X.X..     better than false eye, worse than half eye
(d'') OXO.X     3 < e < 4
      OO.O.
      OXOO.     e = 1 + 2b
      X.X..
      .X...


      .X...
      XOX..     better than false eye, worse than half eye
(e)   O.OXX     3 < e < 4
      OO.O.
      O.OO.     e =  2 + 2a
      XOX..
      .X...


      .X...
      XOX..     false eye, some aji
(e')  O.OXX     e ~ 4
      OO.O.
      OXOO.     e = 2 + a + b
      X.X..
      .X...


      .X...
      X.X..     (slightly) worse than false eye
(e'') OXOXX     4 < e
      OO.O.
      OXOO.     e = 2 + 2b
      X.X..
      .X...


Choosing the values of a and b:
-------------------------------
It may seem obvious that we should use
(i)   a=1/2 and b=3/2
but this turns out to have some drawbacks. These can be solved by
using either of
(ii)  a=2/3, b=4/3
(iii) a=3/4, b=5/4
(iv)  a=4/5, b=6/5

Summarizing the analysis above we have the following table for the
four different choices of a and b.

case    symbolic        a=1/2   a=2/3   a=3/4   a=4/5   desired
        value           b=3/2   b=4/3   b=5/4   b=6/5   interval
(a)     1+a             1.5     1.67    1.75    1.8         e < 2
(a')    1+b             2.5     2.33    2.25    2.2     2 < e < 3
(b)     2+a             2.5     2.67    2.75    2.8     2 < e < 3
(b')    2+b             3.5     3.33    3.25    3.2     3 < e < 4
(c)     2a              1       1.33    1.5     1.6         e < 2
(c')    a+b             2       2       2       2           e ~ 2
(c'')   2b              3       2.67    2.5     2.4     2 < e < 3
(d)     1+2a            2       2.33    2.5     2.6     2 < e < 3
(d')    1+a+b           3       3       3       3           e ~ 3
(d'')   1+2b            4       3.67    3.5     3.4     3 < e < 4
(e)     2+2a            3       3.33    3.5     3.6     3 < e < 4
(e')    2+a+b           4       4       4       4           e ~ 4
(e'')   2+2b            5       4.67    4.5     4.4     4 < e

We can notice that (i) fails for the cases (c''), (d), (d''), and (e).
The other three choices get all values in the correct intervals. The
main distinction between them is the relative ordering of (c'') and
(d) (or analogously (d'') and (e)). If we do a more detailed analysis
of these we can see that in both cases O can secure the eye
unconditionally if he moves first while X can falsify it with ko if he
moves first. The difference is that in (c''), X has to make the first
ko threat, while in (d), O has to make the first ko threat. Thus (c'')
is better for O and ought to have a smaller topological eye value than
(d). This gives an indication that (iv) is the better choice.

Comments:

* Any value of a, b satisfying a+b=2 and 3/4<a<1 would have the same
  qualities as choice (iv) according to the analysis above. One
  interesting choice is a=7/8, b=9/8 since these allow exact
  computations with floating point values having a binary mantissa.
  The latter property is shared by a=3/4 and a=1/2.

* Things get more ugly when there are three kos. More about this in a
  later message. 

/Gunnar