Algoritmos Genéticos em Jogos de Damas

Prévia do material em texto

ALGORITMOS GENÉTICOS APLICADOS A JOGOS DE DAMAS
Diogo Nocera Magalhães
Projeto de Graduação apresentado ao Curso
de Engenharia Eletrônica e de Computação
da Escola Politécnica, Universidade Federal
do Rio de Janeiro, como parte dos requisitos
necessários à obtenção do t́ıtulo de Enge-
nheiro.
Orientador: José Gabriel Rodriguez Car-
neiro Gomes
Rio de Janeiro
Julho de 2021
ALGORITMOS GENÉTICOS APLICADOS A JOGOS DE DAMAS
Diogo Nocera Magalhães
PROJETODEGRADUAÇÃO SUBMETIDO AO CORPODOCENTE DO CURSO
DE ENGENHARIA ELETRÔNICA E DE COMPUTAÇÃO DA ESCOLA PO-
LITÉCNICA DA UNIVERSIDADE FEDERAL DO RIO DE JANEIRO COMO
PARTE DOS REQUISITOS NECESSÁRIOS PARA A OBTENÇÃO DO GRAU
DE ENGENHEIRO ELETRÔNICO E DE COMPUTAÇÃO
Autor:
Diogo Nocera Magalhães
Orientador:
Prof. José Gabriel Rodriguez Carneiro Gomes, Ph.D.
Examinador:
Prof. Mariane Rembold Petraglia, Ph.D.
Examinador:
Prof. Renato Campos Mauro, M.Sc.
Rio de Janeiro
Julho de 2021
ii
Declaração de Autoria e de Direitos
Eu, Diogo Nocera Magalhães CPF 149.068.087-00, autor da monografia Algo-
ritmos Genéticos e Damas, subscrevo para os devidos fins, as seguintes informações:
1. O autor declara que o trabalho apresentado na disciplina de Projeto de Gra-
duação da Escola Politécnica da UFRJ é de sua autoria, sendo original em forma e
conteúdo.
2. Excetuam-se do item 1. eventuais transcrições de texto, figuras, tabelas, conceitos
e idéias, que identifiquem claramente a fonte original, explicitando as autorizações
obtidas dos respectivos proprietários, quando necessárias.
3. O autor permite que a UFRJ, por um prazo indeterminado, efetue em qualquer
mı́dia de divulgação, a publicação do trabalho acadêmico em sua totalidade, ou em
parte. Essa autorização não envolve ônus de qualquer natureza à UFRJ, ou aos seus
representantes.
4. O autor pode, excepcionalmente, encaminhar à Comissão de Projeto de Gra-
duação, a não divulgação do material, por um prazo máximo de 01 (um) ano,
improrrogável, a contar da data de defesa, desde que o pedido seja justificado, e
solicitado antecipadamente, por escrito, à Congregação da Escola Politécnica.
5. O autor declara, ainda, ter a capacidade juŕıdica para a prática do presente ato,
assim como ter conhecimento do teor da presente Declaração, estando ciente das
sanções e punições legais, no que tange a cópia parcial, ou total, de obra intelectual,
o que se configura como violação do direito autoral previsto no Código Penal Bra-
sileiro no art.184 e art.299, bem como na Lei 9.610.
6. O autor é o único responsável pelo conteúdo apresentado nos trabalhos acadêmicos
publicados, não cabendo à UFRJ, aos seus representantes, ou ao(s) orientador(es),
qualquer responsabilização/ indenização nesse sentido.
7. Por ser verdade, firmo a presente declaração.
Diogo Nocera Magalhães
iii
UNIVERSIDADE FEDERAL DO RIO DE JANEIRO
Escola Politécnica - Departamento de Eletrônica e de Computação
Centro de Tecnologia, bloco H, sala H-217, Cidade Universitária
Rio de Janeiro - RJ CEP 21949-900
Este exemplar é de propriedade da Universidade Federal do Rio de Janeiro, que
poderá inclúı-lo em base de dados, armazenar em computador, microfilmar ou adotar
qualquer forma de arquivamento.
É permitida a menção, reprodução parcial ou integral e a transmissão entre bibli-
otecas deste trabalho, sem modificação de seu texto, em qualquer meio que esteja
ou venha a ser fixado, para pesquisa acadêmica, comentários e citações, desde que
sem finalidade comercial e que seja feita a referência bibliográfica completa.
Os conceitos expressos neste trabalho são de responsabilidade do(s) autor(es).
iv
AGRADECIMENTO
Agradeço à universidade que me proporcionou a formação necessária para produzir
este trabalho.
v
RESUMO
Desde que a computação foi inventada, um dos maiores desafios do homem tem
sido criar algoritmos que simulem a inteligência humana e que consigam lidar com
situações de soluções inexatas.
Neste sentido, um dos meios utilizados para criar tais algoritmos, é o prinćıpio da
seleção natural, extráıdo da Computação Evolutiva, através do qual é posśıvel criar
um algoritmo que consiga lidar com as situações supracitadas.
Tendo em vista estes pressupostos, o escopo deste trabalho é criar um algoritmo
de computador que seja capaz de jogar damas de forma a se equiparar ou superar
um ser humano e, para atingir tal objetivo, foi utilizado o conceito da Computação
Evolutiva, em conjunto com redes neurais. Vale ressaltar que existem outros meios
de se atingir tal objetivo como os apontados em [1] e [2].
Sendo assim, através de um Algoritmo Genético, redes neurais, os jogadores,
competem em sucessivos campeonatos para determinar quais os melhores jogadores
durante várias gerações
Depois de várias gerações treinadas, os jogadores já realizavam jogadas que de-
monstravam inteligência por parte do algoritmo. Estes jogadores conseguiam: (i)
empatar com jogadores humanos de ńıvel médiano; (ii) ganhar de jogadores inician-
tes; (iii) ficar entre os 36% melhores jogadores em uma plataforma de competição
entre algoritmos para jogar damas; (iv) ganhar de um aplicativo de damas comer-
cial nas suas menores dificuldades. Além disso, foi demonstrado o potencial de
treinar jogadores melhores, bastando, para isso, apenas algumas melhorias na fase
de treinamento.
Palavras-chave: Inteligência Computacional, Computação Evolutiva, Algoritmos
Genéticos, Redes Neurais.
vi
ABSTRACT
Since computation was created, one of the biggest challenges man needs to over-
come has been to create algorithms that simulate human intelligence and that can
handle situations where there is no right solution.
That said, one of the means used to create said algorithms is the natural selection,
from Evolutionary Computing, which can create an algorithm that is able to handle
the above mentioned solutions.
With this in mind, the scope of this work is to create a computer algorithm that
is able to play checkers in a way that matches or even overcome a human being and,
to reach this objective, Evolutionary Computing was used alongside artificial neural
networks. It is important to take into account that there are other means to achive
this objective like shown in [1] and [2].
With this, through a genetic algorithm, artificial neural networks, players com-
pete in successive championships to determine the best players throughout many
generations.
After many trained generations, players already could play in a way that showed
intelligence. These players could: (i) draw against intermediary players; (ii) win
against beginner players; (iii) get in the top 36% of an online platform where chec-
kers algorithms compete; (iv) win against a checkers commercial app in the lowest
di�culties. Other than that, it showed the potential to train even better players,
for that it only needed some improvements to the training phase.
Key-words: Computational Intelligence, Evolutionary Computing, Genetic Algo-
rithms, Artificial Neural Networks.
vii
SIGLAS
UFRJ - Universidade Federal do Rio de Janeiro
ANN - Artificial Neural Networks
viii
Sumário
1 Introdução 1
1.1 Tema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Delimitação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Justificativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.4 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.5 Metodologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.6 Descrição . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Teoria 6
2.1 Python, Keras e Tensorflow . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Computação Evolutiva e a Seleção Natural . . . . . . . . . . . . . . . 7
2.3 Redes NeuraisArtificiais e seu Funcionamento . . . . . . . . . . . . . 8
2.4 Sistemas Coevolucionários e Damas . . . . . . . . . . . . . . . . . . . 8
2.5 Algoritmo Minmax para Decisão de Jogadas . . . . . . . . . . . . . . 9
3 Metodologia 11
3.1 Jogo de Damas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
3.2 Jogador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.3 Campeonato e Seleção Natural . . . . . . . . . . . . . . . . . . . . . . 18
3.4 Mutação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.5 Avaliação do Sistema durante o Treinamento . . . . . . . . . . . . . . 22
3.6 Testes no Site CodinGame . . . . . . . . . . . . . . . . . . . . . . . . 23
3.7 Meios de Teste Intermediários . . . . . . . . . . . . . . . . . . . . . . 24
4 Resultados 27
4.1 CodinGame . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
ix
4.2 Aplicativo de Damas . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Partidas contra Humanos . . . . . . . . . . . . . . . . . . . . . . . . . 33
4.4 Avaliando Inteligência do Sistema . . . . . . . . . . . . . . . . . . . . 34
4.5 Diminuição da Melhora do Sistema ao longo
das Gerações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.6 Variedade Genética dos Jogadores durante o Treinamento . . . . . . . 37
5 Conclusões 39
5.1 Trabalhos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
Bibliografia 41
A Partidas Realizadas 43
A.1 Partidas contra humanos . . . . . . . . . . . . . . . . . . . . . . . . . 43
A.2 Partidas contra aplicativos . . . . . . . . . . . . . . . . . . . . . . . . 43
A.3 Fontes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
B Entrevistas 44
B.1 Entrevista com Jogador A . . . . . . . . . . . . . . . . . . . . . . . . 44
B.2 Entrevista com Vińıcius Damir . . . . . . . . . . . . . . . . . . . . . 44
C Código Fonte 45
x
Lista de Figuras
1.1 Fluxuograma do Ciclo de Seleção. . . . . . . . . . . . . . . . . . . . . . 3
3.1 Representação de tabuleiro de damas com números e letras identificadores. 13
3.2 Representação da matriz de tabuleiro do ińıcio de uma partida. Nela x
equivale a -1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.3 Representação da matriz de tabuleiro de uma partida em andamento. Nela
x equivale a -1, y equivale a -k e 9 a k. . . . . . . . . . . . . . . . . . . . 17
3.4 Lógica de avaliação de um tabuleiro por um jogador. . . . . . . . . . . . 18
3.5 Lógica de escolha de jogada por um jogador. . . . . . . . . . . . . . . . . 19
3.6 Lógica do algoritmo Minmax para classificação de tabuleiros levando em
consideração jogadas à frente. . . . . . . . . . . . . . . . . . . . . . . . 19
3.7 Fluxuograma explicando um campeonato. . . . . . . . . . . . . . . . . . 21
3.8 Fluxuograma de validação do treinamento. . . . . . . . . . . . . . . . . . 23
4.1 Ranking do sistema ao longo das gerações. . . . . . . . . . . . . . . . . . 30
4.2 Colocação no site Codingame . . . . . . . . . . . . . . . . . . . . . . . 31
4.3 Jogo realizado para testar a inteligência do sistema. . . . . . . . . . . . . 36
xi
Caṕıtulo 1
Introdução
Neste Caṕıtulo será abordado de forma sucinta a proposta deste trabalho. Nele
serão discutidas as razões pelas quais o trabalho foi feito, seus objetivos, limitações
e também haverá uma breve descrição sobre os próximos caṕıtulos do trabalho.
1.1 Tema
A seleção natural [3], desde os primórdios da existência, determina quais in-
div́ıduos de uma população estão mais aptos a sobreviver no meio. Neste sentido, o
objetivo do trabalho é criar um algoritmo de computador que, através de um pro-
cesso que mimetiza a seleção natural, selecione um jogador-computador que jogue
damas de forma a se equiparar ou superar um ser humano.
1.2 Delimitação
O objeto de estudo é ensinar um computador a jogar damas sem que haja a
necessidade de supervisão ou Data Science. Dessa forma, foi decidido o uso de
algoritmos genéticos como método utilizado no projeto.
1.3 Justificativa
Com o avanço da tecnologia, se faz cada vez mais necessário que tarefas antes
realizadas apenas por pessoas sejam realizadas por máquinas para que a dedicação
1
das pessoas possa ser direcionado em outros objetivos. Contudo, dentre essas tarefas,
existem algumas de dif́ıcil automatização graças à sua natureza complexa de se criar
um algoritmo que as resolva.
A complexidade acima citada impossibilita a criação de um algoritmo simples para
sua realização e também o uso de informações prévias que possam auxiliar na ação
a ser realizada, visto que não existe uma definição clara de qual ação o algoritmo
deve tomar em uma dada situação.
Neste sentido, o presente projeto busca avançar o estudo de como ensinar máquinas
a realizar tais tarefas sem ter um parâmetro claramente definido para dizer se uma
ação é boa ou ruim.
1.4 Objetivos
O objetivo geral do trabalho é, então, desenvolver um método que consiga criar
um algoritmo de computador que seja capaz de jogar damas tão bem quanto ou
melhor que um ser humano sem o uso de qualquer dado coletado ou expertise no
assunto.
1.5 Metodologia
A solução utilizada para realizar esse treinamento de forma não supervisionada
é usar um algoritmo genético que, através de várias gerações, selecionará uma rede
neural para jogar damas. Nessa seleção natural, 30 jogadores jogam entre si num
campeonato. Nele cada vitória dá 1 ponto ao jogador. A cada derrota, ele perde 2
pontos. Cada empate dá 0 pontos. Ao final do campeonato, os 15 jogadores com
maior pontuação são selecionados.
Em seguida, esses 15 jogadores geram 15 filhos (mais detalhes são dados na Seção
3.4), um para cada jogador. Terminada essa etapa, a seleção natural começa nova-
mente, com 15 novos jogadores sendo selecionados e assim repetindo o ciclo até que
um bom jogador seja criado.
2
Figura 1.1: Fluxuograma do Ciclo de Seleção.
Para realizar tal objetivo, inicialmente, cria-se uma rede neural que classifique o
quão bom um tabuleiro é para um jogador. Um array que representa esse tabuleiro é
enviado como entrada para uma rede neural de 3 camadas, tendo a primeira camada
40 neurônios1, a segunda 10 neurônios e a terceira camada 1 neurônio (40x10x1) que
tem como uma sáıda um número entre -1 e 1. Quanto maior o número, melhor a
situação do tabuleiro é para o jogador. Quanto menor é o número, pior a situação.
A decisão de qual a melhor jogada é feita através da pontuação dada para cada
jogada posśıvel a partir de um tabuleiro. São olhadas 3 jogadas à frente utilizando
um algoritmo de Minmax Alpha Beta.
1Neurônio é o elemento do qual uma rede neural artificial é composta. Cada neurônio recebe
como entrada todas as sáıdas da camada anterior ou, no caso da primeira camada de uma rede
neural, todas as entradas enviadas pelo sistema para classificação. Cada uma dessas entradas do
neurônio é multiplicada por um peso espećıfico e, após todas as entradas serem multiplicadas por
seus pesos, esses resultados são somados.
3
Além disso, na mutação de cada filho seus pesos e biases2 foram variados assim
como o valor da representação da dama.
Para avaliar os resultados do algoritmo genético, a seguinte metodologia está
sendo utilizada: de 20 em 20 gerações os jogadores atualmente selecionados jogam
com os jogadores de validação. Ao final, a pontuação de cada jogador é observada
e os jogadores atualmente selecionados se tornam os novos jogadores de validação.
Os jogadores de validação são inicializados com os primeiros jogadores criados no
ińıcio do treinamento
Outro meio avaliado foi o de realizar partidas entre uma pessoa e o computador
para verificar se as jogadas do computador, realmente, não estão sendo escolhidas
ao acaso.
Tal processode treinamento pode ser visualizado de forma resumida na Figura
1.1.
1.6 Descrição
No Caṕıtulo 2 será abordada de forma ampla o funcionamento de algoritmos
genéticos e redes neurais para contextualização. Também será abordada a teoria
utilizada para fundamentação do projeto.
No Caṕıtulo 3 a metodologia utilizada para se obter os resultados demonstrados
será explicada passo a passo, desde as ferramentas utilizadas para atingir o objetivo
do trabalho até a lógica da mutação utilizada no projeto.
No Caṕıtulo 4 serão mostrados os resultados obtidos durante o desenvolvimento
do projeto. Tais resultados têm como foco avaliar se o sistema desenvolvido neste
projeto realizou jogadas de forma inteligente ao invés de só fazer jogadas ao acaso.
2Bias é um valor somado à sáıda da multiplicação entre as entradas de um neurônio e seus
pesos.
4
No Caṕıtulo 5 serão apresentadas as conclusões finais do projeto tiradas a partir
dos resultados obtidos. Além disso, também serão propostos trabalhos futuros que
podem agregar valor ao presente projeto.
5
Caṕıtulo 2
Teoria
Para que o presente projeto fosse desenvolvido, foram fundamentais diversos con-
ceitos e ferramentas a serem usadas. Dentre as ferramentas necessárias estão a
linguagem de programação Python e as bibliotecas de código aberto TensorFlow
e Keras. Já os conceitos essenciais para a criação do projeto vão desde a Seleção
Natural de Darwin [3] em conjunto com o conceito de Computação Evolutiva [4] até
conceitos de redes neurais [5] e teoria dos jogos a partir de um algoritmo Minmax
[6].
2.1 Python, Keras e Tensorflow
Python é uma linguagem de programação de alto ńıvel criada por Guido van Ros-
sum [7]. Essa linguagem de programação foi escolhida pela grande quantidade de
ferramentas relacionadas ao treinamento de redes neurais como o Keras e o Tensor-
Flow e à facilidade de escrita da mesma.
Já Tensorflow é uma biblioteca de Python desenvolvida pela Google [8] que fornece
uma gama de ferramentas que auxiliam no desenvolvimento de códigos voltados ao
aprendizado de máquina, como redes neurais.
Para utilizar o TensorFlow foi utilizada a biblioteca Keras [9] que serve como
interface para facilitar o uso e desenvolvimento de redes neurais no TensorFlow.
6
2.2 Computação Evolutiva e a Seleção Natural
Computação Evolutiva [4] é uma área do aprendizado de máquina no qual sistemas
são desenvolvidos a partir de uma simulação da seleção natural conforme descrita
por Darwin em “A Origem das Espécies”[3].
Nela são criados diversos sistemas iniciados de forma aleatória focados na solução
de algum tipo de problema. Tais sistemas são colocados num ambiente simulado em
que eles têm que resolver tal problema e sua capacidade de solucionar tal problema,
aptidão1, é medida. Após medida a aptidão de cada um dos sistemas iniciados,
os mais aptos, com maior aptidão são selecionados. Tal processo de criação de
indiv́ıduos e seleção dos mesmos é denominado geração.
Selecionados os indiv́ıduos mais adaptados ao ambiente, estes se reproduzem e,
em alguns modelos, se perpetuam para as próximas gerações. Tal reprodução se dá
através da mutação dos genes de cada indiv́ıduo e, em alguns casos, da recombinação
dos genes de cada indiv́ıduo, sendo os genes, no contexto atual, parâmetros usados
para resolver o problema desejado que são mudadas ao longo das gerações.
Na recombinação, os genes dos pais são misturados de forma a gerar um ou mais
indiv́ıduos filhos. Essa mistura é feita selecionando alguns genes de um dos pais e o
resto desses genes do outro pai. Na mutação os genes de um indiv́ıduo são alterados
de forma aleatória, com certas limitações, para gerar um filho. Algoritmos que usam
recombinação junto de mutação são algoritmos de Evolution Strategies, já algoritmos
que só usam mutação são algoritmos de Evolutionary Programming.
A mutação citada anteriormente deve ser controlada de alguma forma, visto que,
se a mutação for muito pequena, o novo indiv́ıduo gerado será tão parecido com
o indiv́ıduo original que praticamente não mudará a aptidão do jogador novo em
1Aptidão é um valor numérico usado para medir o quão adaptado a um sistema está um in-
div́ıduo. No caso da Computação Evolutiva, o termo aptidão se refere a quão bem um indiv́ıduo
consegue resolver o problema desejado. Este valor pode ser relativo aos outros indiv́ıduos no trei-
namento, como no caso de uma competição entre indiv́ıduos, ou um valor absoluto, como por
exemplo em um problema que tenha uma solução definida.
7
comparação com o original e, se a mutação for muito grande, o novo indiv́ıduo será
tão diferente do indiv́ıduo original que sua aptidão não terá nenhuma relação com
a aptidão do indiv́ıduo original.
No caso deste projeto, é usado um fator de mutação, representado pela letra grega
�, que determina o quanto os genes são modificados durante a mutação. Esse fator
de mutação é modificado com cada indiv́ıduo de forma que os indiv́ıduos não são
somente avaliados pela sua aptidão, mas pela sua capacidade de gerar filhos que
tenham maior aptidão que o indiv́ıduo original.
Para finalizar, o modo de avaliar a aptidão de um indiv́ıduo deve ser determinado
previamente de acordo com regras que estimulem a seleção de indiv́ıduos com maior
capacidade de resolver o problema em questão.
2.3 Redes Neurais Artificiais e seu Funcionamento
Assim como a Computação Evolutiva, redes neurais artificiais (ANN) é uma área
do aprendizado de máquina. Nesta área os sistemas são desenvolvidos de forma a
simular o sistema nervoso de um animal com algumas poucas diferenças.
Em ANN, cada neurônio recebe várias entradas e entrega apenas uma sáıda que,
por sua vez, pode ser usada como a entrada de outro neurônio ou como a sáıda da
ANN. Essa sáıda da ANN, no contexto desse trabalho, é um valor numérico que
equivale à vantagem ou desvantagem do jogador (Seção 3.2) em relação ao estado
de tabuleiro analisado, mas essa sáıda pode servir para identificar qualquer coisa
relacionada ao problema em mãos.
2.4 Sistemas Coevolucionários e Damas
Conforme explicado na Seção 2.2, para que um um indiv́ıduo seja selecionado é
necessário que sua adaptação ao meio seja medida de uma forma ou de outra. Em
vários casos, é fácil identificar a aptidão, visto que é fácil identificar o quão perto
da solução do problema um indiv́ıduo está.
8
Existem casos em que a medida de adaptação de um indiv́ıduo a um ambiente
é algo muito complexo de se decidir por ser um conceito muito abstrato para tal.
No caso do presente projeto é preciso medir o quão bom um indiv́ıduo é jogador de
damas ou não.
Para que tal situação seja resolvida o conceito de Sistemas Coevolucionários [10]
é utilizado. Este conceito diz que o ńıvel de adaptação de um indiv́ıduo a um meio
não é simplesmente determinado em relação ao ambiente estático, mas também em
relação a outros indiv́ıduos que vivem nele, sejam os efeitos desses outros indiv́ıduos
prejudiciais ou beneficiais ao indiv́ıduo nesse meio.
No contexto do presente projeto, diversos indiv́ıduos diferentes foram colocados
para competir entre si, assim como em [11]. Com essa competição entre indiv́ıduos
sendo realizada, se tornava posśıvel descobrir quais os indiv́ıduos mais adaptados ao
meio, visto que estes obteriam mais vitórias que os menos adaptados.
2.5 Algoritmo Minmax para Decisão de Jogadas
Minmax é um algoritmo usado na teoria dos jogos e no aprendizado de máquina
para auxiliar na escolha da melhor jogada posśıvel em qualquer momento do jogo. A
ideia principal é que são olhadas algumas jogadas à frente a partir de um certo estado
de jogo, assumindo sempre que o jogador adversário fará sempre a melhor jogada
posśıvel, ou seja, será feita a jogada que minimizaráa vantagem do adversário.
Digamos que num jogo existam três posśıveis jogadas no estado de jogo atual
(jogadas A, B e C) e cada uma dessas jogadas permite ao adversário fazer mais 3
jogadas. Assim, se olharmos duas jogadas à frente, vemos 9 posśıveis estados de jogo.
Feito isso, analisamos todos esses 9 estados de jogo depois da jogada do adversário
e vemos qual a melhor jogada posśıvel que o adversário pode fazer em cada umas
dessas situações (jogadas R, S, T, U, V, W, X, Y e Z). Então, se foi feita a jogada A,
a melhor jogada posśıvel que o adversário pode fazer nas 3 possibilidades de jogada
é Z, se foi jogado B a melhor é Y, se foi jogado C a melhor é X. A partir disso É
analisado entre as jogadas X, Y e Z qual delas foi a pior jogada do adversário, ou
9
seja, a em que o jogador passa a ter mais vantagem após feita. Essa jogada define
qual jogada deverá ser feita pelo jogador que está analisando a situação. Se a pior
das 3 jogadas é a X, o jogador fará a jogada A, se foi Y, ele deverá fazer a jogada B
e se foi Z ele deverá fazer a jogada C.
O algoritmo é implementado da seguinte forma:
1. Verifica se o estado de jogo analisado é o do número de jogadas à frente que
deve ser analisado;
2. Se for, lança como sáıda um valor numérico que determina quem está ganhando
a partida. Quanto mais negativo o valor, mais próximo de ganhar a partida o
adversário está, quanto mais positivo o valor, mais o jogador usando Minmax
está próximo de ganhar;
3. Caso contrário, é verificado se a próxima jogada será feita pelo jogador utili-
zando o Minmax ou pelo jogador adversário;
4. Caso a jogada esteja sendo feita pelo jogador usando o Minmax, todas as
jogadas posśıveis formam novos estados de jogo e cada um desses estados de
jogo é analisado nesse algoritmo a partir do passo 1. Feito isso, o que tem o
valor mais positivo é retornado como sáıda;
5. Caso a jogada esteja sendo feita pelo jogador adversário, todas as jogadas
posśıveis formam novos estados de jogo e cada um desses estados de jogo é
analisado nesse algoritmo a partir do passo 1. Feito isso, o que tem o valor
mais negativo é retornado como sáıda;
Para que esse algoritmo seja executado de forma mais rápida foi utilizada a va-
riação de poda ↵-�. Tal variação tem como objetivo reduzir o número de jogadas
a ser analisada pelo algoritmo Minmax. Nela, quando uma jogada pior, no caso de
ser o jogador usando o Minmax ou melhor, no caso de ser o jogador adversário, é
encontrada, a busca de jogadas à frente deste nó é parada pois já foi encontrada a
jogada que que maximizará ou minimizará a sáıda.
10
Caṕıtulo 3
Metodologia
A partir das bases teóricas explicadas no Caṕıtulo 2 e seguindo o caminho proposto
por [11], foi elaborada uma metodologia para se obter um sistema jogador de damas.
Para que o sistema jogador de damas fosse elaborado, se fez necessário implemen-
tar um ambiente que simulasse um jogo de damas, permitindo que jogadas fossem
feitas, mudando o estado do tabuleiro e avaliando se um jogador perdeu, ganhou
ou empatou. Esse sistema foi elaborado em detrimento do uso de um sistema já
pronto para que o desenvolvimento do jogador pudesse ser mais flex́ıvel, visto que
o ambiente desenvolvido poderia ser alterado para se adaptar às necessidades do
projeto e pudesse ter melhor desempenho durante o treinamento, já que apenas o
mı́nimo necessário para a implementação de um jogo de damas foi feito, ao invés de
ser necessária uma interface gráfica, por exemplo.
Em seguida foi desenvolvido um sistema, também chamado de jogador, dotado
das ferramentas necessárias para que ele pudesse jogar uma partida de damas. Entre
essas ferramentas estão: (i) uma rede neural capaz de receber um tabuleiro de damas
como entrada e lançar como sáıda o estado do jogo, uma classificação numérica
representando a vantagem ou desvantagem do jogador em relação ao oponente neste
tabuleiro; (ii) a capacidade de, a partir de um tabuleiro, descobrir todas as jogadas
posśıveis para o jogador atual; (iii) a capacidade de juntar tanto a classificação do
estado de jogo de um tabuleiro com a habilidade de descobrir as posśıveis jogadas a
serem feitas para decidir qual a melhor jogada posśıvel.
11
Depois de desenvolvido esse sistema, foi elaborado um sistema de seleção natural
em forma de campeonatos em que todos os jogadores competem entre si recebendo
pontuações positivas, negativas ou neutras por suas vitórias, derrotas e empates
respectivamente. A partir da pontuação obtida por cada jogador, os melhores eram
selecionados para competirem nas próximas gerações e sofrerem mutação (Seção 3.4)
gerando jogadores filhos.
Depois de serem selecionados os melhores jogadores, estes se reproduziam, so-
frendo mutação em seus genes (Seção 2.2), no caso de uma rede neural, seus pesos
e biases. Além disso, seu fator de mutação, sigma, era alterado para que a mutação
fosse alterada ao longo das gerações.
Como último passo do desenvolvimento do sistema, de 20 em 20 gerações os sis-
temas eram avaliados para verificar se estavam melhorando em relação aos seus
antecessores de duas formas diferentes: a primeira forma era fazer com que os siste-
mas da geração atual competissem com seus antecessores; a segunda forma utilizada
foi ver a classificação do melhor sistema da geração atual no site CodinGame [12] e
compará-la com a classificação do melhor de seus antecessores.
Além desses passos do desenvolvimento, também foi necessário elaborar diversos
meios de teste para que as funções intermediárias de todo o projeto fossem testadas,
como o desenvolvimento de: (i) um testador que permitia que o sistema jogasse com
um ser humano; (ii) um código que avaliava a jogada de um dado sistema treinado
a partir de um tabuleiro inicial; (iii) a verificação de todos os posśıveis movimentos
para um jogador a partir de um estado de tabuleiro; (iv) outros que serão melhor
detalhados na Seção 3.7.
3.1 Jogo de Damas
Para desenvolver o sistema que jogasse damas, primeiro se fez necessário imple-
mentar um ambiente em que fosse posśıvel simular um jogo de damas. Esse sistema
consegue exibir para um usuário o tabuleiro atual, receber jogadas como entrada, ne-
gar jogadas inválidas e determinar o fim da partida por vitória de um dos jogadores
12
Figura 3.1: Representação de tabuleiro de damas com números e letras
identificadores.
ou empate.
O sistema foi implementado seguindo as regras definidas em [13]. Algumas das
regras utilizadas são diferentes da versão mais jogada de damas no Brasil, em que a
dama pode se mover quantas casas quiser para frente ou para trás. Nesta versão de
damas usada no projeto, cada peça normal do jogador pode se mover em direção à
área do adversário, ou seja, para frente, se movendo para uma casa diretamente na
sua diagonal. A dama pode se mover uma casa em ambas as direções para casas na
sua diagonal direta. Caso exista uma peça adversária que possa ser capturada, ela
deverá ser capturada antes que qualquer outra jogada seja realizada.
Para facilitar o entendimento de todas as seções e caṕıtulos futuros, se faz ne-
cessário elaborar um meio de se anotar as jogadas realizadas. Para isso um tabuleiro
de damas é constitúıdo por colunas enumeradas por letras de A a H da esquerda para
a direita e de linhas enumeradas de 1 a 8 de cima para baixo conforme demonstrado
na Figura 3.1. Isso se tornará importante em análises futuras sobre jogadas feitas
pelo sistema e por jogadores.
Com isso em mente, o ambiente de jogo de damas foi desenvolvido utilizando a
linguagem Python [7] a partir do paradigma de programação orientada a objeto [14].
Nesse ambiente foram criadas diversas classes representando diferentes partes do
jogo de damas, sendo estas: (i) o tabuleiro, representando o tabuleiro do jogo de
13
damas com as peçasinclusas; (ii) uma casa do tabuleiro representando uma das casas
de um tabuleiro; (iii) um movimento realizado por uma peça dizendo de qual casa do
tabuleiro a peça começa o movimento e por onde ela passa; (iv) uma partida de jogo
de damas que recebe movimentos de ambos os jogadores e os efetua no tabuleiro.
A classe de tabuleiro é usada principalmente para armazenar o estado atual de um
jogo, ou seja, a localização de todas as peças, receber um objeto da classe movimento,
verificar a validade desse movimento e, caso esse movimento seja válido, atualizar o
estado atual do tabuleiro após a execução desse movimento. Além disso, ela também
cumpre algumas funções auxiliares como exibir em tela para um usuário o estado
atual do tabuleiro armazenado e converter esse tabuleiro em um vetor para que este
seja usado como entrada na rede neural de um jogador.
A classe movimento é usada para anotar um movimento simples que será feito
por um jogador. Ela apenas registra qual a casa inicial do movimento e qual a casa
final do movimento. É a partir dela que o tabuleiro pode mudar seu estado.
A classe casa é utilizada para representar uma das 64 casas do tabuleiro de damas.
Essas casas, conforme explicado no ińıcio dessa Seção, são enumeradas de A a H e
de 1 a 8. No caso do código, como definido pela linguagem Python, as casas são
enumeradas de 0 a 7 ao invés de 1 a 8.
Por último também foi criada a classe partida que é usada para efetuar uma
partida entre dois jogadores. Essa classe foi especializada em uma feita para realizar
a partida entre dois sistemas, a usada no treinamento, e uma em que era posśıvel
que um sistema jogasse com um jogador humano.
Quando iniciada uma partida, essa classe cria um objeto da classe tabuleiro no
estado inicial do jogo de damas, conforme explicado em [13]. A classe partida informa
ou para o jogador humano ou para o sistema o estado atual do tabuleiro e espera
uma resposta no formato de uma classe de movimento que, por sua vez, é mandada
para o tabuleiro para que o estado atual do tabuleiro seja mudado de acordo com
ele.
14
3.2 Jogador
Inicialmente se faz necessário definir o que é um jogador. Um jogador é um sistema
que, a partir de um tabuleiro de entrada, realiza uma jogada a fim de vencer uma
partida de damas.
Tal classificação da vantagem ou desvantagem de um jogador é medida com um
número de -1 a 1. Quanto mais próximo de -1 esta classificação chega, mais próximo
de perder o jogador está. Já, se o jogador estiver próximo de 1 ele está próximo de
ganhar a partida. Na implementação, situações de derrota e vitória são classificadas
como -1 e 1, respectivamente, sem que o tabuleiro seja classificado pela rede neural.
Um jogador é uma rede neural que é capaz de classificar o tamanho da vantagem
ou desvantagem de um tabuleiro para o jogador, ou seja o estado de jogo, e um
algoritmo que, a partir de um tabuleiro, calcula todas as posśıveis jogadas que
podem ser realizadas à frente e, a partir de um algoritmo Minmax [6] determina
qual é a melhor jogada.
A rede neural é criada a partir da biblioteca Keras com o Tensorflow como bac-
kend1 (Seção 2.1). Esta rede neural avalia o estado de jogo. Esta é uma rede neural
que tem 3 camadas e 32 entradas. Sua primeira camada contém 40 neurônios, a
segunda camada 10 neurônios e a última camada 1 neurônio, portanto sua topologia
é 40x10x1. Cada camada da rede neural usa a tangente hiperbólica como função de
ativação. Essa função de ativação foi escolhida, principalmente, pela necessidade de
limitar a sáıda da rede neural na última camada entre -1 e 1, para que a vitória e
derrota pudessem ser equivalentes aos extremos da sáıda da rede neural.
1Backend se refere a uma parte do código que não é usada diretamente. Para que ela seja
usada, é necessário uma interface. No caso do projeto, a biblioteca Keras serve de interface para
a biblioteca TensorFlow. Ou seja, toda a lógica de treinamento de redes neurais e a classificação
das mesmas é na verdade feita no TensoFlow, mas as chamadas para tais funções de classificação e
treinamento são feitas através do Keras. Este modelo é usado para que o uso do TensorFlow seja
simplificado.
15
Esta rede neural recebe como entrada uma representação de um tabuleiro de
damas convertido de matriz para vetor. Nessa matriz representativa de um tabuleiro,
casas vazias eram representadas pelo número 0, casas com peças comuns do sistema
eram representadas pelo número 1, casas com peças comuns do adversário eram
representadas pelo número -1, casas com damas do sistema eram representadas pelo
número k e casas com damas do jogador adversário eram representadas pelo número
-k, onde k é um número de 1 a 3 que é um gene do treinamento e será detalhado
futuramente nesta Seção. Na Figura 3.2 observamos como o tabuleiro é representado
em matriz. Já na Figura 3.3 observamos um jogo em andamento onde ambos os lados
possuem damas e a representação desse jogo em matriz.
Quando recebida essa matriz representativa de um tabuleiro para classificação de
estado de jogo, o jogador sistema remove as casas não usadas no jogo de damas e
converte a mesma para um vetor enfileirando todas as linhas da matriz, lança ela
como entrada de sua rede neural e retorna a sáıda da rede neural como a classificação
do estado de jogo que esse tabuleiro representa. Tal sequência lógica é representada
pela Figura 3.4.
Para realizar uma jogada, o jogador avalia não só o estado do tabuleiro atual, mas
também algumas jogadas à frente. Quando solicitado a fazer uma jogada, o jogador
calcula todos estados de tabuleiro posśıveis no número de jogadas à frente sendo
analisadas no momento, classifica o estado de tabuleiro de cada um desses posśıveis
cenários utilizando o método descrito anteriormente e escolhe como jogada a que,
na pior possibilidade posśıvel determinada pelo sistema, ou seja, assumindo que o
adversário fará a melhor jogada posśıvel, ele terá a menor perda posśıvel seguindo
a lógica do algoritmo Minmax [6].
Nas Figuras 3.5 e 3.6 podemos observar a sequência lógica descrita no páragrafo
anterior. Na Figura 3.5, o jogador recebe um tabuleiro que deve ser classificado,
analisa todas as jogadas posśıveis e cria uma matriz de tabuleiro para cada uma
dessas possibilidades. Em seguida ele envia cada um desses tabuleiros ao algoritmo
Minmax representado na Figura 3.6.
16
Figura 3.2: Representação da matriz de tabuleiro do ińıcio de uma
partida. Nela x equivale a -1.
Figura 3.3: Representação da matriz de tabuleiro de uma partida em
andamento. Nela x equivale a -1, y equivale a -k e 9 a k.
Ao receber um tabuleiro para classificação, o algoritmo Minmax : (i) inverte o
tabuleiro atual e verifica se este é a última jogada à frente a ser analisada; (ii) se
for, caso seja uma jogada do jogador, ele inverte o tabuleiro novamente, avalia o
tabuleiro e retorna sua classificação; (iii) se for, mas se a jogada realizada é do
adversário, é retornada a classificação do tabuleiro; (iv) se a jogada analisada não é
a última jogada à frente a ser analisada, o algoritmo analisa as jogadas que podem
ser realizadas no momento e cria uma matriz de tabuleiro para cada uma dessas
possibilidades; (v) ele repete os passos de (i) a (iv) para cada um dos tabuleiros
criados no passo (iv); (vi) caso a jogada analisada seja do jogador adversário, é
17
Figura 3.4: Lógica de avaliação de um tabuleiro por um jogador.
retornada a menor classificação entre as jogadas classificadas em (v); (vii) caso a
jogada analisada seja do jogador, é retornada a maior classificação entre as jogadas
classificadas em (v).
Um jogador é representado pela classe jogador. É nela em que a rede neural é
definida assim como a lógica do algoritmo Minmax utilizado e os hiperparâmetros2
do treinamento tais como: (i) o númerode jogadas a frente; (ii) o sigma do trei-
namento; (iii) a quantidade de pontos obtidos quando o jogador ganha, perde ou
empata uma partida.
Para efeitos de registro, cada jogador criado tem um nome consistindo da palavra
“Jogador ”concatenada com um identificador único. Cada jogador novo criado é
salvo numa pasta do projeto para facilidade de uso em testes fora do treinamento e
para que seja posśıvel realizar partidas entre ele e seres humanos.
3.3 Campeonato e Seleção Natural
Conforme descrito no ińıcio deste caṕıtulo, um sistema de campeonatos foi de-
senvolvido com o intuito de promover a seleção natural proposta em algoritmos
genéticos conforme elaborado na Seção 2.2. O modelo de seleção natural utilizado
2Hiperparâmetros são parâmetros definidos antes do treinamento e que alteram o progresso e
resultado do mesmo. Tais parâmetros são ajustados durante o treinamento com o fim de melhorar
os resultados do treinamento.
18
Figura 3.5: Lógica de escolha de jogada por um jogador.
Figura 3.6: Lógica do algoritmo Minmax para classificação de tabuleiros levando em
consideração jogadas à frente.
foi o mesmo de [4] e de [11]. Nele a ideia é de que os indiv́ıduos disputem entre si
para determinar os mais aptos que serão selecionados para gerações futuras.
No ińıcio do treinamento são criados quinze jogadores (Seção 3.2). Para cada um
deles, sua respectiva rede neural é iniciada com os pesos e biases entre -0.2 e 0.2 de
forma aleatória uniforme, sendo este valor um hiperparâmetro do treinamento. Após
criados os 15 jogadores iniciais, cada um deles gera um filho a partir de mutação
conforme descrito na Seção 3.4 e assim cada geração possui trinta jogadores.
19
Após os trinta jogadores iniciais serem criados, eles são colocados para competir
entre si em um campeonato composto por 5 rodadas. Numa rodada desse campe-
onato, cada jogador joga 2 partidas contra outro jogador aleatório. Em uma das
partidas ele faz o primeiro movimento, na outra partida ele joga em segundo.
Para a decisão de partidas, a cada jogador foi atribúıdo um número de 1 a 30
e uma lista com os números de 1 a 30 de forma sequencial foi criada. Depois,
utilizando o método shu✏e, da biblioteca Numpy [15], a lista foi embaralhada de
forma aleatória. Finalmente, o primeiro jogador nessa nova lista embaralhada foi
posto para jogar com o segundo jogador dessa lista, o terceiro com o quarto e assim
por diante. Não existe nenhum impedimento de que partidas entre dois jogadores
se repitam em rodadas diferentes.
Cada partida vencida por um jogador garante a ele 1 ponto, cada derrota faz
com que ele perca 2 pontos e empates não mudam sua pontuação. Esse esquema
de pontuação foi escolhido desta forma porque é melhor um jogador que perde o
mı́nimo posśıvel ao invés de um jogador que ganha e perde muito. Qualquer partida
cujo número de jogadas ultrapassasse 100 é considerada um empate para que as
partidas não sejam muito demoradas. Como outro fator importante, esse esquema
de pontos foi variado para experimentação durante diversos treinamentos e o com
melhores resultados observados foi esse.
Após computada a pontuação de todos os trinta jogadores da geração, os quinze
melhores são selecionados para se reproduzirem e os quinze piores são descartados.
A pontuação obtida no campeonato de uma geração não é levada em conta no
campeonato das próximas gerações.
Terminado todos os passos anteriores, um novo campeonato é iniciado assim re-
petindo o ciclo com novos jogadores até que, após diversas gerações treinadas, será
obtido um sistema que jogue damas de forma inteligente.
Esse processo de seleção natural através de campeonatos pode ser observado na
Figura 3.7
20
Figura 3.7: Fluxuograma explicando um campeonato.
3.4 Mutação
Conforme mencionado na Seção anterior, a cada nova geração, os quinze melhores
jogadores se reproduzem dando prosseguimento a seleção natural. Tal reprodução
neste trabalho acontece apenas por meio de mutação sem nenhum tipo de recom-
binação. A recombinação não foi utilizado pois ela precisaria ser feita em pesos
e biases de uma rede neural, assunto no qual não existem referências e estudos
suficientes que possam embasar a proposta de um trabalho de conclusão de curso.
A mutação realizada altera aleatoriamente o valor dos pesos e biases de cada joga-
dor originando um novo jogador sem nenhuma garantia de que ele seja melhor que o
jogador de origem. Essa falta de garantia não é um problema, pois a própria seleção
natural estimula que apenas os melhores jogadores são selecionados para gerações
futuras. Portanto, se um jogador sofrer mutação não se sair bem no campeonato de
sua geração ele não será selecionado para gerações futuras.
�0i(i) = �i exp(⌧Ni(0, 1)), i = 1, ..., Nw (3.1)
21
w
0
i(i) = wi(i) + �
0
i(i)Ni(0, 1), i = 1, ..., Nw (3.2)
Baseado na teoria da Seção 2.2 e usando a mesma mutação de [4], cada jogador,
quando sofre mutação, altera seus pesos e biases de acordo com as fórmulas descritas
nas Equações (3.1) e (3.2), onde w
0
i é o novo peso ou bias, wi é o peso ou bias do
jogador original, �0i é o novo fator de mutação, �i é o fator de mutação do jogador
original, ⌧ = 1/
p
2
p
Nw, Nw é o número de pesos da rede neural, Ni(0, 1) é um
número aleatório cuja função densidade de probabilidade é uma gaussiana de média
zero e variância 1, já o parâmetro de mutação (�) foi iniciado em 0.001 como um
dos hiperparâmetros do treinamento.
K
0
i = max(min(Ki exp(1/
p
(2)Ni(0, 0.1)), 1), 3) (3.3)
Para aplicar mutação no valor das damas, foi utilizada a fórmula da equação (3.3),
onde K
0
i é o valor da dama após a mutação, Ki é o valor original do peso da Dama
e Ni(0, 0.1) é uma gaussiana de média 0 e variância 0.1. Conforme também descrito
nesta equação, o valor da dama foi limitado entre 1 e 3 assim como em [11].
3.5 Avaliação do Sistema durante o Treinamento
Para avaliar se o treinamento do sistema estava funcionando corretamente, foi
elaborado um sistema de testes em que os melhores jogadores da geração atual joga-
vam contra os melhores jogadores de gerações passadas. A partir do resultado dessa
competição era posśıvel avaliar se os novos jogadores selecionados eram melhores
que os jogadores mais antigos.
No ińıcio do treinamento, os quinze melhores jogadores da vigésima geração são
armazenados em memória para uso numa validação que verificará se o treinamento
está conseguindo treinar sistemas melhores com o avanço das gerações. Transcorri-
das 20 gerações depois da vigésima geração, ou seja, na quadragésima geração, os
jogadores anteriormente armazenados entram em um campeonato (Seção 3.3) contra
os quinze melhores jogadores da geração atual. A única diferença desse campeonato
22
Figura 3.8: Fluxuograma de validação do treinamento.
para o da Seção 3.3 é que este campeonato faz com que todos os jogadores da geração
atual joguem contra todos os jogadores armazenados ao invés de apenas realizar 5
rodadas onde as partidas são escolhidas de forma aleatória.
Terminado o campeonato, os resultados são exibidos em tela para avaliação e
gravados em um arquivo para análise futura. Em seguida os quinze jogadores que
tiveram a melhor pontuação no campeonato, sejam eles da geração atual ou da
geração passada, substituem os jogadores armazenados no presente momento para
a validação do treinamento e a seleção natural continua sem que essa validação a
afete de qualquer forma.
Tal fluxo descrito nesta Seção pode ser observado na Figura 3.8.
3.6 Testes no Site CodinGame
Outro meio de avaliar o andamento do treinamento foi o de verificar o ranking do
jogador com melhor pontuação no site CodinGame [12]. Esse teste também tinha
como fim verificar se o treinamento que estava funcionando da formacorreta, ou
23
seja, os sistemas selecionados estavam se tornando melhores jogadores ao longo das
gerações.
A cada vinte gerações o jogador melhor colocado no campeonato (Seção 3.7) da
geração atual era colocado para competir com os outros algoritmos do site Codin-
Game e seu ranking avaliado. Conforme descrito na Seção 4.1, os resultados obtidos
dessa forma podem ser considerados concretos para a avaliação da melhora do sis-
tema.
Visto que o ambiente disponibilizado pelo site CodinGame era diferente do de-
senvolvido no projeto, foi necessário criar um código de interface entre o sistema e o
site CodinGame. Esse código foi escrito no arquivo “codigoExemploCodingameJo-
gadasAFrenteMinMax.py”e ele foi desenvolvido com o intuito de contornar diversas
limitações determinadas pelo site.
A principal limitação do site era que o código do algoritmo submetido tinha que
ser escrito em um único arquivo e não poderia usar o TensorFlow [8], Keras [9]
e outras bibliotecas externas às distribúıdas diretamente com o Python. Então,
para que a classificação de um tabuleiro fosse realizada, foi necessário implementar
manualmente o algoritmo de classificação de uma rede neural e realizar a ativação
da tangente hiperbólica manualmente. Além disso, a classe “gerenciadorDeTabu-
leiro”(Seção 3.2) juntamente do algoritmo Minmax, teve que ser inclúıda nesse ar-
quivo para que o jogador pudesse ser simulado perfeitamente.
Sendo assim foi necessário desenvolver o código “createModelPrint.py”que trans-
formava um jogador salvo em um arquivo (Seção 3.2) em matrizes para inserção
no código “codigoExemploCodingameJogadasAFrenteMinMax.py”de forma que ele
poderia ser testado no site.
3.7 Meios de Teste Intermediários
Durante diversas etapas do desenvolvimento do projeto se fez necessário criar
diversos códigos auxiliares para que as etapas do desenvolvimento fossem testadas e
24
avaliadas de forma a garantir a qualidade do que foi desenvolvido. Dessa forma, foi
preciso validar todo o projeto discutido neste caṕıtulo, desde o ambiente de jogo de
damas até a mutação realizada num jogador.
Foram desenvolvidos três códigos para validar o ambiente de damas desenvol-
vido, sendo esses o “tester inversao de tabuleiro”, “tester movimento tabuleiro”e o
“tester calcula movimentos possiveis”.
O primeiro tem como finalidade testar a inversão de tabuleiro, visto que diversas
funcionalidades do ambiente desenvolvido, como a verificação de posśıveis jogadas
a partir de um tabuleiro, foram criados com sua utilidade focada na visão de um
dos jogadores. Para que essa funcionalidade fosse usada para o outro jogador era
necessário inverter o tabuleiro.
O segundo, a partir de um tabuleiro de entrada e um movimento de entrada,
realiza o movimento no tabuleiro e exibe seu resultado. Este código foi criado para
garantir que o ambiente não permitiria movimentos ilegais.
O terceiro visa verificar, a partir de um tabuleiro, quais as posśıveis jogadas para
o jogador que deve efetuar o movimento. Ele foi desenvolvido com o intuito de
verificar se o código que descobre as posśıveis jogadas e o que impede movimentos
ilegais estavam funcionando corretamente.
Depois disso, para avaliar as funcionalidades de um jogador, foram desenvolvi-
dos sete códigos diferentes: (i) “tester seleciona melhor jogada”; (ii) “tester selecio-
na melhor jogada jogador existente”; (iii) “tester valor predict jogador”; (iv) “tes-
ter - reproducao”; (v) “tester partidas com filho”; (vi) “tester partida jogadores se-
lecionados”; (vii) “tester partida”. Os códigos (i), (ii) e (iii) tinham o intuito de
verificar qual a melhor jogada selecionada por um jogador espećıfico num dado ta-
buleiro. Já os códigos (iv) e (v) tinham como finalidade verificar a mutação de um
jogador. Por fim, os códigos (vi) e (vii) foram desenvolvidos para permitir a rea-
lização de partidas entre dois jogadores treinados e entre um jogador treinado e um
jogador humano respectivamente.
25
Por último, foram feitos códigos de teste que validavam todo o processo de seleção
natural do projeto. Dentre estes códigos, um verificava se a pontuação recebida por
um jogador estava sendo corretamente atribúıda e outro realizava um campeonato
entre diversos jogadores.
26
Caṕıtulo 4
Resultados
Para avaliar os resultados do sistema proposto, o método que melhor se adequou
foi o de colocá-lo para jogar e avaliar se o sistema venceu ou perdeu na partida além
de seu desempenho na mesma. Em casos de vitória fica claro seu desempenho, mas
uma derrota ou empate, por mais que sejam ruins, ainda podem demonstrar alguma
inteligência por parte do sistema, visto que a partida pode ter sido disputada.
O sistema foi submetido a partidas em três situações diferentes para que sua
performance pudesse ser avaliada. Dentre elas, temos o uso do site CodinGame,
uma competição com um aplicativo de damas de Android e realização de partidas
contra seres humanos.
O site CodinGame é uma plataforma online que se dispõe a ser um ambiente no
qual programadores melhoram suas habilidades com desafios. Dentre os desafios
propostos pelo site, está permitir que programadores desenvolvam um algoritmo
que jogue damas e que esse algoritmo participe de uma competição com outros
algoritmos desenvolvidos por outros usuários do site e obtenha um ranking referente
a seu desempenho. Esse método de avaliação foi escolhido por sua objetividade visto
que o ranking obtido nessa competição é sempre dado a partir de um mesmo critério
de avaliação e também graças à facilidade de se comparar dois sistemas treinados
durante o desenvolvimento do projeto conforme é melhor explicado na Seção 4.1.
Nos jogos contra um aplicativo de damas o sistema foi posto para jogar contra um
aplicativo de damas em diversas dificuldades. Esse meio de avaliação foi escolhido
27
também devido à sua objetividade, visto que vitórias contra um aplicativo em certa
dificuldade demonstram a habilidade do sistema. Além disso, esse meio de avaliação
foi escolhido para que fosse comprovado um uso comercial para o projeto realizado,
sendo esse a criação de um aplicativo de damas próprio, seja ele de computador,
Android ou iOS.
As partidas contra humanos foram realizadas contra pessoas de diferentes ńıveis
com o intuito de avaliar o desempenho do sistema em relação a adversários humanos.
Uma segunda razão foi para avaliar se o sistema jogava de forma parecida a um ser
humano ou de forma diferente.
Outro método utilizado para avaliar o sistema foi iniciar uma partida contra o
mesmo com o objetivo de avaliar suas decisões. Ele foi colocado em uma situação
em que uma peça sua poderia ser capturada de forma que ele posteriormente ficaria
em desvantagem na partida caso sua jogada resposta não defendesse essa peça.
Além disso, outro tipo de resultado importante analisado são os de situações
encontradas durante o treinamento, como: (i) o que aconteceu com a variedade
genética dos sistemas criados durante as gerações; (ii) os jogadores foram melho-
rando cada vez menos durante as gerações até que pararam de melhorar. Estas
análises servem de aprendizado para trabalhos futuros no mesmo tema.
O comportamento dos sistemas ao longo das gerações explica como as redes neurais
treinadas através de mutação explicadas na Seção 3.4 se comportaram durante esse
treinamento. Essa análise é vital para que seja posśıvel otimizar o treinamento num
trabalho futuro além de demonstrar problemas que devem ser evitados ou reduzidos
em trabalhos futuros.
Já o comportamento da seleção natural durante as gerações treinadas visa olhar
mais de perto como os indiv́ıduos eram selecionados durante as gerações e como a
genealogia dos indiv́ıduos selecionados progredia ao longo das gerações. Assim como
a análise do comportamento dos indiv́ıduos, a análiseda seleção natural otimizaria
o treinamento em trabalhos futuros.
28
4.1 CodinGame
Conforme descrito na Seção anterior, um primeiro jeito de avaliar o sistema de
forma objetiva foi submetê-lo a diversos jogos contra outros sistemas em uma com-
petição em que todos os sistemas obtêm um ranking.
No site CodinGame [12] é posśıvel implementar um sistema numa linguagem de
escolha do desenvolvedor e, a partir do tabuleiro do estado atual do jogo, o sistema
deve lançar como output a jogada que será realizada por ele. Assim, dois sistemas
diferentes podem ser submetidos pelo site a partidas.
Sempre que um novo sistema é submetido, o site automaticamente realiza diversas
partidas começando com os piores jogadores e vai, conforme o sistema submetido
ganha partidas, lançando partidas contra jogadores melhor classificados aos poucos
até que o sistema começa a empatar e perder partidas. Nesse momento o site
começa a submeter esse sistema a partidas contra os jogadores nessa mesma faixa de
classificação de forma a identificar em que posição exata do ranking ele se encontra.
Como o meio de chegar ao ranking é o mesmo e os jogadores no site mudam
pouco ao longo de poucas horas, se dois sistemas forem submetidos a essa avaliação
do site em momentos próximos, é posśıvel, de forma objetiva, determinar qual dos
dois sistemas é melhor através de seu ranking.
Esse meio de análise foi o principal usado durante o treinamento para visualizar
se os novos sistemas criados haviam melhorado em relação aos sistemas de gerações
anteriores. A cada 20 gerações, o sistema melhor classificado no campeonato (Seção
3.3) era introduzido nessa competição contra outros sistemas e seu ranking era ava-
liado em relação ao ranking do sistema avaliado 20 gerações atrás.
Nas primeiras gerações era posśıvel observar uma melhora significativa entre os
sistemas ao longo das gerações. Essa melhora era observável através do ranking dos
sistemas no site. Sistemas iniciados aleatoriamente ficavam em um ranking próximo
dos últimos colocados, jogadores das primeiras gerações obtinham rankings melhores
e esse ranking ia melhorando significativamente a cada geração passada. Contudo,
29
Figura 4.1: Ranking do sistema ao longo das gerações.
depois de algumas gerações, o ranking dos jogadores passava a não melhorar mais e
ficava oscilando entre dez posições do ranking. Tal comportamento é demonstrado
na Figura 4.1.
Após várias gerações e treinamentos diferentes, a melhor classificação obtida pelo
sistema desenvolvido neste trabalho foi o ranking 74 de 210 competidores, o que
demonstra que ele está entre os 36% melhores sistemas do site. É posśıvel observar
isso na Figura 4.2 vendo o ranking do usuário “noc1243”conforme [16].
Vale enfatizar que o site CodinGame impõe uma limitação de 100 ms por jogada
para cada sistema. Essa limitação fez com que o sistema desenvolvido neste projeto
fosse limitado no número de jogadas a frente a serem analisadas. Nas partidas do
CodinGame o sistema olhava apenas 3 ou menos jogadas à frente, dependendo da
quantidade posśıvel de jogadas que o estado do tabuleiro analisado proporciona.
Quando existem muitas possibilidades de jogada se torna inviável analisar todas as
jogadas posśıveis olhando 3 jogadas a frente nos 100 ms que o site limita, portanto
o sistema se restringe a analisar o máximo posśıvel dentro desse tempo e depois
analisa outras possibilidades sem olhar jogadas à frente.
30
Figura 4.2: Colocação no site Codingame.
A partir dos resultados obtidos, foi posśıvel chegar à conclusão de que o sistema
desenvolvido no trabalho obteve um desempenho melhor do que a média no site.
Além disso, a partir da comparação de sistemas diferentes treinados durante o de-
senvolvimento do projeto foi posśıvel observar com clareza a melhora do sistema
entre as primeiras gerações e as últimas gerações treinadas. Contudo, tais dados
apenas demonstram o desempenho do sistema em relação a outros algoritmos de-
senvolvidos sem fins comerciais, portanto se fez necessário avaliar o sistema das
outras formas enumeradas no ińıcio deste Caṕıtulo.
4.2 Aplicativo de Damas
O segundo meio utilizado para avaliar o desempenho do sistema desenvolvido foi
submetê-lo a partidas contra um aplicativo comercial dispońıvel para Android de
damas chamado Checkers pelo desenvolvedor Cromulent Door. Resultados bons
nessa avaliação demonstrariam que o sistema desenvolvido poderia ser usado de
forma comercial em um aplicativo de damas próprio por exemplo.
Nestes testes uma pessoa serviu de interface entre o aplicativo e o sistema de-
senvolvido. A jogada do aplicativo era inserida para o sistema no computador e
a jogada do sistema era inserida para o aplicativo no celular de forma que os dois
31
tiveram uma partida completa. Em todas as 3 partidas o aplicativo de Android
começou e o sistema fez a segunda jogada.
Para avaliar o sistema, ele foi submetido a jogos contra as dificuldades easy, me-
dium e hard do aplicativo de damas supracitado de forma a saber em qual ńıvel de
jogador o sistema treinado se encontra.
Na partida contra o modo easy da Seção A.2 podemos assistir a reprodução da
partida do sistema, de vermelho, contra o aplicativo de damas em azul no modo easy.
Ao assistir a partida é percept́ıvel que o sistema consegue ganhar do aplicativo de
damas com certa facilidade, visto a vantagem numérica de peças capturadas desde
o ińıcio do jogo.
Na segunda partida da Seção A.2, partida contra aplicativo ńıvel medium, pode-
mos ver a partida do sistema, de vermelho, contra o aplicativo de damas em azul
no modo medium. Acompanhando a partida é posśıvel ver que o sistema consegue
ganhar do aplicativo de damas numa partida disputada pois ambos os jogadores
ficam em pé de igualdade até o final do jogo, quando o sistema consegue vencer
finalmente.
Como última partida temos o sistema, de vermelho, jogando com o aplicativo, de
azul, no modo hard conforme o terceiro v́ıdeo da Seção A.2, partida contra aplicativo
ńıvel hard. Assistida a partida dá para notar que o sistema perde para o aplicativo
com certa facilidade, visto o jeito com que o aplicativo conseguiu obter vantagem
numérica de peças capturadas desde o ińıcio do jogo.
Dados os resultados das 3 partidas acima analisadas é posśıvel concluir que o
sistema performa a ńıvel um pouco acima do medium do aplicativo comercial.
Dito isso, o sistema foi avaliado apenas contra um aplicativo comercial, fazendo
com que os resultados citados sejam restritos a apenas esse aplicativo. Sendo as-
sim, para que um resultado mais conclusivo seja alcançado, seria necessário em um
momento futuro que o sistema fosse avaliado em jogos contra outros aplicativos
comerciais de damas.
32
4.3 Partidas contra Humanos
A terceira maneira para avaliar o sistema foi colocá-lo para jogar contra 3 joga-
dores humanos diferentes que serão denominados, para facilidade de entendimento,
como jogador A, jogador B e o último jogador foi Vińıcius Damir. O jogador
A foi selecionado por ser um jogador inexperiente em damas, enquanto o jogador
B possúıa algum conhecimento no jogo. Já Vińıcius Damir já foi o vice-campeão
mundial de damas, sendo assim um especialista no jogo.
Na partida do jogador A na Seção A.1, observamos a partida entre o jogador
A, de vermelho contra o sistema, de azul. Conforme é posśıvel observar o sistema
ganhou do jogador A e, se notarmos a diferença de peças durante a partida, também
é posśıvel notar certa facilidade do sistema em obter a vitória.
Na partida do jogador B na Seção A.1 observamos a partida entre o jogador
B, de vermelho, contra o sistema, de azul. Nota-se que a partida termina em
empate entre o jogadores após 100 movimentos conforme determinado na Seção
3.2. É posśıvel notar que o jogador B conseguiu obter vantagem numérica sobreo sistema, mas não conseguiu finalizar o jogo antes que o número limite de jogadas
foi observado.
Na partida de Vińıcius Damir da Seção A.1 temos uma partida contra o ex-vice-
campeão mundial, Vińıcius Damir, contra o sistema. Nela podemos observar que
o vice-campeão derrota o sistema sem muita dificuldade. Terminada a partida, foi
perguntado ao damista se ele considerava que o sistema fazia jogadas pensadas ou
aleatórias e se ele jogava como um ser humano ou de forma diferente. O vice-
campeão respondeu dizendo que o sistema jogava de forma aleatória igual a um
jogador iniciante no esporte, ou seja, como uma pessoa introduzida ao esporte de
damas.
Ao analisar as três partidas é posśıvel concluir que o sistema consegue jogar melhor
do que jogadores inexperientes de damas e em pé de igualdade com jogadores de
habilidade mediana, mas é derrotado por especialistas no jogo.
33
Após realizadas as partidas o jogador A e Vińıcius Damir foram entrevistados
de forma sucinta sobre o sistema desenvolvido no projeto. Tal entrevista pode ser
encontrada nas Seções B.1 e B.2
4.4 Avaliando Inteligência do Sistema
Conforme citado no ińıcio desse caṕıtulo, um jogador, chamado jogador C para
facilitar o entendimento, iniciou um jogo contra o sistema com o intuito único de
colocar o sistema em situações em que existiria uma jogada boa e jogadas ruins de
forma fácil de se observar. Na figura 4.3 é posśıvel observar a reprodução de tal
jogo.
Antes de começar a analisar essa sequência de jogadas, é importante notar que a
intenção do jogador C foi de que o tabuleiro chegasse no estado do 5 movimento
representado na Figura 4.3e. Esse cenário foi escolhido para ser avaliado pois o
sistema tinha uma peça ameaçada de captura em G5 pela peça do jogador C em
F4. Caso o sistema não jogasse a peça de G7 para H6, o jogador C capturaria
a peça de G5 colocando sua peça em H6, obtendo assim uma vantagem numérica
sobre o sistema e ainda uma vantagem estratégica, pois o sistema teria várias peças
com movimentos limitados.
Agora, analisando todos os movimentos, primeiramente na Figura 4.3a observamos
o primeiro movimento do jogador C de G3 para H4. Este movimento tinha como
objetivo trazer à tona uma situação similar à do 5 movimento já citado.
Em seguida o sistema jogou sua peça de H6 para G5 conforme a Figura 4.3b.
Nota-se que essa situação não coloca o sistema em desvantagem, visto que a captura
dessa peça é imposśıvel. Esse movimento também pode ser considerado bom no
sentido de que ele prende a peça de H4 do jogador C.
No terceiro movimento da Figura 4.3c, o jogador C jogou de F2 para G3 se
preparado para jogar de G3 para F4 no seu quinto movimento. Essa jogada teve
apenas o intuito de atingir o estado de tabuleiro desejado para analisar o sistema.
34
No quarto movimento, observa-se que o sistema joga de B6 para A5 na Figura
4.3d. É posśıvel notar que o sistema não tomou nenhuma ação para evitar o estado
de tabuleiro que o jogador C deseja nesse momento, mas é posśıvel que isso tenha
acontecido porque ele tinha uma resposta pronta para essa situação e que não traria
nenhuma desvantagem para ele, conforme observaremos na 6 jogada futuramente.
No quinto movimento da Figura 4.3e observamos que o jogador C finalmente
atingiu seu estado de tabuleiro desejado ao movimentar sua peça de G3 para F4.
Nesse momento ele entrou em uma situação em que, se o sistema não reagisse com
o movimento de G7 para H6, o jogador C obteria grande vantagem.
No sexto movimento da Figura 4.3f observamos que o sistema fez a única jogada
posśıvel para que ele não tivesse desvantagem: jogou de G7 para H6, conforme
esperado. Vale notar que qualquer outra jogada feita pelo sistema não permitiria que
o mesmo compensasse a peça que seria perdida. Todas as outras jogadas posśıveis
colocariam o sistema em desvantagem em relação a seu oponente.
Dessa forma, a partir da sequência de jogadas analisadas nessa Seção, podemos
ver que o sistema demonstra inteligência em suas jogadas e não as faz de forma
aleatória.
35
(a) Primeiro movimento. (b) Segundo movimento.
(c) Terceiro movimento. (d) Quarto movimento.
(e) Quinto movimento. (f) Sexto movimento.
Figura 4.3: Jogo realizado para testar a inteligência do sistema.
36
4.5 Diminuição da Melhora do Sistema ao longo
das Gerações
Conforme explicado na Seção 3.3, a cada 20 gerações os sistemas da geração atual
eram submetidos a uma competição com os melhores jogadores de 20 gerações atrás.
Essa análise foi feita com a inteção de avaliar se os novos jogadores selecionados
apresentavam melhor desempenho que os jogadores anteriores vencendo dos mesmos.
Ao observar o comportamento dessas competições entre jogadores de gerações mais
atuais com os jogadores de gerações passadas, inicialmente foi posśıvel obseravar que
os jogadores mais atuais ganhavam dos antigos e apresentavam melhor desempenho.
Depois de diversas gerações, começou a ser posśıvel observar que os jogadores novos
empatavam e até mesmo perdiam para os jogadores mais antigos.
A interpretração mais provável para tal comportamento é que a rede neural usada
para avaliar o tabuleiro atingiu um mı́nimo local e as mutações causadas nessa rede
na fase de criação de novos jogadores não conseguiam levar o sistema para fora desse
mı́nimo, fazendo com que, assim, os jogadores ficassem sempre nas redondezas dele.
4.6 Variedade Genética dos Jogadores durante o
Treinamento
Outro comportamento observado durante a seleção natural usada no treinamento
do sistema foi o fato de que, após as primeiras gerações de treinamento, era viśıvel
que todos os jogadores selecionados originavam-se de uma ou duas genealogias ape-
nas.
Sistemas são considerados de uma mesma genealogia se o sistema que originou
ambos os jogadores for o mesmo, e.g.: o jogador b e c foram criados a partir de
uma mutação do jogador a, portanto ambos são da mesma genealogia do jogador
a; o jogador e foi criado a partir de mutações do jogador d e o jogador b foi criado
a partir de mutações do jogador a, portanto o jogador d e o jogador b não são da
mesma genealogia.
37
Tal comportamento é posśıvel porque todo sistema que tinha um alto desempenho
durante uma geração sofria mutação, gerando um novo sistema em sua genealogia.
Dessa forma, numa primeira geração existiria apenas um sistema de uma genealogia,
mas na segunda geração existiriam dois jogadores dessa genealogia e, caso ambos
tivessem bom desempenho, na terceira geração existiriam 4 jogadores dessa mesma
genealogia, seguindo a lógica de uma progressão geométrica.
A justificativa para esse comportamento acontecer no treinamento de sistemas se
dá pelo fato de que a rede neural inicial de todos os sistemas era iniciada aleato-
riamente conforme indicado na Seção 3.2. Alguns desses sistemas eram iniciados
com melhor aptidão para jogar damas que outros, portanto os sistemas mais aptos
foram mantidos, criando uma genealogia mais longa, enquanto os menos aptos não
tiveram muitas chances de sofrerem mutação para melhorar sua performance.
38
Caṕıtulo 5
Conclusões
A partir dos resultados obtidos no Caṕıtulo 4, foi posśıvel chegar em diversas
conclusões diferentes sobre o projeto. Dentre elas a capacidade de jogar damas do
sistema desenvolvido, um posśıvel potencial comercial sobre o mesmo, seu ńıvel de
habilidade em um jogo de damas e se o sistema desenvolvido joga igual um ser
humano ou não.
Conforme analisado em 4.1 foi posśıvel observar que o sistema desenvolvido obteve
resultados bons o suficiente para que seja conclúıdo que o mesmo sabe jogar damas
até certo ńıvel de habilidade.
Já na Seção 4.3, foi posśıvel observar que, embora o sistema não seja um jogador
especialista em damas ele se sai melhor que um ser humano inexperiente e que, de
acordo com as palavras deVińıcius Damir, ex-vice-campeão mundial de damas, ele
joga da mesma forma que um jogador inexperiente que é iniciante no esporte, o que
quer dizer que o sistema fazia jogadas que simulavam uma pessoa que iniciou no
esporte, ou seja, não fazia jogadas que claramente davam vantagem ao adversário,
assim como qualquer humano jogando.
Na Seção 4.2 notamos, mesmo que de forma parcial, que o jogador desenvolvido
conseguia jogar damas um pouco melhor do que o aplicativo de damas utilizado. Este
resultado demonstra que o sistema desenvolvido tem potencial para ser utilizado um
dia em um aplicativo de damas comercial.
39
Conforme dito nas entrevistas dos jogadores da Seção 4.3, foi posśıvel observar
que o sistema criado jogava de forma similar a um humano.
5.1 Trabalhos Futuros
Devido às restrições do projeto, alguns tópicos careceram de melhor análise e
maior desenvolvimento durante o mesmo. Tais tópicos deverão ser melhor tratados
em trabalhos futuros para que possam ser esclarecidos.
O primeiro tópico que careceu de análise foi a variação do número de jogadas
à frente que o sistema deveria analisar durante o treinamento. Tal tópico não foi
muito avaliado devido ao longo tempo para que cada treinamento fosse realizado e
os resultados do mesmo fossem avaliados.
Em seguida, se faz necessário analisar outros algoritmos para análise de jogadas
à frente no lugar do Minmax (Seção 2.5). Outro algoritmo sendo utilizado pode ter
algum efeito no treinamento, seja ele positivo ou negativo. Ele também pode mudar
o jeito com que os jogadores selecionados jogam.
Como última proposta de trabalho futuro, está a ideia de tentar reproduzir o
projeto atual em um problema de maior grau de complexidade. Tal complexidade
pode ser atingida com outros jogos, como Xadrez, onde existe uma quantidade muito
maior de jogadas a ser analisada, ou jogos como Poker, onde a competição deverá
incluir blefes além de analisar a melhor jogada posśıvel.
40
Referências Bibliográficas
[1] SAMUEL, A. L., “Some Studies in Machine Learning Using the Game of Chec-
kers”, IBM Journal of Research and Development, v. 3, n. 3, pp. 210–229, 1959.
[2] SCHAEFFER, J., CULBERSON, J., TRELOAR, N., et al., “A world champi-
onship caliber checkers program”, Artificial Intelligence, v. 53, n. 2, pp. 273–
289, 1992.
[3] DARWIN, C., On the Origin of Species by Means of Natural Selection. London,
Murray, 1859. or the Preservation of Favored Races in the Struggle for Life.
[4] EIBEN, A. E., SMITH, J. E., Introduction to Evolutionary Computing. 2 ed.
Springer Publishing Company, Incorporated, 2015.
[5] GARDNER, M., DORLING, S., “Artificial neural networks (the multilayer
perceptron)—A review of applications in the atmospheric sciences”, Atmosphe-
ric Environment, v. 32, n. 14-15, pp. 2627–2636, 1998.
[6] KAINDL, H., “Tree Searching Algorithms”. In: Marsland, T. A., Schae↵er, J.
(eds.), Computers, Chess, and Cognition, pp. 133–158, New York, NY, 1990.
[7] ROSSUM, G. V., Python tutorial, Report CS-R9526, Centrum voor Wiskunde
en Informatica (CWI), Amsterdam, May 1995.
[8] ABADI, M., AGARWAL, A., BARHAM, P., et al., “TensorFlow: Large-Scale
Machine Learning on Heterogeneous Systems”, 2015, Software available from
tensorflow.org.
[9] CHOLLET, F., OTHERS, “Keras”, https://keras.io, 2015.
[10] EIBEN, A. E., SMITH, J. E., Introduction to Evolutionary Computing, chapter
Coevolutionary Systems, Academic Press, pp. 223–229, 2015.
41
[11] CHELLAPILA, K., FOGEL, D. B., “Evolving an Expert Checkers Playing Pro-
gram Without Using Human Expertise”, IEEE TRANSACTIONS ON EVO-
LUTIONARY COMPUTATION, v. 5, pp. 422–428, 2001.
[12] DESMOULINS, F. D., ANTONIAZZI, N., BARRAL, A., “Site CodinGame
About Us”, https://www.codingame.com/about/team, Jun. 2021, (Acesso em
26 Junho 2021).
[13] COLEMAN, J., “How to Play Checkers”, https://www.wikihow.com/Play-
Checkers, Jun. 2021, (Acesso em 26 Junho 2021).
[14] NOLETO, C., “POO: tudo sobre Programação Orientada a Objetos!”,
https://blog.betrybe.com/tecnologia/poo-programacao-orientada-a-objetos/,
Aug. 2020, (Acesso em 06 Julho 2021).
[15] HARRIS, C. R., MILLMAN, K. J., WALT, S. J. V. D., et al., “Array program-
ming with NumPy”, Nature, v. 585, n. 7825, pp. 357–362, Sep. 2020.
[16] DESMOULINS, F., ANTONIAZZI, N., BARRAL, A., “Site Codin-
Game Leaderboard”, https://www.codingame.com/multiplayer/bot-
programming/checkers/leaderboard, Jun. 2021, (Acesso em 26 Junho
2021).
[17] GATES, L. B., GENTRY, D., SEVILLA, D., et al., “Math is Fun About Us”,
https://www.mathsisfun.com/aboutmathsisfun.html, Jun. 2021, (Acesso em 30
Junho 2021).
[18] BUDDYBOARDGAMES, “Welcome to BuddyBoardGames”,
https://buddyboardgames.com/, Jun. 2021, (Acesso em 30 Junho 2021).
42
Apêndice A
Partidas Realizadas
A.1 Partidas contra humanos
Partida contra jogador A: https://youtu.be/NIB_IewlCYc
Partida contra jogador B: https://youtu.be/veQZRzRGvZE
Partica contra Vińıcius Damir: https://youtu.be/OC24vGwJpQQ
A.2 Partidas contra aplicativos
Partida contra aplicativo Checkers desenvolvido por Cromulent Door no ńıvel
easy: https://youtu.be/tR1gwYrYMvE
Partida contra aplicativo Checkers desenvolvido por Cromulent Door no ńıvel
medium: https://youtu.be/o9CbKAiL2XM
Partida contra aplicativo Checkers desenvolvido por Cromulent Door no ńıvel
hard: https://youtu.be/4BbNAA_imt4
A.3 Fontes
Todas as partidas exceto a de Vińıcius Damir foram realizados em [17]
Partida de Vińıcius Damir realizada em [18]
43
Apêndice B
Entrevistas
B.1 Entrevista com Jogador A
Pergunta: A inteligência sabia jogar damas até certo ponto, ou você tinha a
percepção de que eram jogadas aleatórias?
Resposta: Pra mim parecia que ela tinha uma estratégia de jogo sim. Por não ter
experiência no jogo, eu tentei jogadas muito simples e até aleatorias e a inteligência
soube aproveitar isso.
Pergunta: A inteligência artificial jogava de forma similar a uma pessoa ou de
forma muito diferente?
Resposta: Sim, me lembrava um humano de certa forma.
B.2 Entrevista com Vińıcius Damir
Pergunta: A inteligência sabia jogar damas até certo ponto, ou você tinha a
percepção de que eram jogadas aleatórias?
Resposta: No meu ver ela (Inteligência artificial) apenas jogou sabendo as regras,
os lances foram bem aleatórios e fracos. Em relação ao ńıvel se compararmos com
dos seres humanos, ela teria um ńıvel iniciante, igual ao de quem está iniciando no
esporte.
44
Apêndice C
Código Fonte
Link código fonte do projeto: https://github.com/noc1243/TCC_Checkers
45