REVISTA CONTEÚDO ARTIGO

Transcrição

REVISTA CONTEÚDO
ARTIGO
TEOREMA MINIMAX: UMA APLICAÇÃO EM JOGOS DE XADREZ1
Érico Leandro Vaccari Stefanini2
Valdir Antonio Vitorino Filho3
RESUMO
Esta pesquisa tem como objetivo desenvolver um agente capaz de encontrar e analisar
movimentos em um software de xadrez, onde as técnicas utilizadas são o Teorema MiniMax
para buscas em profundidade numa árvore de possibilidades e a função Alpha-Beta para
otimização da amplitude da mesma. O agente é modelado de acordo com a Orientação a
Objetos e a metodologia baseia-se na teoria dos agentes. Como resultado obteve-se sucesso na
busca, pois o agente executou adequadamente a sua tarefa utilizando-se das técnicas citadas
acima.
Palavras-Chave: Teorema Minimax; Alpha-Beta; Agentes; Jogo de Xadrez.
MINIMAX THEOREM: AN APPLICATION IN GAMES OF CHESS
ABSTRACT
This research aims to develop an agent capable of finding and analyzing movements in a
chess software, where the techniques used are the MiniMax theorem for in-depth searches in a
tree of possibilities, and Alpha-Beta function for the optimization of the amplitude. The agent
is modeled according to the Object Oriented technology and methodology is based on the
theory of agents. As a result was obtained success in the search because the agent has
performed its task properly using the techniques mentioned above.
Keywords: MiniMax Theorem; Alpha-Beta; Agent; Chess Game.
1
Relato parcial adaptado da monografia de conclusão de curso de Erico Leandro Vaccari Stefanini, no
curso de Ciência da computação, sob orientação da Profa. Dra. Ana Estela Antunes da Silva, da UNIMEP
– Universidade Metodista de Piracicaba.
2
Graduado em Ciência da Computação pela UNIMEP - Universidade Metodista de Piracicaba. E-mail:
[email protected].
3
Mestre em Administração Estratégica pela UNIMEP – Universidade Metodista de Piracicaba; Graduado
em Administração pela FACECAP – Faculdade Cenecista de Capivari. E-mail: [email protected]
© Revista Conteúdo, Capivari, v.1, n.4, ago./dez. 2010 – ISSN 1807-9539
39
REVISTA CONTEÚDO
ARTIGO
1. INTRODUÇÃO
Os algoritmos da busca em jogos têm um papel importante em muitas aplicações no
campo da Inteligência Artificial. Conseqüentemente, muito trabalho foi feito no passado para
aumentar a velocidade da busca. Em jogos de xadrez, o melhor movimento esta relacionado
na velocidade da busca e principalmente na heurística utilizada pelo jogo, ou seja, melhor o
algoritmo heurístico, melhor é o movimento. A heurística no xadrez é implementada como
uma função estática aplicada a cada nó terminal no grafo de busca a fim de encontrar a de
melhor valor. Na busca do melhor movimento, dois algoritmos clássicos são a base para esta
busca, sendo eles o MinMax e o Alpha Beta. O Min-Max está relacionado com a heurística e
o Alpha-Beta com a otimização da árvore de busca.
No xadrez as otimizações das buscas são essenciais devido à grande profundidade da
árvore de busca. A técnica de como aplicar a heurística correta e no momento certo será
discutida neste texto. O momento correto para aplicação da heurística depende de duas
situações a serem escolhidas pelo desenvolvedor: primeira, o agente escolhe a melhor jogada
de acordo com uma profundidade na árvore de busca que atinge. E segunda, o agente escolhe
a melhor jogada de acordo com um determinado intervalo de tempo.
O presente artigo tem como objetivo desenvolver um agente capaz de encontrar e
analisar movimentos em um software de xadrez. Tendo como problemática a inserção das
regras do jogo, as quais nunca podem ser violadas e o desenvolvimento de uma heurística
adequada, sendo aquela que melhor represente o pensamento de um jogador de xadrez
humano.
Tendo como hipótese de pesquisa: o agente deve ser capaz de não infringir as regras
do jogo e através de sua heurística executar jogadas adequadas buscando sempre a vitória.
2. INTELIGÊNCIA ARTIFICIAL
Para Rich (1988) desde os velhos computadores de cartões os povos foram fascinados
com programas de xadrez para computador. Se eles pudessem criariam um computador que
pudesse vencer seres humanos de alto conhecimento no assunto, isso seria um grande marco,
principalmente na estrada da história da Inteligência Artificial. O xadrez é um jogo de
informação perfeita. Isto significa que ao contrário do poker ou do backgamon, toda a
informação do jogo está sendo vista entre ambos os jogadores, por isso não existe nada de
secreto entre ambos. Ambos os jogadores podem ver tudo sobre a posição do jogo no
40
REVISTA CONTEÚDO
ARTIGO
tabuleiro e sabem os possíveis movimentos um do outro, porque os movimentos não são
jogados ao mesmo tempo, mas realizados em ordens alternadas entre os jogadores. Assim, o
xadrez é um jogo puramente intelectual, um ambiente perfeito para testar técnicas da
inteligência artificial.
De acordo com Horizon (2004) a maioria dos pesquisadores concluiu que a maior
vantagem dos computadores estava na sua velocidade de calcular as posições no tabuleiro. Os
computadores utilizariam um variante da rotina da força-bruta, um algoritmo que confiasse
quase puramente em como rapidamente o computador pode processar as posições do
tabuleiro. O xadrez tem um ambiente pequeno: 64 quadrados do tabuleiro, sendo que 24 deles
são ocupados por peças na posição inicial. Mesmo que houvesse um número astronômico de
posições legais no xadrez, os pesquisadores confiavam no fato que os computadores poderiam
processar mais exatamente e mais rapidamente que os humanos.
Ainda Horizon (2004) destaca que por volta de 1960, os computadores possuíam
pouca memória (300K), por isso tinham um jogo limitado. Mas os computadores tornaram-se
mais rápidos, e os programas do xadrez tornaram-se mais fortes e mais espertos. Através de
muitas pesquisas entre os programadores, a árvore do jogo do algoritmo minimax evoluiu para
transformar-se o principal componente do programa de xadrez. Quase todos os programas do
xadrez usam a árvore do minimax4. É o mais bem sucedido e mais popular de todas as
técnicas da Inteligência Artificial na história programação do jogo de tabuleiro.
Em 1990, o Computador Deep Blue II5 da IBM, foi derrotado por Gary Kasparov6,
que era o campeão do mundo naquela época. O programa de xadrez, entretanto, não perdeu
sua utilidade, tanto que sete anos depois derrotou o mesmo Gary Kasparov em uma revanche.
Muito indignado Kasparov disse “Em certas posições os computadores jogam como os
deuses”.
Surgem, então, inúmeras aplicações para as técnicas de Inteligência Artificial nos
jogos, e cada vez mais os novos títulos do mercado apresentam implementações sofisticadas
4
Sendo a árvore de minimax um grafo o qual cada estado é pesquisado por amplitude e/ou profundidade.
Em português o chamado azul profundo um supercomputador e software criados pela IBM, com 256 coprocessadores capaz de analisar aproximadamente 200 milhões de posições por segundo, especialmente
para jogar xadrez.
6
Ex-campão mundial de xadrez, escritor e ativista político, é um dos maiores campeões de xadrez de
todos os tempos, com títulos mundiais consecutivos de 1985 a 2005.
5
41
REVISTA CONTEÚDO
ARTIGO
dessas técnicas, como Redes Neurais para treinamento e aprendizado, lógica Fuzzy7 para
acrescentar naturalidade ao comportamento das entidades, e muitos outros artifícios da área.
Em seguida serão abordados para fundamentação teórica os tópicos: Teoria dos
agentes, a função heurística, o Teorema MiniMax a função Alpha-Beta.
2.1 Teoria dos agentes
Segundo Souza (1996) um agente pode ser definido como “uma entidade (física ou
abstrata), capaz de agir sobre si mesma e sobre o meio, possuindo uma representação parcial
desse meio, que tem capacidade de comunicar com outros agentes, e cujo comportamento é a
seqüência de suas observações, de seus conhecimentos e de suas interações com outros
agentes”.
Para Russel e Norvig (1995) mede-se a racionalidade de um agente, necessitamos
definir graus de sucesso, dar ao agente a percepção de como é o ambiente com o qual ele esta
interagindo e assim ver o que ele sabe sobre o ambiente e as ações que eles podem executar
neste ambiente.
Já Souza (1996) acrescenta que no âmbito das pesquisas realizadas em IA, um agente
identifica um sistema computacional que além de apresentar as propriedades de autonomia,
habilidade social, reatividade e pró-atividade, é conceituado ou implementado utilizando-se
propriedades aplicáveis a pessoas, como por exemplo, conhecimento, crenças e intenções.
Ainda Souza (1996) um sistema inteligente pode ser composto por um ou mais
agentes. Quando existem mais de um agente em um sistema inteligente, dizemos que esse
sistema utiliza a DAI (inteligência artificial distribuída). A DAI pode ser conceituada como "o
estudo do comportamento computacionalmente inteligente, resultante da interação de
múltiplas entidades dotadas de certo grau, possivelmente variável, de autonomia. Estas
entidades são usualmente chamadas de agentes e o sistema como um todo é usualmente
chamado de sociedade”.
Segundo Lima (2004) nos últimos anos a indústria vem avançando e estimulando o
desenvolvimento da Inteligência Artificial: os jogos para computador. Isso vem ocorrendo
através da avançada tecnologia de computação gráfica em tempo real o que torna os cenários
7
Admite valores lógicos intermediários entre o FALSO (0) e o VERDADEIRO (1); por exemplo, o valor
médio 'TALVEZ' (0,5). Isto significa que um valor lógico difuso é um valor qualquer no intervalo de
valores entre 0 e 1.
42
REVISTA CONTEÚDO
ARTIGO
e personagens dos jogos impressionantemente realísticos e em funções heurísticas que fazem
com que o personagem (agente) de qualquer jogo torne-se cada vez mais “inteligente”. Essa
situação vem motivando, nos últimos anos, o desenvolvimento de várias áreas na Inteligência
Artificial, como Agentes Inteligentes, Aprendizado de Máquina e Aquisição de
Conhecimento. Em alguns casos, o agente é capaz de aprender com situações passadas,
adaptando-se dinamicamente às novas situações de jogo, em razão da implementação de
heurísticas no jogo.
Sendo essa pesquisa baseada em definição do ambiente em que o agente irá se situar, a
capacidade de raciocínio, o grau de sucesso e as regras impostas.
2.1.1
Estrutura dos agentes
De acordo com Russel e Norvig (1995) a estrutura dos agentes envolvidos é a
seguinte:
Percepções: no caso do xadrez as percepções dos agentes serão capturadas através das
funções de avaliação e das buscas e isso dará ao agente a sua situação no ambiente.
Ambiente: O ambiente em que o agente se encontra é em um tabuleiro de xadrez com 64
posições divididas e 8 linhas e 8 colunas.Nessas 64 posições encontram se 16 peças para cada
jogador com cores diferentes para cada um. Em termos computacionais, uma matriz
representa muito bem o ambiente no xadrez.
Sensores: Os sensores serão as funções de avaliação e combinações dos algoritmos de busca,
MiniMax e Alpha-Beta.
Mudança de estado: Um determinado estado é gerado a partir da aplicação de alguma ação,
As ações possíveis estão descritas no item ações e sua aplicação resulta em diferentes
possíveis estados num total de aproximadamente 10120 possibilidades.
Ações: As ações dos agentes serão baseadas nas suas percepções e as regras impostas a cada
peça. Para cada peça as ações são:

