General Description

Chinese chess is a Chess-like strategy board game for 2 players. The Chinese Chess is played on a 10x9 board with 64 squares. A river separates the board into two opposing sides, the red side and the black side. There are also diagonal lines which specifies the paths certain pieces have to follow and the boundaries for certain pieces. Pieces can only be placed on line intersections, but they do not necessarily have to follow the line to move.

 

The objective of the game is to capture the "General(將/帥)" of the other player. Like chess, different pieces have different move restrictions. For example, the Cannon(砲/炮) can move horizontally or vertically, but must jump another piece to capture. The middle area of the board, called river, also restricts the movements of some pieces on one side. All pieces can move within their restrictions. Each movement may result in the capture of the other side’s piece if capturing and moving restrictions are obeyed.

​

We successfully implemented a Chinese Chess game and an AI for playing the game.

​

Minimax Search with Alpha-beta Pruning

We implemented a depth-limited minimax search algorithm with alpha-beta pruning.

​

Since there are as many as 184 possible moves in Chinese Chess at one point, the game tree gets very large very quickly. Through our play testing during development, we settled on the depth of 3 because it is sophisticated enough to make a human player feel pressured, while not taking too long to determine a move.

​

We also implemented a heuristic function based on the strength of the piece and the position of the piece. This is because in Chinese Chess, not only do the pieces have different strengths, the positions of the pieces is also a very important metric, as some positions limits the power of certain pieces, while others enhance them. For example, a chariot is more powerful when it is in open spaces than in corners. The heuristic function computes the weighted sum of all the pieces on the board. The weight of each piece is assigned based on the strength and the position of the piece.

Genetic Algorithm

We implemented Genetic Algorithm to improve the piece strength and position values. In normal genetic algorithm, there need to be two things, a genetic representation of the states, and a fitness function to evaluate the states. We created two versions of the genetic algorithm, one for the strengths of the pieces, and the other for position values of a piece.

​

Since we are trying to improve the weights of the pieces so that the minimax algorithm can perform better, we decided to define a genetic state to be a better fit if the AI using this genetic state can beat another AI using another genetic state. This is a very rough estimate of the fitness of states, but our idea is that we would let the two AI play against each other, and choose the better of the genetic state to place in our "genetic pool".

EVALUATION

We evaluated our AI implementation on the following:

• Computation cost

• Chance of Winning against human players 

• Chance of Winning against existing AIs

​

​

​

Click this link for full report.

​