Take the 2-minute tour ×
Programming Puzzles & Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It's 100% free, no registration required.

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.

share|improve this question
4  
some technical discussion of moves, and a solution in 47 moves: arxiv.org/pdf/0803.1245.pdf –  Sean Cheshire Feb 18 '13 at 21:00
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.