Loading...

The red pieces are three musketeers and the blue pieces are Cardinal Richelieu's men, or, the enemy. Enemy's objective is to force all three musketeers to a single horizontal or vertical line. Musketeers' objective is simply to avoid this; if the player to move has no legal moves and the enemy hasn't won, the game ends and musketeers win.

On his turn, a player moves one piece. Musketeers move by capturing an enemy piece in an orthogonally adjacent square and enemies move to an unoccupuied orthogonally adjacent square.

The original rules actually said that the musketeers win only if they capture all enemies, or if they are unable to move on their turn. It wasn't defined what happens when the enemy has at least one piece left but has no legal moves on its turn. There was a short discussion of this at Vying Games and it was agreed that it makes most sense that musketeers win if this happens. Fortunately, such positions are rare.

On the Little Golem forum, user Gregorio gave a tongue-in-cheek explanation of the enemy's objective: Richelieu has a man with only one bullet and wants to kill all three musketeers with a single shot.

Unfortunately, Three Musketeers is a really unfair game: the enemy can force a win easily, no matter how well the musketeers play. To make the game more interesting, the starting locations of the musketeers can be changed. For example, if they start at a1, a2 and b2, enemy's job becomes much more difficult.

I've stored the optimal outcome for every position in a database. Using this, it is easy to play "optimally": simply choose the move that gives you the best result. (A natural definition of "best result" is given by the following rules: winning is better than losing; winning quickly is better than winning slowly; losing slowly is better than losing quickly.) This is exactly what the computer opponent does and it works very well when it is in a winning position. To add variety to the game, when there are several equally good moves it picks one of them randomly.

When the computer is in a lost position, however, this approach isn't very good -- especially when the computer is the enemy. It doesn't try to trick the musketeers to make mistakes, but just plays meaninglessly until it has no pieces left.

There are 25 squares and always exactly 3 musketeers. They can be in C(25,3) = 2,300 different positions. There are 25 - 3 = 22 squares left for the enemy pieces, and since each one of them can be in one of two states (unoccupied or enemy piece), they have 2^22 = 4,194,304 combinations. It can be either player's turn, so the total number of positions is 2,300 * 4,194,304 * 2 = **19,293,798,400**. Compared to games like chess and Go, this is a tiny number.

Many positions are rotations or reflections of each other. Of the 2,300 combinations for musketeers, only 319 are unique. Taking advantage of this, the number of positions we need to store can be reduced to just 319 * 4,194,304 * 2 = **2,675,965,952**. This could be brought down some more if we also considered the symmetries of enemy pieces, but it seems difficult to implement efficiently and the savings would not be very big.

Only about 20% of all positions can be reached from the official start position. But solving the unreachable ones as well makes it possible to experiment with different start positions.