LifeAndDeath Problem (TsumeGo) Solver
After more than 3 years of design and test, XuanXuanGo possesses its
own artificial intelligence and can solve
lifeanddeath problems on its own now. I hope XuanXuanGo is the most powerful, the fastest,
the most userinterface friendly Go problems solver in the world. It
provides most detailed lifeanddeath information and
can solve wide range of problems.
Problem Range
Unfortunately, XuanXuanGo cannot solve all Go problems in the world.
XuanXuanGo can only solve fixed area problems. A fixedareaproblem
means that the problem is confined to a limited board area or
region. To solve such a problem, moves are played in the area. The
most manifest feature of fixedareaproblem is that the problem has
outer stones, they form the wall of safe, which is the boundary of
the problem. The traditional fully enclosed problems are only a subset of
fixedareaproblems, as the problems are not required to be fully
enclosed. The outer stones can be from one side or both sides. If
they are from one side, the problem is called
simpleboundary problem, the side which has outer stones is the
attacker and will try to kill the stones inside the boundary, the
other side is the defender, and will try to live. If both sides has
outer stones, the problem is called compoundedboundary problem and
is usually a semeai (capturerace) problem. Sometimes, a
compoundedboundary problem almost likes a simpleboundary problem,
except that the defender has a few outer stones as reinforcements.
Problems can be located at any part of the board. XuanXuanGo is most
capable of solving simpleboundary problems.
It is estimated that 90% problems in the world are the
fixedareaproblems. Will XuanXuanGo solve 90% problems of the
world? No. If a problem has too many empty points inside the
boundary, XuanXuanGo cannot solve it either. Here involves the
definition of hardness of a problem. For human, the more variations
the problem has, the harder the problem is. But for a computer
solver, the more empty points the problem has, the harder the
problem is. Human is not sensitive to the increasing of empty
points, but for a computer solver, the hardness increases
explosively as the increasing of empty points. Some very easy
problems for human are very hard for computer, and vice versa. It is
estimated that 15% of problems have too many empty points, so
XuanXuanGo should solve 75% problems in the world. But in fact, even
for the fixedareaproblems without too many empty points, 3% to 5%
problems cannot be solved. However, such problems are hopeful to be
solved in the future version if the algorithm is improved. So
finally, XuanXuanGo can solve 70% to 72% problems you meet! I
believe, this means XuanXuanGo is a very strong Go problem solver. Following is the summary of problem range that XuanXuanGo
can solve:
 FixedAreaProblems. This implies: the outer stones form the
boundary and are safe, the stones inside the boundary cannot
escape, unless connect to the reinforcements if they have
 Not too many empty points, usually less than 20
 XuanXuanGo can solve only a small part of tesuji or connecting
problems, these problems should have stones in danger
 XuanXuanGo cannot solve endgame problems. XuanXuanGo
concerns only lifeanddeath
Recognition results
XuanXuanGo provides detailed outcome information for the problem,
they are:
 Lives/Dies
 Lives/Dies by DoubleKo
 Bent4inthecorner
 "Ko, but at least seki" / "Ko in Sente, but at most seki"
 Seki
 Eternal life
 CyclicKo
 Ko in Sente/Ko in Gote/1000YearKo
Except for 1 and 8, 2 and 5 are the most important outcome for
problems. Above are also the preferable levels the solver tries to
pursue, i.e. if the solver can live or kill unconditionally, it will
not live or kill by double ko, and so on. However, providing
detailed outcome information is at the cost of speed. If XuanXuanGo
treats "Lives by DoubleKo", "Ko, but at least seki", Seki, Eternal
life, CyclicKo as Lives, and "Dies by DoubleKo",
"Bent4inthecorner" as Dies, the performance will be at least 4
times better. XuanXuanGo chooses to sacrifice speed and provide
detailed result information.
The problemsolver is the cream of XuanXuanGo, and the
recognition of Seki and DoubleKo is the cream of the cream. When we
talk about Seki, we usually mean two surrounded goups of stones
share at least two public liberties, but in some unusual scenarios,
Seki can be very subtle, as demonstrated following. XuanXuanGo can
recognize very well, both sides cannot atari or remove other side's
stones.
Solving Problems in their original forms
One of the major goals of XuanXuanGo when design the problem solving
function is to solve problems in their original forms. That means
the problems don't need to be fully enclosed by stones, they appear
just like in books. You need neither add stones nor mark the stones
before solving them. There are a lot of Go Problems in SGF files (from
www.goproblems.com, for
example), what
you need to do is to open the files, then press "Solve" button to
get the problems solved.
Categories of problems XuanXuanGo can solve Problems
are classified into 4 categories internally by XuanXuanGo, all
following problems XuanXuanGo can solve successfully.
 Simpleboundary problems




