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 !