Based on C++ realization of gobang AI algorithm thought
- 2020-06-03 07:44:36
- OfStack
Today I would like to share my thoughts on AI for 5 pieces. Because Before doing this, I hadn't been exposed to anything like this. Through this first time, I got to know something about it. My thoughts also came from many blogs on the Internet. After reading a lot, I finally came up with one of my own.
So my 5 pieces are 15 by 15. My AI algorithm requires that every move later after 1 time to calculate the position of every one leisure "score", in short, we need to store one piece of array, deposit indicates whether or not the pieces, and 1 per 1 space array to record "score", the score is the foundation of later AI used to operation, also point you AI control difficult.
My current thinking is divided into two parts. First, if the player drops the ball first, ask the computer AI to drop the ball randomly in any direction where you drop the ball. This is step 1. And then we go into the algorithm.
First initialize your score array to zero. Then, complete traversal will be conducted after each drop. If it is found to be blank, it will check its 8 directions for 4 weeks (of course, if it is the edge position, it will be relatively modified to determine whether the boundary is out). If in the margins, and found one found in a diagonal direction 1 other color piece, so relative to the blank area array score plus one set of scores, and then continue in this direction detection if there are continuous with 1 color piece, if not check other directions or detection under a blank position. If you find a piece of the same color in the same direction, you can double the number of points for the second piece, indicating that the blank is more important. Repeat once and continue the test. (PS: Because where AI's pieces fall in the end depends on finally traversing the entire score array, and then judging where the pieces fall according to the score, as explained below).
After the previous iteration, each drop will result in a change of 1 in the score array, and each change will result in a change in AI's judgment. On this basis, every one of the pieces also for 1 of their own chess color traversal, judge their own situation, at the same time, plus points in the score array, so that 1, the computer will be based on their own pieces and the player's position to judge, which place is more suitable for the position.
Because this is the first time I've done AI, some of the ideas I found on the web are similar to this idea of traversal. Once you understand it, it's easier to write code. You might end up with 1 points that have the same score, so you also have to set 1 random drop. Randomly assign points with the same score.
Personal perception of AI is based on how many points you give each time. Sometimes my AI will be crazy, but the general situation is relatively normal, maybe luck also accounted for 1 part, at the beginning of the design of additional points did not think so much, but now I find it seems good.
If you change your grades, you will come out with a good score.
Post my code below!
void GameScene::Robot(int *x, int *y, int *Sum)
{
ExWhile1 = true;
if (*Sum == 1)
{
while (ExWhile1)
{
ChessOne(*x, *y);
if (ch[*x][*y] == 2){ ExWhile1 = false; }
}
ch[*x][*y] = tp; // Record this point
printpart(*x, *y, tp); // Print out the computer AI The first 1 Time to move later
isTouch = true;
tp++;
tp = tp % 2;
}
else // From the first 2 Start by using a scoring system
{
Findscore(*x, *y);
}
}
void GameScene::Findscore(int &x, int &y) // Find the coordinates with the highest score
{
srand((unsigned)time(NULL));
int i, j, x1, x2, y1, y2, lx;
int Max = 0;
ChessScore(); // Call the scoring function
for (i = 0; i<15; i++)
{
for (j = 0; j<15; j++)
{
if (Score[i][j]>Max)
{
Max = Score[i][j]; // Get the highest score of all points
x1 = i;
y1 = j;
}
}
}
x2 = x1; y2 = y1;
for (i = 0; i<15; i++) // If possible, there are multiple points with the same score
{
for (j = 0; j<15; j++)
{
if (Score[i][j] == Max&&i != x2&&j != y2) // So if you look at all these points with the same score, you look at random 1 a
{
lx = rand() % 10;
if (lx<5)
{
x2 = i, y2 = j;
break;
}
}
}
}
if (x2 != x1 || y2 != y1) // The board has 2 A high score
{
lx = rand() % 10; // random 1 a
if (lx>6)
{
x = x1, y = y1;
}
else
{
x = x2, y = y2;
}
}
else // Nothing on the chessboard 1 A high score
{
x = x1, y = y1;
}
Max = 0; // Clear maximum
ch[x][y] = tp; // Record this point
printpart(x, y, tp); // Print out the computer AI Move later
if (winerValue==2)
{
isTouch = true;
}
tp++;
tp = tp % 2;
}
inline void GameScene::ChessOne(int &x, int &y) // Players go first 1 The drop of a step
{
int i, j;
srand((unsigned)time(NULL)); // Random Numbers change over time
for (i = 0; i<15; i++)
{
for (j = 0; j<15; j++)
{
if (ch[i][j] == 0) // If a player's pieces are found in it 8 Any of the squares 1 Point move later
{
int lx = rand() % 7;
if (lx == 0)
{
x = i + 1; y = j + 1;
if (ch[x][y] == 2){ break; }
}
else if (lx == 1)
{
x = i + 1; y = j - 1;
if (ch[x][y] == 2){ break; }
}
else if (lx == 2)
{
x = i - 1; y = j - 1;
if (ch[x][y] == 2){ break; }
}
else if (lx == 3)
{
x = i - 1; y = j + 1;
if (ch[x][y] == 2){ break; }
}
else if (lx == 4)
{
x = i - 1; y = j; // on
if (ch[x][y] == 2){ break; }
}
else if (lx == 5)
{
x = i; y = j - 1; // On the left
if (ch[x][y] == 2){ break; }
}
else if (lx == 6)
{
x = i; y = j + 1; // right
if (ch[x][y] == 2){ break; }
}
else
{
x = i + 1; y = j; // Under the
if (ch[x][y] == 2){ break; }
}
}
}
}
}
void GameScene::ChessScore()
{
int x, y, i, j, k; // Loop variables
int number1 = 0, number2 = 0; //number Used to count the number of players or computer pieces connected
int empty = 0; //empty To count the number of empty points
memset(Score, 0, sizeof(Score)); // Clear the score array first
for (x = 0; x<15; x++)
{
for (y = 0; y<15; y++)
{
if (ch[x][y] == 2) // If this point is empty
{
for (i = -1; i <= 1; i++)
{
for (j = -1; j <= 1; j++) // judge 8 A direction
{
if (i != 0 || j != 0) // If it is for 0 Well, that's the original coordinates
{
// Score the player's landing point
for (k = 1; i <= 4; k++) // cycle 4 time
{ // That doesn't cross the line And there's the sunspot.
if (x + k*i >= 0 && x + k*i <= 14 &&
y + k*j >= 0 && y + k*j <= 14 &&
ch[x + k*i][y + k*j] == 0)
{
number1++;
}
else if (ch[x + k*i][y + k*j] == 2) // This point is a blank spot, +1 After exit
{
empty++;
break;
}
else // Otherwise it's the wall or the opponent's pieces
{
break;
}
}
for (k = -1; k >= -4; k--) // Judge it in the opposite direction
{ // That doesn't cross the line And there's the sunspot.
if (x + k*i >= 0 && x + k*i <= 14 &&
y + k*j >= 0 && y + k*j <= 14 &&
ch[x + k*i][y + k*j] == 0)
{
number1++;
}
else if (ch[x + k*i][y + k*j] == 2) // This point is a blank spot, +1 After exit
{
empty++;
break;
}
else
{
break;
}
}
if (number2 == 1) //2 A pawn
{
Score[x][y] += 1;
}
else if (number1 == 2) //3 A pawn
{
if (empty == 1)
{
Score[x][y] += 5; // There are 1 An empty spot +5 points die 3
}
else if (empty == 2)
{
Score[x][y] += 10; // There are two empty spots +10 points live 3
}
}
else if (number1 == 3) //4 A pawn
{
if (empty == 1)
{
Score[x][y] += 20; // There are 1 An empty spot +20 points die 4
}
else if (empty == 2)
{
Score[x][y] += 100; // There are 2 An empty spot +100 points live 4
}
}
else if (number1 >= 4)
{
Score[x][y] += 1000; // The other is 5 A piece, score to high, first block
}
empty = 0; // The variable that counts the number of empty points is cleared
// Rate where the computer landed
for (k = 1; i <= 4; k++) // cycle 4 time
{ // That doesn't cross the line And this is in hoku (computer)
if (x + k*i >= 0 && x + k*i <= 14 &&
y + k*j >= 0 && y + k*j <= 14 &&
ch[x + k*i][y + k*j] == 1)
{
number2++;
}
else if (ch[x + k*i][y + k*j] == 2)
{
empty++; break; // Empty spot
}
else
{
break;
}
}
for (k = -1; k >= -4; k--) // Judge it in the opposite direction
{
if (x + k*i >= 0 && x + k*i <= 14 &&
y + k*j >= 0 && y + k*j <= 14 &&
ch[x + k*i][y + k*j] == 1)
{
number2++;
}
else if (ch[x + k*i][y + k*j] == 2)
{
empty++; break;
}
else
{
break; // The comments are the same as in the player version above
}
}
if (number2 == 0)
{
Score[x][y] += 1; //1 A pawn
}
else if (number2 == 1)
{
Score[x][y] += 2; //2 A pawn
}
else if (number2 == 2) //3 A pawn
{
if (empty == 1)
{
Score[x][y] += 8; // die 3
}
else if (empty == 2)
{
Score[x][y] += 30; // live 3
}
}
else if (number2 == 3) //4 A pawn
{
if (empty == 1)
{
Score[x][y] += 50; // die 4
}
else if (empty == 2)
{
Score[x][y] += 200; // live 4
}
}
else if (number2 >= 4)
{
Score[x][y] += 10000; // You can form at this point 5 Five, and you win. Highest score
}
number1 = 0; // Clear zero, so that the next recount
number2 = 0;
empty = 0;
}
}
}
}
}
}
}