This is a post about a small game "Tic-Tac-Toe", which was written in order to replenish the experience of programming on JS. Canvas and DojoBase are used here. The library is used to work with events and to find elements by id (this is very convenient). Sanvas is used to draw the playing field.
The game itself
The rules of "tic-tac-toe" of this implementation are simple: you need to collect a series of five elements (in any direction) before the enemy. The number of moves is the same, that is, if the toes (they go first) have collected a row, and the crosses have a line of four elements, then the round does not end. Yes, in this implementation one game consists of several rounds. The game ends when there are no free cells left on the field. The winner is the one who won more rounds. Cells that were used in previous rounds are flooded and become inactive. The very same field resolution is set depending on the resolution of the browser window.
Creating AI (hereinafter, under AI, a complex of brute-force algorithms is used)
Here the most interesting, of course, is AI. I “taught” him to walk more or less correctly in several stages ... First, AI put his badge on the first free cell that he found. Having tested a little, it became clear to me that this is not interesting. It works, but something is wrong here. Thinking that a better case than this, I screwed rand. After that, it became a bit more fun, but still - not interesting.
So, okay, let him first find all the cells in which you can (and should) go. That is, something similar (highlighted in blue).
These "necessary" cells are determined by the following algorithm "Here all the information about the playing field (what is happening on it) is contained in a two-dimensional global array, the values ​​of the elements of which show the state of the cells. A complete set of directions is used, that is, all adjacent cells with the given one are checked. The array_2 records the search results for the "necessary" cells.
So, determined and what to do with them? It is possible to place an element randomly in any of these cells. And you can assign each cell assessment and on the basis of them to choose the best option, and then use it. It sounds good. But first you need to solve another issue.
When AI moves to zero, a situation may arise that there simply will not be any “needed” cells. For example, during the first round. Now we need to come up with an algorithm for finding the best option in this situation (or when there are no free cells for crosses or zeros). And I think it's good to go where the most spacious.
Therefore, such an algorithm is implemented here.Intermediate data, i.e., rows of free cells (vertical and horizontal) in a specific format, are recorded in the cutout. The result of the work of this function will be recorded in the object of the coordinate. If a segment is the diameter of an “empty” square, then this means that its central point (cell) is the center of the square of free cells, and its sides are equal to this segment.
And the time has come for an algorithm that chooses a move based on estimates.
Here he is
The input of this algorithm is an array with the "necessary" points. An array of m_otsenok, auxiliary and vessels are recorded cell assessments. Here, as in the previous example, a complete search of all directions around the cell is used. Evaluation is carried out by two parameters: the type of stroke (blocking or complementing its row) and the length of the line of elements (1, 2, 3 or 4 cells). The appointment is a special function where you can change the criteria. These estimates (criteria) are summarized in all directions for a given cell.
Conclusion
Well, in the end, I got a little game with AI, which can beat beginners. I easily win it, not “dry”, of course, but still. It is worth noting that when you play for the “crosses”, it’s like a lower level of difficulty, but for the “zeroes” it’s a little more difficult to play.
Multi-round mode made the task more interesting. For example, here the AI ​​must find the optimal cell for the first move. There was also a problem with the fact that single empty cells (in which it was meaningless to walk), it was also necessary to “shade” somehow. But in the end I coped with it.