TicTacToe Minimax算法總是返回最低值

-1

我試圖用minimax算法實現TicTacToe AI。TicTacToe Minimax算法總是返回最低值

當輪到AI輪到我時，我打電話給ComputerTurn（它接受棋盤狀態，一個跟蹤方塊是X，O還是空的int整數）。 ComputerTurn然後調用minimax（minimax算法）和win（連續檢查3個）。

當我運行腳本時，算法總是決定返回最低法定遊戲。 IE，只要左上方的方塊（方塊0）可用，它將始終返回它。如果這個廣場被採用，它將返回頂部中間（平鋪1）等

我不知道這裏發生了什麼，我的傳統調試技術（Debug.Log或打印）導致Unity崩潰在許多點我想看看。

void ComputerTurn(int[] board) 
{ 
    int move = -1; 
    int score = -2; 
    int i; 
    for (i = 0; i < 9; ++i) 
    { 
     if (board[i] == 0) 
     { 
      board[i] = 1; 
      int tempScore = -minimax(board, -1); 
      board[i] = 0; 
      if (tempScore > score) 
      { 
       score = tempScore; 
       move = i; 
      } 
     } 
    } 

    board[move] = 1; 
    if (PlayerTurn == 1) 
    { 
     //Draw an O 
     Board[move] = -1; 
    } 
    else 
    { 
     //Draw an X 
     Board[move] = 1; 
    } 
    //Changes to player's turn 
} 

int minimax(int[] board, int player) 
{ 
    int winner = win(board); 
    if (winner != 0) return winner * player; 

    int move = -1; 
    int score = -2;//Losing moves are preferred to no move 
    int i; 
    for (i = 0; i < 9; ++i) 
    {//For all moves, 
     if (board[i] == 0) 
     {//If legal, 
      board[i] = player;//Try the move 
      int thisScore = -minimax(board, player * -1); 
      if (thisScore > score) 
      { 
       score = thisScore; 
       move = i; 
      }//Pick the one that's worst for the opponent 
      board[i] = 0;//Reset board after try 
     } 
    } 
    if (move == -1) return 0; 
    return score; 
} 

int win(int[] board) 
{ 
    //determines if a player has won, returns 0 otherwise. 
    int[,] wins = new int[8, 3] { { 0, 1, 2 }, { 3, 4, 5 }, { 6, 7, 8 }, { 0, 3, 6 }, { 1, 4, 7 }, { 2, 5, 8 }, { 0, 4, 8 }, { 2, 4, 6 } }; 
    int i; 
    for (i = 0; i< 8; ++i) 
    { 
     if (board[wins[i, 0]] != 0 && 
      board[wins[i, 0]] == board[wins[i, 1]] && 
      board[wins[i, 0]] == board[wins[i, 2]]) 
     { 
      return board[wins[i, 2]]; 
     } 
    } 
    return 0; 
}

來源

2017-04-18 3dward3lric

這不是最小值。這是回溯。 – AhmadWabbi

對不起，我使用了錯誤的術語。儘管我的邏輯錯誤仍然存在，但我仍然感到困惑。我無法弄清楚爲什麼它不會返回最佳舉措。 – 3dward3lric

你不能設置一個斷點嗎？ – Neil

編輯：我該如何標記爲已解決

我找出發生了什麼事。

board[move] = 1; 
if (PlayerTurn == 1) 
{ 
    //Draw an O 
    Board[move] = -1; 
} 
else 
{ 
    //Draw an X 
    Board[move] = 1; 
} 
//Changes to player's turn

實際上應該是

Board[move] = 1; 

if (PlayerTurn == 1) 
{ 
    //Draw a Y 
} 
else 
{ 
    //Draw an X 
} 

//Change turn

也有在我是怎麼做我的球員變成一個錯誤。感謝任何關注我的問題的人。

來源

2017-04-18 18:51:53 3dward3lric

它並不總是返回第一個空單元格。例如，嘗試用[0,0,0,1,0,1,1,0,1]位置給它：它不會返回0，它會選擇4。您的實施不包含任何錯誤。

問題在算法中。由於你的體重函數只能導致1，0或-1，你的程序只能看到是否有可能在該回閤中獲勝，但在強力移動（高勝率輸出）和弱勢移動之間沒有任何區別（哪裏可能獲勝，但不太可能）。它可以濾除鬆動，正如您從提供的示例中看到的那樣。

來源

2017-04-18 10:30:29 rs232

TicTacToe Minimax算法總是返回最低值

回答

相關問題