The game of Mühle (9 Men Morris) is a common game in Europe. It is played on a square board consisting of three concentric squares. Black and white pebbles (or men) are placed on the crossings and later moved around. The following is a picture of the board with the playing positions numbered from 1 to 24.

1--------------------2--------------------3 | | | | | | | 9-------------10------------11 | | | | | | | | | | | | | 17------18-------19 | | | | | | | | | | | | | | 8-----16----24 20----12-----4 | | | | | | | | | | | | | | 23------22-------21 | | | | | | | | | | | | | 15------------14-------------13 | | | | | | | 7--------------------6--------------------5

Notice that the board instances, for the purposes of strategy, validity, moves, etc. form classes of equivalence. Each class has a maximum of 32 different boards and these are generated by:

- 4 rotations
- 2 axial symmetries
- 2 inner-outer square swaps
- 2 colour swaps

Because of the large number of possible boards, it is assumed that that each equivalence class of boards will be stored only once. This will have an extra cost that will be paid at searching and/or insertion time. For this there are two alternatives

(1) Insert any of the boards at insertion time. At searching time we will have to search all of the members of the equivalence class, that is up to 32 searches.

(2) Insert a canonical one (it is quite easy to select a canonical one when we use signatures, we can select the one with the smallest signature). At searching time we search only once after having selected the signature of the canonical one.

The second policy is superior as we do only one search in the
database.
Notice that following a successful signature search we still
have to compare the boards.
Different boards may have equal signatures.
This comparison will seldom fail, it will almost always return true.
I.e. signature collisions are rare, they occur with probability
*O*(1/*n*).

Additive signature functions for Mühle.

Let the positions in the board be numbered from 1 to 24 as shown
above.
Let *W*_{i} and *B*_{i} be random numbers chosen uniformly from
[0,*n*-1] unless otherwise stated.
A linear signature is defined by

where when there is a white pebble in position

Rotations of the board.

To do rotations by multiplication the following equations must hold:

etc. This means that . We can choose to be a non-trivial root of the above, for example for , and if we compute all the

Colour swaps.

If we select
, colour swap is achieved by
complementing the signature.
Cancellations cannot happen as we cannot have two men in a
single position.
It we have no other conditions on the *W*_{i} and *B*_{i} this is a
good solution.

Inner-outer square swaps.

This is not possible to achieve by simple multiplication, as

has only one non-interesting solution. A relatively general technique may be used to solve this problem. If we define a new signature over a single square as

then the signature of the entire board can be represented by a triplet

The inner-outer swap of the signature (

Since we are interested in the minimum signature (in the case of a tuple of values, the ordering will be a lexicographical ordering of the elements left to right), we first choose the minimum between

Axial symmetries.

There is again no obvious solution for symmetries, as a vertical
axis symmetry would have to satisfy:

which gives non-interesting solutions.

Question / exercise.

What are the advantages and disadvantages of the signature defined
by the tuple:

As a final remark, it should be noticed that in reducing the signatures
of the entire board to 3 signatures over squares, the cardinality of
each individual *S*^{*} is only 3^{8}=6561.
So at this point it is probably more useful to use an exact mapping
between squares and integers, for example

Rotations by 90 degrees and symmetries can now be precomputed and stored in tables, their size will be reasonable for any computer. Then all the computation of signatures is reduced to table lookups and the operations done for colour and inner-outer swaps. The resulting signatures will also be unique, so this will save the comparison for equal boards once that the signatures match. This is interesting because with the ideas of signatures we have gone back to a better deterministic algorithm.