Algoritmos recursivos: jogos

Esta página foi extraída (com algumas modificações) do capítulo 6, seção 6.2, do livro de Eric Roberts. O capítulo discute algoritmos que jogam jogos contra o usuário. O capítulo ilustra o poder da recursão.

Um programa que joga nim (= "resta um")

Dois jogadores (um deles é o computador). Treze moedas na mesa. Em cada jogada, o jogador da vez retira 1, 2 ou 3 moedas da mesa. O último jogador a jogar perde o jogo.

Cada "posição" é caracterizada pelo número de moedas na mesa (variável nCoins). Cada posição pode ser boa ou ruim (para o jogador que deve fazer a próxima jogada). O par de funções que decide se uma posição é boa ou ruim é "mutuamente recursivo": a primeira função chama a segunda e a segunda chama a primeira.

// Constantes // ---------- // IntialCoins: número inicial de moedas na pilha // MaxTake: número máximo de moedas que pode ser retirado // em uma jogada // NoGoodMove: sentinela para indicar que não há uma jogada // boa a partir da posição corrente #define InitialCoins 13 #define MaxTake 3 #define NoGoodMove -1 // A função abaixo recebe um número nCoins >= 2 de moedas e // devolve uma jogada (isto é, número de moedas a retirar) // que seja boa. Uma jogada é boa se deixa o adversário em // uma posição ruim. Se tal jogada não existir, a função // devolve a constante NoGoodMove. // int FindGoodMove (int nCoins) { int nTaken; for (nTaken = 1; nTaken <= MaxTake; nTaken++) if (IsBadPosition( nCoins - nTaken)) return nTaken; return NoGoodMove; } // Esta função recebe um número nCoins >= 1 e devolve TRUE // se nCoins é uma posição ruim. Uma posição é ruim se não // existe uma boa jogada a partir dela. Se nCoins é 1 então // a posição é obviamente ruim. // bool IsBadPosition( int nCoins) { if (nCoins == 1) return TRUE; return FindGoodMove( nCoins) == NoGoodMove; }

Eis o programa completo do jogo:

// Este programa simula o jogo de nim. O jogo envolve dois // jogadas alternadas de dois jogadores. O jogo começa com // uma pilha de InitialCoins (usualmente 13) moedas na mesa. // Cada jogada consiste em retirar entre 1 e MaxTake // (usualmente 3) moedas da pilha. O jogador que retirar // a última moeda perde. Neste programa, o jogador humano // joga contra o computador; o humano é sempre o primeiro // a jogar. // Tipos de dados // -------------- // bool: tipo de dados booleano // playerT: de quem é a vez? typedef enum {FALSE, TRUE} bool; typedef enum {Human, Computer} playerT; // Protótipo de funções // -------------------- #include <stdio.h> #include <string.h> int FindGoodMove( int); bool IsBadPosition( int); int GetUserMove( int); int ChooseComputerMove( int); // Código do programa // ------------------ int main( void) { int nCoins, nTaken; playerT whoseTurn; nCoins = InitialCoins; whoseTurn = Human; while (nCoins > 1) { printf( "Há %d moedas na pilha.\n", nCoins); switch (whoseTurn) { case Human: nTaken = GetUserMove( nCoins); whoseTurn = Computer; break; case Computer: nTaken = ChooseComputerMove( nCoins); printf( "Eu pego %d moeda%s.\n", nTaken, (nTaken == 1) ? "" : "s"); whoseTurn = Human; break; } nCoins -= nTaken; } if (nCoins == 0) { printf( "Você pegou a última moeda e perdeu.\n"); } else { printf( "Sobrou uma só moeda.\n"); switch (whoseTurn) { case Human: printf( "Eu ganhei.\n"); break; case Computer: printf( "Eu perdi.\n"); break; } } return 0; } // A função abaixo recebe o número nCoins de moedas na // pilha e devolve o número de moedas que o jogador // humano decidiu retirar. // int GetUserMove( int nCoins) { int nTaken, limit; while (TRUE) { printf( "\nQuantas moedas você quer? "); scanf( "%d", &nTaken); if (nTaken > 0 && nTaken <= MaxTake && nTaken <= nCoins) break; limit = (nCoins < MaxTake) ? nCoins : MaxTake; printf( "Escolha número entre 1 e %d.\n", limit); printf( "Há %d moedas na pilha.\n", nCoins); } return nTaken; } // Esta função recebe o número nCoins de moedas na pilha // e devolve uma boa jogada. Se não houver uma boa jogada // boa, a função devolve 1 (para que o adversário tenha // mais oportunidades de cometer um erro). // int ChooseComputerMove( int nCoins) { int nTaken; nTaken = FindGoodMove( nCoins); if (nTaken == NoGoodMove) nTaken = 1; return nTaken; }

Consumo de tempo

O programa acima é muito lento. Isso acontece porque o computador examina todos os possíveis jogos para escolher uma boa jogada (e repete esse processo em cada iteração). Comece o jogo com 45 moedas no lugar das 13 para sentir esse efeito!

Na verdade, o tempo absoluto é secundário (bastaria trocar o meu computador por outro mais rápido). É muito mais importante a relação entre o consumo de tempo e o parâmetro InitialCoins. Um pouco de experimentação mostra que o consumo de tempo do programa acima cresce explosivamente em função de InitialCoins.

Mas o caráter recursivo do par de função  FindGoodMove, IsBadPosition  não é o culpado por essa lentidão. O programa seria igualmente lento se fosse escrito de maneira iterativa.

Exercícios

1. Compile e use o programa.

2. Faça uma tabela do consumo de tempo da primeira jogada do computador para InitialCoins no intervalo [30..45]. Use o seu relógio de pulso para medir o tempo de resposta do computador.

3. Escreva um programa um pouco mais eficiente da seguinte maneira. Faça um pré-processamento para construir uma tabela de jogadas boas: para cada número n de moedas na mesa, a tabela deve fornecer uma jogada boa (ou a indicação de que não existe jogada boa).

4. O algoritmo acima usa "força bruta" calcular a função IsBadPosition (o algoritmo explora todas as possibilidades).  Invente um algoritmo melhor, que decide se a posição nCoins é ruim com base em certas operações aritméticas sobre o número nCoins.