Tsume go

Solving Tsumego
on Computers
M2 Hirokazu Ishii
Chikayama & Taura Lab
Agenda
1.
2.
3.
Introduction
Related Work
 GoTools
Tsumego Solver

Df-pn (Depth-First Proof-Number Search)
 Df-pn+ (Depth-First Proof-Number Search+)
4.
Conclusion & Future Work
Agenda
1.
2.
3.
Introduction
Related Work
 GoTools
Tsumego Solver

Df-pn (Depth-First Proof-Number Search)
 Df-pn+ (Depth-First Proof-Number Search+)
4.
Conclusion & Future Work
Computer Game Players

Have been studied for many years
 Easy
to evaluate
 Suitable to try out various basic technologies

Were successful in some games
 Othello,

Great challenges remain in some games
 Shogi,

backgammon, chess…
Go…
I study on Go, especially tsumego.
Game Rule




Go is a 2-players game.
A move is played on a line intersection.
If one or more stones are completely surrounded
by other stones, they are captured.
The purpose of Go is to conquer a larger part of
the board than the opponent.
Game Rule

Eye
 An
eye is an area within a group of stones
which is completely surrounded by stones of
the group.
 If the group gets two eyes, they are absolutely
alive.
Definition of Tsumi

Variation of Tsumi
 Semeai
problem
 Escape and Disconnect problem
 Life and Death problem

Goal is to distinguish whether there are two eyes
or not.
Method

AND/OR tree search
 OR
NODE
It corresponds to a first player’s move.
 In order to prove tsumi of this node, we must prove
that one node of child nodes has tsumi.

 AND
NODE
It corresponds to a second player’s move.
 In order to disprove this node, we must disprove
that all nodes of child nodes are tsumi.

Agenda
1.
2.
3.
Introduction
Related Work
 GoTools
Tsumego Solver

Df-pn (Depth-First Proof-Number Search)
 Df-pn+ (Depth-First Proof-Number Search+)
4.
Conclusion & Future Work
GoTools
Has been the best tsume-go solver for 15
years.
 Uses a depth-first search.
 Specializes in completely enclosed
positions.

Heuristics

Static rules
 Most
of the heuristic rules are static.
It is at a particular auspicious point.
 It completes one or more eyes.
・・・

 Static

rules rate moves lower or higher.
Dynamic rules
 The
moves refuting opponent moves at
subsequent positions also get some credit .
Dynamic Rules

1A
2B
3B
4C
Number
 The
sequence
in which the
moves are
made.
6D

5D
○:OR NODE
□:AND NODE
Letter
 The
field where
the stone is
placed.
Agenda
1.
2.
3.
Introduction
Related Work
 GoTools
Tsumego Solver

Df-pn (Depth-First Proof-Number Search)
 Df-pn+ (Depth-First Proof-Number Search+)
4.
Conclusion & Future Work
Tsumego Solver

Important factors are to
 Recognize
the position
 Generate candidate moves
 Evaluate these moves and select the next move
Evaluation of a tsumego is strictly
determined life or death.
 The only method of finding a strict solution
is to search.

Df-pn Search

Depth-First Search
 Memory
and time are used efficiently.
 It is necessary to set a threshold.
Proof number
 Disproof number

Best-First search

Iterative Deepening
 Searches
threshold.
are tried iteratively increasing the
Proof Number
Proof number is the minimum number of
descendant nodes which must be proven
in order to prove the node.
 We can see proof number of the node as
the minimum resource required for search.


Proof number is effective for search
because we want to search the most
promising node.
Disproof Number
Disproof number is the minimum number
of descendant nodes that must be
disproven in order to disprove the node.
 Disproof number is effective for search as
well as the proof number.

Df-pn Search

If n is a leaf node
 when
the value is true
 when
the value is false
pn(n)  0, dn(n)  
pn(n)  , dn(n)  0

When n is an uninspected node
 The
node might be proven or disproven
immediately when inspected
pn(n)  1, dn(n)  1
Df-pn Search

If n is an internal node
 when
n is an OR node
pn(n) 
dn ( n) 
min
Cchildlen of n
pn(C )
 dn (C )
Cchildren of n
 when
n is an AND node
pn (n) 
 pn(n )
