Nella versione più semplice di Minimax, il primo giocatore vuole massimizzare il suo punteggio, ed il secondo giocatore vuole ridurre al minimo il punteggio del primo giocatore. Dal momento che sia primo e il secondo giocatore si preoccupano solo di segnare il primo giocatore, EvaluateStaticPosition
dovrebbe restituire un valore che indica quanto è buono il Consiglio di Stato è per il primo giocatore. Di chi è il turno non è rilevante.
int EvaluateStaticPosition(stateT state)
{
if(CheckForWin(state, FIRST_PLAYER))
{
return WINNING_POSITION;
}
if(CheckForWin(state, Opponent(FIRST_PLAYER)))
{
return LOSING_POSITION;
}
return NEUTRAL_POSITION;
}
Ora, quando si desidera che la mossa che è meglio per il primo giocatore, chiamare MaxMove. Quando vuoi la mossa migliore per il secondo giocatore, chiama 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;
}
Infine, avete alcuni problemi all'interno della MinMove
e MaxMove
. quando si assegna curRating
in uno dei due, non si dovrebbe passare nel bestMove
come secondo argomento al MaxMove
o MinMove
. Sarà quindi messo mossa migliore della dell'avversario in bestMove
, che non ha senso. Invece, dichiarare un oggetto opponentsBestMove
e passarlo come secondo argomento. (In realtà non utilizzerai l'oggetto o guarderai il suo valore in seguito, ma va bene). Con questo cambiamento, non hai mai nulla per assegnare bestMove
all'interno MinMove
, così si dovrebbe fare in modo all'interno del blocco 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;
}
A questo punto si dovrebbe avere un'IA imbattibile!
The final position looks like this:
O | O | X
---+---+---
X | X | O
---+---+---
O | X | X
Cat's game.
Un metodo alternativo sfrutta il fatto che tic-tac-toe è un gioco a somma zero. In altre parole, alla fine del gioco, la somma dei punteggi dei giocatori sarà uguale a zero. Per una partita a due giocatori, questo significa che il punteggio di un giocatore sarà sempre il negativo dell'altro giocatore. Questo è conveniente per noi, poiché minimizzare il punteggio dell'altro giocatore è quindi identico a massimizzare il proprio punteggio. Quindi, invece di un giocatore che massimizza il suo punteggio e un giocatore che riduce al minimo il punteggio dell'altro giocatore, possiamo semplicemente fare in modo che entrambi i giocatori tentino di massimizzare il proprio punteggio.
Sostituire EvaluateStaticPosition
nella sua forma originale, in modo da fornire un punteggio in base a quanto è buono lo stato della scheda per il lettore corrente.
int EvaluateStaticPosition(stateT state)
{
if(CheckForWin(state, state.whoseTurn))
{
return WINNING_POSITION;
}
if(CheckForWin(state, Opponent(state.whoseTurn)))
{
return LOSING_POSITION;
}
return NEUTRAL_POSITION;
}
Elimina MinMove
, poiché ci interessa solo massimizzare. Riscrivere MaxMove
in modo che sceglie la mossa che dà l'avversario peggiore punteggio possibile. Il punteggio per la mossa migliore è il negativo del peggior punteggio dell'altro giocatore.
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;
}
Dal MaxMove
viene utilizzato per entrambi i giocatori, non abbiamo più bisogno di distinguere tra i giocatori nella funzione MiniMax
.
moveT MiniMax(stateT state)
{
moveT bestMove;
int i = 0;
i = MaxMove(state, bestMove);
cout<<"i is "<<i<<endl;
return bestMove;
}
Il codice che hai postato sopra è aggiornato? Perché non sembra che dovrebbe compilare. In 'min_move' chiami' max_move' con tre argomenti, ma max_move può solo prendere due argomenti. – Kevin
@ Kevin: Oops, è ora aggiornato. Ho provato a limitare la profondità ad un certo punto. – motiur
Grazie per l'aggiornamento, ma la linea errata è ancora lì: 'int curValue = max_move (stato, profondità + 1, bestMove);' Questo mi fa preoccupare; mi fa sospettare che il codice che stai postando non sia il codice che stai compilando. Ciò rende doppiamente difficile per i potenziali rispondenti individuare il problema. Identificheremo i bug nel codice pubblicato che non sono presenti nel codice reale e non saremo in grado di trovare bug nel codice reale se non sono nel codice pubblicato. – Kevin