Universidade Federal de Uberlândia - UFU
Faculdade de Computação
Mestrado em Ciências da Computação
Uma proposta para resolver o
problema de loop no LSDraughts
e no VisionDraughts: criação de
um jogador de final de jogo
Valquíria Ap. Rosa Duarte
Orientadora: Profa. Dra. Rita Maria Silva Julia
Estrutura da apresentação






Introdução e motivação
Trabalhos relacionados
Proposta - Jogador de final de jogo
Resultados esperados
Cronograma
Referências
II Workshop de Dissertações – Mestrado em Ciência da Computação
2/18
Introdução e Motivação




Jogador baseado nos jogadores NeuroDraughts e
LS-VisionDraughts
Problemas de loop encontrado nesses jogadores
Empate de jogos que estão em condições de vitória
Melhoria da eficiência dos jogadores
II Workshop de Dissertações – Mestrado em Ciência da Computação
3/18
Trabalhos relacionados

Jogos de tabuleiros:
 NeuroDraughts
 LS-Draughts
 VisionDraughts
 Chinook
 Anaconda
 GO
II Workshop de Dissertações – Mestrado em Ciência da Computação
4/18
NeuroDraughts

Utiliza o mínimo de intervenção possível
 Regras



do jogo e conjunto de características
Aprendizado por TD(λ) e aprendizagem por
reforço
Influência das características
Treinamento por self-play com clonagem
II Workshop de Dissertações – Mestrado em Ciência da Computação
5/18
LS-Draughts






Extensão do NeuroDraughts
Características selecionadas através de AG
Sistema gerador de agentes jogadores
Busca minimax
Presença de loops
Longo período de treinamento
II Workshop de Dissertações – Mestrado em Ciência da Computação
6/18
LS-Draughts - Mapeamento por
Características
7/18
VisionDraughts

Altera a arquitetura do NeuroDraughts:
 Substitui
minimax por busca eficiente com poda alfabeta, tabela de transposição e iterative deepening
 Acrescenta base de dados de final de jogo


Redução em 95% do tempo de busca
Menor incidência de loops
II Workshop de Dissertações – Mestrado em Ciência da Computação
8/18
Outros jogadores

Chinook:





Anaconda:




Campeão mundial homem-máquina
Forte conhecimento humano - Marion Tinsley
Ajuste manual das funções
Usado para testar a eficiência do jogador de final de jogo
Mínimo de intervenção humana possível
Aprendizado baseado em Redes Neurais
Presença de loops
Go:


Presença de loops
Generalized thermography
II Workshop de Dissertações – Mestrado em Ciência da Computação
9/18
Nossa proposta – Jogador de final de
Jogo

Ordenação parcial em todos os nós da árvore de
busca
 Aumentar
o número de podas
 Alcançar maior profundidade de busca (look ahead)
 Aumentar a visão do jogador

Criação de uma segunda rede neural MLP
 Agente
 Base
de final de jogo
de dados – Redes de Kohonen
II Workshop de Dissertações – Mestrado em Ciência da Computação
10/18
Mapeamento de Sm (4)
CONJUNTO
CARACTERÍSTICAS
(CC)
Sn(3)
Si, iésima
folha de S0 (2)
Um
Individuo
REAJUSTE
PESOS
(RP)
(6)
Obs: tem acesso ao
valor de P’(M - 1)
Mapeamento de Sn (8)
REDE
NEURAL
(RN’)
(9)
P’m
Obs: corresponde à rede RN
comos pesos reajustados
(1)
ALFA BETA
ITERATIVE DEEPENING
TABELA TRANSPOSIÇÃO
RN com pesos reajustados (7)
ALGORITMO
GENÉTICO
(AG)
Mapeamento de Si
Pi
REDE
NEURAL
(RN)
Novos Pesos
Arquitetura
do jogador
TABULEIRO
ESTADO S0
11/18
Criação de uma segunda rede neural MLP


Versão multi-agente do jogador LS-VisionDraugths
Duas redes neurais:
 Inicio
até ‘meio’ do jogo: LS-VisionDraughts
 ‘Meio’ até final do jogo:jogador de final de jogo

