19
\$\begingroup\$

In Chess, it's possible for the game to end after 4 moves (2 each) with a Fool's Mate.

Your goal is to find the Fool's Mate of Halma: the 2-player game of Halma that minimises the number of turns played.

There are over 1056 board states, and I've seen the branching factor surpass 1000, so chances are no one will find the optimal solution. Instead, you're trying to find the best solution you can.

You should submit a list of moves, and any code you used to generate those moves.

Explanation of the Game

Halma is similar to Chinese Checkers, but played on a 16*16 square board.

Initially, the board looks like this:

Starting Board

The goal of the game is to move all your pieces to the starting positions of your opponent's pieces.

On a player's turn, he/she may:

  • Pass the turn

  • Move one of his/her pieces to an adjacent empty space. Adjacent spaces include diagonals.

  • Take one of his/her pieces and do the following any number of times: Jump the piece over an adjacent piece, landing it on the space opposite the piece jumped over.

Here's an example to illustrate the 2nd type of move.

Jumps

Rules

Submit a list of legal moves which result in the game ending.

Submit any code you used to generate the list.

If you obtain a better result from someone else's code, post the result in a comment or edit their post with the new results.

Each move must be either None to pass the turn, or (x1,y1,x2,y2) to move a piece, where (x1,y1) are the coordinates of the piece to move and (x2,y2) are the destination of that piece (for jump moves, ignore intermediate coordinates). The coordinates start at (0,0) at the top left corner. x-coordinates increase to the right, y-coordinates increase downward. Moves should be separated by newlines.

You can use this python script to verify your moves. Use python halma_verify.py < file to verify moves in file.

Shortest list wins.

\$\endgroup\$
17
\$\begingroup\$

The shortest game of halma is 49 moves

49 move solution

Proof there is no 48-move solution

Code used for this solution

The code now supports pass

Notice that the 47 move solution in the paper is for the army transfer problem, not for the shortest game of halma

I'll hopefully get to doing a proper writeup this weekend

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.