C++ Minmax Failing

Question

Я работаю над этим так долго, что это уже не смешно. Я пытаюсь реализовать Minmax на Tic Tac Toe, и, хотя я получил несколько версий AI, которые делают разумные начальные шаги, я никогда не смогу сделать тот, который никогда не теряет.

Одной из проблем, которые я не могу разобраться, является эвристическое значение. В настоящий момент он возвращается как -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 часов, и это кажется такой простой задачей, не может узнать, что случилось

Answer 1

После кода может помочь вам:

(Bonus: Alphabeta с менее чем 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; 
} 

Счетчик «итераций» - это количество проверенных досок.