Rei: O Rei pode mover-se uma casa na horizontal, vertical ou diagonal. O Rei do
lado a jogar nunca pode estar em xeque após a realização de uma jogada. Se não for
43
REVISTA CONTEÚDO
ARTIGO
possível evitar que o Rei esteja em cheque à posição passa a ser de mate e o lado do
Rei que está a ser atacado perde.

Dama: A Dama pode movimentar-se em qualquer número de casas na horizontal,
vertical ou qualquer em uma das diagonais.

Bispo: O Bispo pode movimentar-se em qualquer número de casas em qualquer uma
das diagonais.

Cavalo: O Cavalo movimenta-se em forma de L, e é a única peça que pode "saltar"
por cima de outras.
O movimento do cavalo define-se como: duas casas numa
direção e outra na perpendicular.

Torre: A Torre pode movimentar-se em qualquer número de casas na horizontal ou
vertical.
 Peão: O peão move-se de formas distintas quer se esteja a mover ou a capturar uma
peça. Quando um peão se move avança uma casa na vertical em direção ao lado do
adversário. Se ele ocupar a sua casa inicial pode avançar uma ou duas casas. Para
capturar o peão move-se uma casa na diagonal.
Também existe um movimento especial dos peões chama-se tomada en-passant
(expressão em francês que significa ao passar). Esta é possível quando um peão avança duas
casas e quando simultaneamente um peão inimigo se encontra em posição de ataque a casa
por onde o peão que se move passa. Nesse caso o peão atacante pode capturar o que se move
movendo-se para a casa de passagem. Esta tomada só pode acontecer no lance seguinte ao
movimento.

