Rules of the game
- The game is played on an 8×8 board, only on black cells
- Checkers at the beginning of the game occupy the first three rows on each side
- You can hit any number of checkers in any direction
- Checkers move only forward
- A simple checker can cut backwards
- Queen moves any number of squares in any direction
- The loser is the one who has no pieces or moves left
- Checker is removed from the field after the battle (can be paraphrased as: one checker cannot be cut down twice in one move)
- It is obligatory to hit
- A checker turns into a king when it reaches the eighth (for White) or the first (for Black) line of the board
- If during the capturing the checker passes through the kings row it becomes a king and subsequent fights (if they are possible) will be performed as a king.
Implementing
First we need to define how our board will be stored in memory. The optimal solution, in my opinion, is an array of 32 objects, each with a set of methods and properties. Properties store all possible information about the cell, for example:
name: a1 //the name of the square on the real board.
color: 1 //the color of the checker, 1 is white, 2 is black, 0 is empty.
queen: false //Does the checker have a king?
border: false //is the box illuminated?
doubleWay: false
goldWay: true //these two fields will be explained a little later.
Of course, these are not all required properties, but I don’t see the point in listing them all. As for the methods, they are few and perform simple actions like changing the queen, color and other fields, and then update the image. So, in combat, functions will be called to “clear” the square where the fight is taking place and the square where the cut down checker is, as well as to draw the checker on the field where the fight is taking place.
However, how does one determine whether a checker is to be cut or not? To do this, the board is scanned before each move, checking for several conditions, the fulfillment of which means to hit. But in order to do that, you have to divide the board diagonally, since that’s where the combat takes place (which, by the way, is also needed for normal moves).
GoldWay: a1, b2, c3, d4, e5, f6, g7, h8 //The so-called “Big Road”.
DoubleWayG1A7: g1, f2, e3, d4, c5, b6, a7 //DoubleWay
DoubleWayH2B8: h2, g3, f4, e5, d6, c7, b8
TripleWayC1A3: c1, b2, a3 //Triples
TripleWayC1H6: c1, d2, e3, f4, g5, h6
TripleWayH6F8: h6, g7, f8
TripleWayA3F8: a3, b4, c5, d6, e7, f8
UltraWayA5D8: a5, b6, c7, d8
UltraWayH4D8: h4, g5, f6, e7, d8
UltraWayE1A5: e1, d2, c3, b4, a5
UltraWayE1H4: e1, f2, g3, h4
The breakdown into diagonals is done in this way. Note that all diagonals are listed from bottom to top. This is done for the programmer’s convenience, although it is not obligatory. All these diagonals are listed in the object properties, and those diagonals that have a cell on them have true, the others have false.
So I created several arrays, each containing references to objects that correspond to the cells that are on the diagonal the array corresponds to. This allows us to make the checkers move.
I won’t describe the algorithm in detail, but only in general terms: if the following situation occurs on any of the diagonals:
“checker(1) – checker(2) – empty field” (where 1 and 2 are players and the move is made by player 1), or “empty field – checker(2) – checker(1)” [for a fight in both directions], then assign to the first cell property, responsible for information, whether it should cut, a one. In addition, assign a one to some general variable (let’s call it jumpInd) that is responsible for combat. This is necessary because there may be a situation where the player has a choice of which checker to hack.
When a player clicks on any checker the first thing he does is check the condition jumpInd. If jumpInd=1 and the checker the player clicked should not hit, nothing happens or a message is displayed saying that the player must hit. If jumpInd=0, it checks if this checker can make a move.
The check is similar to the check for combat, only slightly shorter: if on one of the diagonals there is a situation:
“checker(1) – empty field (for white) and empty field – checker(1)” [for black], then illuminate that field. If jumpInd=1 and the player chose a checker, which will be used for this battle, then the square, which will be used for the battle, is also highlighted.
It is also possible to highlight the checker, which will be used to make the move. These actions are only for the convenience of the player. The next action the player can click on another checker and then the algorithm will start again, or he can click on the highlighted field and thus make his move.
After the player has clicked on the highlighted field, all methods that “clean up tails” and change cell colors are executed. If jumpInd was zero, we pass the turn to the second player. If jumpInd=1, then we need to check if the player can cut down anything else. If yes, then highlight the fields he can get to as a result of combat. Don’t forget to check if the checker has become a king. If yes, then the combat will be carried out by the rules of the game. If there is no combat at all, we will check again for transformation into a king, zero out jumpInd and pass the turn.
We have managed to implement simple checker moves, but that is just the beginning. Now we have to implement a queen move. This is a bit more complicated to implement, at least I have worked with them a lot, although the idea is similar.
For each diagonal, we check both ways, but I’ll only write one way, because the point is only in the order of the checks.
Check for a move: if there is a situation: “queen – empty field”, then illuminate this cell and check the next one. Continue until the diagonal is over, or until a checker (king) of the opposite color is encountered.
Checking for the battle: if the situation “king – z empty squares – opposite color checker(-s) – n empty squares” occurs (z>=0, n>0) then illuminate all n empty squares after the opponent’s piece (if one more enemy piece occurs then stop) and do all those manipulations with variables storing information about battles as in the case with the usual checker.
After the player clicks on the highlighted square, he should check the possibility of another battle in any direction other than the one we came from. Implementing all these checks and conditions took me a lot of time and space, but maybe I just missed something and could have implemented everything shorter and prettier.
And one more very important thing: do not forget about the following condition: a checker cannot be cut down twice. This means that if a checker on the diagonal, which you are now on, has already been cut down, then the turn ends (for a regular checker on the field where it stands now, and for a king on any of the empty fields up to this already cut down opponent’s checker). As an alternative: you could store the addresses of already-cutdown checkers in an array of some kind, zeroing it out only when passing a move. (in fact, that’s roughly what I did).
To make the program understand where the first click and where the second click are, we create a logical variable, false = first click, true = second click.
That’s pretty much the end of the implementation of the game rules. Everything looks relatively uncomplicated, but when transferring the algorithm into the code, there are a lot of little problems and difficulties, that make the code swell and swell.
Blame it on the principle of implementation of the board, which I’ve chosen, but it’s the best of what came to mind during those two or three weeks (and those with noticeable interruptions), because all the actions are maximally clear, it’s almost impossible to get confused, and the code is easy enough to read. I think it’s acceptable to sacrifice brevity of code for the sake of it.
Artificial Intelligence
However, our adventures don’t end here. It’s great that we have taught checkers to move, but who are we going to play with? We need to create artificial intelligence for the game. Unfortunately, I failed to fully implement it, because due to poor optimization the program began to hang when calculating more than 5-6 moves (about 20-25 thousand positions).
For the implementation I used the book Programming Chess and Other Logic Games and recommend it for everyone who is interested in the problem of AI in the logic games. I settled on the improved “alpha-beta cutoff” algorithm, but I will not describe it here, because it has already been described many times on Habra, for example:
Unfortunately, the concept of my project for the contest, as I said in the beginning, has changed – so the AI was left unfinished and was placed in a distant drawer. Some of the principles of position evaluation that I managed to formulate – too. I could cite them here, but they are of little interest because of their specificity.
If anyone is interested, I can write a separate article on the evaluation function and cutoff algorithm. Since all this happened half a year ago and I wrote this article mainly from memory, I may have some discrepancies or inconsistencies – I will be happy if you tell me about them in comments. If there is anything that needs to be described in more detail, feel free to contact me there as well. Thank you for your attention.
