Federations in Go Endgames
Matthew Harren
Math 275 Final Project
Professor Elwyn
Berlekamp
Combinatorial
game theory relies on the ability to decompose games into sums of smaller
independent games. This document
describes an extension of the AnalGo endgame analyzer to consider cases when Go
subgames are “mostly” independent but may interact under some circumstances. The new extension to AnalGo allows users to
declare “federations” of subgames which may interact with one another. In these
federations, users specify conditions under which regions interact, and the
effects that these interactions could have.
AnalGo then uses this information to combine the subgames.
1. Introduction
The AnalGo
program by Brian Carnes [2] helps users analyze Go endgames. Using this software, users identify hot
regions on the board and explore all possible outcomes for that subgame. Given the complete game tree and information
on which player is the ko-master, AnalGo can compute the temperature of each
region. To play the Go game using HotStrat [1], a player would simply play in the region
labeled with the highest temperature.
Decomposing
a game into a sum of subgames works only so long as the subgames are
independent. However, we commonly find
that nearby regions interact in some way, and that the play in one region
affects the choice of moves in another.
One solution to this problem would be to consider the entire area of the
board to be one region, but this is very onerous for the user. A large region of partially-independent
subgames would have a very large game tree, since at each step we would have a
choice of which subgame to play in. With
AnalGo, the user would have to completely explore this game tree, which takes
unnecessary effort and increases the risk of deriving an incorrect answer
because the user forgot to explore part of the tree.
A second
solution, used in AnalGo today, is subregions. The complete game tree for this part of the
board must be explored until the game is settled enough that the subgames are
truly independent. At this point, we
declare that the current position is a “pseudoterminal” and that the
newly-independent subgames are subregions.
These subregions are analyzed in the same way that other regions are,
and at the pseudoterminal their thermographs are combined to find the value of
that position.
A new
alternative, described in this document, is to consider the partially-independent
subgames to be separate regions that are joined in a federation. The value of a
federation of two games A and B is the value of the sum A + B with adjustments
for any cases in which the game trees interact.
Section 2 describes federations as
they are implemented in AnalGo. The
interface to the new features is described in Section 3, and Section 4 walks
through an example. Section 5 describes
the current status of the code, and Section 6 concludes.
2. Federations
The new
features in AnalGo allow users to declare that a group of regions are united in
a federation. AnalGo will treat a
federation as the sum of its regions, and thus the federation’s game tree is
the complete set of permutations of moves in the various regions. Therefore, users can see the complete sum
game without having to manually enter it.
From the game tree, we compute the usual thermograph to let players know
when it is profitable to play in this federation, and if so which move. Users may edit the regions individually, and
AnalGo will recompute the federation’s game tree as necessary.
To allow
users to describe the interactions between regions of a federation, terminal
positions can be annotated with extra parameters. In each region, the user can declare
parameters that represent any concept he or she likes. Many of these have to do with life or death
for a group that touches more than one region.
For example, we might record whether there is a connection between two
groups, or how many eyes a group was able to form in this region. The user then gives values for each of these
parameters at each terminal position in the game tree of this region. To make this process easier, users specify
default values for the parameters, so that only exceptional positions need to
be hand-annotated.
At the
federation level users can specify conditions, in terms of these parameters,
under which regions interact. Along with
these conditions is an integer score offset that is applied should the
condition hold. For example, suppose two
regions A and B are adjacent to a common group.
These regions may declare parameters Aeyes and
Beyes, respectively, that state the number of eyes
that the group in question was able to form in the separate regions. In the federation, the user would declare
that if “Aeyes + Beyes <
2”, then the score should be adjusted by a certain amount to reflect the fact
that this group has been killed.[1]
3. The Program Interface
The main
display has two new features: a
parameters display to the right of the Go board, and federations on the go
board itself, which are shown in blue. A
federation’s area is considered to be the union of the regions it
contains. Analogously to green regions,
federations are shown in light blue when selected, and dark blue otherwise. The Tab key cycles through regions and
federations alike.
Figure
1 shows the additions to the Regions menu in AnalGo. The commands are as follows:
Declare Parameters. May be used whenever
a region is selected. Will bring up a dialog
box with two columns; parameter names for this region are specified on the
left, and default values on the right.
Parameter names must start with a letter and contain only letters and
digits, to allow conditions to be specified later. Default values must be integers. This command is the same as the “New
Parameters” button on the parameters board.
Set Parameters at this Terminal.
May be used only when in a region with parameters and the current
position has no children. Will bring up
a dialog box which allows you to specify integer values for any declared
parameters. An empty entry means that
the default value should be used. This
command is the same as the “Change Values…” button on the parameters display.
Create Federation Here. May only be used
when a region is selected. Creates a new
federation consisting only of this region.
Add Region to Federation. May only be
used when a region or federation is selected.
Allows you to incorporate a new region into an existing
federation.. Now that you have at least
two regions in your federation, it automatically brings up dialog box described
in Change Score Offsets below.
Change Score Offsets. Allows you to view or
change the conditions under which scores must be adjusted, and the amounts to
adjust them by. The conditions must
consist of comparisons of arithmetic expressions, joined by &, |, and ! for
and, or, and not. The complete grammar for this is given below:
condition:
condition
& condition
| condition
| condition
| ! condition
| ( condition
)
| exp
compare exp Where “compare” is
one of <, =, >, <=, !=, >=
exp:
numeric_constant
| parameter_name
| exp + exp
| exp
- exp
| exp
* exp
| exp
/ exp
| - exp
| ( exp
)
“==”, “&&”, and “||” can be substituted for “=”, “&”, and “|”., and parameter_name refers to
any parameter declared in one of the member regions. The score offset to be applied when the
condition holds is given on the right side, and must be an integer. (As usual, positive numbers favor Black.)
When you choose “OK,” each condition is evaluated at each
terminal in the sum game. When the
condition holds, the score at that terminal is adjusted. The thermograph of the federation is adjusted
to reflect the changed values of these terminals. You can see whether a condition was applied
at a terminal by navigating to it and looking for a note between the “Scoring:”
and “Prisoners:” displays on the right side of the screen.
Refresh Federation. May only be used when
a federation is selected. If you change
the contents of a region included in this federation (including perhaps
parameter values), this operation tells AnalGo to recompute the game tree of
the federation, along with its score offsets and thermograph.
4. Example
As an example, consider the Go regions shown in Figure
2. This game has a six-square region on
the left and a two-square region on the right, which we’ll refer to as regions
A and B respectively. All of the White
stones are alive accept for F13, and the Black stones at O11 are also
alive. The black group that makes up the
majority of this picture is alive only if it makes two eyes in region A, or
makes the connection in region B.
We first
explore the complete game tree in the two regions, as usual. Then we select region A and use the Declare
Parameters command to define the parameter “eyes” with a default value of
1. Navigating to the terminal position
where Black wins both J14 and K13, we use
the Set Parameters at this Terminal
command to change the value of “eyes” to 2 for this position, since
Black can form two eyes in this case.
Similarly,
we select region B and create a parameter named perhaps “connection.” We’ll
give this a default value of 0, although there are only three terminals here,
so in terms of the work required it matters little which outcome we consider
the default. The one case where there is
no connection is when white takes M13, N12, and fills the ko, so we go to this
terminal and set the value of “connection” to 0.
Figure 3: A possible (but unlikely) outcome of the game
in Figure 2 in which the Black group is dead, and a score adjustment is needed.
Now we’re
ready to make the federation. Selecting
one of the two regions, we choose “Create Federation Here” and see that a new
(blue) federation is created with the same location and same game tree as the
(green) region. Now we choose “Add Region to Federation” and click on the other
region to bring it into the federation. This
also brings up the score offsets dialog box.
For the condition, we use “eyes < 2 && connections = 0” to
represent the case when the Black group dies (there are many equivalent
expressions that could be used here).
And finally, for the score offset itself, we put “-45” in the box to the
right of the condition. Forty-five
points is an approximation, but it is enough to tell AnalGo that Black will
avoid the condition if at all possible.
And we’re done! You can examine the resulting game tree and thermograph be selecting the federation (with the Tab key, if necessary) and using the arrow keys to navigate. If you see a missing move or incorrect parameter value at a terminal, you can edit the appropriate region and then use “Refresh Federation” to rebuild the federation’s game tree. To edit the condition itself, use the “Change Score Offsets” command.
5. Availability and Current Status
This
documentation and the current version of AnalGo are available from http://www.cs.berkeley.edu/~matth/analgo. Source code is available from matth(at)cs.berkeley.edu. Please email me with any suggestions,
questions, or requests.
Known limitations:
Each
federation may only have a total of 4 parameters defined by its member
regions. This was due to the limited
space on the right side of the screen, but I can move things around to allow
more than four parameters if this would be useful.
SGR
recordings are not as useful for federations as they are for other AnalGo
features, because they do not record any content you add to dialog boxes. This is a preexisting issue with the playback
feature, but it is much more noticeable when using federations. I am currently reworking the playback feature
to remember what happens in dialog boxes.
Federations
were designed as an alternative to subregions, not as a complementary feature,
so including a subregion or pseudoterminal in a federation is not officially
supported (although it may work).
6 Conclusion
Combinatorial
game theory relies on the ability to decompose games into sums of smaller
independent games. Federations allow users
to describe interactions between regions that interact under certain circumstances,
and compute the sum of these regions for use in ordinary combinatorial game
theory analysis. We have implemented
federations in AnalGo in a way that should allow users the flexibility to
describe a variety of possible interactions.
Acknowledgements
Professor
References:
[1] Elwyn R. Berlekamp, John H Conway, and Richard K
Guy. Winning
Ways for Your Mathematical Plays 2nd ed. Volume 1. 2001
[2] Brian Carnes. “AnalGo.” http://www.icsi.berkeley.edu/~carnes/ 2003