A simple variant of the traditional checkers game, where the program will generate a move after every user move.
An 8x8 chessboard with 12 black and 12 white pieces initially positioned as shown.
The user is side black and the program (computer) generate moves for side white. Black makes a move first.
In a single turn, the player either makes a move or a capture
Move (only diagonally forward for one step towards the opponent):
Capture (jumps forward to an open cell diagonally as shown, landing cell must be empty):
Towers: whenever a normal piece reach the furthest row, it becomes a tower and is able to make a move or capture both forward or backward (at maximum 4 possible moves). Note the cell B1:
A player wins the game if it is the opponent's turn and they cannot take action, move or capture, either because no pieces / towers are left or no legal moves or capture are possible.
This program implements the minimax algorithm to make decision on which move to take. If white is making a move, it constructs a tree of all reacheable board configurations, with a depth of 5. So the root node will be the current board configuration\n and the children nodes will be the boards of all possible moves made by white. Children nodes of these nodes will be all possible moves made by black, we keep doing\n this until reach a tree height of 5.
We calculate the 'board cost' at the leaf nodes, which is: Board Cost = b + 3B - w - 3W
Where b and w are the number of black and white pieces; B and W are the number of black and white towers. Therefore black moves would want to maximise cost while white moves would want to minimise cost. Board costs of other nodes are imputed by looking at the children nodes with max / min costs if black / white is making a move. This bottom-up imputation will eventually lead to the cost at the root node, where a decision is made (choose the board configuration that has this optimal cost).