Cchildren of n
dn(n) 
min
Cchildlen of n
c
dn(C )
Df-pn Search
Is a depth-first search.
 Uses two kinds of threshold (proof number
and disproof number)

１ .Assign
r.thp  , r.thd  
where r is the root node
Df-pn Search
２.At each node n, the search process
continues to search below n until
pn(n)  n.thp
or
dn(n)  n.thd
(We call it the ending condition)
Df-pn Search
３.If n is an OR node
 At
each node n, select the child nc with the
minimum proof number and the child n2 with
the second minimum proof number. Search
below nc with assigning
nc .thp  min(n.thp , n2 . pn  1)
nc .thd  n.thd  nc .dn 
 C.dn
Cchildren of n
Df-pn Search
４.If n is an AND node
 At
each node n, select the child nc and the
child n2 . Search below nc with assigning
nc .th p  n.th p  nc . pn 
 C. pn
Cchildren of n
nc .thd  min(n.thd , n2 .dn  1)
５.If the ending condition holds, the search
process returns to the parent node.
Df-pn Search
[ pn, dn]
○:OR NODE
□:AND NODE
(2,∞-2)
A
30 nodes
[1,1]
[30,1]
R
[1,1]
[0,∞]
[1,3]
[2,2]
(31,∞-1)
(2,∞-2)
B
[1,1]
[2,1]
[0,∞]
(th p , thd )
(3,∞-2)
C
[1,1]
[∞,0]
(30,2)
・・・
[1,1]
(∞,∞)
D
[0,∞]
[1,1]
E
(31,∞-1)
[0,∞]
[1,1]
[1,1] [1,1]
H
[0,∞]
I
J
[∞,0]
[0,∞]
F
G
[0,∞]
[∞,0]
Df-pn+
Intends to distinguish promising moves
more accurately and to search them much
more deeper.
 Uses two kinds of additional information
during search.

Df-pn+

Two kinds of information
 cost(dis)proof(n,

nchild)
The cost of inspection of nchild starting from n.
 h(dis)proof(n)

Heuristic estimate of the cost to reach any proof
solution from position n.
Df-pn+

The formula for calculating proof number
and disproof number are modified from
df-pn.

If node n is an uninspected node
pn(n)  h proof (n)
dn(n)  hdisproof (n)
Df-pn+

If n is an internal node
pn(n) 
dn (n) 
min
Cchildlen of n
( pn(C )
 (dn(C )
Cchildren of n
 cost proof (n, C ) )
 cost disproof (n, C ) )
At each node n, search below nc with
assigning
nc .thp  min(n.thp , n2 . pn  cos t proof (n, n2 )  1)
 cos t proof (n, nc )
nc .thd  n.thd  nc .dn  (nchild.dn  cos tdisproof (n, nc ))

Bouzy’s 5/21 Algorithm

Dilation
 If
the intersection is not surrounding
opponent’s stones, then add to the
intersection the number of own interim
territory and stones.

Erosion
 Subtract
the number of intersections
with opponent’s stones or vacant.
Bouzy’s 5/21 Algorithm
1
2
2
4
1
2
1
2
1
4 Dilation + 2 Erosion
2
8
6
10
6
2
10
5
12
8
11
12
2
7
9
1
5
1
5
5
10
8
2
6
2
Bouzy’s 5/21 Algorithm
 In
GNU Go ver. 2.6, it was
extensively used
5
Dilation and 21 Erosion are used for territory.
 5 Dilation and 10 Erosion are used for moyo.
 4 Dilation and 0 Erosion are used for area.


Higher Bouzy value means higher
expectation to form an eye.
Because two eyes are required to live, the
second maximum Bouzy value may give a
good criterion.
Agenda
1.
2.
3.
Introduction
Related Work
 GoTools
Tsumego Solver

Df-pn (Depth-First Proof-Number Search)
 Df-pn+ (Depth-First Proof-Number Search+)
4.
Conclusion & Future Work
Conclusion & Future Work

I showed…
 Definition
of tsumi
 Feature of tsumego solver ‘GoTools’
 Df-pn+
 Bouzy’s 5/21 algorithm and its use in tsumego.


Firstly, I have to finish implementing the program.
I also plan to apply the combinatorial game theory
to the program.

Download Report