Problema
Minimax é como os programas de jogos escolhem jogadas: suponha que os dois jogadores jogam perfeitamente, dê uma pontuação a cada partida terminada e suba as pontuações pela árvore de jogo. O jogador da vez escolhe o filho com a maior pontuação para si.
O tabuleiro é uma string de 9 caracteres lida linha por linha (índices 0-8), com "X", "O" ou "." para uma casa vazia. X sempre começa, então é a vez de X quando os dois têm o mesmo número de marcas, e a vez de O caso contrário.
Pontue uma partida terminada do ponto de vista do jogador da vez: +1 por vitória, 0 por empate, -1 por derrota. Retorne a casa vazia cuja jogada tem a melhor pontuação minimax; se várias forem igualmente boas, retorne o menor índice.
Implemente best_move(board).
Entrada
board: Uma posição válida em que ninguém venceu ainda e há pelo menos uma casa vazia.
Saída
Retorne o índice (0-8) da melhor jogada.
Restrições
board tem exatamente 9 caracteres, cada um X, O ou .
A posição pode ocorrer em uma partida real, ninguém venceu e há pelo menos uma casa vazia
Exemplos
Entrada:
board = "XX.OO...."
Saída esperada:
expected = 2Entrada:
std::string board = "XX.OO....";
Saída esperada:
long long expected = 2;Entrada:
string board = "XX.OO....";
Saída esperada:
long expected = 2;Explicação
X e O têm duas marcas cada, então é a vez de X. Jogar em 2 completa a linha de cima e vence na hora (+1).
Entrada:
board = "X..OO...X"
Saída esperada:
expected = 5Entrada:
std::string board = "X..OO...X";
Saída esperada:
long long expected = 5;Entrada:
string board = "X..OO...X";
Saída esperada:
long expected = 5;Explicação
É a vez de X. O ameaça completar a linha do meio em 5. Qualquer outra jogada deixa O vencer (-1), enquanto bloquear em 5 leva ao empate (0), então a resposta é 5.
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Determine de quem é a vez a partir das contagens de X e O e então avalie recursivamente cada jogada legal.
Dica 2
Dê score aos tabuleiros terminais da perspectiva do jogador atual e escolha a jogada que maximiza esse valor.
Dica 3
Se várias jogadas empatarem, mantenha o menor índice de célula vazia, e garanta que vitórias sejam detectadas antes de considerar outras jogadas.
Complexidade esperada
tempo O(9!), espaço extra O(9)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.