Game Gomoku (tic-tac-toe, 5 in a row)

Reading the publications on Habré, I found a couple of articles about the algorithms of the Gomoku game: this one and this one . In the first article, various solutions are analyzed, but there is no implementation in the form of a game, in the second, there is a game, but the computer is “weak”. I decided to make my own version of the gomoku game with blackjack a fairly strong computer game. Publication of what happened in the end. For those who love to immediately fight - the game itself .

First I want to decide on the main points. First, there are many varieties of gomoku game, I stopped at this option: the playing field is 15x15, the crosses go first, the one who first builds 5 in a row wins. Secondly, for simplicity I will call the game algorithm for calculating progress by computer AI.

AI theory

shebeko in his article considered various algorithms AI. It is clear that with a simple enumeration of all variants of moves, while deepening for several moves, the number of required calculations goes off scale. Therefore, it is necessary to implement some algorithm smarter brute force in the forehead.

Reading his article, I thought about the phrase: "Gomoku is a divergent game with complete information and sudden death." Chess is given as an example of another game with sudden death. In my understanding, there is a huge difference between chess and Homoku: one move in chess can drastically change the balance of forces. In chess, pieces can go far and affect a multitude of cells. A queen or a rook can potentially attack any cell of the field in 1 move, i.e. in 1 move, you can put so that any particular cell will be attacked (if the lines of progress and attacks are free). In Gomoku, there is no such effect; one figure (a “stone” - a cross or a zero) can influence only 5 neighboring cells in each direction. This is the first prerequisite to my AI algorithm.
')
The second important assumption is that there are “endgames” in Gomoku - patterns that lead to victory. Remember Tarantino's rhetorical question: “How long does a person count to 600?” Similarly, to build a winning line of 5 pieces, you first need to build a line of 4 (in general: out of 5 with 1 missing from the edge (line of 4) or in the middle ), on the other - no way. Continuing the argument, we obtain that a triple is necessary for 4, and a triple for a triple.

I assumed that such patterns of moves is something analogous to the calculation of moves in depth, since The moves are local (they have a relatively small radius of influence, unlike chess, for example). So, you can simply iterate through all possible templates for each potential move. This is the second half of the AI ​​algorithm.

It remains to determine the potential moves - those cells of the field in which you can put a figure. In general, potential moves are all empty (unoccupied) board cells. Given that the moves are local, we don’t need all the cells, we can only consider the ones nearest the pieces that are already on the board. This is the first half of the AI ​​algorithm.

AI algorithm

1. Identify potential moves

Since influence of figures locally, it makes no sense to identify potential moves each time anew. You can simply accumulate them.
- Special situation: if at the beginning of the game the computer goes first - the move is carried out in a pre-installed cell - the center of the board (the array of potential moves consists of 1 cell).
- Later, after the user's move or AI, the fields separated by 2 cells from the move cell (adjacent and adjacent to neighboring) are added to the array of potential moves, and the cell into which the move is completed is removed from this array.

2. The calculation of the importance of each cell potential moves

For each cell from the array of potential moves:
1) 4 lines of 9 cells are collected in the middle of which the selected cell itself (2 diagonal, vertical, horizontal)
2) each line is compared with all available templates. When a cell enters the pattern, its significance increases by the weight of this pattern. If there is a possibility to put a “plug” in the cage, then its weight will be 2 times larger (it will be summed up from the weights of the templates of two lines).

3. Select the cells with the maximum importance

The calculation of the weights will be carried out separately for the attack (based on the AI ​​figures) and protection (comparison of lines from the opponent's figures with the same patterns), then they are summarized. And the cell with the maximum weight is the best move in terms of AI.

Possible AI improvements

The first improvement is the addition of templates that I missed :)
The second is the implementation of the calculation algorithm for at least a couple of moves ahead in order to identify potential forks and a series of winning moves in the future. This is, by the way, the main way I manage to beat AI - creating a series of moves in which AI is forced to close 4 in order not to lose (it essentially has no alternative to the move) and as a result of this series of moves a fork is made of two prefinal lines (for example, two quadruples), so bury them in one move is not possible.

Implementation of the game

The game is written in pure JavaScript (without jQuery frameworks). The graphical interface of the game is implemented on Canvas.

Result

The game itself , the source code for github (MIT).

Thanks for attention. I hope you enjoyed reading and playing, as I realized :)

PS A small request, if you win easily - please attach a screenshot of the game and the moves (from the console logs) to analyze and improve the algorithm.

Update 1

1. By 10% increased the importance of scales for the attack. Now the attack for AI is preferable to protection, all other things being equal. For example, if AI and user have 4k, then AI will prefer to win.

2. Changed the values ​​of scales by patterns. With a clearer balance weights, you can achieve a better game AI.
The weights for the templates are now:
99999 - xxxxx - five in a row (final winning line)
7000 - _xxxx_ - the open four
4000 - _xxxx - a four-closed four (two such fours are preferable to one open, perhaps a “more interesting game” will be)
2000 - _x_xxx, _xx_xx, _xxx_x - a half-closed four with a gap (2 such fours are equal to one open foursome and “preferable” to an open three; but if only 1 such four, then an open three is preferable)
3000 - _xxx_ - open triple
1500 - _xxx - half-closed triple
800 - _xx_x, _x_xx - a half-closed triple with a gap
200 - _xx_ open deuce
Also, small weights (from 1 to 20-30) are around all the moves to create a “small randomness of the move”.