Roque: O roque é um lance especial em que o Rei e a Torre se movimentam
simultaneamente. Este só pode ser realizado uma vez por cada jogador. Para o roque
ser possível tem de se verificar as seguintes condições:
 O Rei que vai fazer o lance não se pode ter movido durante o jogo.
 A Torre vai fazer o lance não se pode ter movido durante o jogo.
 O Rei envolvido não está em xeque.
 Todas as casas entre o Rei e a Torre têm de estar desocupadas.
 O Rei não passa por uma casa atacada por uma peça inimiga durante o movimento.
 A casa de destino do Rei não está a ser atacada.
 O Rei e a Torre têm de ser do mesmo lado.
44
REVISTA CONTEÚDO
ARTIGO
O movimento do roque consiste no Rei movimentarem-se duas casas na direção da
Torre e a Torre passar para a casa adjacente ao Rei do lado oposto ao que se encontra
inicialmente.
Estado Objetivo: O objetivo de um agente é dar checkmate8 em outro agente. Para que
ocorra um checkmate o Rei de um dos agentes tem que estar em um estado, o qual o ele esteja
sendo atacado por uma peça do agente e inimigo e não tenha saída, ou seja, não possa mudar
de estado para sair do ataque.
Critérios de Desempenho: O desempenho dos agentes terá uma ligação direta com a
heurística aplicada na função de avaliação. A função heurística levará em consideração as
informações dadas a ela.
Estado Inicial: O estado inicial no xadrez é sempre o mesmo, ou seja, todas as peças brancas
se encontram na primeira e segunda linha e as peças negras se encontram na sétima e oitava
linha.
O ambiente no xadrez é formado por um tabuleiro dividido em 64 partes, onde em cada parte
pode não conter, ou conter no máximo uma peça por vez. Cada uma das partes possui uma
posição fixa na horizontal e uma posição fixa na vertical, elas recebem letras de “A” a “H” na
horizontal e recebem números de 1 a 8 na vertical. Então, uma parte será formada por uma
letra e por um numero. Na posição inicial existem 32 peças sobre o tabuleiro, essas peças
sempre começam na mesma posição. Cada jogador, aqui chamado de agente tem o controle de
16 peças a partir da posição inicial, essa quantidade nunca aumenta e tem sempre uma grande
probabilidade de diminuir ao decorrer do jogo. O agente que possuir o controle das peças
brancas sempre faz o primeiro movimento, sempre que ele inicia um jogo ele tem a
possibilidade de fazer um dos 20 movimentos possíveis a partir da posição inicial, isso
também acontece com o jogador das pecas negras. A partir do segundo movimento esse
numero aumenta e fica na média de 40 movimentos possíveis a cada jogada.
O agente utiliza-se dos seus sensores (função de busca e função heurística) para
realizar movimentos que dê a vantagem a ele, portanto ele tem uma média de 40 movimentos
possíveis para serem verificados e procurar fazer o melhor entre eles. Para fazer isso o agente
8
Em persa siginifica “o rei está morto”, é uma expressão usada no enxadrismo para designar o lance que
põe fim à partida, quando o Rei atacado por uma ou mais peças adversárias não pode permanecer na casa
em que está, movimentar-se para outra ou ser defendido por outra peça. Se um jogador aplicar o xequemate e o adversário conseguir de algum modo escapar quem aplicou o xeque-mate automaticamente
perdeu o jogo.
45
REVISTA CONTEÚDO
ARTIGO
tem que analisar cada um dos movimentos possíveis. Esta análise é feita percorrendo as 64
partes do tabuleiro, assim que ele encontra uma das suas peças ele armazena os movimentos
possíveis daquela peça e depois aplica a cada movimento possível a função heurística que vai
atribuir valores aos possíveis estados gerados por aquele movimento. O agente também
precisa verificar os movimentos possíveis do adversário e verificar a vantagem que aquele
movimento ira trazer contra ele, surge então à necessidade de utilizar uma função que alterne
a vez de jogar e verifique a cada mudança de jogador o valor da posição, a função que faz isso
é a função MiniMax. A função MiniMax avalia a posição depois de várias jogadas a frente, ou
seja, ela armazena todas as possíveis jogadas em um grafo, percorre em profundidade e a cada
nó ou estado do grafo ela aplica a função heurística e verifica o valor da posição. A função
MiniMax fica em um laço de repetição que possui como condição a profundidade a ser
buscada, ou seja, de profundidade 1 ate profundidade determinada a ela. Quanto maior a
profundidade a ser verificada, maior o tempo de resposta da função MiniMax. No meio jogo
existe uma média de 40 movimentos possíveis, então em uma profundidade 10, por exemplo,
poderá ser gerado um numero de 4010 estados, lembrando que em cada estado ela precisa
verificar cada peça, multiplicar o valor da peça pelo valor da posição da peça e somar os
valores para chegar ao valor total da posição.
2.2 Função Heurística
Salientam Schaeffer e Van Den Herik (2002) que a Inteligência Artificial tem como
objetivo estudar os processos de raciocínio do cérebro humano, e assim procurar imitá-los
através dos algoritmos e heurísticas, a fim de criar softwares que imitem ou simulem a
maneira de pensar dos seres humanos. Isso vem ocorrendo desde a década de 50 e no futuro
espera-se que seja possível interagir com um programa de computador e não saber se o ser
que estamos interagindo é de fato uma máquina ou um outro ser humano.
É exatamente isso que um jogador de xadrez, talvez, espera do comportamento do
personagem jogo, que seus atos, seus pensamentos e suas conclusões sejam, além de
parecidos com os de uma pessoa real, sejam as melhores possíveis. Devido ao impressionante
desenvolvimento do hardware e do grande estudo feito sobre os algoritmos de busca, as
conclusões já estão perto de serem as melhores possíveis.
Complementa Rich (1988, p. 4):
Para resolver problemas difíceis com eficiência, muitas vezes é necessário
comprometer as exigências de mobilidade e sistematicidade, e construir uma
46
REVISTA CONTEÚDO
ARTIGO
estrutura de controle que não mais tenha a garantia de encontrar a melhor resposta,
mas que quase sempre encontre uma resposta muito boa. Assim introduzimos a idéia
da técnica heurística.
Booch e Jacobson (1999) para atingir esses objetivos, o básico para jogos dessa área, é
a implementação de algoritmos clássicos de busca como o MiniMax e o Alpha-Beta.
Dependendo do nível de inteligência (Inferência) do jogo ocorrem algumas variações nesses
algoritmos a fim de tirar o maior proveito possível.
Existem jogos que o nível de dificuldade é modificado dinamicamente de acordo com
a habilidade do oponente, eles utilizam procedimentos de Aprendizado. Um bom exemplo é o
jogo de damas de Samuel. O jogo de damas de Samuel era um software que tinha alto
aprendizado, ou seja, a cada jogo que ele disputava fazia uma alta avaliação e analisava se
tinha condições de melhorar. O software fazia uma cópia do motor de inferência e fazia
algumas alterações na função de avaliação. As duas funções jogavam contra o oponente e
caso a atual perdesse e a cópia alterada ganhasse, a atual era atualizada pela cópia.
Pode-se também chamar as funções heurísticas de funções estáticas que de alguma
forma quantificam ou qualificam um determinado estado ou posição do jogo.
Como o jogo de xadrez é um jogo de muitas possibilidades de movimentos e posições,
que estão em torno de 10120 já no primeiro movimento, temos 20 possibilidades. A função da
heurística aqui é determinar qual deles é o melhor movimento possível ou um bom
movimento.
Damásio (2004) para que a função heurística chegue a alguma conclusão é preciso
passar a ela regras e valores, que nada mais são que o conhecimento. Tais regras e valores são
fornecidos por um especialista na área, um mestre de xadrez.
O xadrez por ser um jogo complexo requer muito estudo. O conhecimento dos
especialistas na área vem passando de geração a geração desde o século XV.
Devido a esse grande tempo de estudos teóricos no xadrez, chegou se a algumas
conclusões básicas que todo jogador bom de xadrez tem que conhecer e aplicá-las a cada
jogo.
Baseando-se nestas regras básicas já definidas ao longo do tempo, podemos construir
uma função heurística que vai avaliar a posição do tabuleiro e dizer qual dos dois agentes
estará em vantagem ou se a posição é de empate.
Assegura Rich (1988, p.10):
47
REVISTA CONTEÚDO
ARTIGO
Boa parte do trabalho nos programas de jogos foi dedicada ao desenvolvimento de
boas funções de avaliação estática. Uma função de avaliação estática muito simples,
baseada em vantagem de peça, foi proposta por Turing para o xadrez – somam-se
simplesmente os valores das peças pretas (B), os valores das peças brancas (W), e
depois se calcula a vantagem de uma sobre a outra.
A função heurística ou estática que o estudo irá definir é a seguinte:
H = ∑ (P*peso)
Onde:
H é o valor da posição avaliado pelos dois agentes, quanto maior o valor de H maior é a
vantagem para um dos agentes na posição.
P são as peças do jogo.
Peso é o peso dado a cada peça de acordo com o local do tabuleiro onde ela se encontra.
O peso pode variar seguindo as regras já definidas, que são as seguintes:

