In der einfachsten Version von Minimax möchte der erste Spieler seine Punktzahl maximieren, und der zweite Spieler möchte die Punktzahl des ersten Spielers minimieren. Da sowohl der erste als auch der zweite Spieler sich nur um die Punktzahl des ersten Spielers kümmern, sollte EvaluateStaticPosition einen Wert zurückgeben, der angibt, wie gut der Spielstand für den ersten Spieler ist. Wessen Drehung es ist, ist nicht relevant.
int EvaluateStaticPosition(stateT state)
{
if(CheckForWin(state, FIRST_PLAYER))
{
return WINNING_POSITION;
}
if(CheckForWin(state, Opponent(FIRST_PLAYER)))
{
return LOSING_POSITION;
}
return NEUTRAL_POSITION;
}
Jetzt, wenn Sie den Zug wünschen, der für den ersten Spieler am besten ist, rufen Sie MaxMove. Wenn du den richtigen Zug für den zweiten Spieler willst, rufe MinMove an.
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;
}
Schließlich haben Sie einige Probleme innerhalb von MinMove und MaxMove. Wenn Sie curRating in beiden zuweisen, sollten Sie bestMove nicht als zweites Argument an MaxMove oder MinMove übergeben. Es wird dann die Gegner besten Umzug in bestMove setzen, die keinen Sinn macht. Deklarieren Sie stattdessen ein opponentsBestMove-Objekt und übergeben Sie das als zweites Argument. (Sie werden das Objekt tatsächlich nicht benutzen oder nachsehen, aber das ist ok). Mit dieser Änderung weisen Sie bestMove innerhalb MinMove niemals etwas zu, also sollten Sie dies innerhalb des if(curRating < v) Blocks tun.
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;
}
An diesem Punkt sollten Sie eine unschlagbare KI haben!
The final position looks like this:
O | O | X
---+---+---
X | X | O
---+---+---
O | X | X
Cat's game.
Ein alternatives Verfahren sich die Tatsache zunutze, dass nimmt Tic-Tac-Toe-Spiel ein Nullsummen ist. Mit anderen Worten, am Ende des Spiels ist die Summe der Punktzahlen der Spieler gleich Null. Für ein Zwei-Spieler-Spiel bedeutet dies, dass die Punktzahl eines Spielers immer die des anderen Spielers ist. Dies ist für uns praktisch, da das Minimieren der Punktzahl des anderen Spielers dann identisch ist mit der Maximierung des eigenen Spielstandes. Anstatt dass ein Spieler seine Punktzahl maximiert und ein Spieler den Punktestand des anderen Spielers minimiert, können wir einfach beide Spieler versuchen, ihren eigenen Punktestand zu maximieren.
Ändern Sie EvaluateStaticPosition zurück in seine ursprüngliche Form, so dass es eine Punktzahl basierend darauf gibt, wie gut der Boardstatus für den aktuellen Spieler ist.
Löschen MinMove, da wir nur auf Maximierung achten. Schreiben Sie MaxMove so um, dass es den Zug auswählt, der dem Gegner die schlechteste Punktzahl gibt. Die Punktzahl für den besten Zug ist das Negativ des schlechtesten Ergebnisses des anderen Spielers.
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;
}
Da MaxMove für beide Spieler verwendet wird, müssen wir nicht mehr unter den Spielern in der Funktion MiniMax unterscheiden.
moveT MiniMax(stateT state)
{
moveT bestMove;
int i = 0;
i = MaxMove(state, bestMove);
cout<<"i is "<<i<<endl;
return bestMove;
}
Ist der Code, den Sie oben gepostet haben, aktuell? Weil es nicht so aussieht, als müsste es kompilieren. In 'min_move' rufen Sie' max_move' mit drei Argumenten auf, aber max_move kann nur zwei Argumente annehmen. – Kevin
@Kevin: Ups, es ist jetzt aktualisiert. Ich habe versucht, die Tiefe irgendwann zu begrenzen. – motiur
Danke für die Aktualisierung, aber die falsche Zeile ist immer noch da: 'int curValue = max_move (state, depth + 1, bestMove);' Das macht mir Sorgen; Das lässt mich vermuten, dass der Code, den Sie veröffentlichen, nicht der Code ist, den Sie kompilieren. Das macht es für potenzielle Beantworter doppelt schwierig, das Problem zu finden. Wir werden Bugs im geposteten Code identifizieren, die nicht im echten Code enthalten sind, und wir werden keine Fehler im echten Code finden, wenn sie nicht im geposteten Code enthalten sind. – Kevin