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

Reading publications on Habré, I found a couple of articles about the homoku game algorithms: this and this . In the first article, various options for solving the problem are analyzed, but there is no implementation in the form of a game, in the second - there is a game, but the computer "plays" rather poorly. I decided to make my version of the homoku game with blackjack a fairly strong computer game. The publication of what happened in the end. For those who like to fight immediately, the game itself .

First, I want to decide on the main points. Firstly, there are many varietiesGomoku games, I settled on 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 the course by a computer AI.

AI Theory

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

Reading his article, I thought about the phrase: "Gomoku is a diverging game with full information and sudden death." As an example of another game with sudden death, chess is given. In my understanding, there is a huge difference between chess and homoku: a single move in chess can dramatically change the balance of power. In chess, pieces can go far and influence many cells. The queen or rook can potentially attack any square cell in 1 turn, i.e. in 1 move, you can set so that any specific cell will be attacked (if the lines of movement and attack are free). There is no such effect in homoku, one figure (“stone” - a cross or a toe) can affect only 5 neighboring cells in each direction. This is the first prerequisite for my AI algorithm.

The second important assumption is that there are “endgames” in homoku — templates that lead to victory. Remember the Tarantino rhetorical question: “How long does a person count to 600?” Similarly, in order to build a winning line of 5 figures, you must first build a line of 4 (in general: from 5 with 1 skipped from the edge (line of 4) or in the middle ), in another way. Continuing the argument, we get that for 4 you need a three, for a three - a two.

I suggested that such move patterns are something similar to calculating the moves in depth, because moves are local (have a relatively small radius of influence, unlike chess, for example). So, you can simply sort through all the possible options for 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 piece. In general, potential moves are all empty (unoccupied) cells of the board. Given that the moves are local, then we do not need all the cells, we can only consider the ones closest to the pieces already on the board. This is the first half of the AI ​​algorithm.

AI Algorithm

1. Identification of potential moves

Because Since the influence of the pieces is local, it makes no sense to determine potential moves each time anew. You can simply accumulate them.
- A special situation: if at the beginning of the game the computer goes first - the move is made to the pre-installed cell - the center of the board (the array of potential moves consists of 1 cell).
- In the future, after a user or AI move, fields are added to the array of potential moves that are 2 cells away from the move cell (adjacent and neighboring to neighboring ones), and the cell into which the move is made is deleted from this array.

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

For each cell from an 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 patterns. When a cell enters a template, its significance increases by the weight of this template. If it is possible to put a “plug” in the cage, then its weight will be 2 times more (it will be summed from the weights of the patterns of two lines).

3. Selecting a cell with maximum importance

Calculation of weights will be carried out separately for attack (based on AI figures) and defense (comparison of lines from the opponent’s figures with the same patterns), then they are summarized. And a cell with 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 an algorithm for calculating at least a couple of moves ahead in order to identify potential “forks” and a series of winning moves in the future. This, by the way, is the main way I manage to beat AI - by creating a series of moves in which AI is forced to close 4 so as not to lose (it essentially has no alternative to the move) and as a result of this series of moves a fork is created from two prefinal lines (for example, two fours), so burying them in one move is not possible.

Game implementation

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

Result

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

Thanks for attention. I hope you were also pleased to read and play, as I implement it :)

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

Update 1

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

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