B to play first 
W to play first 
W to play first 
W to play first 
XuanXuanGo has the best performance when solving this type of
problems. If there are not too many empty points, XuanXuanGo will
solve instantly. Fortunately, most of lifeanddeath problems belong
to this category.
 Compoundedboundary problemsSemeai (capture race)




B to play first 
B to play first 
W to play first 
W to play first 
For Compoundedboundary problems, the performance is not as good
as Simpleboundary problems. Here, problem 3 above has 3 groups of
outer stones, 2 groups of inner stones will have a complicated
capture race. It takes 208 seconds to solve on my computer (Dell
D630, 1.8GZ).
 Compoundedboundary problemswith reinforcements




B to play first 
B to play first 
W to play first 
B to play first 
This type of problems looks like type 1 or 2, except that the
defense side has reinforcements. Here, problem 1 above, the five
black
stones have two ways to live: win the capture race against 8 white
stones, or connect to 3 outer reinforcements. For human, this is not
a very hard problem, but for XuanXuanGo, the problem is very hard
indeed. It takes 113 seconds to solve on my computer (Dell D630,
1.8GZ). Problem 2 above, black has 2 outer reinforcement stones, it
seems that the inner black stones can never connect to it, but it is the reinforcements
that give black the hope of live. Problem 3 above, white need to kill the
inner black stones while prevent them from connecting to their outer
reinforcements. Problem 4 above, the 4 black stones are in trouble, the
only way of survival is to connect to the outer reinforcements.
 Semiopened problems
2 lines opened




