Life-And-Death Problem (Tsume-Go) Solver
After more than 3 years of design and test, XuanXuanGo possesses its own artificial intelligence and can solve life-and-death problems on its own now. I hope XuanXuanGo is the most powerful, the fastest, the most user-interface friendly Go problems solver in the world. It provides most detailed life-and-death 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 fixed-area-problem 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 fixed-area-problem 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 fixed-area-problems, 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 simple-boundary 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 compounded-boundary problem and is usually a semeai (capture-race) problem. Sometimes, a compounded-boundary problem almost likes a simple-boundary 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 simple-boundary problems.
It is estimated that 90% problems in the world are the fixed-area-problems. 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 fixed-area-problems 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:
- Fixed-Area-Problems. 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 end-game problems. XuanXuanGo concerns only life-and-death
Recognition results
XuanXuanGo provides detailed outcome information for the problem, they are:
- Lives/Dies
- Lives/Dies by Double-Ko
- Bent-4-in-the-corner
- "Ko, but at least seki" / "Ko in Sente, but at most seki"
- Seki
- Eternal life
- Cyclic-Ko
- Ko in Sente/Ko in Gote/1000-Year-Ko
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 Double-Ko", "Ko, but at least seki", Seki, Eternal life, Cyclic-Ko as Lives, and "Dies by Double-Ko", "Bent-4-in-the-corner" as Dies, the performance will be at least 4 times better. XuanXuanGo chooses to sacrifice speed and provide detailed result information.
The problem-solver is the cream of XuanXuanGo, and the recognition of Seki and Double-Ko 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.
- Simple-boundary 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 life-and-death problems belong to this category.
- Compounded-boundary problems--Semeai (capture race)
B to play first
B to play first
W to play first
W to play first
For Compounded-boundary problems, the performance is not as good as Simple-boundary 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).
- Compounded-boundary problems--with 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.
- Semi-opened 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 two-lines-open 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 compounded-boundary capture-race problem too, with a 2-lines-open. All problems above have only one 2-lines-open, if a problem has two 2-lines-open 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 life-and-death positions in new games or open an existing life-and-death 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 right-click on the board-area 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 life-and-death 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 'black-first-to-play-black-dies' or 'black-first-to-play-white-lives', 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 Double-Ko, 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 life-and-death 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 life-and-death problems in a full game
If the entire board position is a life-and-death 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 life-and-death problem. To analyze it, we need just "encircle" the problem region with "Selection" marks (yellow blocks), then press "Solve" button
to toggle read-only 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 board-status from other program's window or Clipboard, this makes XuanXuanGo much more practical in solving life-and-death problems in real games. Click here to view more examples of solving real problems.
Let the solver engine do life-and-death practice
XuanXuanGo has the function to let users do life-and-death practice, this has nothing to do with artificial intelligence. In the life-and-death 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 (fixed-area, 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 web-Go.
- To analyze existing life-and-death problems. Sometimes, the tsume-go 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 tsume-go 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 semi-opened 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 capture-race 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 Tsume-Go 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 Tsume-Go 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:
The problem The official solution XuanXuanGo's discovery Black to play first Diagram 1 Diagram 2 This is a capture-race problem from a Japanese classic Tsume-Go book, which was written in about 1811. The problem is a mistake: Black can never save the besieged stones, it's a black-first-black-dies problem. In the official solution, white 4 is a bad move. If white 4 plays like Diagram 2, white can make an eye, so the black stones can not be saved. Time used by XuanXuanGo to solve this problem: 1.23 seconds
Click here to view more mistakes made by professional Go players
Solver's self-assessment
XuanXuanGo reaches the level of professional Go players in solving fixed-area-problems 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.
