Problema
Minimax es la forma en que los programas de juegos eligen jugadas: supón que ambos jugadores juegan perfectamente, puntúa cada partida terminada y sube las puntuaciones por el árbol de juego. El jugador al que le toca elige el hijo con la puntuación más alta para sí mismo.
El tablero es una cadena de 9 caracteres leída fila a fila (índices 0-8), con "X", "O" o "." para una casilla vacía. X siempre empieza, así que le toca a X cuando ambos tienen el mismo número de marcas y a O en caso contrario.
Puntúa una partida terminada desde el punto de vista del jugador al que le toca: +1 si gana, 0 si empata, -1 si pierde. Devuelve la casilla vacía cuya jugada tenga la mejor puntuación minimax; si varias son igual de buenas, devuelve el índice menor.
Implementa best_move(board).
Entrada
board: Una posición válida en la que nadie ha ganado todavía y hay al menos una casilla vacía.
Salida
Devuelve el índice (0-8) de la mejor jugada.
Restricciones
board tiene exactamente 9 caracteres, cada uno X, O o .
La posición puede darse en una partida real, nadie ha ganado y hay al menos una casilla vacía
Ejemplos
Entrada:
board = "XX.OO...."
Salida esperada:
expected = 2Entrada:
std::string board = "XX.OO....";
Salida esperada:
long long expected = 2;Entrada:
string board = "XX.OO....";
Salida esperada:
long expected = 2;Explicación
X y O tienen dos marcas cada uno, así que juega X. Jugar en 2 completa la fila superior y gana al instante (+1).
Entrada:
board = "X..OO...X"
Salida esperada:
expected = 5Entrada:
std::string board = "X..OO...X";
Salida esperada:
long long expected = 5;Entrada:
string board = "X..OO...X";
Salida esperada:
long expected = 5;Explicación
Juega X. O amenaza con completar la fila del medio en 5. Cualquier otra jugada deja ganar a O (-1), mientras que bloquear en 5 lleva al empate (0), así que la respuesta es 5.
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Determina de quién es el turno según los conteos de X y O, y luego evalúa recursivamente cada movimiento legal.
Pista 2
Asigna puntuación a los tableros terminales desde la perspectiva del jugador actual y elige el movimiento que maximice ese valor.
Pista 3
Si varios movimientos empatan, conserva el primer índice de celda vacía, y asegúrate de detectar las victorias antes de considerar más movimientos.
Complejidad esperada
tiempo O(9!), espacio extra O(9)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.