我曾尝试编写 Russel Norvig 关于人工智能的书中给出的 tic-tac-toe 的 minimax 算法。它拥有一切，除了将 bestMove 返回给用户的方法。我正在努力返回 bestMove，但无法决定何时选择 bestMove。帮忙，有人吗？

moveT MiniMax(stateT state)
{
    moveT bestMove;

    max_move(state,bestMove);

    return bestMove;

}

int max_move(stateT state,int & bestMove)
{
    int v = -10000;
    if(GameIsOver(state))
    {
        return EvaluateStaticPosition(state);

    }

    vector<moveT> moveList;
    GenerateMoveList(state, moveList);
    int nMoves = moveList.size();

    for(int i = 0 ; i < nMoves ; i++)
    {
        moveT move = moveList[i];
        MakeMove(state, move);

        int curValue = min_move(state,bestMove);

            if(curValue > v)
            {
              v = curValue;
              bestMove = move;
            }
        RetractMove(state, move);

    }

    return v;

}

int min_move(stateT state, int &bestMove)
{
    int v = 10000;
    if(GameIsOver(state))
    {
      return EvaluateStaticPosition(state);

    }
    vector<moveT> moveList;
    GenerateMoveList(state, moveList);

    int nMoves = moveList.size();

    for(int i = 0 ; i < nMoves; i++)
    {
        moveT move = moveList[i];
        MakeMove(state, move);

        int curValue = max_move(state,depth+1,bestMove);

            if(curValue < v)
            {
              curValue = v;
            }
        RetractMove(state, move);

    }
    return v;
}

P.S.:还有其他伪代码可以找到 minmax 值。然而，他们只专注于井字游戏，我正在尝试将其扩展到其他游戏。谢谢。

更新:完整代码可以在这里找到:http://ideone.com/XPswCl

最佳答案

在 minimax 的最简单版本中，第一个玩家希望最大化他的分数，而第二个玩家希望最小化第一个玩家的分数。 由于第一个和第二个玩家都只关心第一个玩家的分数，EvaluateStaticPosition应该返回一个值，指示第一个玩家的棋盘状态有多好。轮到谁不重要。

int EvaluateStaticPosition(stateT state)
{
        if(CheckForWin(state, FIRST_PLAYER))
        {
                return WINNING_POSITION;
        } 
        if(CheckForWin(state, Opponent(FIRST_PLAYER)))
        {
                return LOSING_POSITION;
        } 
        return NEUTRAL_POSITION;
}

现在，当您想要最适合第一个玩家的移动时，请调用 MaxMove。当您想要对第二个玩家最好的移动时，请调用 MinMove。

moveT MiniMax(stateT state)
{
    moveT bestMove;
    int i = 0;
    if (state.whoseTurn == FIRST_PLAYER){
        i = MaxMove(state, bestMove);
    }
    else{
        i = MinMove(state,bestMove);
    }
    cout<<"i is "<<i<<endl;
    return bestMove;
}

最后，您在 MinMove 内部遇到了一些问题和 MaxMove .当你分配 curRating在任何一个中，你都不应该传递 bestMove作为 MaxMove 的第二个参数或 MinMove .然后它会将对手的最佳着法放入bestMove。 ，这没有意义。相反，声明一个 opponentsBestMove对象并将其作为第二个参数传递。 (您实际上不会使用该对象，甚至不会在之后查看它的值，但这没关系)。通过该更改，您永远不会为 bestMove 分配任何内容在 MinMove 内, 所以你应该在 if(curRating < v) 里面这样做 block 。

int MaxMove(stateT state, moveT &bestMove)
{
        if(GameIsOver(state))
        {
            return EvaluateStaticPosition(state);
        }
        vector<moveT> moveList;
        GenerateMoveList(state, moveList);
        int nMoves = moveList.size();
        int v = -1000;
        for(int i = 0 ;i<nMoves; i++)
        {
                moveT move = moveList[i];
                MakeMove(state, move);
                moveT opponentsBestMove;
                int curRating = MinMove(state, opponentsBestMove);
                if (curRating > v)
                {
                        v = curRating;
                        bestMove = move;
                }
                RetractMove(state, move);
        }
        return v;

}
int MinMove(stateT state,  moveT &bestMove)
{
        if(GameIsOver(state))
        {
                return EvaluateStaticPosition(state);
        }
        vector<moveT>moveList;
        GenerateMoveList(state, moveList);
        int nMoves = moveList.size();
        int v = 1000;
        for(int i = 0 ; i<nMoves; i++)
        {
                moveT move = moveList[i];
                MakeMove(state , move);
                moveT opponentsBestMove;
                int curRating = MaxMove(state,opponentsBestMove);
                if(curRating < v)
                {
                        v = curRating;
                        bestMove = move;
                }
                RetractMove(state, move);
        }
        return v;
}

此时您应该拥有一个无与伦比的 AI!<​​>

The final position looks like this:

 O | O | X
---+---+---
 X | X | O
---+---+---
 O | X | X

Cat's game.

另一种方法利用井字游戏是零和游戏这一事实。换句话说，在游戏结束时，玩家的分数总和将为零。对于两人游戏，这意味着一个玩家的分数将始终为另一个玩家的负值。这对我们来说很方便，因为最小化其他玩家的分数等同于最大化自己的分数。因此，不是一个玩家最大化他的分数，一个玩家最小化另一个玩家的分数，我们可以让两个玩家都尝试最大化他们自己的分数。

更改 EvaluateStaticPosition回到原来的形式，这样它就可以根据当前玩家的棋盘状态给出一个分数。

int EvaluateStaticPosition(stateT state)
{
        if(CheckForWin(state, state.whoseTurn))
        {
                return WINNING_POSITION;
        }
        if(CheckForWin(state, Opponent(state.whoseTurn)))
        {
                return LOSING_POSITION;
        }
        return NEUTRAL_POSITION;
}

删除MinMove ，因为我们只关心最大化。 重写 MaxMove以便它选择给对手最差分数的着法。最佳着法的得分是对方最差得分的负值。

int MaxMove(stateT state, moveT &bestMove)
{
        if(GameIsOver(state))
        {
                return EvaluateStaticPosition(state);
        }
        vector<moveT> moveList;
        GenerateMoveList(state, moveList);
        int nMoves = moveList.size();
        int v = -1000;
        for(int i = 0 ;i<nMoves; i++)
        {
                moveT move = moveList[i];
                MakeMove(state, move);
                moveT opponentsBestMove;
                int curRating = -MaxMove(state, opponentsBestMove);
                if (curRating > v)
                {
                        v = curRating;
                        bestMove = move;
                }
                RetractMove(state, move);
        }
        return v;

}

自 MaxMove用于两个玩家，我们不再需要在 MiniMax 中区分玩家功能。

moveT MiniMax(stateT state)
{
    moveT bestMove;
    int i = 0;
    i = MaxMove(state, bestMove);
    cout<<"i is "<<i<<endl;
    return bestMove;
}

关于c++ - 返回 tic tac toe 的 minimax 算法中的最佳 Move，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13523050/