[[manual]]

Table of Contents

This page is the manual of Glop 1.0, released in April 2007. New versions of Glop are available.

In the top of the “parameters” tab, you can choose either a classic starting position (a n-spot game), or a free starting position. To determine the representation of a position, you can do as follows :

First of all, notice that this position determines 5 regions in the plane, one of them isn’t bounded. The two regions on the left are isolated from the 3 others, so we’ll divide this position into 2 lands : the end-of-land character is “]”, the end-of-position character is “!”, so the representation will be something like : “land1]land2]!”. The end-of-region character is “}”, so we’ll have “R1}R2}]R3}R4}R5}]!”.

The gray vertices have no life left, so they won’t be displayed in the representation. The green vertices have 3 lives left, they’ll be displayed as “0”. The yellow vertices have two lives left, they’ll be displayed as “1”. There are two sorts of vertices with 1 life left (the red ones), those that are in two regions (upper-case letters), and those that are in only one region (lower-case letters).

To write the representation of a region, we enumerate the boundaries. The end-of boundary character is “.”, and we must pay attention to orientation : in a given region, we turn counterclockwise around the outer boundary, and clockwise around the others. So, the representation will be : “1aa.AB.}AB.}]0.aaABC.}0.1ab1bcDca.ACB.}D.}]!”

It is impossible to play in the region “D.}”, so we delete this region, and then we replace the letter “D” - that appears only once in the representation - with the generic number “2”. When a lower case vertex occurs twice in a row, as in “1aa”, we also replace these two letters with “2”. The representation we give to the program is : “12.AB.}AB.}]0.2ABC.}0.1ab1bc2ca.ACB.}]!”.

When inside a region, there is 3 lives or less, it is useless to separate boundaries; so, we delete any “.” except the last in the representation. Instead of “2.AB.}AB.]!”, the representation of the above position is “2AB.}AB.}]!”.

- Start computation : click on the “Compute” button of the “Computation” tab.
- Stop computation : you can stop an incomplete computation at any time, by just clicking on the “Stop” button.

The point reached by computation is regularly refreshed in the interface, as a vertical list of levels. What we call a “level” is just the list of children of a given position. When you try to compute the state of a position (win/loss or nimber), you basically need to compute the state of its children, and computing is recursive on the “children”. At a given time, computation can be represented as the list of each child currently computed in a given level, and that’s exactly what we display in the interface.

First of all we need to understand the underlying game theory. To compute the win/loss of a position, we need to find one losing child (so the position is winning; only one losing child is needed), or to prove that all children are winning (so the position is losing).

As only one losing child is needed to show that a position is winning, there are several ways to complete a computation. Some of them are much easier than others, so by choosing to study the right children, you can make the computation much faster (for instance, it’s easy to be 50 times faster on the n=12 computation !).

Here’s the features of the program that help you to choose the right children :

- Choose a child : you can change the current computed child of any given level just by clicking on a cell in this level. Click on the first three cells (”Numero”, “Alive”, “Lives”) to reach the next child, and on the fourth cell (”Nimber”) to reach the previous child.
- Display all children : click on the “Position” cell to display a list of all children in a given level. Then you just need to click on the desired child in the list to reach it.

Notice that positions are displayed on the right side of the interface, so you can choose the positions that seem to be easier to compute (like those who tend to separate into lands).

We also use a system of colors to guide user choices in the interface. Green color means that a given level has no more than 4 remaining children in an unknown state, and red color means there is only one left. When you see a green or red level, it indicates that the position on the above level is probably a losing one.

The ideal situation is a succession of the following kind : {green or red}/any color/{green or red}/any color... Please notice that this “zapping” game has been found very addictive by its programmers and they cannot be held responsible for any damage to your social life.

During a computation, the program stores the positions whose nimber is known (ie losing position+nimber) in a database, the “Main base”. On the top left of the interface, the number of stored positions is indicated. Keep an eye on this number, it will help you to control your RAM (100,000 positions need approximately 10MB).

