O jogo da velha 3D e as conversas de corredor
Eu encontrei uma professora, doutora em computação, que curiosamente foi minha caloura na época que eu estava no mestrado e fui monitor de uma disciplina na USP que se chamava MAC 122, que era a primeira matéria que encarava algoritmos de verdade e estrutura de dados.
E ela veio me perguntar se eu lembrava de uma competição que eu fiz de jogo da velha 3D, que era o último exercício-programa que deveria ser entregue da disciplina. E era uma época que eu estava muito animado com Java e essa brincadeira de jogos um combatendo o outro, num momento que inteligência artificial era algo muito rudimentar, ainda mais com pouco acesso computacional.
Enfim, o que ela relatou é de como era interessante você parar para pensar na estratégia de um jogo que você nunca tinha visto, no caso o jogo da velha 3D, e depois colocar um computador para batalhar contra o outro. A gente criou um formato de output padrão e com isso, no último dia de aula, a gente colocou uma disputa para ver quem venceria. E o algoritmo precisava aceitar N dimensões.
Ela disse que foi uma experiência muito interessante porque causava essa conversa entre os corredores de ideias de estratégia. E ela também disse que hoje, entre alunos e alunas de computação, isso fica mais escasso porque, por mais que já no Google houvesse estratégias para jogos como esse, tudo se acelerou com a inteligência artificial, onde o acesso fica ainda mais fácil e você cai rapidamente para a conclusão. Não há mais uma troca entre as pessoas e uma discussão, que certamente é um esforço produtivo, que traz experiência e conhecimento para quem está aprendendo.
Eu me lembro vagamente desses exercícios. Isso já deve fazer uns 23, 24 anos. Mas tenho na memória uma imagem das bolinhas do jogo da velha caindo de maneira animada, usando o Java 3D, que era uma biblioteca que tentou prometer algo para jogos da época, mas obviamente não faria sentido nenhum.
Percebo como eu sempre estive nessa parte de inteligência de jogos, jogos 3D, apesar de que nunca me aprofundei em nenhuma dessas questões.
Atualização: encontrei uma versão de 2010 desse exercício-programa, ainda na MAC 122, com o torneio entre os programas dos alunos no fim do semestre.
Atualização 2: dias depois dessa nota, tive a felicidade de receber essa mensagem do Sérgio Lopes, meu sócio e amigo, que estava em 2003 nessa turma na faculdade. Inclusive o enunciado inteiro do exercício segue no ar no site do IME, e deixo uma cópia abaixo para registro.
MAC 122 - Princípios de Desenvolvimento de Algoritmos
EP 1: Jogo da Velha 3D - entrega 18 de setembro de 2003
Monitor: Paulo E. Silveira
O objetivo deste exercício-programa é fazer um programa que jogue o jogo da velha tridimensional que apareceu na Maratona de Programação 2003. Abaixo o jogo é descrito.
O jogo é feito de n × n pinos, dispostos em forma de uma matriz quadrada. Cada pino tem espaço para receber n bolinhas das duas cores (azuis e brancas). Como no jogo da velha tradicional o objetivo é conseguir uma seqüência completa (em qualquer direção) de n bolinhas da mesma cor. Note que ao colocar uma bolinha num dos pinos ela necessariamente cai até chegar ao primeiro nível vazio por causa da gravidade. As brancas sempre começam. Na figura abaixo mostramos uma situação do jogo em que as azuis ganharam.
A estratégia do seu programa será baseada na tentativa de todas as possibilidades. Seu programa deverá testar todas as possíveis jogadas, e para cada uma delas, todas as possíveis respostas do oponente, e para cada uma, todas as suas possíveis opções, e assim por diante. O usuário poderá definir no início do jogo um nível em que seu programa jogará, que é o número de jogadas do oponente que ele preverá. Assim, no nível 0 o seu programa apenas testa as suas possibilidades; no nível 1, testa suas possibilidades, para cada uma as possíveis respostas e para cada uma suas opções; e assim por diante. A implementação da estratégia deverá usar uma pilha, como visto em sala de aula.
Como a estratégia é fixa, os programas vão se diferenciar pela análise que fizerem do tabuleiro para escolher sua jogada. Caprichem, pois, é claro, o melhor programa receberá um grande prêmio!!
Para determinar o melhor jogador vamos organizar um campeonato. Seu programa deverá estar preparado para jogar com as brancas ou as azuis (dado através da chamada do programa, juntamente com o nível e o tamanho do tabuleiro), e a seqüência de jogadas do seu adversário será dada através da entrada padrão, uma jogada por linha (coordenadas x e y). Da mesma forma, seu programa deverá dar como saída a coordenada que está jogando na saída padrão. Maiores detalhes serão dados no fórum da disciplina.
Citados neste texto: USP · Sérgio Lopes · Google