Game description - Checkers for mobile and stationary devices
Below is a brief outline of the game of checkers which I used while creating my game:
- a piece may move one space diagonally forward to a free square,
- a piece can capture forward as well as backward,
- a king may move diagonally across any number of unoccupied squares forward or backward and during the same move it can capture its opponent,
- capturing is compulsory,
- the winner is the player who captures or blocks all the opponent's pieces,
- in case of triple repetition of the player's and the opponent's move there is a draw.
The examples of capturing by a piece and a king is shown on the pictures below. Possible moves of the computer are shown with a red cross.
The game has been written in a similar way to Tic Tac Toe (noughts and crosses) - see: Game descrition - advanced tic-tac-toe for mobile and stationary devices. While developing my game of checkers, I used an algorithm known as “alpha-beta pruning” in order to determine the moves of the computer. The biggest challenge for me in writing this game was accomplishing a jump by a piece or king. Below, I present a function that returns all the jumps made by pieces and kings (the function returns all the paths from the root to all the leaves and it uses recursion).
function possibleBeatsMovePath(matrixIn, inn ,enemies, pathIn, pathLen, paths) { pathIn[pathLen] = inn; pathLen++; matrixIn[inn.beat_y][inn.beat_x] = blank; var x = inn.x; var y = inn.y; var value = inn.value; if( (draftsman_black === inn.value) || (draftsman_white === inn.value) ){ var out = possibleBeatsDraftsman( matrixIn, x, y, value, enemies ); } if( (king_black === inn.value) || (king_white === inn.value) ){ var out = possibleBeatsKing( matrixIn, x, y, value, enemies, inn.beat_x, inn.beat_y ); } if( !out.length ){ var beat = []; for(var j=1; j<pathLen; j++ ){ beat.push(pathIn[j]); } if( !beat.length ){ return false; } var path = { 'x': x, 'y': y }; path.beats = []; path.beats = beat; paths.push( path ); return paths; } for (var ii in out){ paths = possibleBeatsMovePath(matrixIn, out[ii], enemies, pathIn, pathLen, paths); } return paths; }
Where functions: "possibleBeatsDraftsman" and "possibleBeatsKing" return possible jumps for x and y coordinates for pieces and kings, respectively.
The evaluating function of the board, which I called 'evaluate' is relatively simple and it is used to determine the optimal computer move. I have assumed that a player's piece has the value of 2 and the king has 12, while a computer piece is -2, and king is -12. Evaluating of the board in my game is the sum:
- sum of points of pieces and kings,
- the sum of the points of the pieces and kings that a given player captures,
- the sum of the points of the pieces and kings that a given player loses with the opposite sign.
A piece, which is in the first and the second row, and the last and penultimate one gets a larger number of points.
I have written 63 unit tests using mocha.js that checks the logic of the game. In order to call up the test checking the best move for the first board that I have shown above, you must execute the command:
./node_modules/mocha/bin/mocha -g 'getBestMatix testMatrix'
I have also written a test where the computer plays with itself. The name of that test is 'test comp vs comp'. For the first player (player1) I have set two depth of "Alpha-beta pruning" algorithm and for the second player (player2) I have changed this depth from one to twelve. Each time the second player starts the game. Below I present the result of my tests:
depth player2 | sum of points final board | evaluate final board | win |
---|---|---|---|
1 | -28 | -298 | player1 |
2 | 16 | 171 | player2 |
3 | -- | -- | repeated move |
4 | -- | -- | repeated move |
5 | 20 | 212 | player2 |
6 | 16 | 164 | player2 |
7 | 18 | 186 | player2 |
8 | 20 | 211 | player2 |
9 | 28 | 285 | player2 |
10 | 28 | 284 | player2 |
11 | 20 | 210 | player2 |
12 | 6 | 66 | player2 |
For the third and fourth depth of "Alpha-beta pruning" algorithm of the second player I was not able to determine the sum of points and the winning player, because the player's moves were repeated (every four moves) infinitely. For the increasing depth of the algorithm "Alpha-beta pruning" the second player wins and that behavior is in line with my expectations. In my opinion, it is very difficult to win with the computer at the sixth depth of algorithm, that is the third level in my game.