我尝试根据Russel Norvig的《人工智能》书中给出的方法编写井字游戏的极小化极大算法。代码中包含了所有内容，除了如何将最佳移动返回给用户。我努力尝试返回最佳移动，但无法决定何时选择最佳移动。有人能帮帮我吗？

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

附注：有其他用于查找极小化极大值的伪代码。然而，它们仅关注井字游戏，我试图将其扩展到其他游戏。谢谢。

更新：完整代码可在此处找到：http://ideone.com/XPswCl

回答：

在最简单的极小化极大算法版本中，第一位玩家希望最大化自己的得分，而第二位玩家希望最小化第一位玩家的得分。由于第一位和第二位玩家都只关心第一位玩家的得分，因此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对象，并将其作为第二个参数传递。（你实际上不会使用该对象或查看其值，但这没关系）。通过这种更改，你永远不会在MinMove中向bestMove分配任何内容，因此你应该在if(curRating < v)块中这样做。

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

此时，你应该拥有一个不可战胜的人工智能！

最终位置看起来像这样： O | O | X---+---+--- X | X | O---+---+--- O | X | X平局游戏。

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

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