B to play first 
B to play first 
W to play first 
W to play first 
For this type of problems, the besieged stones have the
possibility to escape, as there is a twolinesopen along the side
lines. The outer stones will have to kill the inner stones while
prevent them from escaping. This tremendously increases the
calculation tasks for the solver engine, and the performance is
worst among all types of problems. Here, problem 3 above, it's a
compoundedboundary capturerace problem too, with a 2linesopen.
All problems above have only one 2linesopen, if a problem has two
2linesopen on both sides, the chance for success is very slim.
Solver's user interface
The use of XuanXuanGo's solver is very simple. Just
setup your own lifeanddeath positions in new games or
open an existing lifeanddeath file (SGF or XGF), then Press "Solve"
button,
XuanXuanGo will think for the side next to play, which you can tell
at program's status bar, you can rightclick on the boardarea to
toggle the side next to play. If there are not too many empty
points, XuanXuanGo can usually find the solution in seconds.
For hard problems, it may take the solver a few minutes to find the
solution, depending on how many empty points the problem has and the
type of the problem, meanwhile, you will see a progress bar on the
status bar and how much time the solver engine currently used.
During the process, you can switch to other games to launch another
task to solve another problem. But the task number should not overnumber that of the cores of your CPU. There is a time limit for
the solver to find the solution, the default value is 20
minutes, you can change this value in the
Settings dialog box.
Interactive mode
Once the solver engine plays its first move, it is activated
for the game, you will see the results and how much time the engine
used for current move. When the solver engine is activated, the game
enters an interactive mode, which means if you put a stones on the
board, the engine will respond immediately, finding the best move
for the side next to play. Under interactive mode, you
can play the lifeanddeath problems against computer like a game.
You can go back for any steps and play where you think is good, the
engine will automatically respond to your move, this means you have
the opportunity to play through any possible sequence and to get
immediate reply from the computer. The engine usually takes
much less time to find its latter moves. Under interactive mode, you
can take Ko stones immediately, ignoring Ko rules. If your last move is good
enough and the engine thinks wherever it plays, it gets the worst
results, the engine will Pass. If the problem is a wrong problem,
such as 'blackfirsttoplayblackdies' or
'blackfirsttoplaywhitelives', the engine's first move will also
be a Pass, because the engine thinks it's not worthwhile to waste a
move to make no differences. Under such circumstances, you can go
back for one step and play where you think is good, the engine will
let you know why your last move is useless. If the results is Ko,
the engine may use Ko threats in the problem, sometimes it may use
Pass as Ko threats. If you play anywhere outside the problem, the
solver engine will treat your move as a Pass, and play its next
move.
If the result of a solver engine's move is
not an extreme one (Live or Die), you can press "Solve" button
repeatedly, letting the engine find best moves for both sides,
otherwise, the engine's next move will be a Pass. For
example, if the result is Seki or Ko, or DoubleKo, etc. you can
press "Solve" button repeatedly until the board status reaches
stable. Then you can go back for any steps to try other moves, the
engine will respond to your moves.
Activating the solver engine for a game consumes about 200MB
memory of your system. Unless your computer is rich in memory,
please don't let too many games' solver engine be activated. To
deactivate the solver engine of a game, press the "Stop" button,
this button can also be used to stop current solving process, the
memory used by the solver engine will be released. If a game
contains many lifeanddeath problems, the engine should be
deactivated before solving another problem in the same game.
XuanXuanGo recommends that each game contains only one problem, a
game file can contain many problems, though.
Analyzing lifeanddeath problems in a full game
If the entire board position is a lifeanddeath problem, you just
need to press "Solve" button to get the problem solved. However, if
you're reviewing a played game, and there are problems in the game
need analyzing, you can, of cause, create a new game, and put
related stones in it and analyze, but this is too troublesome. XuanXuanGo provides an easy way doing this:
In above picture, on the lower right part of the game, there is a lifeanddeath
problem. To analyze it, we need just "encircle" the problem region
with "Selection" marks (yellow blocks), then press "Solve" button,
XuanXuanGo will try to find the solution to the problem. For the
problem in above picture, the solver uses 34.91 seconds on my
computer, the result is Seki. Because
XuanXuanGo always thinks for the side next to play, please make sure
that the side next to play is correct before you encircle the region.
The solver engine will be activated for the game, you can try any
moves inside the region. Please be noted, the marks should FULLY
encircle the problem region, as in above picture, any stones outside will be
ignored by the solver engine. If the problem has reinforcement
stones, the
marks should include them. After the analysis is done, press "Stop"
button
to deactivate the solver engine. The analysis results and time used
by the engine can be saved, on condition that the game is not in
"ReadOnly" mode. By default, XuanXuanGo set the newly opened file
as readonly and you cannot mark on the stones or board. You
have two ways to bypass, the first, enter "trial" mode, the second,
use "Readonly" button
to toggle readonly mode off. Under trial mode, you don't need to
worry about changing the game file, so the analysis results cannot
be saved.
From version 6.0, XuanXuaGo has the ability to
get the boardstatus from other
program's window or Clipboard, this makes XuanXuanGo much
more practical in solving lifeanddeath problems in real games.
Click here to view more examples
of solving real problems.
Let the solver engine do lifeanddeath practice
XuanXuanGo has the function to let users do lifeanddeath practice,
this has nothing to do with artificial intelligence. In the
lifeanddeath
games, all possible moves have been input, human plays the odd number
moves and the program responds with the even number moves. If the
problem is solvable for XuanXuanGo (fixedarea, with not too many
empty points), we can ask the solver try to do the practice.
When the game is waiting for human to solve, we just press "Solve"
button, let the solver do the job. After the solver successfully
plays its move, the system will respond with even
number moves, then we need press "Solve" button again and
again, until
the problem is solved. You can use toolbar button
to toggle the Edit/Practice mode of a game. If the game is not in
practice mode, the system will not automatically response with even
number moves and you need manually play, or, press "Solve" button
repeatedly if the result is not extreme (Live/Die).
When to use XuanXuanGo's problem solver?
 To analyze problems you meet in real games, for example,
when you are watching webGo.

To analyze existing lifeanddeath problems. Sometimes, the
tsumego books may have too few variations for problems, or even
with no solutions provided, you might want to know "what if I
play like this, will the problem be solved?" With XuanXuanGo,
all these questions can be answered. With the help
of XuanXuanGo, you have a tsumego master at side.
 To analyze problems in existing game files.