Especialidade da segunda rede: jogar em
tabuleiros que tenha como estado inicial 10 peças
ou menos.
II Workshop de Dissertações – Mestrado em Ciência da Computação
12/18
Criação de uma segunda rede neural
(cont.)


Obtida a partir do treinamento envolvendo
gerações de redes neurais especializadas em
estados de final de jogo, que são minerados por
Redes de Kohonen
Aprendizado por reforço e por TD(λ)
II Workshop de Dissertações – Mestrado em Ciência da Computação
13/18
Aspectos gerais do jogador de final
de jogo



Características iniciais: idem usadas no LS-Draughts
Uso de um AG para selecionar um conjunto mínimo
de características de final de jogo
Treinamento feito através de Aprendizagem por
reforço TD (λ) com self-play com clonagem
II Workshop de Dissertações – Mestrado em Ciência da Computação
14/18
Seleção de estados de tabuleiro com
10 peças




Por que 10 peças no tabuleiro?
Base de dados formada a partir da junção dos
jogadores LS e VisionDraughts
Classificação dos estados da base através de
Redes de Kohonen
Seleção feita por incidência dos estados na base
II Workshop de Dissertações – Mestrado em Ciência da Computação
15/18
Resultados esperados




Jogador de final de jogo competitivo
Conjunto mínimo de características para
representar final de partida
Mínimo de intervenção humana no treinamento da
rede
Eliminar ou, no mínimo, reduzir situações de loops
indesejáveis
II Workshop de Dissertações – Mestrado em Ciência da Computação
16/18
Cronograma
Atividade/Mês
Ago Set Out Nov Dez Jan Fev Mar Abr Mai Jun Jul
2008 2008 2008 2008 2008 2009 2009 2009 2009 2009 2009 2009
Pesquisas Bibliográficas
X
X
Estudo do jogador NeuroDraughts
Estudo do jogador LsDraughts
Estudo do jogador VisionDraughts
Ordenação da árvore de busca
Testes ordenação
Junção do LsDraughts e VisionDraughts
Testes junção
Implementação da segunda RNA
Testes com a rede
Analise de resultados obtidos em cada
implementação
Comparação de resultados
Submissão de artigos
Redação da dissertação
Apresentação/Defesa
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
X
II Workshop de Dissertações – Mestrado em Ciência da Computação
X
X
X
X
X
X
X
X
X
X
X
X
X
17/18
Referências







BERLEKAMP, E. (1996). The economist’s view of combinatorial games. Proceedings of MSRI Workshop
on Combinatorial Games.
CAIXETA, G. S. (2008). Visiondraughts -um sistema de aprendizagem de jogos de damas baseado
em redes neurais, diferenças temporais, algoritmos eficientes de busca em árvores e informações
perfeitas contidas em bases de dados. Master’s thesis, Universidade Federal de Uberlândia.
Caixeta, G. S. and da Silva Julia, R. M. (2008). A draughts learning system based on neural
networks and temporal differences: The impact of an efficient tree-search algorithm. The 19th
Brazilian Symposium on Artificial Intelligence, SBIA 2008.
CHELLAPILLA, K. and FOGEL, D. B. (2000). Anaconda defeats hoyle 6-0: A case study competing an
evolved checkers program against commercially available software. Proceedings of the 2000
Congress on Evolutionary Computation CEC00, La Jolla Marriott Hotel La Jolla, California, USA,
page 857.
LYNCH, M. (2007). Neurodraughts - an application of temporal diference learning to
draughts.Master’s thesis, Dept. of CSIS, University of Limerick, Ireland.
NETO, H. C. (2007). Ls-draughts - um sistema de aprendizagem de jogos de damas baseado em
algoritmos genéticos, redes neurais e diferenças temporais. Master’s thesis, Universidade Federal de
Uberlândia.
NETO, H. C., JULIA, R. M. S., and Caixeta, G. (2008). LS-Draughts- A Draughts Learning System
Based on Genetic Algorithms, Neural Network and Temporal Differences, pages 73– 82.
Kirchengasse: I-Tech Educational and Publishing KG,2008.
18/18