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 ?

If you want to experiment by yourself, you can find the complete Actionscript 3 source of the project on GitHub:

Chinese Checkers lib on GitHub

It contains everything you need to build games (logic and display), including AI.


7 comments:

  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
  2. Where do I play this game? Need address?

    ReplyDelete
    Replies
    1. You can contact me at email address:
      denidowi@yahoo.com
      for further information about playing Chinese checkers

      Delete
  3. Your Algorithum does not follow the rules of Chinese Checkers.
    In move 3, the 1st hop and 3rd hop are illegal.
    In move 5, the 2nd hop and 4th hop are illegal.

    ReplyDelete
    Replies
    1. The moves ar completely legal and follow the rules.

      Please learn how to play or look more carefully.

      Delete
    2. Sorry Anon, you are WRONG !

      Delete
  4. These moves are v good - it is the same opening I have been using for 55 years - Totally and unequivocally, undefeated over all that time, whether against man or machine.
    In fact, I classify myself the world's best player ... you are most welcome to challenge me if you wish, provided I can record it and place on YouTube. I am still at denidowi@yahoo.com

    ReplyDelete