Problema
Minimax è il modo in cui i programmi di gioco scelgono le mosse: supponi che entrambi i giocatori giochino in modo perfetto, assegna un punteggio a ogni partita finita e riporta i punteggi verso l'alto nell'albero di gioco. Il giocatore di turno sceglie il figlio con il punteggio più alto per sé.
La scacchiera è una stringa di 9 caratteri letta riga per riga (indici 0-8), con "X", "O" o "." per una casella vuota. X muove sempre per primo, quindi tocca a X quando entrambi hanno lo stesso numero di segni, altrimenti tocca a O.
Assegna il punteggio a una partita finita dal punto di vista del giocatore di turno: +1 per una vittoria, 0 per un pareggio, -1 per una sconfitta. Restituisci la casella vuota la cui mossa ha il miglior punteggio minimax; se più caselle sono ugualmente buone, restituisci l'indice minore.
Implementa best_move(board).
Input
board: Una posizione valida in cui nessuno ha ancora vinto e almeno una casella è vuota.
Output
Restituisci l'indice (0-8) della mossa migliore.
Vincoli
board ha esattamente 9 caratteri, ciascuno X, O o .
La posizione può verificarsi in una partita reale, nessuno ha vinto e almeno una casella è vuota
Esempi
Input:
board = "XX.OO...."
Output atteso:
expected = 2Input:
std::string board = "XX.OO....";
Output atteso:
long long expected = 2;Input:
string board = "XX.OO....";
Output atteso:
long expected = 2;Spiegazione
X e O hanno due segni ciascuno, quindi muove X. Giocare in 2 completa la riga in alto e vince subito (+1).
Input:
board = "X..OO...X"
Output atteso:
expected = 5Input:
std::string board = "X..OO...X";
Output atteso:
long long expected = 5;Input:
string board = "X..OO...X";
Output atteso:
long expected = 5;Spiegazione
Muove X. O minaccia di completare la riga centrale in 5. Ogni altra mossa fa vincere O (-1), mentre bloccare in 5 porta a un pareggio (0), quindi la risposta è 5.
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.