c – 为tictactoe返回minimax算法中的bestMove

我试图在Russel Norvig的人工智能书中给出了用于井字游戏的极小极大算法.它拥有除了将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对象并将其作为第二个参数传递. (您实际上不会使用该对象,甚至不会在之后查看其值,但这没关系).通过该更改,您永远不会在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;
}

此时你应该有一个无与伦比的AI！

The final position looks like this:
 
 O | O | X
---+---+---
 X | X | O
---+---+---
 O | X | X
 
Cat's game.

另一种方法利用了tic-tac-toe是零和游戏的事实.换句话说,在游戏结束时,玩家的得分总和将等于零.对于双人游戏,这意味着一个玩家的得分将始终是另一个玩家的得分.这对我们来说很方便,因为最小化其他玩家的分数与最大化自己的分数相同.因此,不是一个玩家最大化他的分数而一个玩家最小化另一个玩家的分数,我们可以让两个玩家都试图最大化他们自己的分数.

将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,move);
                moveT opponentsBestMove;
                int curRating = -MaxMove(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 – 为tictactoe返回minimax算法中的bestMove

解决方法

猜你在找的C&C++相关文章