Goudkov K.S.
Moscow Institute of
Physics and Technology,
State Research Institute
of Aviation Systems
Combinatorial approach for solving
capturing races emerging in multi-move go-like games
Go (weiqi, baduk) is an
ancient board logic territorial game that is very popular in Korea, China, and
Japan. Like chess there are many varieties of game go. One direction of
modifying the game is placing several stones instead of one. The most famous of
such games is trigo invented by Steve Metzger [1]. This game is played on a
hexagon with triangular gridlines but keeps the rules, tactics, and strategy of
standard game go. In every move except the first move a player places two
stones instead of one. So we can call trigo as double-move go. It is natural to
consider the full succession of multi-move go-like games.
In every game in the
considered sequence there is a problem of capturing races. Capturing races are
the situations where both players don’t have unconditionally alive groups and
try to capture the opponent’s group by using its shortage of liberties. If you
capture the opponent’s group faster you are alive. To determine who wins in the
capturing race it is necessary to estimate the number of liberties of every
group. A group can include a big eye that is the number of squares that can’t
build the number of eyes necessary to form a live group. It is two eyes for
standard go, three eyes for trigo and N-1
for N-move go. The goal of this
article is to estimate the number of liberties of a big eye in multi-move
go-like games.
Let N be a number of moves in a multi-move go. To fill the big eye it
is necessary to fill every square in it except the squares that can be filled
in two last moves and fill the (N-1)-dimensional
eye. Let’s prove that squares filled in two last moves don’t count as the liberties.
When the first player fills the last but one part of stones the second player
has to respond. So both the squares filled by the first player and the squares
filled by the second player are not the liberties. Let n be a size of a big eye and f(n)
be a number of liberties of a big eye. So the recurrence has the following
form:
It is important to mention that
recurrence has no sense when eye is smaller than 2N. In this case the number of liberties is strictly equal to the number
of squares. It is natural because every respond move can only decrease the
number of liberties in this case.
Let’s find a solution of
the recurrence in the form of a polynomial:
Let’s use the boundary
condition:
So the solution of the
recurrence has the following form:
Let’s consider two
important cases of general equation.
The case of N=1 corresponds to game go. The case of N=2 corresponds to game Trigo. In go
game literature it is a standard approach to memorize the numbers of liberties
for the big eyes. For example this succession is given in [2]: 1-1, 2-2, 3-3, 4-5, 5-8, 6-12, 7-17. It
is easy to see that general formula for N
= 1, n >= 2 fully corresponds to this well-known succession. The similar
succession can be constructed for trigo using the same formula for N = 2, n >= 4: 1-1, 2-2, 3-3, 4-4, 5-5, 6-7, 7-10, 8-14, 9-19, 10-25.
In this article the problem
of estimation of the big eyes’ number of liberties in multi-move go-like games
was considered. The recurrence for this number was obtained and solved. The
final formula for the case of N=1 is
in agreement with succession for memorization given in the go game literature.
The effects concerning approaching corners and sides of the board are beyond
the scope of this article. The possibilities of forming the required number of
eyes for unconditional life for the given size of the big eye are also beyond
the scope of this article.
Literature:
1. http://www.iggamecenter.com/info/en/trigo.html
2.
Bozulich
R. The second book of go // Kiseido Publishing Company. – 1987.