Monday, June 10, 2013

Chinese checkers best opening moves

If you are a chinese checkers player, I am sure you already ask yourself what is the best opening moves you can do.

Trying to answer this question, I wrote an algorithm that found what we could call the best 5 starting moves !

Here are the moves:



To better understand why these moves are interesting, let's see how my algorithm work.

The algorithm just focus on the first player moves and his basis is a depth first search with maximum depth 5. It means that from the starting board configuration, the algorithm tries all sequences of 5 moves for the first player (green), then keeps the best among all. I used the depth first search and not a breadth first search because it allows to manage more easily the memory by cuting the uninteresting branchs all along the computation.

So, why a depth search of 5 ? The number is obviously arbitrary, but it leads to a decent computing time (1 hour on my machine) and it allows a pawn to reach the center of the board. It means that with depths higher than 5, our pawns will certainly meet an opponent's pawn. So in this case we just can't ignore what the opponent moves and we are out of what we consider as "opening moves".

Then, why can I consider these 5 moves as the best ? In fact it depends on what we consider as "best". So it depends on what method we use to compare the configurations in order to keep what we consider as the "best". In my algorithm, I focus only on the distances from our pawns to the goal. More precisely, I consider the sum of the cartesian distances from our pawns to the average of the target positions. Less this sum is, more I consider the configuration is good.

An illustration will help to understand :
The algorithm keeps the configuration that minimize the sum of the purple lines lengths after 5 moves

The question now I ask myself is the following : is there any strategical considerations we could add to have a better result ?

1 comment:

  1. I think it's important to realize that turn order and your opponents opening sequence should affect your move sequence significantly.

    In the illustration above each side has made it to move 4 of the 5 move sequence you've laid out, but the 5th move will definitely be different for both sides. Likely whichever side gets to move next will have a great advantage simply by extending the intended 5th move's jump by 2 (not by 3 though). This allows them to achieve a significant depth advantage while also blocking their opponent from taking the same path. Additionally they can continue to follow this path to increase the depth advantage unless the other side pushes a pawn forward by 1 without jumping. Ultimately the exchange would result in the player who moves 2nd to be at a great disadvantage.

    ReplyDelete