минимакс — C ++ Minmax Failing
Я работал над этим так долго, что это уже не смешно. Я пытаюсь реализовать Minmax на Tic Tac Toe, и хотя у меня есть несколько версий ИИ, которые делают разумные начальные ходы, я никогда не смогу сделать тот, который никогда не проигрывает.
Одна из проблем, с которыми я не могу разобраться, — это эвристическая ценность. В настоящее время он возвращается как -10 при первом вызове Minmax, тогда как он должен возвращать 0 (он должен иметь возможность рисовать независимо от того, что происходит).
Другая проблема заключается в том, что он проходит 400 000 итераций, в то время как 322 000 является максимальным и, учитывая ситуации раннего выигрыша, должны даже остановиться около 250 000.
Любая помощь будет бесконечно оценена.
int MiniMax(TGameBoard _GameBoard)
{
//Always goes for max of course, just expanded in case you wanted two AIs
int iBestMove;
int iHeuristicReturned = 0;
if (_GameBoard.ePlayer == COMPUTER)
{
iHeuristicReturned = MaxMove(_GameBoard, iBestMove);
}
else
{
iHeuristicReturned = MinMove(_GameBoard, iBestMove);
}
//cout<<"\nHeuristic is "<<iHeuristicReturned<<endl;
g_iHeuristic = iHeuristicReturned;
return iBestMove;
}
int MaxMove(TGameBoard _GameBoard, int& _iMove)
{
//Logic
//If its an end node, calculate the score
//Otherwise, do minmax until the end node, and pass back the value
//If returned value is greater than v, then pass the move back upwards
++g_iIterations;
if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
{
int x;
x = EvaluateStaticPosition(_GameBoard, MAX);
return EvaluateStaticPosition(_GameBoard, MAX);
}
vector<int> moveList;
GenerateMoveList(_GameBoard, moveList);
int iNumMoves = moveList.size();
int v = -10000;
for(int i = 0; i < iNumMoves; ++i)
{
int iMove = moveList[i];
_GameBoard.Set(iMove, CROSS);
int opponentsBestMove;
++g_iDepth;
int curRating = MinMove(_GameBoard, opponentsBestMove);
--g_iDepth;
if (curRating > v)
{
v = curRating;
_iMove = iMove;
}
RetractMove(&_GameBoard, iMove);
}
return v;
}
int MinMove(TGameBoard _GameBoard, int& _iMove)
{
++g_iIterations;
if (g_iIterations > 320000)
{
int x = 0;
}
if(_GameBoard.CheckWinner(_GameBoard) || _GameBoard.IsFull())
{
return EvaluateStaticPosition(_GameBoard, MIN);
}
vector<int> moveList;
GenerateMoveList(_GameBoard, moveList);
int iNumMoves = moveList.size();
int v = 10000;
for(int i = 0; i < iNumMoves; ++i)
{
int iMove = moveList[i];
_GameBoard.Set(iMove, NAUGHT);
int opponentsBestMove;
++g_iDepth;
int curRating = MaxMove(_GameBoard, opponentsBestMove);
--g_iDepth;
if (curRating < v)
{
v = curRating;
_iMove = iMove;
}
RetractMove(&_GameBoard, iMove);
}
return v;
}
int EvaluateStaticPosition(TGameBoard _GameBoard, EGoal _eGoal)
{
if(_GameBoard.CheckWinner(_GameBoard, COMPUTER))
{
return 10;
}
if(_GameBoard.CheckWinner(_GameBoard, PLAYER))
{
return -10;
}
return 0;
}
Другие связанные функции можно проверить здесь, но я уверен, что они в порядке.
http://pastebin.com/eyaNfBsq
Да, я знаю, что есть несколько ненужных параметров — после сбоя собственной версии я попытался следовать учебному пособию через Интернет. К сожалению, они дают одинаковые результаты.
Я был на этом в течение 12 часов, и это кажется такой простой задачей, не могу понять, что не так
Решение
Следующий код может помочь вам:
(Бонус: алфавит с менее чем 8000 досок.)
#include <algorithm>
#include <array>
#include <cassert>
#include <iostream>
enum class Square
{
Empty,
O,
X
};
Square other(Square c) {
switch (c) {
case Square::O: return Square::X;
case Square::X: return Square::O;
default: assert(0); return Square::Empty;
};
}
template <typename STREAM>
STREAM& operator << (STREAM& stream, Square c)
{
switch (c)
{
case Square::Empty: stream << "."; break;
case Square::X: stream << "X"; break;
case Square::O: stream << "O"; break;
}
return stream;
}
class Board
{
public:
Board() : board({{Square::Empty, Square::Empty, Square::Empty,
Square::Empty, Square::Empty, Square::Empty,
Square::Empty, Square::Empty, Square::Empty}})
{}
void display() const {
for (int y = 0; y != 3; ++y) {
for (int x = 0; x != 3; ++x) {
std::cout << board[3 * y + x] << " ";
}
std::cout << std::endl;
}
}
void play(unsigned int x, unsigned int y, Square c)
{
assert(x < 3);
assert(y < 3);
board[3 * y + x] = c;
}
void play(unsigned int offset, Square c)
{
assert(offset < 9);
board[offset] = c;
}
bool isFull() const {
return std::find(board.cbegin(), board.cend(), Square::Empty) == board.cend();
}
int computeScore(Square c) const
{
for (int i = 0; i < 3; ++i) {
if (board[3 * i] != Square::Empty && board[3 * i] == board[3 * i + 1] && board[3 * i] == board[3 * i + 2]) {
return board[3 * i] == c ? 1 : -1;
}
if (board[i] != Square::Empty && board[i] == board[i + 3] && board[i] == board[i + 6]) {
return board[i] == c ? 1 : -1;
}
}
if (board[4] == Square::Empty) {
return 0;
}
if ((board[4] == board[0] && board[4] == board[8])
|| (board[4] == board[2] && board[4] == board[6])) {
return board[4] == c ? 1 : -1;
}
return 0;
}
int minmax(Square c, unsigned int* counter, unsigned int* pos = NULL)
{
const int currentScore = computeScore(c);
if (currentScore != 0 || isFull()) {
if (counter) {++*counter; }
return currentScore;
}
int bestScore = -10;
for (unsigned int i = 0; i != 9; ++i) {
if (board[i] != Square::Empty) { continue; }
play(i, c);
int score = -minmax(other(c), counter);
if (bestScore < score) {
bestScore = score;
if (pos) { *pos = i; }
}
play(i, Square::Empty);
}
return bestScore;
}
int alphabeta(Square c, int alpha, int beta, unsigned int* counter, unsigned int* pos = NULL)
{
const int currentScore = computeScore(c);
if (currentScore != 0 || isFull()) {
if (counter) {++*counter; }
return currentScore;
}
for (unsigned int i = 0; i != 9; ++i) {
if (board[i] != Square::Empty) { continue; }
play(i, c);
int score = -alphabeta(other(c), -beta, -alpha, counter);
if (beta <= score) {
if (pos) { *pos = i; }
play(i, Square::Empty);
return score;
}
if (alpha < score) {
alpha = score;
if (pos) { *pos = i; }
}
play(i, Square::Empty);
}
return alpha;
}
private:
std::array<Square, 9> board;
};
int main()
{
Board b;
Square c = Square::X;
while (b.computeScore(Square::X) == 0 && b.isFull() == false) {
std::cout << c << " to play" << std::endl;
b.display();
unsigned int counter = 0;
unsigned int pos;
const int s = b.minmax(c, &counter, &pos);
//const int s = b.alphabeta(c, -10, 10, &counter, &pos);
b.play(pos, c);
std::cout << "score for "<< c <<" = " << s << std::endl;
std::cout << "#final boards examined = " << counter << std::endl;
std::cout << "----------------" << std::endl;
c = other(c);
}
std::cout << "Final score for X = " << b.computeScore(Square::X) << std::endl;
b.display();
return 0;
}
Количество «итераций» — это количество проверенных финальных досок.
Другие решения
Других решений пока нет …