19
2
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:
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.
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.
cardboard_box
Posted 2013-02-16T18:46:57.013
Reputation: 5 150
6
some technical discussion of moves, and a solution in 47 moves: http://arxiv.org/pdf/0803.1245.pdf
– SeanC – 2013-02-18T21:00:21.653