Exemplo de Árvores de Jogos em C: Avaliação de Movimentos no Jogo da Velha

398 Estruturas de Dados Usando C Cap 5 56 UM EXEMPLO ÁRVORES DE JOGOS Uma aplicação de árvores destinase à execução de jogos por computador Ilustraremos essa aplicação escrevendo um programa em C para determinar o melhor movimento no jogodavelha a partir de determinada posição do tabuleiro Suponha que exista uma função evaluate que aceite uma posição do tabuleiro e uma indicação de um jogador X ou O e retorne um valor numérico que representa quão boa é essa posição para o jogador quanto maior o valor retornado por evaluate melhor a posição Evidentemente uma posição vencedora resulta no maior valor possível e uma posição perdedora no menor valor Um exemplo dessa função de avaliação para o jogodavelha é o número de fileiras colunas e diagonais que permanecem abertas para um jogador menos o número de posições abertas para seu oponente exceto pelo fato de que o valor 9 seria retornado para uma posição ganhadora e 9 para uma posição perdedora Essa função não prevê nenhuma das posições do tabuleiro que possam resultar a partir da atual posição ela simplesmente avalia uma posição estática do tabuleiro Dada uma posição do tabuleiro o melhor movimento seguinte pode ria ser determinado considerando todos os movimentos possíveis e posições resultantes O movimento selecionado deve ser aquele que resulte na posição do tabuleiro com a avaliação mais alta Entretanto essa análise não resulta necessariamente na melhor jogada A Figura 561 ilustra uma posição e as cinco jogadas possíveis que X pode fazer a partir dessa posição A aplicação da função de avaliação recémdescrita nas cinco posições resultantes resulta nos valores apresentados Quatro movimentos resultam na mesma avaliação máxima embora três deles sejam distintamente inferiores ao quarto A quarta posição resulta em vitória certa de X enquanto as outras três podem ser empatadas por O Na realidade a jogada que resulta na menor avaliação é tão eficiente ou melhor do que os movimentos que resultam numa avaliação mais alta Portanto a função de avaliação estática não é eficiente o bastante para prever o resultado do jogo Uma função de avaliação mais eficiente poderia ser facilmente produzida para o jogodavelha mesmo pelo método de força bruta de listar todas as posições e a resposta correta mas a maioria dos jogos é complexa demais para os avaliadores estáticos determinarem a melhor resposta Cap 5 Arvores 399 Vamos supor que fosse possível prever várias jogadas Sendo assim a opção de um movimento poderia ser consideravelmente aprimorada Defina o nível de previsões como o número de futuros movimentos a ser conside rado A partir de qualquer posição é possível formar uma árvore das posições do tabuleiro que possam resultar de cada jogada Essa árvore é chamada árvore do jogo A árvore do jogo para a posição de abertura do jogodavelha com um nível de previsão igual a 2 é ilustrada na Figura 561 Na verdade existem outras posições mas pelas considerações de simetria essas são efetivamente idênticas às posições mostradas Observe que o nível máximo chamado profundidade dos nós nessa árvore é igual ao nível de previsões Designemos o jogador que deverá fazer um movimento na posição de jogo da raiz como mais e seu oponente como menos Tentaremos descobrir a melhor jogada de mais a partir da posição de jogo da raiz Os nós restantes da árvore podem ser designados como nós de mais ou nós de menos dependendo do jogador que deverá fazer o movimento a partir da posição desse nó Cada nó da Figura 562 é marcado como um nó de mais ou como um nó de menos Figura 561 Suponha que as posições de jogo de todos os filhos de um nó de mais tenham sido avaliadas para o jogador mais Sendo assim mais deve escolher a jogada que resulta na avaliação máxima Conseqüentemente o valor de um nó de mais para o jogador mais é o máximo dos valores de seus filhos Por outro lado assim que mais se movimentar menos selecionará o movi mento que resulta na avaliação mínima para o jogador mais Dessa forma o valor de um nó de menos para o jogador mais é o mínimo dos valores de seus filhos 2 2 2 2 1 x o X o X o X X X o X X X o o X o X X o o X o X X X o X o Figura 562 Uma árvore de jogo para o jogodavelha 400 Estruturas de Dados Usando C Cap 5 Cap 5 Árvores 401 Portanto para determinar a melhor jogada para o jogador mais a partir da raiz as posições nas folhas precisam ser avaliadas para o jogador mais usando uma função de avaliação estática Esses valores são então deslocados para cima na árvore de jogo atribuindose a cada nó de mais o máximo dos valores de seus filhos e a cada nó de menos o mínimo dos valores de seus filhos partindose da premissa de que menos selecionará o pior movimento para mais O valor atribuído por esse processo a cada nó da Figura 562 aparece nessa figura logo abaixo do nó O movimento que mais deve selecionar dada a posição do tabuleiro no nó da raiz é aquele que maximiza seu valor Sendo assim a jogada de abertura de X deve ser o quadrado do meio conforme ilustrado na Figura 562 A Figura 563 ilustra a determinação da melhor resposta de O Observe que a designação de mais e menos depende do movimento de quem está sendo calculado Dessa forma na Figura 562 X é designado como mais enquanto na Figura 563 O é designado como mais Ao aplicar a função de avaliação estática numa posição do tabuleiro é calculado o valor da posição para o jogador designado como mais Esse método é chamado método minimax porque à medida que a árvore é escalada as funções máximas e mínimas são aplicadas alternativamente Figura 563 Computando a resposta de O 402 Estruturas de Dados Usando C Cap 5 A melhor jogada para um jogador a partir de dada posição pode ser determinada pelo primeiro formando a árvore de jogo e aplicando uma função de avaliação estática às folhas Esses valores são em seguida deslocados árvore acima aplicando o mínimo e o máximo nos nós de menos e de mais respectivamente Cada nó da árvore de jogo deve incluir uma representação do tabuleiro e uma indicação de um nó de mais ou de um nó de menos Os nós podem portanto ser declarados por struct nodetype char board33 int turn struct nodetype son struct nodetype next typedef struct nodetype NODEPTR pboardij tem o valor X O ou dependendo de o quadrado na fileira i e coluna j desse nó estar ocupado por um dos jogadores ou estar desocupado pturn tem o valor 1 ou 1 dependendo de o nó ser um nó de mais ou de menos respectivamente Os dois campos restantes do nó são usados para posicionálo dentro da árvore pson aponta para o filho mais velho do nó e pnext aponta para seu próximo irmão mais novo Presumimos que a declaração anterior seja global que uma lista disponível de nós tenha sido estabelecida e que rotinas getnode e freenode apropriadas tenham sido escritas A função em C nextmovebrd player looklevel newbrd calcula a melhor jogada seguinte brd é um vetor de 3 por 3 representando a atual posição do tabuleiro player é X ou O dependendo do movimento de quem está sendo calculado observe que no jogodavelha o valor de player pode ser computado a partir de brd de modo que esse parâmetro não é estritamente necessário e looklevel é o nível de previsão usado ao construir a árvore newbrd é um parâmetro de saída que representa a melhor posição do tabuleiro que pode ser alcançada por player a partir da posição brd nextmove usa duas rotinas auxiliares buildtree e bestbranch A função buildtree forma a árvore do jogo e retorna um ponteiro para sua raiz A função bestbranch calcula o valor de dois parâmetros de saída best que é um ponteiro para o nó da árvore representando a melhor jogada e value que é a avaliação desse movimento usando a técnica de minimax nextmovebrd looklevel player newbrd char b r d 3 newbrd3 Cap 5 Árvores 403 int looklevel char player NODEPTR ptree best int i j value ptree buildtreebrd looklevel bestbranchptree player best value for i0 i 3 i for j0 j 3 j newbrdij bestboardij fim nextmove A função buildtree retorna um ponteiro para a raiz de uma árvore de jogo Ela usa a função auxiliar getnode que aloca armazenamento para um nó e retorna um ponteiro para ele e utiliza também uma rotina expandp plevel depth na qual p é um ponteiro para um nó numa árvore de jogo plevel é seu nível e depth é a profundidade da árvore do jogo que deverá ser formada expand gera a subárvore enraizada em p com a profun didade correta NODEPTR buildtreebrd looklevel char brd3 int looklevel NODEPTR ptree int i j cria a raiz da arvore e inicializaa ptree getnode for i0 i 3 i for j0 j 3 j ptreeboardij brdij a raiz eh um noh de mais por definição ptreeturn 1 ptreeson NULL ptreenext NULL cria o restante da arvore de jogo expandptree 0 looklevel returnptree fim buildtree expand pode ser implementada gerando todas as posições do tabu leiro que podem ser obtidas a partir da posição de tabuleiro apontada por p e estabelecendoas como filhos de p na árvore de jogo Em seguida expand 404 Estruturas de Dados Usando C Cap 5 chama a si mesma recursivamente usando estes filhos como parâmetros até que a profundidade desejada seja alcançada expand usa uma função auxi liar generate que aceita uma posição de tabuleiro brd e retorna um ponteiro para uma lista de nós contendo as posições de tabuleiro que podem ser obtidas a partir de brd Essa lista é ligada pelo campo next Deixamos a codificação de generate como exercício para o leitor expandp plevel depth NODEPTR p int plevel depth NODEPTR q if plevel depth p nao estah no nivel maximo q generatepboard pson q while q 1 NULL percorre a lista de nohs if pturn 1 qturn 1 else qturn 1 qson NULL expandq plevel1 depth q qnext fim while fim if I fim expand Assim que a árvore de jogo for criada bestbranch avalia os nós da árvore Quando um ponteiro para uma folha é passado para bestbranch ela chama uma função evaluate que avalia estaticamente a posição de tabuleiro dessa folha para o jogador cujo movimento estamos determinando A codifi cação de evaluate ficará como exercício Quando um ponteiro para um nó nãofolha é passado para bestbranch a rotina chama a si mesma recursiva mente em cada um de seus filhos e em seguida atribui o máximo dos valores de seus filhos ao nãofolha se for um nó de mais e o valor mínimo se for um nó de menos bestbranch também lembra de qual filho resultou esse valor mínimo ou máximo Septúrn for 1 o nó apontado por p será um nó de menos e receberá a atribuição do valor mínimo atribuído a seus filhos Entretanto septurn for 1 o nó apontado por p será um nó de mais e seu valor deverá ser o Cap 5 Árvores 405 máximo dos valores atribuídos aos filhos do nó Se minxy for o mínimo de x e y e maxxy for o valor máximo minxy maxx y procure demonstrar isso como um exercício simples Sendo assim o máximo ou o mínimo correto podem ser encontrados da seguinte maneira no caso de um nó de mais calcule o máximo no caso de um nó de menos compute o mínimo dos negativos dos valores e depois inverta o sinal do resultado Essas idéias estão incorporadas em bestbranch Os parâmetros de saída pbest e pvalue são respectivamente um ponteiro para o filho da raiz da árvore que maximiza seu valor e o valor desse filho atribuído agora à raiz bestbranchpnd player pbest pvalue NODEPTR pnd pbest int pvalue char player NODEPTR p pbest2 int val if pndson NULL pnd eh uma folha pvalue evaluatepndboard player pbest pnd else o noh nao eh uma folha atravessa a lista de filhos p pndson bestbranchp player pbest pvalue pbest p if pndturn 1 pvalue pvalue p pnext while p NULL bestbranchp player pbest2 val if pndturn 1 val val if val pvalue pvalue val pbest p fim if p pnext fim while if pndturn 1 pvalue pvalue fim if fim bestbranch