Я реализовал Negamax, как это можно найти на википедия, который включает в себя альфа / бета-обрезку.
Тем не менее, он, кажется, поддерживает проигрышный ход, который, насколько мне известно, является неверным результатом.
Игра Tic-Tac-Toe, я абстрагировал большую часть игрового процесса, поэтому должно быть довольно легко обнаружить ошибку в алгоритме.
#include <list>
#include <climits>
#include <iostream>
//#define DEBUG 1
using namespace std;
struct Move {
int row, col;
Move(int row, int col) : row(row), col(col) { }
Move(const Move& m) { row = m.row; col = m.col; }
};
struct Board {
char player;
char opponent;
char board[3][3];
Board() { }
void read(istream& stream) {
stream >> player;
opponent = player == 'X' ? 'O' : 'X';
for(int row = 0; row < 3; row++) {
for(int col = 0; col < 3; col++) {
char playa;
stream >> playa;
board[row][col] = playa == '_' ? 0 : playa == player ? 1 : -1;
}
}
}
void print(ostream& stream) {
for(int row = 0; row < 3; row++) {
for(int col = 0; col < 3; col++) {
switch(board[row][col]) {
case -1:
stream << opponent;
break;
case 0:
stream << '_';
break;
case 1:
stream << player;
break;
}
}
stream << endl;
}
}
void do_move(const Move& move, int player) {
board[move.row][move.col] = player;
}
void undo_move(const Move& move) {
board[move.row][move.col] = 0;
}
bool isWon() {
if (board[0][0] != 0) {
if (board[0][0] == board[0][1] &&
board[0][1] == board[0][2])
return true;
if (board[0][0] == board[1][0] &&
board[1][0] == board[2][0])
return true;
}
if (board[2][2] != 0) {
if (board[2][0] == board[2][1] &&
board[2][1] == board[2][2])
return true;
if (board[0][2] == board[1][2] &&
board[1][2] == board[2][2])
return true;
}
if (board[1][1] != 0) {
if (board[0][1] == board[1][1] &&
board[1][1] == board[2][1])
return true;
if (board[1][0] == board[1][1] &&
board[1][1] == board[1][2])
return true;
if (board[0][0] == board[1][1] &&
board[1][1] == board[2][2])
return true;
if (board[0][2] == board [1][1] &&
board[1][1] == board[2][0])
return true;
}
return false;
}
list<Move> getMoves() {
list<Move> moveList;
for(int row = 0; row < 3; row++)
for(int col = 0; col < 3; col++)
if (board[row][col] == 0)
moveList.push_back(Move(row, col));
return moveList;
}
};
ostream& operator<< (ostream& stream, Board& board) {
board.print(stream);
return stream;
}
istream& operator>> (istream& stream, Board& board) {
board.read(stream);
return stream;
}
int evaluate(Board& board) {
int score = board.isWon() ? 100 : 0;
for(int row = 0; row < 3; row++)
for(int col = 0; col < 3; col++)
if (board.board[row][col] == 0)
score += 1;
return score;
}
int negamax(Board& board, int depth, int player, int alpha, int beta) {
if (board.isWon() || depth <= 0) {
#if DEBUG > 1
cout << "Found winner board at depth " << depth << endl;
cout << board << endl;
#endif
return player * evaluate(board);
}
list<Move> allMoves = board.getMoves();
if (allMoves.size() == 0)
return player * evaluate(board);
for(list<Move>::iterator it = allMoves.begin(); it != allMoves.end(); it++) {
board.do_move(*it, -player);
int val = -negamax(board, depth - 1, -player, -beta, -alpha);
board.undo_move(*it);
if (val >= beta)
return val;
if (val > alpha)
alpha = val;
}
return alpha;
}
void nextMove(Board& board) {
list<Move> allMoves = board.getMoves();
Move* bestMove = NULL;
int bestScore = INT_MIN;
for(list<Move>::iterator it = allMoves.begin(); it != allMoves.end(); it++) {
board.do_move(*it, 1);
int score = -negamax(board, 100, 1, INT_MIN + 1, INT_MAX);
board.undo_move(*it);
#if DEBUG
cout << it->row << ' ' << it->col << " = " << score << endl;
#endif
if (score > bestScore) {
bestMove = &*it;
bestScore = score;
}
}
if (!bestMove)
return;
cout << bestMove->row << ' ' << bestMove->col << endl;
#if DEBUG
board.do_move(*bestMove, 1);
cout << board;
#endif
}
int main() {
Board board;
cin >> board;
#if DEBUG
cout << "Starting board:" << endl;
cout << board;
#endif
nextMove(board);
return 0;
}
Предоставляя этот вклад:
O
X__
___
___
Алгоритм выбирает размещение фигуры в 0, 1, что приводит к гарантированному проигрышу и делает эту ловушку (ничто не может быть сделано, чтобы выиграть или закончить в ничьей):
XO_
X__
___
Я уверен, что реализация игры правильная, но алгоритм должен быть в порядке.
РЕДАКТИРОВАТЬ: обновленный evaluate
а также nextMove
,
EDIT2: Исправлена первая проблема, хотя все еще есть ошибки
Ваш evaluate
Функция считает пустые места и не распознает выигрышную доску.
РЕДАКТИРОВАТЬ:
Есть также относительно небольшая проблема в nextMove
, Линия должна быть
int score = -negamax(board, 0, -1, INT_MIN + 1, INT_MAX);
Исправить это (и evaluate
), и код выбирает правильный ход.
РЕДАКТИРОВАТЬ:
Это исправляет это:
if (board.isWon() || depth <= 0) {
#if DEBUG > 1
cout << "Found winner board at depth " << depth << endl;
cout << board << endl;
#endif
return -100;
}
Почти все эти проблемы проистекают из непонимания смысла score
, Это с точки зрения player
, Если negamax
оценивает позицию игрока 1, и игрок 1 не может выиграть, счет должен быть низким (например, -100); если negamax
оценивает позицию игрока -1, а игрок -1 не может выиграть, счет должен быть низким (например, -100). Если evaluate()
не может отличить игроков, а затем возвращает счет player * evaluate(board)
это просто неправильно.
isWon
возвращает true как для победы, так и для проигрыша игрока. Это не может помочь.
Кажется, что-то смешное с использованием плеера.
Ваш цикл верхнего уровня вызывает «board.do_move (* it, 1);» затем вызывает negamax с игроком = 1.
Тогда negamax назовет «board.do_move (* it, player);», так что похоже, что первый игрок фактически получает 2 хода.