Tic Tac Toe "Without Borders"
Tic-tac-toe ... they all played, I'm sure. The game is attractive in its simplicity, especially when you pull a watch somewhere in a lesson, a pair, and there is nothing at hand except a notebook sheet and a simple pencil. I don’t know who the first one ever thought to draw crosses and circles in 9 squares, but since then the game has not lost in demand at all, especially since the people came up with a great many of its variations.
This article is about the process of developing AI on javascript for playing one of these variations of daggers: there was a lot of material, but I diluted it with animation and pictures. In any case, at least it is worth trying to play it.
The differences of this version of the game from the original are as follows:
')
Everything is simple ... and at the same time difficult: the outcome of the game cannot be calculated in advance, as in the classic version. This "little project" took me a lot of time and nerves. I hope you will be interested.
I am forced to apologize in advance for the volume of the article and in some places not quite an intelligible statement of thought, but I did not manage to squeeze the flock without a loss in content and quality.
I recommend first to get acquainted with the result . Code
Hotkeys and commands:
You need to start with the implementation of the game itself, i.e. write an application for two players, as long as no bot. For my own purposes, I decided to use javascript + jquery + bootstrap4, although it is practically not used there, but it is better to leave it - or the table will float. There is nothing special to tell, the material on js, jquery and bootstrap on Habré is full. Let me just say that I used MVC. And in general, I will not explain absolutely all the code - there was already a lot of material.
So, the playing field was ready. You can set the figures in the cells. But the victory of any of the players was not fixed.
The game ends when one of the players puts 5 pieces in a row. “It's simple!” I thought. And he began to scan absolutely all the cells of the field: first all the horizontals, then the verticals and, finally, the diagonals.
It's a dumb way, but it worked. However, it could be significantly improved, which I did: Most of the cells will remain empty throughout the game - the playing field is too large to fill it up completely. Since it was necessary to scan it every move, and in one move only one figure is put - then you can focus only on this figure (cell): scan only one horizontal, vertical and two diagonals of the cell that owns that cell.
Plus, you do not need to scan all the cells of the lines. Since the end of the game is 5 figures in a row, we are not interested in figures located 6 cells apart from each other. It is enough to scan five cells in each side. Unclear? See the animation below.
So, we have already written a page with tic-tac-toe. We proceed to the main task - AI.
You can not just take and write code, if you do not know how: you need to think about the logic of the bot.
The bottom line is to analyze the playing field, at least part of it, and miscalculate the price (weight) of each cell on the field. The cage with the greatest weight - the most promising - is where the bot comes and puts the figure. The main difficulty is in the calculation of the weight of one cell.
Noughts and crosses are figures.
Attack we will call several identical figures standing side by side on the same line. In fact, this set. The number of pieces in the attack - its power . One separate figure is also an attack (power 1).
On the adjacent attack cells (at the ends) there may be empty cells or enemy pieces. It is logical to think that the attack with two empty cells at the "ends", we can develop in two directions, which makes it more promising. The number of empty cells at the “ends” of the attack will be called its potential . The potential can be 0, 1 or 2.
Attacks are denoted as follows: [attack power, potential] . For example, attack [4: 1] .
Figure 1. Attack [4: 1]
During the analysis, we will evaluate all the cells that are in a specific area. Each cell will calculate its weight . It is calculated based on the weights of all attacks that are affected by a given cell.
Imagine that on the playing field there are already several attacks of one and second player. Someone from the players makes a move (let the crosses). Naturally, he makes a move to an empty cell - and thus he can:
That is, our protagonist can attack and defend. And maybe all at once in one move. For him it is important, both the first and second.
The essence of the analysis is as follows:
In fact, with this algorithm we check what will happen if we go like this ... and what will happen if the opponent goes like that. We look one step ahead and choose the most suitable cell - with the greatest weight.
If a cell has more weight than another, it means that it creates more dangerous attacks, or blocks strong enemy attacks. Everything is logical ... it seems to me.
If you go to the page and write in the console SHOW_WEIGHTS = true, you can visually feel the work of the algorithm (Cell weights will be shown).
I lost my mind and brought this correspondence of attacks and scales:
Selected empirically - perhaps this is not the best option.
I added an attack with a power of 5 with an extremely high weight. This can be explained by the fact that the bot analyzes the game, looking at a step forward (substituting the figure into a cell). Skipping such an attack is nothing but a defeat. Well, or a victory ... looking for someone.
Attacks with great potential are valued higher.
The attack [4: 2] in most cases decides the outcome of the game. If the player managed to create such an attack, then the opponent will not be able to block it. However, this is not a victory. The enemy can finish the game faster, even if we have an attack on the field [4: 2], so its weight is lower than that of attacks with a power of 5. See the example below.
Figure 2. Attack [4: 2]
In this paragraph, the code is not presented. Here we introduce the concept of the attack divider and explain the essence of the “ragged attacks” .
Consider the following situation: when replacing a shape at a distance of several empty cells, but not more than 5, another one is located.
And like, two identical figures, on the same line ... visually it looks like an attack, but in fact not. Do not order, as such "ragged" attacks also carry a potential threat.
Especially for such cases, for each attack we will calculate the divisor. Initially, its value is 1.
Figure 3. Analysis of the "torn attack". Scanned cell with a yellow cross.
Thus, "torn" attacks will also be taken into account by the AI. In fact, these will be ordinary attacks, but the farther they are from the scanned cell, the less influence it has and, accordingly, they have less weight (thanks to the divider).
First, create an attack class . The attack will have 3 attributes, which I wrote about earlier:
And one method that will return the weight of this attack:
Further. Search for all attacks for a single cell will be divided into:
All these are lines , and the algorithm for searching for attacks on these lines can be summarized: the class checkLine .
However, we do not need to check the entire line. The maximum attack power that interests us is 5. Certainly, creating an attack with a power of, say, 6 is possible. But for the AI, who analyzes the game situation of the next move, it’s like 6, that 5. The prospect of getting one of these attacks speaks of the end of the game on the next move. Accordingly, the weight of the analyzed cell will be the same in both cases.
Class Attributes:
It is necessary to stop here, as the question may arise: why check the 6th cell, if the maximum attack power is 5. The answer is to determine the potential remote from the center of attack.
Here is an example: the attack with a power of 1 in the picture is on the border of the scanned area. To find out the potential of this attack, you need to "look abroad."
Fig. 3. Scan 6th cells. If you do not scan the 6th cell, you can incorrectly determine the attack potential.
To complete some attacks may simply not enough space. Considering the attackplace, we can understand in advance which of the attacks are unpromising.
Fig. 4. Place to attack
The algorithm is as follows:
1) Let's start with the central cell. It should be empty (we're going to make a move in it, aren't we? However, we do not forget that our AI should substitute figures in this cell for analyzing the next move. The figure we substitute — this.subfig — is a cross by default. Since the central cell will initially contain some shape after the substitution, it will belong to some kind of attack this.curAttack :
All of these items we have displayed in the values ​​of the default constructor - see the code above.
2) Next, reducing the iterator, sort through 5 cells on one side of the scan. The getAttacks function (cellX, cellY, subFig, dx, dy) is responsible for this, where:
cellX, cellY - coordinates of the checked cell
subFig - the shape that we substitute in the checked cell
dx, dy - changes of x and y coordinates in cycles - this is how we set the search direction:
In a sense, this is a vector parallel to the search line. Thus, one function will be able to search in 4 directions and we will not violate the DRY principle once again.
Function code:
Please note that if checkCell () returns something, then the loop is terminated.
3) Check the shape of these cells.
The checkCell (x, y) function is responsible for this:
First, let's write the figure in the variable fig :
Model.Field is our playing field.
fig can be 'x', 'o', 'b' (border), 0 (empty cell).
4) If the figure on the 5th square coincides with the central cell, then the attack “rested” on the border and in order to determine the attack potential it is necessary to “check the border” ( this.checkEdge = true ).
The checkCell function is ready. However, we continue to work on the class checkLine .
5) After the first cycle, you need to "turn around." We translate the iterator to the center and the central attack, with the index 0, remove from the array of attacks and set as the current one.
6) Next, go to the other side of the current cell, increasing the iterator.
Absolutely the same check of figures. (The code has already been written - getAttacks function)
7) Everything, we collected all the attacks that were on the line in one array.
On this with the class checkLine all ... finished.
Well, then everything is simple - create a checkLine object for each of the lines (2 diagonals, horizontal and vertical) and call the getAttacks function. That is, for each line - its own checkLine object and, accordingly, its own set of attacks.
Let the getAllAttacks () function be responsible for all this - already separately from the classes described above;
At the exit we have an object with all the attacks for the checked cell.
However, you may have noticed some kind of filter function. Its task is to screen out "unpromising" attacks:
However, if the attack has a power greater than 5, then the filter will miss it. Such a bot should see attacks, their screening will lead to jambs at the end of the game.
Yes ... the term is again, sorry! So we will call the situation in the game when one wrong move decides the outcome of the game.
For example, the attack [3: 2] is a breakpoint. If the opponent does not block it by placing a piece next to it, then with the next move, we already have an attack on the playing field [4: 2] - well, the outcome of the game is decided, no matter how cool (In the overwhelming majority of cases).
Or attack [4: 1]. One yawn - and the game can be easily completed.
Figure 5. Breakpoint
Everything is clear and understandable here, and the algorithm about which it was written above is already able to take into account breakpoint and timely block them. Bot looks at the course ahead. He will see that on the next move, the opponent is able to create an attack [5: 1], for example, whose weight is 200 - it means that the cunning bootyar goes here.
However, imagine a situation where one of the players manages to get 2 breakpoint on the field. And this, obviously, leaves no chance to the opponent, since in one move we can block only one breakpoint. How to teach our AI to block such attacks?
Figure 6. 2 Breakpoint
Everything is simple, when analyzing a cell, when substituting a figure into it, we will count the number of breakpoints we will receive on the next turn (the bot looks at the course ahead, do not forget). Having counted 2 breakpoints, we increase the cell weight by 100.
And now, the bot will not only prevent such game situations, but also be able to create them, which makes it now a more formidable opponent.
Let's start with the obvious: any attack, with a capacity of 4 - breakpoint. Just one missed move gives us the opportunity to complete the game, i.e. put 5 pieces in a row.
Further, if the attack potential is 2, then we will spend 1 more stroke to block such an attack, which means there is a breakpoint with a power of 3. But such a breakpoint is only one - this is an attack [3: 2].
And then harder - "ragged attacks . "
We will consider only attacks with one empty cell in the middle - no more. This is explained by the fact that to complete the attack with two empty cells in the middle, you need to spend at least 2 turns - this is clearly not a breakpoint.
As we remember, we consider ragged attacks as somewhat normal: one central attack and side attacks. The central attack belongs to the scanned cell, the secondary divisor has more than 1 - this was written above.
Algorithm for finding breakpoint (it can be easier - read below):
So, the main hell behind is described above. It is time to blind from it something working. The countWeight (x, y) function takes the cell coordinates as input, and returns its weight. What does she have under the hood?
First, we get an array of all the attacks that the cell belongs to. ( getAllAttacks (x, y) ). Going through all the lines, we count the number of breakpoints. If 2 breakpoint - remember that this situation can decide the outcome of the game, and increase the weight of the cell by 100.
However, all breakpoints should belong to the same player, so I had to implement a check in 2 steps: first crosses, then zeros.
Since in the array of attack weights ( ATTACK_WEIGHTS [] ) I did not consider attacks with a power of 6 or more, I had to replace them with attacks of power 5. No difference — they all lead to the end of the game.
Well, we summarize the weights of the attacks - and that was all.
Another small point: in order for the bot not to fail at the end of the game, when it has already built an attack with a power of 4 and is thinking about the current move, it is necessary to significantly increase the weight of the cell to complete such an attack. Without this, the AI, simply simply, can begin to defend against the "dangerous" attacks of the opponent, although the game seemed to be won. The last move is important.
Now, when calling this function for a specific cell, we will get its weight. We carry out this operation for all cells and choose the best (with the greatest weight). Go and go)
You can find the rest of the code on github . There is already enough material, and his presentation, as I did not try, leaves much to be desired. But if you could read this far, dear reader, then I am grateful to you.
It will do! Yes, you can beat him, but to make it a little problematic for me personally. Maybe I'm just not attentive enough. Try your strength too.
I know that it can be easier, but I do not know how. I would like to listen to people who know or look at other implementations of such a bot.
I know what can be better. Yes ... you can use well-known algorithms, like a minimax, but for this you need to have some knowledge base in the field of game theory, which, unfortunately, I cannot boast.
In the future, I plan to add an analysis of breakpoits a few steps ahead, which will make the bot an even more serious rival. However, now I do not have a clear idea about the implementation of this; I only have the upcoming session and the unfinished diploma - which saddens me.
Thanks if you read to the end.
This article is about the process of developing AI on javascript for playing one of these variations of daggers: there was a lot of material, but I diluted it with animation and pictures. In any case, at least it is worth trying to play it.
The differences of this version of the game from the original are as follows:
')
- The field can be arbitrarily large (How long is enough notebook)
- The one who puts 5 pieces (if you can call them that) in a row wins.
Everything is simple ... and at the same time difficult: the outcome of the game cannot be calculated in advance, as in the classic version. This "little project" took me a lot of time and nerves. I hope you will be interested.
Before we begin
I am forced to apologize in advance for the volume of the article and in some places not quite an intelligible statement of thought, but I did not manage to squeeze the flock without a loss in content and quality.
I recommend first to get acquainted with the result . Code
Hotkeys and commands:
- D - AI will make a move for you
- T - view cell weight
- Write in the console SHOW_WEIGHTS = true to view the weights of all the analyzed cells.
Let's start
You need to start with the implementation of the game itself, i.e. write an application for two players, as long as no bot. For my own purposes, I decided to use javascript + jquery + bootstrap4, although it is practically not used there, but it is better to leave it - or the table will float. There is nothing special to tell, the material on js, jquery and bootstrap on Habré is full. Let me just say that I used MVC. And in general, I will not explain absolutely all the code - there was already a lot of material.
So, the playing field was ready. You can set the figures in the cells. But the victory of any of the players was not fixed.
Scan the "end of the game"
The game ends when one of the players puts 5 pieces in a row. “It's simple!” I thought. And he began to scan absolutely all the cells of the field: first all the horizontals, then the verticals and, finally, the diagonals.
It's a dumb way, but it worked. However, it could be significantly improved, which I did: Most of the cells will remain empty throughout the game - the playing field is too large to fill it up completely. Since it was necessary to scan it every move, and in one move only one figure is put - then you can focus only on this figure (cell): scan only one horizontal, vertical and two diagonals of the cell that owns that cell.
Plus, you do not need to scan all the cells of the lines. Since the end of the game is 5 figures in a row, we are not interested in figures located 6 cells apart from each other. It is enough to scan five cells in each side. Unclear? See the animation below.
View code
checkWin( cellX, cellY ){ var res = null; var newFig = getFig(cellX,cellY); if( ! newFig ) return false; var res; res = res || checkLine( cellX, cellY, 1, 0 ); //horizontal res = res || checkLine( cellX, cellY, 0, 1 ); //vertical res = res || checkLine( cellX, cellY, 1, 1 ); //diagonal 45 res = res || checkLine( cellX, cellY, 1, -1 ); //diagonal 135 return res; function getFig( x, y ){ return Model.Field[x] && Model.Field[x][y] ? Model.Field[x][y] : 'b'; } function checkLine( x, y, dx, dy ){ x = +x; y = +y; var score = 0; while( getFig( x - dx, y - dy ) == newFig ){ x -= dx; y -= dy; } while( getFig( x, y ) == newFig ){ x += dx; y += dy; score++; } if( score >= 5 ) return true; return false; } } Let's get to the bot itself
So, we have already written a page with tic-tac-toe. We proceed to the main task - AI.
You can not just take and write code, if you do not know how: you need to think about the logic of the bot.
The bottom line is to analyze the playing field, at least part of it, and miscalculate the price (weight) of each cell on the field. The cage with the greatest weight - the most promising - is where the bot comes and puts the figure. The main difficulty is in the calculation of the weight of one cell.
Terminology
Noughts and crosses are figures.
Attack we will call several identical figures standing side by side on the same line. In fact, this set. The number of pieces in the attack - its power . One separate figure is also an attack (power 1).
On the adjacent attack cells (at the ends) there may be empty cells or enemy pieces. It is logical to think that the attack with two empty cells at the "ends", we can develop in two directions, which makes it more promising. The number of empty cells at the “ends” of the attack will be called its potential . The potential can be 0, 1 or 2.
Attacks are denoted as follows: [attack power, potential] . For example, attack [4: 1] .
Figure 1. Attack [4: 1]
During the analysis, we will evaluate all the cells that are in a specific area. Each cell will calculate its weight . It is calculated based on the weights of all attacks that are affected by a given cell.
The essence of the analysis
Imagine that on the playing field there are already several attacks of one and second player. Someone from the players makes a move (let the crosses). Naturally, he makes a move to an empty cell - and thus he can:
- Develop your attack, and maybe not just one, by increasing its power. Can start a new attack, etc.
- Prevent the development of an enemy attack or block it altogether.
That is, our protagonist can attack and defend. And maybe all at once in one move. For him it is important, both the first and second.
The essence of the analysis is as follows:
- The bot inserts figures into the checked cell: first a cross, then a zero.
- Next, he searches for all the attacks that were received by such moves and summarizes their weights.
- The amount received is the weight of the cell.
- A similar algorithm is performed for all cells of the playing field.
In fact, with this algorithm we check what will happen if we go like this ... and what will happen if the opponent goes like that. We look one step ahead and choose the most suitable cell - with the greatest weight.
If a cell has more weight than another, it means that it creates more dangerous attacks, or blocks strong enemy attacks. Everything is logical ... it seems to me.
If you go to the page and write in the console SHOW_WEIGHTS = true, you can visually feel the work of the algorithm (Cell weights will be shown).
Attack weights
I lost my mind and brought this correspondence of attacks and scales:
ATTACK_WEIGHT = [[],[],[],[],[],[]]; ATTACK_WEIGHT[1][1] = 0.1; ATTACK_WEIGHT[2][1] = 2; ATTACK_WEIGHT[3][1] = 4; ATTACK_WEIGHT[4][1] = 6; ATTACK_WEIGHT[5][1] = 200; ATTACK_WEIGHT[1][2] = 0.25; ATTACK_WEIGHT[2][2] = 5; ATTACK_WEIGHT[3][2] = 7; ATTACK_WEIGHT[4][2] = 100; ATTACK_WEIGHT[5][2] = 200; ATTACK_WEIGHT[5][0] = 200; Selected empirically - perhaps this is not the best option.
I added an attack with a power of 5 with an extremely high weight. This can be explained by the fact that the bot analyzes the game, looking at a step forward (substituting the figure into a cell). Skipping such an attack is nothing but a defeat. Well, or a victory ... looking for someone.
Attacks with great potential are valued higher.
The attack [4: 2] in most cases decides the outcome of the game. If the player managed to create such an attack, then the opponent will not be able to block it. However, this is not a victory. The enemy can finish the game faster, even if we have an attack on the field [4: 2], so its weight is lower than that of attacks with a power of 5. See the example below.
Figure 2. Attack [4: 2]
Ripped Attacks
In this paragraph, the code is not presented. Here we introduce the concept of the attack divider and explain the essence of the “ragged attacks” .
Consider the following situation: when replacing a shape at a distance of several empty cells, but not more than 5, another one is located.
And like, two identical figures, on the same line ... visually it looks like an attack, but in fact not. Do not order, as such "ragged" attacks also carry a potential threat.
Especially for such cases, for each attack we will calculate the divisor. Initially, its value is 1.
- We present the “torn” attack as a few ordinary
- We count the number of empty cells between the central attack and the side
- For each empty cell, the divisor is increased by 1
- The weight of the central attack is calculated as usual, the weight of the secondary is divided by the divisor.
Figure 3. Analysis of the "torn attack". Scanned cell with a yellow cross.
Thus, "torn" attacks will also be taken into account by the AI. In fact, these will be ordinary attacks, but the farther they are from the scanned cell, the less influence it has and, accordingly, they have less weight (thanks to the divider).
Attack search algorithm
First, create an attack class . The attack will have 3 attributes, which I wrote about earlier:
class Attack{ constructor( cap = 0, pot = 0, div = 1 ){ this.capability = cap; // this.potential = pot; // this.divider = div; // } And one method that will return the weight of this attack:
countWeigth(){ return ATTACK_WEIGHT[ this.capability, this.potential ] / this.divider } } Further. Search for all attacks for a single cell will be divided into:
- Horizontal search
- Vertical search
- 45 degree diagonal search
- Search on 135 degrees diagonal
All these are lines , and the algorithm for searching for attacks on these lines can be summarized: the class checkLine .
However, we do not need to check the entire line. The maximum attack power that interests us is 5. Certainly, creating an attack with a power of, say, 6 is possible. But for the AI, who analyzes the game situation of the next move, it’s like 6, that 5. The prospect of getting one of these attacks speaks of the end of the game on the next move. Accordingly, the weight of the analyzed cell will be the same in both cases.
Class Attributes:
class checkLine{ constructor(){ //, this.subFig = "×"; // . «0» - . this.Attacks = []; // this.curAttack = new Attack; // ( ) this.iter = 1; //, this.checkEdge = false; It is necessary to stop here, as the question may arise: why check the 6th cell, if the maximum attack power is 5. The answer is to determine the potential remote from the center of attack.
Here is an example: the attack with a power of 1 in the picture is on the border of the scanned area. To find out the potential of this attack, you need to "look abroad."
Fig. 3. Scan 6th cells. If you do not scan the 6th cell, you can incorrectly determine the attack potential.
// this.attackplace = 1; } To complete some attacks may simply not enough space. Considering the attackplace, we can understand in advance which of the attacks are unpromising.
Fig. 4. Place to attack
The algorithm is as follows:
1) Let's start with the central cell. It should be empty (we're going to make a move in it, aren't we? However, we do not forget that our AI should substitute figures in this cell for analyzing the next move. The figure we substitute — this.subfig — is a cross by default. Since the central cell will initially contain some shape after the substitution, it will belong to some kind of attack this.curAttack :
- its power will be at least 1 (figure in the central cell)
- the divisor is 1, since it is a central attack (it owns the scanned cell);
- potential is not yet known - default is 0;
All of these items we have displayed in the values ​​of the default constructor - see the code above.
2) Next, reducing the iterator, sort through 5 cells on one side of the scan. The getAttacks function (cellX, cellY, subFig, dx, dy) is responsible for this, where:
cellX, cellY - coordinates of the checked cell
subFig - the shape that we substitute in the checked cell
dx, dy - changes of x and y coordinates in cycles - this is how we set the search direction:
- Horizontal (dx = 1, dy = 0)
- Vertical (dx = 0, dy = 1)
- Diagonal 45 (dx = 1, dy = -1)
- 135 diagonal (dx = 1, dy = 1)
In a sense, this is a vector parallel to the search line. Thus, one function will be able to search in 4 directions and we will not violate the DRY principle once again.
Function code:
getAttacks( cellX, cellY, subFig, dx, dy ){ this.substitudeFigure( subFig ); // – ... for( var x = cellX - dx, y = cellY - dy; Math.abs( x - cellX ) <= 5 && Math.abs( y - cellY ) <= 5; x -= dx, y -= dy ) if( this.checkCell( x, y ) ) break; //: // ( ) this.turnAround(); // - ... for( var x = cellX + dx, y = cellY + dy; Math.abs( x - cellX ) <= 5 && Math.abs( y - cellY ) <= 5; x += dx, y += dy ) if( this.checkCell( x, y ) ) break; return this.Attacks; } Please note that if checkCell () returns something, then the loop is terminated.
3) Check the shape of these cells.
The checkCell (x, y) function is responsible for this:
First, let's write the figure in the variable fig :
Model.Field is our playing field.
checkCell( x, y ){ var fig = Model.Field[x] && Model.Field[x][y] !== undefined ? Model.Field[x][y] : 'b'; fig can be 'x', 'o', 'b' (border), 0 (empty cell).
- If such a figure coincides with the central cell ( this.subFig ), then we continue the algorithm - then we continue to scan the attack, everything is fine, we continue in the same spirit. The extra figure in the attack - plus its power ( this.curAttack.capability ) and place ( this.attackplace ).
(See the code in the next paragraph) - If this is a different figure, then the attack that we scanned before (this.curAttack) is blocked from this side. We change nothing in the attack parameters, write it into the array of attacks and fall out of the loop.
if( fig == 'â—‹' || fig == 'Ă—' ){ if( this.subFig != fig ){ // this.Attacks.push( this.curAttack ); // return fig; // } else{ // this.curAttack.capability++; // + this.attackplace++; // + } } - If there is no such cell, it means that it fell outside the field, which means that the attack is blocked. We write it into an array of all attacks and exit the loop.
else if( fig == 'b' ){ // this.Attacks.push( this.curAttack ); return 'b'; } - If you catch an empty cage - then the current attack is over, or we are dealing with a "torn attack." Plus, the potential and the place to attack (because the attack is not blocked). However, we are not leaving the loop - perhaps this is a “torn attack” - we simply write this.curAttack into the array of all attacks of the this.Attacks [] line. We create a new “current” attack and increase its divisor by 1 (this is already a side attack).
else{ // if( this.curAttack.capability ){ this.curAttack.potential++; this.Attacks.push( this.curAttack ); this.curAttack = new Attack; this.curAttack.potential++; } this.curAttack.divider++; this.attackplace++; }
4) If the figure on the 5th square coincides with the central cell, then the attack “rested” on the border and in order to determine the attack potential it is necessary to “check the border” ( this.checkEdge = true ).
if( this.iter == 4 && fig == this.subFig ) // 5- this.checkEdge = true; else if( this.iter == 5 ){ if( this.checkEdge ){ if( fig == this.curFig || fig == 0 ) this.curAttack.potential++; this.Attacks.push( this.curAttack ) } return 0; } this.iter++ The checkCell function is ready. However, we continue to work on the class checkLine .
5) After the first cycle, you need to "turn around." We translate the iterator to the center and the central attack, with the index 0, remove from the array of attacks and set as the current one.
turnAround(){ this.iter = 1; this.checkEdge = false; this.curAttack = this.Attacks[0]; this.Attacks.splice(0,1) } 6) Next, go to the other side of the current cell, increasing the iterator.
Absolutely the same check of figures. (The code has already been written - getAttacks function)
7) Everything, we collected all the attacks that were on the line in one array.
On this with the class checkLine all ... finished.
Well, then everything is simple - create a checkLine object for each of the lines (2 diagonals, horizontal and vertical) and call the getAttacks function. That is, for each line - its own checkLine object and, accordingly, its own set of attacks.
Let the getAllAttacks () function be responsible for all this - already separately from the classes described above;
getAllAttacks( cellX, cellY ){ // , , // if( Model.Field[ cellX ][ cellY ] ) return false var cX = []; var cO = []; // ... cX['0'] = this.getAttacksLine( cellX, cellY, 'Ă—', 1, 0 ); cX['90'] = this.getAttacksLine( cellX, cellY, 'Ă—', 0, 1 ); cX['45'] = this.getAttacksLine( cellX, cellY, 'Ă—', 1, -1 ); cX['135'] = this.getAttacksLine( cellX, cellY, 'Ă—', 1, 1 ); // ... cO['0'] = this.getAttacksLine( cellX, cellY, 'â—‹', 1, 0 ); cO['90'] = this.getAttacksLine( cellX, cellY, 'â—‹', 0, 1 ); cO['45'] = this.getAttacksLine( cellX, cellY, 'â—‹', 1, -1 ); cO['135'] = this.getAttacksLine( cellX, cellY, 'â—‹', 1, 1 ); return { // 'x': cX, 'o': cO } } getAttacksLine( cellX, cellY, subFig, dx, dy ){ // var C = new checkLine; C.getAttacks( cellX, cellY, subFig, dx, dy ); return this.filterAttacks( C ) // } At the exit we have an object with all the attacks for the checked cell.
However, you may have noticed some kind of filter function. Its task is to screen out "unpromising" attacks:
- With zero power (you never know will get into the array)
- Attacks that lack space (attackplace <5)
- With zero potential.
However, if the attack has a power greater than 5, then the filter will miss it. Such a bot should see attacks, their screening will lead to jambs at the end of the game.
filterAttacks( attackLine ){ var res = [] if( attackLine.attackplace >= 5 ) attackLine.Attacks.forEach( ( a )=>{ if( a.capability && a.potential || a.capability >= 5 ) res.push( a ) }) attackLine.Attacks = res; return res } Breakpoints
Yes ... the term is again, sorry! So we will call the situation in the game when one wrong move decides the outcome of the game.
For example, the attack [3: 2] is a breakpoint. If the opponent does not block it by placing a piece next to it, then with the next move, we already have an attack on the playing field [4: 2] - well, the outcome of the game is decided, no matter how cool (In the overwhelming majority of cases).
Or attack [4: 1]. One yawn - and the game can be easily completed.
Figure 5. Breakpoint
Everything is clear and understandable here, and the algorithm about which it was written above is already able to take into account breakpoint and timely block them. Bot looks at the course ahead. He will see that on the next move, the opponent is able to create an attack [5: 1], for example, whose weight is 200 - it means that the cunning bootyar goes here.
However, imagine a situation where one of the players manages to get 2 breakpoint on the field. And this, obviously, leaves no chance to the opponent, since in one move we can block only one breakpoint. How to teach our AI to block such attacks?
Figure 6. 2 Breakpoint
Everything is simple, when analyzing a cell, when substituting a figure into it, we will count the number of breakpoints we will receive on the next turn (the bot looks at the course ahead, do not forget). Having counted 2 breakpoints, we increase the cell weight by 100.
And now, the bot will not only prevent such game situations, but also be able to create them, which makes it now a more formidable opponent.
How to understand that the attack - breakpoint
Let's start with the obvious: any attack, with a capacity of 4 - breakpoint. Just one missed move gives us the opportunity to complete the game, i.e. put 5 pieces in a row.
Further, if the attack potential is 2, then we will spend 1 more stroke to block such an attack, which means there is a breakpoint with a power of 3. But such a breakpoint is only one - this is an attack [3: 2].
And then harder - "ragged attacks . "
We will consider only attacks with one empty cell in the middle - no more. This is explained by the fact that to complete the attack with two empty cells in the middle, you need to spend at least 2 turns - this is clearly not a breakpoint.
As we remember, we consider ragged attacks as somewhat normal: one central attack and side attacks. The central attack belongs to the scanned cell, the secondary divisor has more than 1 - this was written above.
Algorithm for finding breakpoint (it can be easier - read below):
- We introduce the score variable
- We take the central attack, we consider the power
- Take one of the side, if its divider is not more than 2x.
- Score - the sum of the powers of the central and side attacks
- If the potentials of the central and side attacks are equal to 2, then to block such an attack, you need to spend one more move. Therefore, score increase by 1
- If score > = 4, then this is breakpoint
In fact, breakpoint could simply be enumerated, there are not so many of them, but I did not understand this immediately.
isBreakPoint( attackLine ){ if( ! attackLine || ! attackLine.length ) return false; var centAtk; attackLine.forEach( ( a )=>{ if( a.divider == 1 ) centAtk = a; }) if( centAtk.capability >= 4 ) return true if( centAtk.potential == 2 && centAtk.capability >= 3 ) return true; var res = false; attackLine.forEach( ( a )=>{ var score = centAtk.capability; if( a.divider == 2 ){ //side attack if( centAtk.potential == 2 && a.potential == 2 ) score++; if( score + a.capability >= 4 ){ res = true; return; } } }) return res; } Yes, finally we put it all together
So, the main hell behind is described above. It is time to blind from it something working. The countWeight (x, y) function takes the cell coordinates as input, and returns its weight. What does she have under the hood?
First, we get an array of all the attacks that the cell belongs to. ( getAllAttacks (x, y) ). Going through all the lines, we count the number of breakpoints. If 2 breakpoint - remember that this situation can decide the outcome of the game, and increase the weight of the cell by 100.
However, all breakpoints should belong to the same player, so I had to implement a check in 2 steps: first crosses, then zeros.
Since in the array of attack weights ( ATTACK_WEIGHTS [] ) I did not consider attacks with a power of 6 or more, I had to replace them with attacks of power 5. No difference — they all lead to the end of the game.
Well, we summarize the weights of the attacks - and that was all.
Another small point: in order for the bot not to fail at the end of the game, when it has already built an attack with a power of 4 and is thinking about the current move, it is necessary to significantly increase the weight of the cell to complete such an attack. Without this, the AI, simply simply, can begin to defend against the "dangerous" attacks of the opponent, although the game seemed to be won. The last move is important.
countWeight( x, y ){ var attacks = this.getAttacks( x, y ) if( ! attacks ) return; var sum = 0; sum += count.call( this, attacks.x, 'Ă—' ); sum += count.call( this, attacks.o, 'â—‹' ); return sum function count( atks, curFig ){ var weight = 0; var breakPoints = 0; [ "0", "45", "90", "135" ].forEach( ( p )=>{ if( this.isBreakPoint( atks[p] ) ){ debug( "Break point" ) if( ++breakPoints == 2 ){ weight += 100; debug( "Good cell" ) return; } } atks[p].forEach( ( a )=>{ if( a.capability > 5 ) a.capability = 5; if( a.capability == 5 && curFig == Model.whoPlays.char ) weight += 100; weight += a.getWeight(); }); }) return weight } } Now, when calling this function for a specific cell, we will get its weight. We carry out this operation for all cells and choose the best (with the greatest weight). Go and go)
You can find the rest of the code on github . There is already enough material, and his presentation, as I did not try, leaves much to be desired. But if you could read this far, dear reader, then I am grateful to you.
My opinion about the result
It will do! Yes, you can beat him, but to make it a little problematic for me personally. Maybe I'm just not attentive enough. Try your strength too.
I know that it can be easier, but I do not know how. I would like to listen to people who know or look at other implementations of such a bot.
I know what can be better. Yes ... you can use well-known algorithms, like a minimax, but for this you need to have some knowledge base in the field of game theory, which, unfortunately, I cannot boast.
In the future, I plan to add an analysis of breakpoits a few steps ahead, which will make the bot an even more serious rival. However, now I do not have a clear idea about the implementation of this; I only have the upcoming session and the unfinished diploma - which saddens me.
Thanks if you read to the end.
Source: https://habr.com/ru/post/430708/
All Articles