Em problemas onde se deseja planejar, com antecedˆencia, as a¸c˜oes a serem executadas por um agente em um ambiente onde outros agentes est˜ao fazendo planos contr´arios `aquele, surge o chamado problema de busca competitiva. Nesses ambientes, as metas dos agentes s˜ao mutuamente exclusivas. Os jogos s˜ao exemplos de ambientes que apresentam este tipo de problema de busca competitiva: o jogador n˜ao tem que se preocupar apenas em atingir seu objetivo final, mas tamb´em em evitar que algum oponente chegue antes dele, ou seja, ven¸ca o jogo. Desta maneira, o jogador deve se antecipar `a jogada do seu advers´ario para fazer a jogada mais promissora com rela¸c˜ao `a sua meta. Esta se¸c˜ao apresenta o algoritmo Minimax e sua otimiza¸c˜ao atrav´es do algoritmo poda Alfa-Beta, uma vez que tais algoritmos foram propostos para solucionar este tipo de problema em jogos disputados por dois jogadores.
2.6.1 Algoritmo Minimax
O Minimax [30] ´e uma t´ecnica de busca para determinar a estrat´egia ´otima em um cen´ario de jogo com dois jogadores. O objetivo dessa estrat´egia ´e decidir a melhor jogada para um dado estado do jogo. H´a dois jogadores no Minimax: o MAX e o MIN. Uma busca em profundidade ´e feita a partir de uma ´arvore onde a raiz ´e a posi¸c˜ao corrente do jogo. As folhas dessa ´arvore s˜ao avaliadas pela ´otica do jogador MAX, e os valores dos n´os internos s˜ao atribu´ıdos de baixo para cima com essas avalia¸c˜oes. As folhas do n´ıvel minimizar s˜ao preenchidas com o menor valor de todos os seus filhos, e o n´ıvel maximizar s˜ao preenchidos com o maior valor de todos os n´os filhos.
A figura 2.13 mostra um exemplo de aplica¸c˜ao do algoritmo Minimax que gera a ´arvore de busca do jogo para um determinado estado.
Figura 2.13: ´Arvore de busca expandida pelo algoritmo Minimax
Note que os valores das folhas 0.3 e 0.2 s˜ao retornadas para os n´os S2 e S3, respectivamente, uma
vez que estes n´os est˜ao em um n´ıvel de minimiza¸c˜ao, ou seja, recebem o menor valor de seus filhos. O valor 0.4 ´e retornado para S0 que ´e a raiz da ´arvore e est´a em um n´ıvel de maximiza¸c˜ao (recebe
2.6. Algoritmos de Busca 29 o maior valor de seus filhos). Desta forma, na Figura 2.13, o melhor movimento que o agente deve escolher ´e o movimento A.
O problema do algoritmo Minimax ´e que o n´umero de estados de jogo que ele tem de examinar ´e exponencial em rela¸c˜ao ao n´umero de movimentos. Isso faz com que a busca seja demasiadamente demorada, pois diversos estados s˜ao visitados sem necessidade, ou seja, n˜ao alteram o resultado final da busca. Uma alternativa para solucionar tal problema ´e o emprego da t´ecnica poda alfa- beta no algoritmo Minimax, denominado como algoritmo de busca Alfa-Beta, apresentado na se¸c˜ao a seguir.
2.6.2 Algoritmo Alfa-Beta
O algoritmo Alfa-Beta otimiza o algoritmo Minimax por eliminar se¸c˜oes da ´arvore que n˜ao podem conter a melhor predi¸c˜ao [60]. Por exemplo, na Figura 2.14, o algoritmo Alfa-Beta, diferente- mente do algoritmo Minimax (veja a figura 2.13) detecta que n˜ao h´a necessidade de avaliar as predi¸c˜oes dos n´os destacados. Portanto, o melhor movimento (movimento A) ´e encontrado mais rapidamente.
Este algoritmo recebe tal nome devido a dois valores: alfa e beta. Estes valores delimitam o intervalo que o valor da predi¸c˜ao do melhor movimento correspondente `a entrada do estado de tabuleiro deve pertencer. Desta forma, para os sucessores de um n´o n, as seguintes situa¸c˜oes podem ocorrer [30]:
• poda α: n ´e minimizador, portanto, a avalia¸c˜ao de seus sucessores pode ser interrompida t˜ao logo a predi¸c˜ao calculada para um deles (chamada besteval) seja menor que o valor de alfa.
• poda β: n ´e maximizador, portanto, a avalia¸c˜ao de seus sucessores pode ser interrompida t˜ao logo a predi¸c˜ao calculada para um deles (besteval) seja maior que beta.
O algoritmo Alfa-Beta conta com duas vers˜oes chamadas hard-soft e fail-soft que diferem apenas no valor da predi¸c˜ao associada aos n´os (ou estados de tabuleiro) dos subproblemas relacionados `a raiz da ´arvore. Neste contexto, o valor correspondente `a ra´ız da ´arvore (retorno final do algoritmo) ´e o mesmo valor minimax para ambas as vers˜oes [61], [62]. As subse¸c˜oes a seguir apresentam estas duas variantes do algoritmo Alfa-Beta.
2.6.2.1 Variante hard-soft do algoritmo Alfa-Beta
A variante hard-soft do algoritmo Alfa-Beta atua da seguinte forma, considerando que besteval representa o melhor valor de predi¸c˜ao a ser associado a um n´o n:
• se n ´e um n´o maximizador, sempre que besteval ≥ beta, o algoritmo retorna beta como valor m´ınimo da predi¸c˜ao.
• se n ´e um n´o minimizador, sempre que besteval ≤ alf a, a algoritmo retorna alfa como valor m´aximo da predi¸c˜ao.
Figura 2.14: ´Arvore de busca expandida pelo algoritmo Alfa-Beta na vers˜ao hard-soft
Portanto, o valor retornado representa ou o valor minimax ou o limite imposto pelo intervalo alfa-beta. Por exemplo, na Figura 2.14, o valor ≤ 0.4 ser´a retornado para o n´o S2 e S3 indicando
que com os movimentos B ou D, o valor da predi¸c˜ao de ambos os n´os ir´a ser pelo menos 0.4. De fato, ap´os calcular que os valores dos sucessores mais `a esquerda dos n´os S2 e S3tiveram predi¸c˜oes
0.3 e 0.2, respectivamente, o algoritmo detecta que n˜ao ´e necess´ario explorar os n´os destacados na figura 2.14 (que causam uma poda). Por esta raz˜ao, se eles tiverem uma predi¸c˜ao inferior ao de seu irm˜ao mais `a esquerda, suas predi¸c˜oes seriam candidatas a “subirem” para seus pais (que s˜ao n´os minimizadores). No entanto, de qualquer forma, eles n˜ao poderiam ser escolhidos pelo n´o maximizador S0 que j´a tem dispon´ıvel o valor 0.4 produzido pelo n´o S1. Por outro lado, se eles
tiverem uma predi¸c˜ao superior a seu irm˜ao mais a esquerda, eles n˜ao podem ser escolhidos por seus pais (n´os minimizadores).
A variante hard-soft possui uma limita¸c˜ao quando ´e pretendido fazer uso deste algoritmo em cojunto com uma Tabela de Transposi¸c˜ao (TT). Uma TT ´e um reposit´orio onde s˜ao armazenadas predi¸c˜oes associadas a n´os j´a avaliados para quando um n´o for submetido ao procedimento de busca novamente (veja a se¸c˜ao 2.9). Por exemplo, considere novamente a Figura 2.14, se a vers˜ao hard-soft fosse utilizada, seria armazenado a predi¸c˜ao 0.4 para os n´os S2 e S3 na TT. Certamente,
este valor 0.4 existente na TT poderia n˜ao ser o valor real da predi¸c˜ao destes n´os, mas dos limites impostos pelo intervalo alfa-beta. Portanto, se a variante hard-soft for utilizada em conjunto com uma TT para calcular o melhor movimento, e durante este processo, os estados S2 e S3
ocorrerem novamente, as suas respectivas predi¸c˜oes seriam buscadas na TT. Todavia, caso estes estados encontrados na TT pudessem ser utilizados (ao cumprirem um conjunto de restri¸c˜oes detalhadas na se¸c˜ao 6.2.3.6) poderia ser realizado um movimento diferente do escolhido pelo algoritmo minimax.
Como o presente trabalho far´a uso de TT para compor seu m´odulo de busca, uma alternativa para solucionar a limita¸c˜ao existente na vers˜ao hard-soft do algoritmo Alfa-Beta em conjunto com TT
2.6. Algoritmos de Busca 31 foi adotada. Neste contexto, a pr´oxima se¸c˜ao apresenta a variante fail-soft do algoritmo Alfa-Beta que soluciona tal limita¸c˜ao.
2.6.2.2 Variante fail-soft do algoritmo Alfa-Beta
A variante fail-soft do algoritmo alfa-beta atua da seguinte forma, considerando que besteval representa o melhor valor de predi¸c˜ao a ser associado a um n´o n:
• se n ´e um n´o maximizador, sempre que besteval ≥ beta, o algoritmo retorna besteval como valor da predi¸c˜ao.
• se n ´e um n´o minimizador, sempre que besteval ≤ alf a, o algoritmo retorna besteval como valor da predi¸c˜ao.
Figura 2.15: ´Arvore de busca expandida pelo algoritmo Alfa-Beta na vers˜ao fail-soft
A vers˜ao fail-soft ´e muito parecida com a vers˜ao hard-soft, diferindo apenas no valor das predi¸c˜oes associadas aos n´os dos subproblemas procedentes da raiz da ´arvore, fato que permite sua integra¸c˜ao com TT. A vers˜ao fail-soft retorna o verdadeiro valor minimax para cada um dos subproblemas existentes na expans˜ao da ´arvore de busca, ou seja, o valor calculado sempre representa um limite do valor minimax. Por exemplo, na Figura 2.15, quando o algoritmo observa o movimento C, ele retorna o valor 0.3 (apesar do fato de 0.3 estar fora do intervalo alfa-beta), o que significa que o movimento B possui um valor de predi¸c˜ao igual a 0.3 [19]. Portanto, se esta vers˜ao do algoritmo Alfa-Beta for utilizada em conjunto com TT, caso um estado Si esteja na tabela e este valor
satisfa¸ca um conjunto de restri¸c˜oes (detalhadas na se¸c˜ao 6.2.3.6 que apresenta a integra¸c˜ao do algoritmo de busca deste trabalho com TT) o valor retornado ´e correspondente ao valor minimax. Desta forma, o resultado final do algoritmo n˜ao sofre altera¸c˜oes, ou seja, possui o mesmo retorno caso a ´arvore fosse expandida fazendo uso do algoritmo Minimax.