Transcript FileNewTemplate - River Rock Cohousing

How To Play A Perfect Endgame
(An introduction to Combinatorial Go Theory)
Howard A. Landman
U.S. Go Congress, Boston MA August 5, 2016
Perfect Endgame (the hard way)
• Read out all possible sequences of moves
on the whole board (perfectly).
• Score each of them (perfectly).
• Pick the highest score.
Problem: There is an exponentially huge
number of global sequences.
Question: Is it possible to be more efficient
without losing points?
Perfect Endgame (the easy way)
Go endgame breaks up into a bunch of
independent subgames. So maybe we can:
• Read out each subgame (perfectly) and
score it (perfectly)
• Combine/compare the results to find the
global best move.
But how to combine/compare?
Outline of rest of talk
• Basic Combinatorial Go theory
• Some examples (simple to moderate)
– Gote
– Sente and reverse sente
• A simplified rule that is often right
• General guidelines
Some basic conventions
• We imagine we are on Black’s side
– Black territory is positive numbers
– White territory is negative numbers
– Any game which is a first-player loss (e.g.
seki) has value zero
• Black is left and White is right.
– {10|8} is a 2-point gote, Black can make a 10
point territory or White can reduce it to 8.
– In diagrams, numbers increase to the left.
Left and right stops
• The “left stop” or “Black stop” of a game is
the result if Black plays first and then the
players alternate moves (BWBWBW…)
• The “right stop” or “White stop” of a game
is the result if White plays first and then
the players alternate moves (WBWBWB…)
CGT key idea: Temperature
• We charge each player a “tax” for every
move they make. When the tax gets large
enough, neither player wants to move
anymore (left stop = right stop).
• The minimum tax that causes this is called
the “temperature” T(G) of the game and is
the profit from playing in that game.
• Thermograph: Graph the stops as a
function of the tax.
CGT key idea: Mean Value
• Every game has a Mean Value M(G).
– M = value of game when tax equals temp
– Or, when left and right stops become equal
• Left stop ≥ mean value ≥ right stop
• Theorem: The value of N copies of g is
approximately N×M(G). Often this is
exact: 2 copies of 1 point in gote equals 1
point (ignoring ko threats).
Example: 1 point in gote
a
a = {1|0}
1
0
Example: 1 point in gote
•
•
•
•
•
1
G = {1|0}
At tax=0.5, B=W
So T(G)=0.5
Also, M(G) = 0.5
For simple gote,
Mean = (B+W)/2
Temp = (B-W)/2
0.75
T 0.5
0.25
1
0.75
M
0.5
0
0.25
0
How to think about gote
後手 后手 후수
• Mean value = average of the stops
– 1 point gote {1|0} is worth ½ point
• Each move is worth half the difference.
– Black can ADD ½ point to make 1.
– White can SUBTRACT ½ point to make 0.
• 2 gotes of the same temperature are miai
(they add up to a number).
– {1|0} + {1|0} = 1
Beyond simple gote
• In simple gote, one move from either
player finishes the game.
• What happens when one of the moves
doesn’t finish the game, but enables a
follow-up move?
– E.g. pushing into a corridor
• What happens when the move makes a
large threat?
Moves in a corridor
a
c
b
d
1
0.75
0.5
a
4
3.5
c
b
3
2.5
2
1.5
d
1
0.5
0.25
0
0
Moves in a corridor
•
•
•
•
d = {1|0}, M=½, T=½
c = {2|d} ≈ {2|½}, M=1¼, T=¾
b = {3|c} ≈ {3|1¼}, M=2⅛, T=⅞
T(a)=15/16, deeper gives 31/32, 63/64, …
1
0.75
0.5
a
4
3.5
c
b
3
2.5
2
1.5
d
1
0.5
0.25
0
0
What did we just learn?
• Moves in 1-point gote corridors are worth
½, ¾, ⅞ …
• Play in the LONGEST such corridor is the
biggest!
• For multi-step games, we can approximate
subgames by their mean value IF they are
lower temperature than the supergame.
(Gets M(G) and T(G) right, but not graph.)
Myungwan Kim problem #1
a
b
Problem #1 Thermographs
6
a
5
b
4
3
2
a
1
b
0
8
7
6
5
4
3
2
1
0
-1
-2
-3
-4
-5
-6
Miai
見合い 见合 맞보기
• Normal Go meaning of miai is that there
are two moves that balance each other out.
– Often neither one is urgent.
• In CGT, a set of games is miai if they are
not numbers but their sum is a number.
– E.g. equal-temp gotes: {8|7} + {2|1} = 9
– Temperature is ≤ 0
– Miai sets can have more than 2 games!
Another way to prove M=2¾
• 4 copies of the game exactly equals 11
points, no matter who moves first.
– First four moves, Black plays a twice and
White plays a twice (making 2 bs).
– Next two moves, Black connects one b and
White captures one b.
– Total is 8 + 8 + 1 + -6 = 11
a
– The 4 copies are miai.
b
Approximate miai is not miai!!!
• Consider {50|0} + {0|-50} + {1|-1}
– The 2 big games are miai: {50|0}+{0|-50} = 0
– You can play in the smallest game and still get
maximum score!
• Consider {51|0} + {0|-50} + {0|-1}
– {51|0} + {0|-50} = hot 1 point double sente!!!
– You MUST play the largest one to win.
• Miai must be EXACT, or there is stuff left.
Myungwan Kim problem #2
a
b
Let’s analyze without graph first
• Black at a gives +10.
• White at a gives b-4.
• By itself, b is {5|0}.
a
b
– 5 point gote, mean value 2½, temperature 2½
– So b-4 = {1|-4}, mean value -1½, same temp
• So a = {10|b-4} = {10|{1|-4}} ≈ {10|-1½}
– Mean value = (10 + -1½)/2 = 8½/2 = 4¼
– Temperature = (10 - -1½)/2 = 11½/2 = 5¾
Problem #2 Thermographs
7
a
6
b
5
4
a
3
2
b
1
0
10
9
8
7
6
5
4
3
2
1
0
-1
-2
-3
-4
Sente, reverse sente
先手 선수,
逆先手 역끝내기
• In normal Go usage, a move is sente if you
expect your opponent will answer it in
gote.
• A move which is sente for your opponent
is reverse sente for you.
{4|{3|0}} (sente for W)
a
b
b is larger than a, so a is sente
2
1.5
1
b
a
0.5
0
4
3.5
3
2.5
2
1.5
1
0.5
0
Properties of sente
• M = value if sente is played and answered
– left stop (for Black sente)
– right stop (for White sente)
• Temperature is full difference
– Recall gote is half of difference
• A large threat can make it playable above
its temperature
– But above top of “flagpole” it is not sente yet
Corridor with threat at end
a
c
b
d
1.5
1
a
c
b
0.5
d
0
5
4.5
4
3.5
3
2.5
2
1.5
1
0.5
0
Sente vs Gote corridors
• In a corridor with a threat at the end, all
moves have temperature 1
– Thermograph “looks like sente”
– Same value as sente even if not answered
– Bigger than moves in a gote corridor
Double Sente
• When a game is sente for both players, it
can be very hot.
4 points in double sente
{{38|2} | {-2|-38}}
Double sente thermograph
T=20, as hot as 40 points in gote!!!
Even slightly bigger than killing!!!
25
20
15
10
5
0
40
35
30
25
20
15
10
5
0
-5
-10
-15
-20
-25
-30
-35
-40
Simple sometimes-correct rule
http://senseis.xmp.net/?MiaiCounting
1. Find result if B plays first (left stop).
2. Find result if W plays first (right stop).
3. Subtract them. This gives the total
number of points at stake. (P = B – W)
4. Find the number of moves difference (N).
5. Divide the points by the moves to get a
“points per move”. (T = P / N)
Examples of simple rule
• 1 point in gote:
• P=1, N=2, value=½
• 1 point in sente:
• P=1, N=1, value=1
• 1 point ko:
• P=1, N=3, value=1/3
• 4 points in double sente:
• P=4, M=0, value = 4/0 = +∞ ?! (Epic fail!)
Some things we didn’t cover
• At the same temperature, play sente before
gote before reverse sente.
– This requires analyzing tiny (infinitesimal)
advantages.
• Eyespace values
– You can apply this theory to counting eyes,
with some warping (3 eyes is not > 2 eyes)
Summary
• We learned basic concepts and computing
methods of Combinatorial Game Theory.
– Game = {L|R}
– Left and right stops (limits)
– Mean value (expected or average value)
– Temperature (value of playing a move)
Summary (cont’d)
• We worked through examples
– Simple gote
– Gote with follow-up moves
• 2 level
• Corridor with no threat at end
• Corridor with threat at end
– Sente and reverse sente
– Double sente
Summary (cont’d)
• We saw that games can often be replaced
by their mean value.
• We learned a simple rule (“miai counting”)
to often get the right value without doing
full calculation
– and looked at cases where it doesn’t work!
References
• Some books and articles you could read to
study this subject further are …
On Numbers And Games
John H.Conway
• Complete math
development of the
theory from scratch
• Hard, but rigorous
• Fun if you like math
and infinities
• Not much Go
content
Mathematical Go Endgames
Berlekamp & Wolfe
• The best text on
CGT for Go
endgames.
• Lots of examples,
but some of them
are a bit artificial
and unlikely to
occur in actual play
Eyespace Values in Go
Howard A. Landman
• Applies the theory to
counting eyes
• Lots of examples
• Download:
http://library.msri.or
g/books/Book29/file
s/landman.ps.gz