Negamax 구현이 tic-tac-toe와 함께 작동하지 않는 것으로 보입니다

Question

나는 Negamax를 구현했습니다. 알파/베타 가지 치기를 포함하는 wikipedia에서 찾을 수 있습니다.

그러나 잃어버린 움직임을 선호하는 것 같습니다. 이것은 내 지식에 무효 한 결과입니다.

게임은 Tic-Tac-Toe입니다. 게임 플레이의 대부분을 추상화 했으므로 알고리즘 내에서 오류를 발견하기가 쉽습니다. (아무것도가 승리 또는 종료하기 위해 수행 할 수 없습니다이 함정에 수행 보장 된 손실을 일으키는 원인이

이

O 
X__ 
___ 
___ 

알고리즘은 0, 1에서 조각을 배치 할 선택 :

#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; 
} 

이 입력을주기 그리기) :

XO_ 
X__ 
___ 

저는 게임 구현이 정확하다고 확신하지만 알고리즘은 잘 유지되어야합니다.

편집 :evaluate 및 nextMove으로 업데이트되었습니다.

는 EDIT2 : 고정 첫 번째 문제, 여전히

Answer 1

귀하의 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) 점수를 반환하는 것은 잘못된 것입니다.

Answer 2

isWon은 플레이어의 승패에 대해 true를 반환합니다. 그건 도움이 될 수 없어요.

Answer 3

플레이어의 사용으로 재미있는 일이있는 것 같습니다.

최상위 루프가 "board.do_move (* it, 1);"을 호출합니다. 플레이어 = 1 인 Negamax를 호출합니다.

그러면 negamax는 "board.do_move (* it, player);"를 호출하여 첫 ​​번째 플레이어가 실제로 2 개의 동작을 얻는 것처럼 보입니다.