MiaiCountingWithTrees

    Keywords: EndGame

Hopefully this page will someday be a complete description of how to calculate the Miai value of a move with trees. The main advantage to this method is that if you don't know whether a move is sente or gote, you can try it out.


Planned TOC:

  • Algorithm
  • simple Gote example
  • simple Sente example
  • more complex example (HaneTsugi perhaps?)

Algorithm and Notation

First, the tree notation. I attempt to follow BillSpight as closely as possible, for consistency and because he outranks me :). A miai counting game tree is a binary tree where each node represents the board position after either black or white making a locally optimal play. A leaf node (one with no children or subtrees) represents a position where neither player can improve the local count. By convention, the left branch represents a black move, and the right branch represents a white move.

As our first example, consider a game tree with this structure:

   A
  / \
 B   C
    / \
   D   E

For a first example, each node can be associated with a board like so:


[Diagram]
Position A  
[Diagram]
Position B  
[Diagram]
Position C  
[Diagram]
Position D  
[Diagram]
Position E  


Note that positions B, D, and E we can directly count the score for both players in the immediate area. In B, black has 4 points. In D, black has 3 points. In E, black has 2 points. Whenever we know the count for a position, we can fill it in for our tree:

   A
  / \
 4   C
    / \
   3   2

Now what about A and C? Here are the basic formulas for a (sub-)tree with 2 leafs:

Temperature = (blackcount-Whitecount)/(blacktally-whitetally)

Count = blackcount - (blacktally * Temperature) OR Count = whitecount + (whitetally * Temperature)

The temperature is the value of one move by either black or white in that position. The count is the average number of points that can be expected from this endgame.

Now we calculate the count for C. Using the formulas above, blacktally-whitetally is 2 - this is the move difference between D and E. This is also known as the local tally, based upon D and E. The difference between D and E's count is 1. Hence we obtain the temperature at C: 0.5 . The count for C is then equal to the count at D minus the tally difference between C and D times the temperature. This works out as 3 - ( 1 * 0.5 ) = 2.5. This can be recorded in the tree as follows.

   A
  / \
 4  2.5  (0.5)
    / \
   3   2

Now that the count for C is known, we can treat C like a leaf node and apply same method to calculate A's count:

(0.75)  3.25
        / \
       4  2.5  (0.5)
          / \
         3   2

The temperature is (4-2.5)/2 = 0.75, and the count is

blackcount - (blacktally * Temperature) = 4 - (1 * 0.75) = 3.25

Alternatively:

whitecount + (whitetally * Temperature) = 2.5 + (1 * 0.75) = 3.25

If temperature values either decrease or stay the same as you move down the tree, then you're done, and all the moves were gote. The position has a miai value of 3/4.

A sente example

Now let's change the board in position A to look like this:

[Diagram]
Position A  



Otherwise, the tree is the same shape, and looks like this to begin:

   A
  / \
 4   C
    / \
   3   -17

The only change is that now if black tenukis twice, white captures the group and makes 17 points. Now we calculate the mean and temperature as before:

(5.5)  -1.5
        / \
       4  -7  (10)
          / \
         3   -17

But this time the temperature has increased from 5.5 to 10. From this we can tell that W move C was sente. If the first move is big enough for white to play (no move on the board that is larger than 5.5) then the 10 points follow-up is certainly the biggest move for black and he will always answer the sente. The actual score for not answering the sente, -17, is irrelevant as this position is never reached. It may be replaced by "-∞" indicating a loss for black that excludes this move entirely. So we cut out this variation from the tree and repeat the calculation:

(1)      3
        / \
       4   C  ()
          /
         3

And the move has miai value of 1 point. Note we do (4-3)/1 since the local tally difference is 1 now, not two, and the Count is 4 - 1*1 = 3.

A ko example

Miai counting is also useful for evaluating positions with ko (position A):

[Diagram]
Position A  
[Diagram]
Position B  
[Diagram]
Position C  
[Diagram]
Position D  



gametreeko
Diagram 1

White can connect and live with 2 eyes, which makes a count of -2 (position B). If it is black's turn, he can fight the ko and capture one stone (position C). White can re-capture the black stone and go back to position A (after playing a ko threat, which is answered by black). If black ignores the ko threat, he can kill the group (position D), which gives a total count of 13 (6 captives, 7 points for territory).



gametreeko2
Diagram 2

The swing value (point difference for loosing or winning the ko) is 13-(-2)=15 points. It requires 2 moves for black to win and one move for white to win, so the local tally is 3. In other words, 3 moves are required to gain 15 points, so the gain per move is 15/3=5. Each move by black increases the value of the position by 5 points and each move by white decreases the value of the position by 5 points. Therefore, the count for position C is 8 points and the count for position A is 3 points.




MiaiCountingWithTrees last edited by tamingo on March 12, 2016 - 14:43
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