You can stop your computation, save your database, shut down the program and then later reload the database to resume the computation. You also can load several databases, and the program will check that the results are coherent (an error message is displayed if any position has a different nimber in two databases).

The “Main base” is not the only database in this program, the other databases are described below. The default extension for these databases is “.spr”.

Once a computation succeeds, you may want to check the result. By clicking on the “check” button, the program checks that the database allows you to compute the position indicated in the “parameters” tab. An error message is displayed if needed.

The algorithm tries to use the minimal amount of positions to check this result, storing these positions in the check database. So, using “check computation”, you can reduce the number of positions. This is useful to save memory, and also if you want to do hand-checked proofs for little positions.

You can also save the check database with the appropriate button.

If you tick in the box in the “parameters” tab, a file will be generated during the check computation. This file will allow you to either draw a graph of the computation using the program “Graphviz”, or have a hand-checkable proof, if you read the file with a text editor.

After a check computation, click on the “Save check graph” button, and save the “.dot” file. Then, if Graphviz is installed on your system, the command “dot -T png -o example.png example.dot” will generate the graph. Make sure the graph is readable only if the position isn’t too complicated (n<6). A node in the graph represents a couple (position;nimber). On the right of the graph, the number of lives of the positions of this level is indicated.

Options in the “parameters” tab :

- if you use colors, losing couples will be in red, winning couples in blue, and couples with several lands will be in yellow.
- detail level : a couple is represented by : a dot (level 1), a number (level 2), the full text describing the couple (level 3).
- you can choose to print only the positions with more than a certain number of lives. This is useful for complicated positions (n>5), to show the beginning of the computation.

We can see a graph above showing the beginning of a computation for n=11. On the right of the graph, you can see that only positions from 24 to 33 lives are represented. In this example, we decided to represent a couple by a number (detail level 2), as it would be unreadable if we drew all the positions. But if we read the file “.dot” generated by the program with a text editor, we will see the couples represented by those numbers.

Here’s another example, with detail level 3. It’s a complete calculation, for the 3-spot game, showing that the first player has a winning strategy. On those two graphs, it appears that for a losing couple (a red one), ie a position whose nimber is known, we must check that every child is winning, so it is linked to many couples below. On the contrary, to show that a couple is a winning one (in blue), ie a position whose number is unknown, we only need to find one losing child. A yellow couple is a position with several lands, it can either be winning or losing. To find it, we must check every land composing this position, further down in the graph.

For a given winning couple, if we know that the nimber is neither a nor b, then it will be linked to a losing position with nimber a and another losing position with nimber b. So it sometimes happens that a winning couple is linked to several children, just like in the graph below, where the couple 18 (2AB.}AB.}]! not 0 1) is linked to 22 (22.}]! 1) and to 16 (! 0, void position).

If you click on the “Complete check” button, the program will check the nimber of any position in the main database, warning you if needed.

In the “Children” tab, we can compute the children of a given position. Make sure you use a correct syntax. If the nimber of the child is known in the main database, it is printed at the end of the line.

This tab can be used to play Sprouts by correspondence : suppose you play a 12-spot game. First of all, you compute the win/loss of the 12-spot game with the program, or you load a database that allows you to solve it. The starting position is a loss, which means you should let the other player begin. Let’s suppose he does, and that he plays 0.0.0.0.0.0.0.0.AB.}0.0.0.AB.}]!. Then, using the children tab, you find that the nimber is 0 for 0.0.0.0.A.}0.0.0.0.A.}]0.0.0.}]!, ie it’s a loss. So you play this. Then, if your opponent plays 0.0.0.0.A.}0.0.0.0.A.}]0.0.AB.}AB.}]!, you can play 0.0.0.0.A.}0.0.0.0.A.}]0.1a2a.}]! because its nimber is 0, etc...

We can filter the positions in the main database, keeping only those that verify some of these parameters :

- Number of lives (we can choose a minimal or a maximal number of lives).
- Nimber (we can choose a minimal or a maximal nimber).