井字遊戲C++算法調試幫助

Question

請幫我理解爲什麼這不起作用。我不知道我的代碼中是否存在錯誤，或者我的算法是否存在根本上邏輯上的缺陷。

我的算法基於minimax，但我已經放棄了一個更簡單的技術的啓發式評估函數。由於簡單的3x3 tic tac tac腳趾的簡單性，我只想計算每個潛在動作的所有可能的遊戲結果，並選擇具有最高'分數'的那個。我創建了一個有效動作的「頂級」矢量，以及一個匹配大小的矢量，用於他們相應的「分數」 - 即.e。對於此舉之後的每一個可能的結果：++獲勝並且 - 損失。

然而，我的移動分數矢量變得奇怪的非對稱值。儘管代碼起作用，但從邏輯的角度來看，可能導致大部分勝利和最少損失的舉措，對於像叉子這樣的簡單策略而言是盲目的？我的直覺說是，但我沒有詳細計算出數學。

char board [9] = { '.','.','.','.','.','.','.','.','.' }; 

int com_turn(int turn) 
    { 
    char player=COM; // keeps track of current player 

    cout<<"Computer turn. \n"; 

    vector<int> moves = get_valid_moves(board); // top level move list 
    vector<int> m_scores (moves.size(), 0); // top level move scores 

    for (int m=0; m < moves.size(); m++) // eval each top level move 
    { 
     board[moves[m]] = player; // do move 

     evaluate(board, turn, &m_scores[m], player); 
     cout<< m_scores[m] <<' '; // for debugging 

     board[moves[m]]='.'; // undo move 
    } 

    int bestmove; 
    for (int i=0; i < moves.size(); i++) // find best score 
    { 
     bestmove = max(bestmove, m_scores[i]); 
    } 
    for (int i=0; i < moves.size(); i++) // match to best move 
    { 
     if (bestmove == m_scores[i]) 
     { 
      bestmove = moves[i]; 
      break; 
     } 
    } 

    board[bestmove]=COM; // finally make com move 
    print_board(); 
} 

vector<int> get_valid_moves(char *board) 
{ 
    vector<int> vmoves; 
    for (int i=0; i < 9; i++) 
    { 
     if (board[i]=='.') vmoves.push_back(i); 
    } 
    return vmoves; 
} 


void evaluate(char *board, int turn, int *mscore, char player) 
{ 
    if (check_win(board)) 
    { 
     (player==HUMAN)? *mscore -= 1: *mscore += 1; 
     return; 
    } 
    if (turn > 9) return; 

    vector<int> child_moves = get_valid_moves(board); 
    if (child_moves.size() < 1) return; 

    (player==COM)? player=HUMAN: player=COM; // switch player 

    for (int m=0; m < child_moves.size(); m++) 
    { 
     board[child_moves[m]] = player; // do move 

     evaluate(board, ++turn, mscore, player); 

     board[child_moves[m]]='.'; // undo move 
    } 
} 

Answer 1

我想你會看到問題出在哪裏，如果你讓評估返回分數而不是使用通過引用返回。

評估應該是最小化，但現在我認爲它正在做一些奇怪的葉節點總和，因爲增加和減少的副作用。

爲什麼分數相加是不正確的

假設我有董事會：

. . O 
. . . 
. X X 

然後Ø只有一個移動，（塊），因爲X的下一步行動將贏得如果O沒有成功。不過，也有很多的遊戲路徑即開始在澳進行其他動作，帶O獲勝，如：

O2 O1 O 
. . X1 
. X X 

，其中數字表示該舉動是第一。

所以你看，只是得到總和是不會給你正確的答案。

我推薦將值傳遞給樹的原因是，這迫使你寫出節點上的分數與孩子的函數。在你的代碼中，函數是總和，在minimax中，它是最小值或最大值，取決於玩家的回合。