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.

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.

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

ReplyDeleteIn 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.

Where do I play this game? Need address?

ReplyDeleteYou can contact me at email address:

Deletedenidowi@yahoo.com

for further information about playing Chinese checkers

Your Algorithum does not follow the rules of Chinese Checkers.

ReplyDeleteIn move 3, the 1st hop and 3rd hop are illegal.

In move 5, the 2nd hop and 4th hop are illegal.

The moves ar completely legal and follow the rules.

DeletePlease learn how to play or look more carefully.

Sorry Anon, you are WRONG !

DeleteThese 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.

ReplyDeleteIn 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

This comment has been removed by the author.

ReplyDeletehow did you present the distances in the program? in moves number or like points in Math?

ReplyDeleteDistance are simply cartesian distances, from (x,y) to (x',y')

Deleteoh...because i thought that maybe its beter with the moves...i'm not sure you see chinese checkers is my programing project and i'm a little stuck with the AI

DeleteYou can try with other methods, but as an heuristic, choose the one being as fast as possible.

Deleteok, thanks for answering. much appreciated

DeleteThis comment has been removed by a blog administrator.

ReplyDeleteThis comment has been removed by a blog administrator.

ReplyDelete