Peão no centro do tabuleiro tem um valor (peso) maior.

Peões do lado do Roque do Rei tem pesos maiores se estiverem na mesma linha, ou
seja, na segunda-feira.

O Bispo tem o mesmo peso do cavalo, mas dois Bispos têm mais peso do que dois
cavalos.

O valor do peão será definido com valor 1 e o mesmo valor será dado para sua posição
no tabuleiro. Se ele estiver na coluna “D” ou “E” e na quarta linha, o valor do peso
será 1.2

O valor do cavalo será definido com o valor 3 e aqui vamos definir o peso 1 para
qualquer posição do tabuleiro.

O valor do Bispo será definido com o valor 3 e aqui vamos definir o peso 1 para
qualquer posição no tabuleiro.

O valor da torre será definido com o valor 5 e assumirá o peso 1 para qualquer posição
do tabuleiro.

O valor da Dama será definido com o valor de 9 e assumirá o peso 1 para qualquer
posição do tabuleiro.
48
REVISTA CONTEÚDO

ARTIGO
O valor do Rei será definido como Infinito, pois o Rei como sempre esta no jogo tem
um peso maior que qualquer outra peça e aqui por meio de simplificação irá definir o
peso 1 para qualquer posição dele no tabuleiro.
Se analisarmos uma posição aplicando somente as regras acima, veremos que a
função heurística pode trazer bons resultados.
Vejamos o diagrama abaixo:
Figura 1 – Heurística na posição inicial
Fonte: Software de xadrez - Fritz®
Analisando a função heurística nesta posição temos:
H = ∑ (a2*1 +b2*1+ c2*1+d2*1+e2*1+f2*1+g2*1+h2*1+Torre*1+Cavalo*1+ Bispo*1+
Dama*1+ Rei*1+Bispo*1+Cavalo*1+Torre*1)
H=39+Rei
Na posição inicial vemos que a função heurística tem o mesmo valor para qualquer um
dos agentes, ou seja, 39.
Após o primeiro movimento que é feito por parte do Agente que joga com as peças
brancas ocorre uma pequena mudança.
49
REVISTA CONTEÚDO
ARTIGO
Figura 2 – Abertura do Peão E4
H= ∑ (a2*1+b2*1+c2*1+d2*1+e2*1.2+f2*1+g2*1+h2*1+
Torre*1+Cavalo*1+Bispo*1+Dama*1+Rei*1+Bispo*1+Cavalo*1+Torre*1)
H=39.2+Rei (Para o agente com peças brancas)
H=39+Rei (Para o agente com peças preta)
Embora a diferença seja de apenas 0.2, o acumulo de vantagens (no xadrez chamamos
de micro-vantagens) levam um dos lados a vitória.
Pode parecer muito simples avaliar uma posição desta maneira, mas existem posições
que podem “enganar” a função heurística, vejamos uma delas.
Figura 3 – Heurística em posições complexas
50
REVISTA CONTEÚDO
ARTIGO
Analisando esta posição pela função estática temos os seguintes valores:
Peças Brancas = 39,2
Peças Negras = 39,2
A posição esta empatada. Se a vez de jogar for das brancas certamente, baseando-se
nas regras dadas a função heurística, o movimento a ser feito aqui será de peão da posição d5,
tomara o cavalo que está em e6. Este movimento que aparentemente ganha uma peça das
brancas não é o melhor da posição, já que no próximo movimento das peças negras é capturar
com o peão que esta em b5 a dama branca que esta em c4 que dará às peças negras uma
grande vantagem.
Sendo assim concluímos que em um jogo de xadrez existe a necessidade de
verificarmos como a posição vai ficar após alguns movimentos mais à frente para evitar
problemas como este na posição acima.
Para isso existem alguns algoritmos clássicos de busca em profundidade que ajudam a
resolver este problema, sendo eles, o MiniMax e o Alpha-Beta.
2.3 MiniMax
Segundo Schaeffer e Van Den Herik (2002) o algoritmo minimax é um algoritmo
muito clássico no ramo da IA. A sua função é calcular a decisão minimax a partir do estado
atual. Ele é um algoritmo recursivo que obtém os valores minimax de cada estado sucessor até
chegar aos terminais. Assim que os nós terminais são encontrados, é aplicado sobre eles as
funções heurísticas. Após a aplicação das funções é retornado pela árvore os valores MAX e
MIN daquele estado terminal.
Para Russel e Norvig (1995) o algoritmo minimax executa uma exploração completa
em profundidade da árvore de jogo. Se a profundidade máxima da árvore é m e existem b
movimentos válidos em cada ponto, a complexidade de tempo do algoritmo minimax é
O(bm), A complexidade de espaço é O(bm) para um algoritmo que gera todos os sucessores
de uma vez ou O(m) para um algoritmo que gera um sucessor de cada vez.”.
O xadrez é um jogo de soma zero, ou seja, a vantagem de um é a desvantagem do
outro, portanto se a posição esta empatada a função de avaliação tem o valor 0 para ambos os
51
REVISTA CONTEÚDO
ARTIGO
lados. Se aplicarmos o minimax em jogos de xadrez, definimos que um dos agentes jogam
movimentos dos nós MAX e o outro dos nós MIN. Os arcos que partem dos nós MAX
correspondem aos movimentos disponíveis para o agente 1 e os arcos que partem dos nós
MIN, correspondem aos movimentos disponíveis para o agente 2. Cada ramificação na árvore
do jogo significa uma seqüência de escolhas feitas alternadamente por cada um dos dois
agentes.
Damásio (2004) nos nós terminais do jogo pode ocorrer três situações, onde o agente 1
vence, ou seja valor MAX é suficientemente ganhador, ou o agente 2 vence, portanto o nó
MIN é suficientemente ganhador ou ocorre um empate, o valor MAX é igual o valor MIN.
Na figura abaixo pode-se ver uma árvore que representa nós MAX e MIN no
minimax:
Figura 4 – Exemplo de uma árvore com MINIMAX
Fonte: Adaptado de Russel e Norvig (1995).
Um exemplo do algoritmo minimax ficaria da seguinte forma:
Algoritmo Minimax
Função MINIMAX ( N )
{
Se N é nó Terminal então
Retorne o valor da função de avaliação
Senão
{
Para cada sucessor Ni de N faça
Se N é um nó MIN então
52
REVISTA CONTEÚDO
ARTIGO
Retorne MIN (MINIMAX( N1 ),MINIMAX ( N2 ),...,MINIMAX ( Nm) )
Senão
Retorne MAX (MINIMAX( N1 ),MINIMAX ( N2 ),...,MINIMAX ( Nm) )
}
}
onde:
N é a posição atual do tabuleiro, que representa um nó da arvore
Ni é cada nó sucessor de N
2.4 Alpha-Beta
Para Lima (2004) embora a busca minimax seja uma boa solução para percorrer a
arvore de movimentos verificar cada estado, ela tem um problema. Esse problema ocorre
porque o número de estados que tem que ser verificado aumenta exponencialmente conforme
o número de movimentos.
Como não se pode eliminar tal expoente, podemos aplicar técnicas que diminuirão a
árvore de busca pela metade e ainda não afetará as melhores decisões do mini-max. Essa
técnica chamada de poda Alpha-Beta fará uma “poda” na árvore de busca. O objetivo desta
poda é eliminar os estados e seus sucessores que não interessam, ou seja, tem valor menor
para a busca mini-max em relação a cada agente.
[3,3]
B
3
12 8
[3,3]
A
[-999,2]
C
2
[2,2]
14
D
5 2
Figura 5 – Busca MiniMax
Fonte: Elaborado pelos autores.
53
REVISTA CONTEÚDO
ARTIGO
No primeiro nó terminal após B, o valor é 3. Conseqüentemente, B, que é um nó MIN,
tem valor máximo 3. O segundo nó terminal após B tem valor 12; MIN evitaria esse
movimento, de forma que o valor de B ainda é o máximo 3. O terceiro nó terminal sob B tem
valor 8; depois de ser percorrido todos os sucessores de B, o valor do mesmo é 3. Agora,
podemos deduzir, que o valor da raiz é pelo menos 3, porque MAX tem uma escolha de valor
3 na raiz. O primeiro nó após C tem valor 2. Com isso, C que é um nó de MIN, tem valor
máximo 2 . Porém, sabemos que B vale 3; portanto, MAX nunca escolheria C. Desse modo
não há razão para se examinar os outros sucessores de C. Aqui entra a poda Alpha-beta. O
primeiro nó abaixo de D tem valor 14 e então D vale no máximo 14. Esse valor ainda é mais
alto que a melhor alternativa de MAX, ou seja 3, e portanto precisamos continuar a explorar
sucessores de D. Note também que agora temos limites para todos os sucessores da raiz,
portanto, o valor da raiz também é no máximo 14. O segundo sucessor de D vale 5, e assim
novamente precisamos continuar a exploração. O terceiro sucessor vale 2 e agora D vale
exatamente 2. A decisão MAX na raiz é efetuar o movimento para B, o que nos dá o valor 3.
[RUSS 04].
Pode-se aplicar a poda Alpha-Beta, independente da profundidade da árvore. Sendo
que, para a sua implementação dois valores são relevantes:

Valor Alpha, que é a melhor escolha de MAX

Valor Beta, que é a melhor escolha para MIN
Abaixo segue algoritmo bem clássico da poda Alpha-Beta:
Algoritmo Alpha-beta
função Alpha-Beta ( N , A , B )
{
Alpha = A;
Beta = B;
Se N for folha da arvore
então
retorne o valor da posição
senão
Se N for um nó MIN
então
{
para cada sucessor Ni de N faça
{
Alfabeta ( Ni , Alpha , Beta )
Beta = min ( Beta , Val )
54
REVISTA CONTEÚDO
ARTIGO
Se Beta <= Alpha
return Beta
}
else
{
para cada sucessor Ni of N faça
{
Alpha-Beta ( Ni , Alpha , Beta )
Alpha = max ( Alpha , Val )
Se Alpha >= Beta
return Alpha
}
}
}
Onde:
N é a posição atual do tabuleiro, que representa um nó da árvore.
Ni é a próxima posição do tabuleiro que será buscada no vetor de movimentos possíveis
Alpha e Beta serão os valores da heurística aplicada em cada posição analisada.
Neste caso não estão sendo considerados parâmetros como à profundidade da busca e
variáveis que definem os agentes por exemplo. Outra função que deve ser considerada e com
certeza vai estar presente em um algoritmo Alpha-beta é uma função que gera movimentos, a
qual vai gerar movimentos válidos para as árvores de busca.
Para Russel e Norvig (1995) matematicamente está provado que um algoritmo AlphaBeta examina apenas O (bd/2) nós para escolher o melhor movimento, em vez de O (bd) para o
algoritmo minimax, no caso do xadrez, a média de nós analisados será na ordem de 6 para o
Alpha-Beta contra 35 do Minimax. Com isso o algoritmo Alpha-Beta pode verificar na arvore
uma profundidade 2 vezes maior que o Minimax. Se levarmos em conta que no xadrez muitos
movimentos levam por transposição à mesma posição após alguns movimentos, a busca
Alpha-Beta torna-se 2 vezes melhor do que o melhor caso e, portanto passa a ser O (bb/4).
3. RESULTADOS E DISCUSSÕES
O algoritmo do jogo de xadrez foi desenvolvido com base na Teoria dos Agentes e
modelado de acordo com a Orientação a Objetos. A figura abaixo mostra o diagrama de
classes.
55
REVISTA CONTEÚDO
ARTIGO
Figura 6 - Diagrama de Classes
Fonte: Elaborado pelos autores.
56
REVISTA CONTEÚDO
ARTIGO
Lima (2004) diz que o diagrama de classe mostra os métodos e atributos de cada
classe. A classe busca tem maior relevância neste projeto, pois e nela que se encontram os
métodos de busca e funções heurísticas.
Definem Booch e Jacobson (1999) o diagrama de estados mostra os possíveis estados
que um jogo de xadrez pode obter. O estado inicial sempre inicia com as pecas brancas, por
isso elas fazem sempre o primeiro movimento. A partir do movimento das brancas, os
próximos estados pode ser movimento das pecas negras, o jogo pode empatar ou as pecas
brancas vencem. O estado final pode ser e somente ser atingido se o jogo terminar empatado
ou com uma vitória das pecas brancas ou pecas negras.
Segundo os mesmos autores o diagrama de seqüência mostra a interação entre objetos
com ênfase na ordenação temporal das mensagens trocas pelos objetos, assim, mostram um
encadeamento de chamadas de operação. No algoritmo desenvolvido, como o humano sempre
joga com as brancas, ele inicia o jogo passando a primeira mensagem para o objeto tabuleiro.
Ele verifica o movimento válido e envia o movimento realizado, e a posição atual para as
classes de busca para que elas encontrem (através das funções heurísticas) o movimento para
as peças negras.
Souza (1996) diz que agentes são compostos por ações, percepções e objetivos. As
ações do agente foram implementadas através de funções e procedimentos para que o agente
movesse as peças no jogo. Através dessas funções o agente pode verificar quais os
movimentos válidos e assim mover uma peça.
Ainda Souza (1996) as percepções do agente são funções de busca e avaliação que
verificam a posição do tabuleiro e através dessa posição tentam descobrir qual o melhor
movimento para ser realizado. O agente tem como objetivo dar cheque-mate no oponente, ou
seja, vencer a partida. Para ele atingir uma posição de cheque-mate ele precisa coordenar as
suas peças de tal forma que o rei adversário não possua saída.
Cada peça possui uma ação diferente já que ela se movimenta diferentemente no
tabuleiro. Transformando isso em linguagem de programação, podemos criar uma classe
tabuleiro que é uma matriz 8x8, ela representara muito bem o ambiente no qual o agente vai
agir. As ações do agente nesse ambiente serão verificadas uma a uma, por exemplo, a
mudança de estado de um peão, que é um objeto, no tabuleiro é realizada com regras de linhas
e colunas sobre a matriz, ou seja, o peão anda sempre na mesma coluna, mas quando captura
outra peça ele vai para outra. Cada peça tem regras semelhantes e têm de ser verificadas uma
57
REVISTA CONTEÚDO
ARTIGO
a uma. Inserimos uma função que recebe a lista de movimentos válidos e o movimento
realizado. Se o movimento realizado for encontrado na lista de movimentos possíveis naquela
posição ela a função retorna verdadeiro.
Também será necessária uma função que gere movimentos possíveis. Esta terá que
saber as regras de cada peça do jogo e aplicá-las em cada estado do ambiente, ou seja, o
agente terá sempre um ambiente diferente a cada jogada. O minimax começa a fazer a busca
em profundidade e o estado vai sempre mudando até que algo maior interrompa, tal como ele
encontre um bom movimento ou o tempo limite de busca tenha acabado.
Percepções e Sensores do Agente
As percepções do agente são realizadas a partir das funções de busca e da avaliação
das posições. A função de busca utilizada foi à função Mini-Max utilizando podas AlphaBeta. Essa função faz uma busca na lista de movimentos possíveis e retorna o melhor
movimento encontrado, descartando os movimentos ruins.
A função Alpha-Beta recebe como parâmetro o movimento realizado, a vez de quem
joga (Minha vez ou Sua vez) e lista de movimentos, computador ou humano respectivamente,
a pontuação de ambos e a profundidade da busca. Ela faz chamadas as funções de avaliação,
que é a função heurística.
A função heurística avalia a posição, obtém o valor dela e verifica se as peças negras
estão em vantagem ou em desvantagem. Ela faz isso multiplicando cada peça pelo valor da
posição onde ela se encontra, soma todos os valores das pecas brancas e todos os valores das
pecas negras.
Após determinar o valor da posição de ambos os jogadores a função subtrai um valor
do outro para saber quem está com a vantagem.
Vantagem = Total Jogador 1 – Total Jogador 2.
Se a vantagem der positiva o jogador 1 está melhor, caso contrário estará melhor o
jogador 2.
4. CONSIDERAÇÕES FINAIS
Embora o software desenvolvido tenha realizado bons movimentos através da função
de avaliação, ele ainda esta muito distante dos softwares profissionais em termos de
conhecimento e velocidade de busca. Para que o algoritmo desenvolvido melhore, serão
necessárias três mudanças.
58
REVISTA CONTEÚDO
ARTIGO
A primeira é um melhor controle de memória e um algoritmo de Busca mais eficiente,
já que, quanto maior for à profundidade de busca melhor o seu conhecimento.
A outra mudança e uma função de avaliação que represente melhor o estado atual, para
assim, saber com mais precisão a vantagem de cada lado.
A terceira e mais importante é a implementação de um livro de abertura (também
conhecido como Book). O livro de abertura é essencial já que como os movimentos de
abertura dificilmente mudam principalmente nos 10 primeiros movimentos, com o Book, o
software faz somente movimentos que os quais já foram estudados, analisados e avaliados,
fazendo assim com que o software faça somente os melhores movimentos, já que eles estão
no book.
De acordo com os resultados obtidos a hipótese formulada: “o agente deve ser capaz
de não infringir as regras do jogo e através de sua heurística executar jogadas adequadas
buscando sempre a vitória” pode ser aceita como verdadeira, pois o agente segue as regras
impostas e executa movimentos sempre tentando maximizar a sua vantagem em relação aos
movimentos executados pelo oponente, realizada essa análise buscando estados com maior
vantagem na árvore minimax os quais são analisados pela função e nunca ultrapassando os
limites de profundidade e/ou de tempos imposto a ele.
O raciocínio está ligado ao planejamento, ou seja, um programa com a capacidade de
planejar é capaz de executar tarefas hipotéticas, ordenar as suas escolhas de acordo a
maximizar seus ganhos e minimizar suas perdas. Consegue conduzir um plano conciso e
coerente de atividades para fornecer a sinergia necessária para a combinação de inteligências
e capacidade de memória, sendo assim o próximo desafio encontra-se no ramo das estratégias
e raciocínios sintéticos ao longo de bases de conhecimento diferentes.
Uma forte tendência aos computadores é a aprendizagem computacional, onde os
computadores aprendem com seus erros e atualizam sua própria informação. Essa tendência
se aplica ao jogo estudado e desenvolvido, pois o xadrez é um dos poucos jogos que
contemplam várias áreas do conhecimento.
REFERÊNCIAS
BOOCH, G; Rumbough, J. e JACOBSON, I. The Unified Modeling Language User Guide.
Addison-Wesley Object Technology Series, 1999.
59
REVISTA CONTEÚDO
ARTIGO
DAMÁSIO, Carlos Viegas. Pesquisa em Jogos. Disponível em: <http://ssdi.di.fct.unl.pt/~iia/
trabalhos /jogos/ jogos.htm>. Acesso em 20 de fevereiro de 2004.
HORIZON, A.I. Introduction to Chess Programming and AI. Disponível em:
<http://www.aihorizon.com/essays/chessai/intro_print.htm>. Acesso em 02 de abril de 2004.
LIMA, M. Cynthia. Linguagens para Inteligência Artificial. Disponível
em:<http://sites.uol.com.br/cynthia_m_lima/ia2.htm>. Acesso em 05 de abril de 2004
SOUZA, Eliane M. S. 1996. Teoria dos Agentes. In: “Uma Estrutura de Agentes para
Assessoria na Internet”. Disponível em:
<http://www.eps.ufsc.br/disserta96/eliane/cap3/cap3.htm>. Acesso em 23 de abril de 2004.
RICH, Elaine. Inteligência Artificial. Editora: McGraw-Hill, São Paulo-SP, 1988.
RUSSEL, Stuart e NORVIG, Peter. Inteligência Artificial. Editora: Prentice Hall, São PauloSP, 1995.
RUSSEL, Stuart; NORVIG, Peter. Artificial Intelligence: A Modern Approach. Editora:
Prentice Hall, 1995.
SCHAEFFER, J; VAN DEN HERIK, H. J. Games, computers, and artificial intelligence.
Department of Computing Science, University of Alberta, Edmonton, AB, Canadá, 2002.
60

REVISTA CONTEÚDO ARTIGO

Transcrição

Documentos relacionados

Dmcar - Manutenção e Repara

Inventa o teu Jogo

Projeto: Oficina de Xadrez Introdução Objetivos Público-Alvo

Xadrez Feminino 2016 - Clube de Xadrez de Contagem

Confira o artigo na íntegra - Tribunal de Contas do Estado da Paraíba

PREMIAÇÃO (R$ 2.000,00)!

barreira de contenção maximax e minimax

O PROFESSOR DE XADREZ Professor Wilson da Silva Quando o

Torneio Jovem Dolce Vita Porto / Distrital de Honra Jovem 2007

17 - Jesus Divino Mestre