As I wrote checkers

Prehistory

It so happened that my first more or less serious project related to programming was the implementation of drafts for “Step into the Future”. Unfortunately, I didn’t manage to finish it to the end, because after a while the concept of the project changed dramatically. Despite this, the program was almost ready and it was even possible to play with it, besides, the process of writing it was very interesting, so I decided to share those ideas and algorithms that I managed to come up with.

Rules of the game

• The game is played on a board of 8x8 cells, only on black cells.
• Checkers at the beginning of the game occupy the first three rows on each side
• You can beat an arbitrary number of checkers in any direction.
• Simple checkers go only forward.
• A simple checker can cut back
• The lady goes to any number of fields in any direction.
• The one who has no pieces, or moves loses
• The checker is removed from the field after the battle (you can paraphrase like this: one checker cannot be cut down twice in one move)
• Beat necessarily
• The checker turns into a queen, reaching the eighth (for white) or the first (for black) line of the board
• If a saber passes through the ladies field during a battle, then it turns into a lady and the next battles (if possible) are performed like a lady

')

Implementation

First you need to determine how our board will be stored in memory. The best solution, in my opinion, is an array of 32 objects, each of which has a set of methods and properties. Properties store all possible information about the cell, for example:

• name: a1 // Cell name on real board
• color: 1 // Color checkers, 1 - white, 2 - black, 0 - cell is empty
• queen: false // Is the checker lady
• border: false // whether the field is highlighted
• doubleWay: false
• goldWay: true // these two fields will be explained later

Of course, these are not all the necessary properties, but I don’t see the point of citing everything. As for the methods, they are few and they perform simple actions such as changing the queen, color and other fields, and then update the image. Thus, during a fight, functions will be called up for “cleansing” the cell with which the battle is taking place and that cell on which the cut checker is standing, as well as for drawing the checkers on the field where the battle takes place.

However, how to determine whether to chop or not? To do this, before each move the board is scanned, checking the fulfillment of several conditions, the fulfillment of which means that you need to hit But in order to do this, it will be necessary to break the boards on the diagonal, since the battle takes place precisely on them (this, by the way, is also necessary for ordinary moves).

• GoldWay: a1, b2, c3, d4, e5, f6, g7, h8 // The so-called “Big Road”
• DoubleWayG1A7: g1, f2, e3, d4, c5, b6, a7 // Twins
• DoubleWayH2B8: h2, g3, f4, e5, d6, c7, b8
• TripleWayC1A3: c1, b2, a3 // Tees
• TripleWayC1H6: c1, d2, e3, f4, g5, h6
• TripleWayH6F8: h6, g7, f8
• TripleWayA3F8: a3, b4, c5, d6, e7, f8
• UltraWayA5D8: a5, b6, c7, d8 // jambs
• UltraWayH4D8: h4, g5, f6, e7, d8
• UltraWayE1A5: e1, d2, c3, b4, a5
• UltraWayE1H4: e1, f2, g3, h4

The breakdown on the diagonal is exactly that. Please note that all diagonals are listed bottom-up. This is done for the convenience of the programmer, although it is not mandatory. The properties of the objects list all these diagonals, and those diagonals on which the cell lies are true, on the rest - false.

