У меня есть большая проблема в моем минимаксном алгоритме. Я должен реализовать игру, где есть игрок и игрок AI. Оба они могут подняться вверх, вниз, вправо, влево по диагонали, и после этого они должны заблокировать ячейку, где другой игрок не может шагнуть (c, где другой игрок остается заблокированной ячейкой и не может заблокируйте его, и вы не можете заблокировать уже заблокированную ячейку тоже). Для этого я написал небольшой минимаксный алгоритм, но по странному поводу ИИ не может выбрать лучшее root.
struct Position
{
int x, y;
} MaxP, MinP;
int k = 2;
char board[10][10];
int currentPlayer = 2;
//Here are my global variables, MaxP is the AI, and MinP is the player.
Я установил ячейки B (заблокированные) вокруг своего стола. Алгоритм вычисления минимакса:
int nyertesErtek(int result) //return a winning value, if result=1 Ai Wins, if result=2 Player Wins, if result=0, then the game it's still going
{
if (result == 1) return 10;
if (result == 2) return -10;
}
int minimax(char pBoard[10][10], int depth, bool isMaximizing)
{
int result = 0;
if (isMaximizing==true)
{
int checkX[8] = { -1,-1,0,1,1,1,0,-1 };
int checkY[8] = { 0,1,1,1,0,-1,-1,-1 };
bool lephetMax = false;
bool lephetMin = false;
for (int i = 0; i < 8; i++)
{
if (pBoard[MaxP.x + checkX[i]][MaxP.y + checkY[i]] != 'B')
{
lephetMax = true;
break;
}
}
if (lephetMax == false)
{
result = 2;
}
}
if (isMaximizing == false)
{
int checkX[8] = { -1,-1,0,1,1,1,0,-1 };
int checkY[8] = { 0,1,1,1,0,-1,-1,-1 };
bool lephetMin = false;
for (int i = 0; i < 8; i++)
{
if (pBoard[MinP.x + checkX[i]][MinP.y + checkY[i]] != 'B')
{
lephetMin = true;
break;
}
}
if (lephetMin == false)
{
result = 1;
}
}
if (result != 0) //ha nem terminal state
{
//cout << "Resultra jutott"<<endl;
//cout << "---------------->Kovetkezne a: " << isMaximizing << " Result=" << result << " NyeresErtek=" << nyertesErtek(result) <<" depth="<<depth<< "<---------------"<<endl;
//printBoard();
return nyertesErtek(result);
}
int checkX[8] = { -1,-1,0,1,1,1,0,-1 };
int checkY[8] = { 0,1,1,1,0,-1,-1,-1 };
if (isMaximizing)
{
int bestScore = -INT_MAX;
int szabadX;
int szabadY;
for (int l = 0; l < 8; l++)
{
if (pBoard[MaxP.x + checkX[l]][MaxP.y + checkY[l]] != 'B')
{
int oldMaxPX = MaxP.x;
int oldMaxPY = MaxP.y;
MaxP.x = MaxP.x + checkX[l];
MaxP.y= MaxP.y + checkY[l];
pBoard[MaxP.x][MaxP.y] = 'B';
pBoard[oldMaxPX][oldMaxPY] = 'o';
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= k; j++)
{
if (pBoard[i][j] != 'B')
{
szabadX = i;
szabadY = j;
pBoard[szabadX][szabadY] = 'B';
//cout << "Maximizing, depth=" << depth << endl;
//printBoard();
int score = minimax(pBoard, depth + 1, false);
pBoard[szabadX][szabadY] = 'o';
if (score > bestScore)
{
bestScore = score;
}
}
}
}
pBoard[MaxP.x][MaxP.y] = 'o';
pBoard[oldMaxPX][oldMaxPY] = 'B';
MaxP.x = oldMaxPX;
MaxP.y = oldMaxPY;
}
}
return bestScore;
}
else
{
int bestScore = INT_MAX;
int szabadX;
int szabadY;
for (int l = 0; l < 8; l++)
{
if (pBoard[MinP.x + checkX[l]][MinP.y + checkY[l]] != 'B')
{
int oldMinPX = MinP.x;
int oldMinPY = MinP.y;
MinP.x = MinP.x + checkX[l];
MinP.y = MinP.y + checkY[l];
//pBoard[MinP.x + checkX[l]][MinP.y + checkY[l]] = 'B';
pBoard[MinP.x][MinP.y] = 'B';
pBoard[oldMinPX][oldMinPY] = 'o';
//cout << "Minimizing depth= " << depth << endl;
//printBoard();
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= k; j++)
{
if (pBoard[i][j] != 'B')
{
szabadX = i;
szabadY = j;
pBoard[szabadX][szabadY] = 'B';
int score = minimax(pBoard, depth + 1, true);
//pBoard[MinP.x + checkX[l]][MinP.y + checkY[l]] = 'o';
pBoard[szabadX][szabadY] = 'o';
if (score < bestScore)
{
bestScore = score;
}
}
}
}
pBoard[MinP.x][MinP.y] = 'o';
pBoard[oldMinPX][oldMinPY] = 'B';
MinP.x = oldMinPX;
MinP.y = oldMinPY;
}
}
return bestScore;
}
}
И перемещение ИИ находится в этой функции:
void bestMove() {
int checkX[8] = { -1,-1,0,1,1,1,0,-1 };
int checkY[8] = { 0,1,1,1,0,-1,-1,-1 };
int bestScore = -INT_MAX;
Position move;
int AIBlockX, AIBlockY;
int szabadX;
int szabadY;
for (int l = 0; l < 8; l++)
{
if (board[MaxP.x + checkX[l]][MaxP.y + checkY[l]] != 'B')
{
int oldMaxPX = MaxP.x;
int oldMaxPY = MaxP.y;
MaxP.x = MaxP.x + checkX[l];
MaxP.y = MaxP.y + checkY[l];
board[MaxP.x][MaxP.y] = 'B';
board[oldMaxPX][oldMaxPY] = 'o';
for (int i = 1; i <= k; i++)
{
for (int j = 1; j <= k; j++)
{
if (board[i][j] != 'B')
{
szabadX = i;
szabadY = j;
board[szabadX][szabadY] = 'B';
int score = minimax(board, 0, false);
cout << endl << "Ennyi a score amit kaptam pech=" << score << endl;
board[szabadX][szabadY] = 'o';
if (score > bestScore)
{
bestScore = score;
move.x = MaxP.x;
move.y = MaxP.y;
AIBlockX = szabadX;
AIBlockY = szabadY;
cout << "BESTMOVE: " << move.x << " " << move.y << " bestscore= " << bestScore << endl;
}
}
}
}
board[MaxP.x][MaxP.y] = 'o';
board[oldMaxPX][oldMaxPY] = 'B';
MaxP.x = oldMaxPX;
MaxP.y = oldMaxPY;
}
}
board[move.x][move.y] = 'B';
board[MaxP.x][MaxP.y] = 'o';
MaxP.x = move.x;
MaxP.y = move.y;
board[AIBlockX][AIBlockY] = 'B';
currentPlayer = 2;
}
Я думаю, что моя главная проблема заключается в чем-то в функции минимакса: когда я проверяю, где игрок можно go -> и после этого все возможные блокировки перемещаются. И в этой тройке, когда я переписываю лучший результат с текущим счетом, я не могу вернуть значение напрямую, потому что мне приходится проверять другие возможные шаги в первых итерациях. Итак, в конце концов (: D) мой вопрос заключается в том, как я могу сохранить лучший ход после того, как была сделана блокировка ячейки, и вернуть его моему ИИ для перехода туда? Спасибо за ответ. :)
ps: извините, если этот пост слишком длинный, но я подумал, чтобы полностью понять мою проблему, вы также должны увидеть часть алгоритма.