c++ - Tic Tac Toe C++算法调试帮助

Question

请帮助我理解为什么这不起作用。我不知道我的代码是否有错误，或者我的算法是否存在根本性的逻辑缺陷。

我的算法基于极小极大算法，但我放弃了启发式评估函数，转而采用更简单的技术。由于普通 3x3 tic tac toe 的简单性，我只想计算每个潜在 Action 的所有可能游戏结果，并选择“分数”最高的那个。我创建了一个有效移动的“顶级” vector 以及相应“分数”的匹配大小 vector - 即对于该行动之后的每一种可能结果:++ 获胜，-- 失败。

但是，我的移动得分 vector 出现了奇怪的非对称值。虽然即使代码有效，但从逻辑上讲，计算出最多获胜和最少损失的举动可能对诸如 fork 之类的简单策略视而不见吗？我的直觉说是的，但我还没有详细计算出数学。

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

我想如果你让 evaluate 返回分数而不是使用 return-by-reference，你就会明白问题出在哪里。

Evaluate 应该是 minimaxing，但现在我认为由于加法和减法的副作用，它正在对叶节点进行一些奇怪的求和。

为什么总分不对

假设我有板子:

. . O
. . .
. X X

然后 O 只有 一个 步，(block)，因为如果 O 不走，X 的下一步就会赢。然而，有很多游戏路径从 O 开始，然后进行其他移动，O 获胜，例如:

O2 O1 O
.  .  X1
.  X  X

其中数字表示哪一步先到。

所以你看，仅仅得到总和不会给你正确的答案。

我建议将值向上传递到树中的原因是，这会迫使您写出节点的分数作为子节点的函数。现在在您的代码中，函数是求和，在 minimax 中，它是最小值或最大值，具体取决于玩家的回合。