Teoria de Jogos por Alda Carvalho - O roubo de estratégia
Eixos de Opinião de Maio de 2021
Alda Carvalho - Docente do Ensino Superior e Investigadora do CEMAPRE/ISEG. (Ver +)
Título: O roubo de estratégia
Neste texto exemplificaremos como o roubo de estratégia pode ser utilizado para analisar alguns jogos, nomeadamente o DENTADA e o QUADRADOS ASSINADOS E QUADRADOS ANÓNIMOS (desafio lançado em Novembro de 2019 aqui).
No jogo DENTADA (CHOMP) a posição inicial é um chocolate com forma rectangular (nxm). O quadradinho no canto inferior esquerdo está envenenado. Considere-se a seguinte posição inicial (5x3) como exemplo.
Uma jogada consiste em escolher um quadradinho e comer esse quadradinho, juntamente com todos os outros que não estejam nem à esquerda nem abaixo dele. Naturalmente, quem tiver de comer o quadradinho envenenado morre e, por consequência, perde o jogo.
Eis um exemplo de um jogo entre a Louise e o Richard, sendo a Louise a começar.
Neste jogo, o Richard perde o jogo por ter de comer o quadradinho envenenado.
É possível utilizar um argumento de roubo de estratégia para provar que o primeiro jogador consegue forçar a vitória. Trata-se de um argumento não constructivo, isto é, pode provar-se a vitória do primeiro jogador, sem que se saiba como a conseguir. Suponhamos que o primeiro jogador tira o quadradinho do canto superior direito. Se essa jogada for uma jogada ganhadora, o primeiro jogador ganha. Se essa jogada não for uma jogada ganhadora, então o segundo jogador tem uma resposta ganhadora contra a remoção do quadradinho do canto superior direito. Mas essa resposta já estava disponível para o primeiro jogador na sua primeira jogada. Logo, também neste caso, se conclui que o primeiro jogador ganha.
Vamos recuperar o jogo QUADRADOS ASSINADOS E QUADRADOS ANÓNIMOS, relembremos as regras antes do desafio.
O jogo PONTOS E QUADRADOS é praticado num pontilhado quadriculado. Alternadamente, cada jogador une dois pontos vizinhos com um segmento horizontal ou vertical. Quando um dos jogadores completa um quadrado, escreve a sua inicial no interior do quadrado e joga outra vez. Sempre que um jogador dispuser de uma jogada que fecha um quadrado, não é obrigado a fazê lo. O objectivo é obter o maior número de quadrados com o seu nome.
As regras do jogo QUADRADOS ASSINADOS E QUADRADOS ANÓNIMOS são exactamente as mesmas do jogo PONTOS E QUADRADOS com uma diferença: sempre que um jogador fecha um ou dois quadrados pode não os assinar para não ter de jogar novamente. No final, quando for efectada a contagem, esses quadrados são neutros. O desafio foi analisar este jogo para qualquer grelha mxn, com o objectivo de determinar se é o primeiro ou o segundo jogador que consegue forçar a vitória.
Em primeiro lugar, observe-se que quem fecha o primeiro quadradinho ganha. Esse facto deve se a um roubo de estratégia. Se, após a jogada que fecha o primeiro quadradinho, quem jogar primeiro não perder pontos na posição resultante, então o quadradinho deve ser assinado para poder continuar a jogar. Isso garante a vitória a quem fecha esse primeiro quadradinho. Por outro lado, se, após a jogada que fecha o primeiro quadradinho, quem jogar primeiro perder pontos na posição resultante, então o quadradinho deve ser deixado anónimo para deixar o adversário jogar numa posição desfavorável. Mais uma vez, isso garante a vitória a quem fecha esse primeiro quadradinho. Em qualquer dos casos, quem fecha o primeiro quadradinho ganha.
Em segundo lugar, vejamos quem pode forçar a conquista do primeiro quadradinho. Em grelhas nxm, com n e m ímpares, o segundo jogador consegue fechar o primeiro quadradinho jogando simetricamente em relação ao ponto central (imagem, à esquerda). Em grelhas nxm, com n ímpar e m par (ou n par e m ímpar), o primeiro jogador consegue fechar o primeiro quadradinho traçando a aresta central horizontal (vertical) na primeira jogada e jogando simetricamente em relação ao ponto central (imagem, ao centro). Em grelhas nxm, com n e m pares, o segundo jogador consegue fechar o primeiro quadradinho jogando simetricamente em relação ao ponto central (imagem, à direita).
Sendo assim, o primeiro jogador ganha se e só se a grelha tiver dimensões nxm, com n ímpar e m par ou n par e m ímpar.