The shortcoming of XuanXuanGo Solver XuanXuanGo solver
has some shortcomings. First of all, it cannot solve all problems in
the world, following are the others:

The moves may not be optimized. For example, if there are two
ways of making live, one lives bigger and is better than the
other, XuanXuanGo may not choose the better one. Sometimes,
XuanXuanGo may take meaningless sente, as demonstrated in
following figure:

Black to play first
The first correct move should be at C, however,
XuanXuanGo plays at A first, it's a sente move, after
white plays at B, black plays at C. Obviously, playing at
A is a meaningless sente move. 
 The safety of outer stones is ignored. XuanXuanGo assumes
the outer stones will never be attacked.

White to play first
Normally, XuanXuanGo uses 0.6 second to find the
solution for this problem. However, if white (human) plays at A or B,
XuanXuanGo (black) will not respond at C or D. The
reason is that XuanXuanGo thinks the 3 top black stones
are a wall of safe, playing at A or B is regarded as a Pass
move. 

Black to play first。This is a semiopened problem. it takes less than 0.4
second to find the right solution. Because the result is
"Ko in sente", we can press "Solve" button repeatedly to
let XuanXuanGo play for both sides until the board
status reaches stable. Everything seems to be perfect.
The problem is, if white (human) plays at A,
black (XuanXuanGo) won't response at B, because XuanXuanGo
takes the marked stones as outer stones and never expects
white to play at A. 

As I said before, XuanXuanGo solves problems in their original
forms. This involves the recognition of which stones are outer,
which stones are inner.
The program should have enough Go knowledge to distinguish
between inner and outer stones. Sometimes, XuanXuanGo may regard
inner stones as outer, or vice versa. If the inner stones are
regarded as outer, it's impossible to get the right solution, if
outer stones are treated as inner, the solver will use much
longer time to solve the problem, usually, this will result in a
failure.

White to play first
This is a capturerace problem, because the distance
between A and B is greater than 1, XuanXuanGo wrongly
treats the 4 inner stones as outer. If we add a black
stone at C or D, the essence is not changed, but
everything is OK. 

White to play first。
Because the 2 marked stones have 4 liberties, and they
are at line 2, XuanXuanGo wrongly treats them as outer
stones. Although stones with 4 liberties at line 2 are
usually safe, but for this problem, they aren't, when
their liberties are decreased, black may finally be able
to capture them at A. Sometimes, adding a black stone at
A and a white stone at B doesn't change the essence very
much, and the solution is correct, but the problem is
not in its original form any more. 

Black to play first
The 3 marked stones actually have no safety issues, but
XuanXuanGo wrongly regards them as inner stones. The
solving process becomes very slow. If we add a black
stone at A or B, it takes about 1 second for XuanXuanGo
to get the correct solution. Connecting
the absolutely safe
stones to outer stones will significantly speed up the
solving process! 
As we can see from above, it's not an easy task to develop a good
solver. There are too many things need to be taken into consideration
and too many difficulties need to overcome.
Problem solving tests
XuanXuanGo has been tested with problems from more than 50
TsumeGo books. Most of the books are written by Japanese
professional Go players, including Go Seigen, Honinbo Shusai, Maeda
Nobuaki, Hashimoto Utaro, Fujisawa Hideyuki, etc, they are all TsumeGo
super masters. The computer used to do the test is Dell D630,
Core(TM)2 Duo notebook, 1.8GZ. The total number of problems is
7268,
5239 problems are solved successfully,
i.e. more than
72% of the
problems are solved!
Mistakes made by professional Go players
During the testing process, more than 40 problems
are found to have mistakes, following are some of them:
Click here
to view more mistakes made by professional Go players
Solver's selfassessment
XuanXuanGo reaches the level of professional
Go players in solving fixedareaproblems with not too many empty
points. It's not perfect, but for most problems, it can provide you
guidance or solution that is reliable, authoritative, and professional.
Many problems that may take professional players hours to solve can
be solved in minutes. The solver can be activated for a problem so
that it enters into interactive mode, in which you can try any
variation for the problem.
