Chinese checkers on a spherical board

Do you like board games ? Do you like to experiment new game concepts ?

If you answered yes to one of these questions, I think you will appreciate this article. Indeed, here I offer you a variation of the chinese checkers game... on a spherical board ! This was already done for chess, but I think it is the first time for chinese checkers. So, just stop to speak now and have a game.

Choose to play against a friend on the same computer (Human VS Human), against the machine (Human VS AI), or just see the machine against herself. Then, drag the screen to navigate around the sphere and just follow instructions :

Content displayed within Unity Web Player

This project was a good opportunity for me to learn more about Unity 3D, C#, data structures and IA.

First I built the board in 3D Studio Max (from the geosphere primitive) and then I imported it into Unity. The most boring part in my C# code was to write a parser able to analyze the mesh board structure and generate automatically the core graph data structure. Indeed, it was out of question to generate the graph structure "by hand" ; I wanted a flexible solution, able to work quickly with new board designs without any long and boring new configurations. So maybe the next version of the game will offer you a large set of original boards, with some strange topologies...

Then I built my game code following a very simple MVC pattern. If you are curious about how we can apply MVC to board games, I think it will be interesting for you to look into my package structure. Maybe you could think that this is a very large package for such a simple game, but I always work in a way that allow me to extend my projects. Here my package structure is suitable to add new boards, new AI, new game modes...

• [_] chineseCheckers
• [_] controlers
• [_] ai
• AIControler
• DistanceTable
• [_] human
• HumanControler
• AbstractControler
• MoveData
• [_] data
• CellData
• DataManager
• [_] games
• AbstractGame
• AIVsAIGame
• HumanVsAIGame
• HumanVsHumanGame
• [_] gui
• [_] elements
• InGameHud
• Menu
• GameGui
• [_] navigator
• DragNavigator
• [_] parser
• BoardParser
• [_] view
• Cell3D
• CellColors
• Pawn
• View

[_] FOLDER

CLASS

Finally, I coded an AI, trying to keep it very simple and CPU-light. I will explain the algorithm in a future article, but you can see now that it is very fast (so fast that I must slow-down the run in order to keep the "AI vs AI" game comprehensible).

I hope you enjoyed the game !

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.

Chinese checkers artificial intelligence

I am currently experimenting artificial intelligence for chinese checkers. This game is very interesting, because despite very simple rules, it is not obvious to obtain a challenging AI.

So, at first I give you my list of constraints :

About the game :

• versus game : one player against one player
• the board can have any arbitrary shape (not only the classic star shape)
• any total number of pawns (but the 2 players have the same number)
• the goals positions of a player are the starting positions of the opponent
• we suppose that the pawns of a player start as a group (not disseminated)

About the AI :

• the AI must play in real time
• the AI must play in resonable time
• the AI algorithms must be not blocking (don't freeze the application because overloading the processor)

The game contraints are "weak". I chose them because I think it can be interesting to experiment some variations of the chinese checkers while keeping the rules of movement.  On the other side, the AI constraints just ensure that it is comfortably playable.

So, after some experimentations (depth search, alpha-beta, some heuristics...) I have a first interesting result. I mean that I have an AI that is playable and challenging.

If you like chinese checkers, I invite you to play a game ! Just choose your board, and start by moving a red spawn. You will notice an assistant helping you by showing the reachable positions.

The classic star board :

Small board version :

More experimental weird board :

So as previously said, the AI is interesting. But I feel not satisfied because better can be done.

I  currently use the following heuristics, inspired by my own way to play the game:

1. We only analyses our own moves. The moves of the opponent are not anticipated. It means that the algorithm don't use any form of minimax method. I tried it at first, but the time consumed was very high. And finally I really think that a good chinese checkers player don't try to anticipate the opponent's moves. So my algorithm is based on a breadth first search. Actually the tree generated has depth 3.
2. A board configuration is scored using only the sum of the distances from our pawns to the goal. It brings a really simple and fast way to compare many board configurations. That is exactly what we need when we have to choose a good move among many thousands.
3. We never play a pawn in backward direction, except near the end of the game. It is a simple way to limit the moves in consideration when building the tree. It can divide the time consumed by a factor 2.
4. If a good move is possible, we do it immediatly ; we don't wait. It is a natural balance for the 1. Because we don't anticipate the opponent's moves, we need to avoid too complex strategies, because too fragile.  It better to play a good move immediatly instead of try a better move but in 2 or 3 turns.

I think a good way to improve the AI would be to divide the game in 3 phases:

1. the beginning (the first 5 turns), when the pawns ot each players are not in interactions. This phase only needs a breadth first search, but with high depth.
2. the main, when the pawns are meeting in the center of the board. It could be interesting to switch to a minimax of low depth.
3. the end, when we need to carefully put the pawns in goal. Switch again to a breadth first search would be a good choice.

More experimentations soon !