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.
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.