Thus, I created several arrays, each of which contained references to objects corresponding to cells that are on the diagonal, to which the array corresponds. This allows us to make the checkers move.
I will not paint the algorithm in detail, I will only describe in general terms: if the following situation occurs on any of the diagonals:
"Checker (1) - checker (2) is an empty field" (where 1 and 2 are players and player 1 is making the move), or "empty field is a checker (2) - checker (1)" [for fighting in both side], then assign the property of the first cell, which is responsible for information about whether it should chop, one. In addition, assign a common variable (let's call it jumpInd), which is responsible for the battles, one. This is necessary because a situation may arise in which the player will have a choice of which of the checkers to chop.

When a player clicks on a checker, the jumpInd condition is checked first. If jumpInd = 1, and the checker that the player clicked on should not hit, then nothing happens, or a message is displayed indicating that the player must chop. If jumpInd = 0, then it is checked whether this checker can make a move. The check is performed in the same way as a battle check, only slightly shorter: if the situation is found on one of the diagonals: “checker (1) is an empty field (for white) and empty field is a checker (1)” [for black], then highlight this field. If jumpInd = 1 and the player chose the checker with which this fight will be performed, then the cell on which the fight will be performed is also highlighted. You can highlight and checker, which will be made a move. These actions are only for the convenience of the player. The next action a player can click on another checker and then the algorithm will start over, or it can click on the highlighted field and make a move in this way.



After the player has clicked on the highlighted field, all methods that “clean up the tails” and change the colors of the cells are performed. If jumpInd was equal to zero, then we pass the move to the second player. If jumpInd = 1, then you need to check whether the player can cut down something else. If yes, then highlight the fields to which he can get as a result of the battle. Do not forget to check whether the checker has become a woman. If so, the battle will be made already by the ladies rules. If there is no fight at all, then again we will check for the transformation into a woman, we will drop jumpInd and pass the turn.

We managed to implement simple movements of checkers, but this is only the beginning. Now we have to realize the movement of the ladies. Here, everything is somewhat more difficult to implement, at least I am fairly sweating with them, although the essence is similar.

For each diagonal, conditions are checked in both directions, but I will write only in one, because the essence is only in the order of checks.
Check for a move: if a situation occurs: “A lady is an empty field”, then highlight this cell and check the next one. Perform until the diagonal is over, or until the checker (woman) of the opposite color is encountered.
Check for a fight: if the situation occurs: "queen - z empty fields - checker (queen) of the opposite color - n empty fields" (z> = 0, n> 0), then highlight all n empty fields after the opponent's checkers (if more one opponent's piece, then stop) and do all those manipulations with variables that store information about fights, as in the case of a regular piece. After the player clicks on the highlighted cell, you should check the possibility of another fight in any direction except the one from which we came. The implementation of all these checks and conditions took me a lot of time and space, but perhaps I just missed something and could be implemented more and more beautifully.



And one more very important thing: do not forget about the following condition: the sword cannot be cut down twice. This means that if the checker on the diagonal, on which you are now, has already been cut down, then the course ends (for the usual checkers in the field where it now stands, and for the queen on any of the empty fields up to this already cut down opponent’s checkers ). As an option: you can store the addresses of the already-cut checkers in an array, zeroing it only when passing a turn. (actually, I did something like this)


(The black lady is obliged to chop in the following way: h4: e1: c3: e5 and stop, since the g3 checker is still on the board. After that, the white ones cut to queens and win)

This whole algorithm can be described very briefly with the following block diagram:

First click:


Second click:


To make the program understand where the first click and where the second is, we create a logical variable, false = first click, true = second click.

In general, the implementation of the rules of the game ends there. Everything looks relatively simple, but when transferring the algorithm to the code, many small problems and difficulties arise, due to which the code swells and swells everything. The very principle of the implementation of the board, chosen by me, is to blame for this, but this is the best that came to mind during those two or three weeks (and those with tangible interruptions), since all actions are as clear as possible, it is almost impossible to get confused, and the code is read easy enough. I believe that sacrificing for the sake of this concise code is permissible.

Artificial Intelligence

However, our adventures do not end there. It's great that we taught the checkers to move, but who are we going to play with? We need to create artificial intelligence for the game. Unfortunately, I did not succeed in fully implementing it, because due to poor optimization, the program started to hang when rendering more than 5-6 moves (about 20-25 thousand positions). When implementing, I used the book Programming Chess and Other Logic Games and recommend it to anyone who is interested in the problem of AI in logic games. I stopped at the improved alpha-beta cut-off algorithm, but I will not describe it here, because it has already been described many times on Habré before me, for example:

The use of machine learning in building AI for the game of Japanese chess (shogi)
Minimax on the example of the game in the hare and wolves
other.

Unfortunately, the concept of my project for the contest, as I said at the beginning, has changed - so the AI ​​remained unfinished and was thrown into the back box. Some principles for assessing the position that I managed to formulate - too. I could bring them here, but they are not of particular interest because of their specificity. If someone is interested, I can write a separate article about the evaluation function and the cut-off algorithm. Since the whole thing happened half a year ago and I wrote the article mainly from memory, inaccuracies or inconsistencies could arise somewhere, I would be glad if you point me to them in the comments. If you need to paint something in more detail, then contact us there. Thanks for attention.