在极小极大的最简单版本中,第一个玩家希望最大化他的分数,而第二个玩家希望最小化第一个玩家的分数。由于第一个和第二个玩家都只关心第一个玩家的分数,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
最后,你在and内部有一些问题MaxMove
。当您分配curRating
其中任何一个时,您不应将bestMove
其作为第二个参数传递给MaxMove
or MinMove
。然后它将对手的最佳移动放入bestMove
,这是没有意义的。相反,声明一个opponentsBestMove
对象并将其作为第二个参数传递。(您实际上不会使用该对象,甚至不会在之后查看它的值,但这没关系)。通过该更改,您永远不会为bestMove
within分配任何内容MinMove
,因此您应该在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.
另一种方法利用井字游戏是零和游戏这一事实。换句话说,在游戏结束时,玩家的得分总和将为零。对于两人游戏,这意味着一个玩家的分数将永远是另一个玩家的负数。这对我们来说很方便,因为最小化其他玩家的分数与最大化自己的分数是相同的。因此,我们可以让两个玩家都尝试最大化自己的分数,而不是让一个玩家最大化他的分数,而一个玩家最小化另一个玩家的分数。
改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;
}