MiaiCountingWithTrees
Miai counting with game trees? is a visualized algorithm applying combinatorial game theory. One of the practical outcomes is that you can determine if a move is sente or gote.
Table of contents |
Notation
First, the tree notation.
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
Algorithm and gote example
For a first example, each node can be associated with a board like so:
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:
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 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).
(?) A / \ (?) B -2 / 13
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.
(5) 3 / \ (5) 8 -2 / 13