Home MadLab   Info Avoid goal
Avoid goal

MadLab uses an algorithm that is designed to obtain goals. Avoiding goals is not always as easy to handle as obtaining goals, so there is an asymmetric relationship between obtaining and avoiding. For instance it may be easy to prove that a particular block of stones can be captured by the attacker, but it may be much less easy to prove that the block can never be captured if the defender plays in a particular way.

This means that the program may be in doubt even in situations where most humans would consider the block indisputably alive -- for instance because it can merge with another block and thereby acheive a large number of liberties. But many liberties do not necessarily mean that the block is safe (even though this is often so). Instead the program keeps augmenting the lambda-order to see whether or not a particular defending move saves the stones from a subsequent attack.

 

Example: White to avoid being captured

 

This example is taken from the "Quick guided tour". As described there, the two white stones can be captured by Black (C6) if White does not try to save them. If you right-click on one of the white stones and choose "Escape", MadLab will start looking for white moves to avoid the capture.

The lambda-order soon reaches n=3, meaning that these candidate white moves are tested by a subsequent 'obtain-search' of lambda-order 3. At some point you will see the following:

 

 

The gray intersections represent white moves that have not been tried yet, whereas the red marker indicates the move currently being analyzed. When a gray move is analyzed, it may either disappear (if Black can still capture White after that particular white move) or turn yellow or green. Yellow means an undecided move that will need more analysis. Green means that the move survives a subsequent attack by Black of the current lambda-order (shown above the board: in this case n=3). Any move that is not marked on the board will not work for White.

Each time the lambda-order is augmented, all remaining markers turn gray and the process repeats itself. After some more time, you will see the following board:

 

The program is now busy analyzing the moves that turned yellow in the first phase of 'avoid goal'. Note that the gray markers on F4, G5 and G6 have disappeard. The other markers are mostly yellow -- awaiting further analysis -- but three of them are green. After a white move on one of the green intersections, Black cannot capture White by means of a search of lambda-order n=3. Note that this does not prove that any of these three escape attempts will save the white stones against capture, because the moves may be vulnerable to a black attack of lambda-order n=4 or higher. (An analogy: just because a block of stones survives an attempt to kill them in a ladder, this does not necessarily mean that they are immune to being killed in a loose ladder).

 

In many problems, the number of defending moves narrows down pretty quickly. And if all defending moves are eliminated, the search terminates, and the program informs you that the attacker wins no matter what the defender tries (and the program plays the most resistive defending move for you to refute).

 

So if you want to try to solve a particular problem yourself, you can try to play the attacking move that you think works, and afterwards activate 'avoid goal'. If this search terminates, you are on the right track to solve the problem. But if the program keeps thinking, this is because it has found one or more defending moves that are hard (or maybe even impossible) to refute.

 

More details

 

The way 'avoid goal' works is that for all the candidate defending moves, the move is played, and 'obtain goal' is called silently. So if MadLab ponders a long time over a particular defending move, you may prefer to stop the 'avoid goal' search, play the defending move yourself and call 'obtain goal'. This way you can obtain more information about the variations the program is considering (for instance via the menu 'View' --> 'Show Thinking').

 

Note that the problem of connecting two blocks is an 'obtain goal', whereas the problem of disconnecting two blocks is an 'avoid goal'.

 

There is an interesting recent paper available on how to combine goals by means of the operators AND, OR and NOT here.