UNIVERSIDADE TÉCNICA DE LISBOA
INSTITUTO SUPERIOR TÉCNICO
Abalearn:
Uma abordagem Sensı́vel ao Risco para a
Aprendizagem Automática do Abalone
Pedro Filipe Pereira Campos
(Licenciado)
Dissertação para a obtenção do grau de Mestre
em
Engenharia Informática e de Computadores
Orientador: Doutor Thibault Nicolas Langlois
Júri:
Presidente:
Doutor Arlindo Manuel Limede de Oliveira
Vogais:
Doutor João Pedro Neto
Doutor Fernando Henrique Corte Real Mira da Silva
Doutor Thibault Nicolas Langlois
Tı́tulo: Abalearn: Uma abordagem Sensı́vel ao Risco para a Aprendizagem Automática
do Abalone
Nome: Pedro Filipe Pereira Campos
Curso de Mestrado em: Engenharia Informática e de Computadores
Orientador: Professor Doutor Thibault Nicolas Langlois
Co-orientador: Professor Doutor Fernando Corte Real Mira da Silva
Provas concluı́das em:
Resumo
O paradigma da Aprendizagem por Reforço tem sido de grande interesse na área da Aprendizagem
Automática, por não ser necessário um “professor” inteligente para o fornecimento de exemplos
de treino, tornando-o particularmente adequado a domı́nios complexos onde a obtenção desses
exemplos seja difı́cil ou até impossı́vel.
Esta dissertação apresenta o Abalearn: um programa que se treina a si próprio e que aprende a jogar
Abalone, sendo capaz de alcançar automaticamente um nı́vel intermédio de jogo sem recorrer a
exemplos de treino rotulados, procuras profundas ou exposição a jogadores competentes.
A nossa abordagem é baseada num algoritmo de Aprendizagem por Reforço que é orientado ao
risco, uma vez que jogadores defensivos no Abalone tendem a nunca terminar o jogo. Mostramos
que é essa sensibilidade ao risco que permite um auto-treino bem sucedido. Também propomos
um conjunto de atributos relevantes para a aquisição automática de estratégias e mostramos que
esses atributos aumentam o desempenho do programa.
Avaliamos a nossa abordagem usando um jogador heurı́stico fixo como medida principal de desempenho, mas também fazendo jogar os nossos agentes contra jogadores experientes humanos e
contra programas existentes de alto desempenho.
Palavras-Chave: Aprendizagem Automática, Aprendizagem por Reforço, Redes Neuronais, Sensibilidade ao Risco, Aproximação de Funções, Auto-Treino.
i
ii
Title: Abalearn: A Risk-Sensitive Approach to Self-Play Learning in Abalone
Abstract
The Reinforcement Learning paradigm has had great interest in the field of Machine Learning,
since it does not require an intelligent “teacher” for supplying training examples, which makes it
particularly suitable to complex domains where training examples are hard to obtain.
This thesis presents Abalearn, a self-teaching Abalone program capable of automatically reaching
an intermediate level of play without needing expert-labeled training examples, deep searches or
exposure to competent play.
Our approach is based on a Reinforcement Learning algorithm that is risk-seeking, since defensive
players in Abalone tend to never end a game. We show that it is the risk-sensitivity that allows a
successful self-play training. We also propose a set of features that seem relevant for achieving a
good level of play.
We evaluate our approach using a fixed heuristic opponent as a benchmark, pitting our agents
against human players online and comparing samples of our agents at different times of training.
Keywords: Machine Learning, Reinforcement Learning, Neural Networks, Function Approximation, Risk-Sensitivity, Self-Training.
iii
iv
Agradecimentos
Esta dissertação traduz a minha reflexão inquieta sobre o que mais me seduziu neste longo
percurso.
Por isso não posso deixar de agradecer ao meu Orientador Cientı́fico, Professor Thibault
Langlois, pela liberdade de investigação que sempre me proporcionou, sem prejuı́zo do
rigor que sempre presidiu às nossas reuniões semanais. Idêntico agradecimento ao Professor Fernando Corte Real, que gentilmente acedeu ser Co-orientador desta dissertação.
Agradeço aos avaliadores anónimos da European Conference on Machine Learning 2003,
as crı́ticas pertinentes e as sugestões extremamente interessantes.
Aos investigadores Jordan Pollack, Peter Dayan e Susan Epstein, pela disponibilidade
que sempre me dispensaram sobre pormenores importantes dos seus trabalhos. A todos
os jogadores de Abalone que desafiaram o Abalearn nas suas inúmeras versões e que
teceram comentários muito úteis sobre estratégias de jogo.
Um agradecimento muito especial àqueles que mais de perto sempre me acompanharam
nesta “cidade que nunca dorme”: o meu irmão Mig, o causı́dico, pela persistência com
que sempre me confrontou a mim e ao Abalearn, e a minha irmã Ana, a prestimosa garante
das refeições de Domingo.
À Sónia, cujo rodopiante colorido enfeitou os meus dias. Loving is waiting.
Finalmente, agradeço às pessoas que mais me ajudaram neste percurso: os meus pais, que
estiveram sempre comigo. Agradecer-vos é pouco.
v
vi
Conteúdo
1
Introdução
1.1 O Legado de A. Samuel . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Estrutura do Documento e Contribuições . . . . . . . . . . . . . . . . . .
2
Abalone
2.1 Regras do Jogo . . . . . . . . . . . . . .
2.1.1 Movimentos das Peças . . . . . .
2.1.2 Empurrando as peças adversárias
2.1.3 “Bola Fora” e Fim do Jogo . . . .
2.1.4 Notação dos Movimentos . . . .
2.1.5 Estratégia e Problemas . . . . . .
2.2 Versões Existentes do Jogo . . . . . . . .
3
4
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Estado da Arte
3.1 Introdução . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2 Aprendizagem por Reforço . . . . . . . . . . . . . . . . . .
3.3 Diferença Temporal . . . . . . . . . . . . . . . . . . . . . .
3.3.1 A Receita do Sucesso . . . . . . . . . . . . . . . . .
3.3.2 A experiência de Pollack e Blair revisitada . . . . .
3.3.3 Análise dos resultados . . . . . . . . . . . . . . . .
3.3.4 Poderá o sucesso ser repetido? . . . . . . . . . . . .
3.4 Complexidade dos Jogos . . . . . . . . . . . . . . . . . . .
3.5 Representações de Estado . . . . . . . . . . . . . . . . . . .
3.5.1 Explorando caracterı́sticas espaciais e temporais . .
3.5.2 Representando relações entre as peças . . . . . . . .
3.6 Processos de Treino Utilizados . . . . . . . . . . . . . . . .
3.6.1 Ajustando automaticamente os parâmetros do treino
3.6.2 Combinando a Aprendizagem com Procura Minimax
3.7 Funções de Avaliação Lineares vs. Não-Lineares . . . . . .
3.8 Chips desafiando Campeões . . . . . . . . . . . . . . . . .
Aprendizagem por Reforço
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
1
2
3
.
.
.
.
.
.
.
5
5
5
8
8
8
10
10
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
13
13
15
16
17
18
20
22
23
25
25
26
27
29
31
32
33
35
vii
4.1
4.2
4.3
4.4
4.5
Modelo Conceptual . . . . . . . . . . .
Exemplos e Aplicações . . . . . . . . .
Conceitos Básicos . . . . . . . . . . . .
Ilustração dos Algoritmos . . . . . . . .
4.4.1 Programação Dinâmica . . . . .
4.4.2 Q-Learning . . . . . . . . . . .
4.4.3 Sarsa . . . . . . . . . . . . . .
4.4.4 TD(λ) . . . . . . . . . . . . . .
A Escolha das Acções . . . . . . . . . .
4.5.1 O Problema do N-Armed Bandit
4.5.2 Métodos Acção-Valor . . . . .
4.5.3 Descrição da experiência . . . .
4.5.4 Resultados . . . . . . . . . . .
4.5.5 Conclusões . . . . . . . . . . .
4.5.6 Exploração Dirigida . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
5 Treino por TD(λ) Clássico
5.1 Modelo Experimental . . . . . . . . . . . . . . . . . . . . .
5.1.1 Os Agentes . . . . . . . . . . . . . . . . . . . . . .
5.1.2 O Ambiente . . . . . . . . . . . . . . . . . . . . . .
5.1.3 A Simulação . . . . . . . . . . . . . . . . . . . . .
5.2 TD(λ) Clássico . . . . . . . . . . . . . . . . . . . . . . . .
5.2.1 O Problema da Generalização . . . . . . . . . . . .
5.2.2 O Processo de Treino . . . . . . . . . . . . . . . . .
5.3 Representação do Estado . . . . . . . . . . . . . . . . . . .
5.3.1 Abalearn 1: Representação Directa . . . . . . . . .
5.3.2 Abalearn 2: Representação Espacial . . . . . . . . .
5.3.3 Abalearn 3: Representação com Atributos Relevantes
5.4 Resultados Experimentais - Método I . . . . . . . . . . . . .
5.4.1 Análise dos Resultados . . . . . . . . . . . . . . . .
5.5 O valor dos Atributos . . . . . . . . . . . . . . . . . . . . .
5.6 Treino por um oponente Perito . . . . . . . . . . . . . . . .
6 Treino por TD(λ) Sensı́vel ao Risco
6.1 Introdução . . . . . . . . . . . . . . . . . . .
6.2 Fundamento Teórico . . . . . . . . . . . . .
6.3 Resultados Experimentais . . . . . . . . . . .
6.3.1 Desempenho face a outros Programas
6.3.2 Desempenho contra Humanos Peritos
6.4 Comparação entre os Métodos . . . . . . . .
6.5 Uma Abordagem Alternativa . . . . . . . . .
viii
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
36
37
39
39
40
41
43
44
44
45
46
46
48
49
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
53
53
54
54
55
55
56
57
59
61
61
62
64
65
71
71
.
.
.
.
.
.
.
73
73
74
77
82
84
85
86
7
Conclusões
7.1 Trabalho Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
89
90
A Diferenças Temporais
A.1 TD(λ) para Retropropagação . . . . . . . . . . . . . . . . . . . . . . . .
A.1.1 TD(0) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.1.2 TD(λ) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
93
93
94
94
B O Sistema ELO
B.1 A Invenção de Arpad Elo . . . . . . . . . . . . . . . . . . . . . . . . . .
B.2 O ELO no contexto do Abalone . . . . . . . . . . . . . . . . . . . . . .
97
97
99
ix
x
Lista de Figuras
2.1
2.2
2.3
2.4
2.5
2.6
2.7
2.8
Aspecto geral do mais recente Torneio Internacional de Abalone. . . . .
A posição do tabuleiro inicial no Abalone. . . . . . . . . . . . . . . .
As seis direcções nas quais uma peça ou grupo de peças se pode mover.
Exemplos de jogadas “Em Linha”. . . . . . . . . . . . . . . . . . . . .
Exemplo de jogada “Em Flecha”. . . . . . . . . . . . . . . . . . . . .
Exemplos de jogadas legais. . . . . . . . . . . . . . . . . . . . . . . .
Exemplos de jogadas ilegais. . . . . . . . . . . . . . . . . . . . . . . .
Sistema possı́vel de legenda das posições do tabuleiro. . . . . . . . . .
.
.
.
.
.
.
.
.
6
6
7
7
7
8
9
9
3.1
3.2
A rede utilizada na experiência de co-evolução . . . . . . . . . . . . . .
Percentagem de vitórias obtidas pelas redes amostradas de 100 em 100
gerações contra as redes de referência 1000 e 2000 . . . . . . . . . . . .
19
4.1
4.2
4.3
4.4
4.5
4.6
20
A interacção agente-ambiente em aprendizagem por reforço. . . . . . . .
Policy Evaluation para estimar V (s). . . . . . . . . . . . . . . . . . . . .
Value Iteration aplicada ao Mundo em Grelha 20×20 Simples. . . . . . .
Mundo em Grelha 20×20 com Lagos e Túnel. . . . . . . . . . . . . . .
Q-Learning aplicado ao Mundo em Grelha 20×20 com Lagos e Túnel. .
Performance do Q-Learning aplicado ao Mundo em Grelha 20×20 com
Lagos e Túnel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7 Variação da Temperatura (percentagem de acções óptimas escolhidas) . .
4.8 Variação da Temperatura (recompensa média obtida) . . . . . . . . . . .
4.9 Variação do número de acções (percentagem de acções óptimas escolhidas)
4.10 Variação do número de acções (recompensa média obtida) . . . . . . . .
36
39
40
42
42
5.1
5.2
55
5.3
5.4
5.5
5.6
5.7
5.8
O sistema dinâmico desenvolvido. . . . . . . . . . . . . . . . . . . . . .
Esquema da rede neuronal multi-camada utilizada no Abalearn para aproximar a função de avaliação. . . . . . . . . . . . . . . . . . . . . . . . .
Uma má superfı́cie de erro, com muitos mı́nimos locais. . . . . . . . . . .
Uma boa superfı́cie de erro, cujo mı́nimo óptimo pode ser facilmente obtido
A arquitectura utilizada para o Abalearn 2, designado Abalearn-Espacial .
A arquitectura utilizada para o Abalearn 3, designado Abalearn-Atributos
Exemplo de um dos jogos de treino. . . . . . . . . . . . . . . . . . . . .
Medição da recompensa média inicial (primeiros 100 jogos de treino). . .
xi
43
47
48
49
50
57
60
60
62
63
63
66
5.9
5.10
5.11
5.12
5.13
5.14
5.15
Representação construı́da pelo agente após 10 jogos de treino (λ=0.7). .
Representação construı́da pelo agente após 1000 jogos de treino (λ=0.7).
Representação construı́da pelo agente após 1000 jogos de treino (λ=0.1).
Percentagem de vitórias obtida contra um jogador Minimax . . . . . . .
Comparação entre as Redes . . . . . . . . . . . . . . . . . . . . . . . .
Desempenho global das redes . . . . . . . . . . . . . . . . . . . . . . .
Desempenho do Treino jogando contra vários tipos de oponentes. . . .
6.1
6.2
Um MDP simples com 2 estados . . . . . . . . . . . . . . . . . . . . . .
Desempenho dos agentes treinados por AR sensı́vel ao risco para diferentes valores de κ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Aumento do desempenho do agente sensı́vel ao risco treinado jogando
contra si mesmo (κ = −1). . . . . . . . . . . . . . . . . . . . . . . . . .
Valor do peso associado à Vantagem Material (peças ganhas – peças perdidas) para diferentes valores de κ. . . . . . . . . . . . . . . . . . . . . .
Valores de três dos mais importantes atributos para κ = 0. . . . . . . . .
Valores de três dos mais importantes atributos para κ = −0.8. . . . . . .
Valores de três dos mais importantes atributos para κ = −1. . . . . . . .
Desempenho do agente treinado com exploração por traço de contabilidade.
6.3
6.4
6.5
6.6
6.7
6.8
xii
.
.
.
.
.
.
.
66
66
67
67
69
70
72
76
79
79
80
81
81
82
87
Lista de Tabelas
3.1
3.2
3.3
5.1
5.2
5.3
6.1
6.2
6.3
6.4
6.5
Co-evolução: alguns valores de confiança a 95% para os resultados apresentados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Complexidade dos Jogos. . . . . . . . . . . . . . . . . . . . . . . . . . .
Previsão da força dos programas para a Computer Olympiad de 2010
(Jaap van der Herik et al., 2002). . . . . . . . . . . . . . . . . . . . . . .
Intervalos de confiança a 95% para alguns pontos no gráfico. . . . . . . .
Sumário de alguns resultados obtidos com λ = 0.7 . . . . . . . . . . . . .
Comparação entre as representações de estado (Taxa de Vitórias contra
jogador Minimax). . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Desempenho do Abalearn contra o A BA -P RO, para vários nı́veis de profundidade. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Desempenho do Abalearn usando o método II contra o T ERMINATOR III,
para vários nı́veis de profundidade. . . . . . . . . . . . . . . . . . . . . .
Abalearn treinado pelo método I jogou online e conseguiu vencer alguns
jogadores intermédios. . . . . . . . . . . . . . . . . . . . . . . . . . . .
O desempenho contra jogadores peritos humanos é superior usando o
Método II. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Comparação entre os métodos (Taxa de Vitórias contra jogador Minimax).
21
24
24
68
71
71
83
84
84
84
86
B.1 Modificações entre o Modelo 1 e Modelo 2. . . . . . . . . . . . . . . . . 101
xiii
xiv
Lista de Algoritmos
1
2
3
Co-Evolução . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Gradiente Descendente para TD(λ) . . . . . . . . . . . . . . . . . . . . .
Exploração com Traço de Contabilidade . . . . . . . . . . . . . . . . . .
xv
19
59
86
xvi
Notações Utilizadas
t
T
st
at
rt
Rt
π
π∗
π(s, a)
R
T
A(s)
V (s)
V π (s)
V ∗ (s)
Q(s, a)
Qπ (s, a)
Q∗ (s, a)
~e
w
~
α, β
ε
γ
λ
dt
σ
G
c(s)
κ
χκ (x)
ρ
Φ(s)
intervalo de tempo discreto
passo final de um episódio
estado no instante t
acção escolhida no instante t
recompensa no instante t
retorno (recompensa acumulada descontada) após t
polı́tica
polı́tica óptima
probabilidade de escolha da acção a no estado s seguindo a polı́tica π
função de recompensa (retorno imediato esperado)
função de transição
conjunto de todas as acções possı́veis no estado s
função de avaliação para os estados (estimativa)
avaliação do estado s seguindo a polı́tica π
avaliação do estado s seguindo a polı́tica óptima
avaliação da acção a no estado s (estimativa)
avaliação da acção a no estado s seguindo a polı́tica π
avaliação da acção a no estado s seguindo a polı́tica óptima
vector de eligibilidades de estados
vector de parâmetros de aproximação à função de avaliação
taxas de aprendizagem
probabilidade de escolha de uma acção aleatória
factor de desconto
factor de decaimento das eligibilidades
erro da diferença temporal no instante t
desvio padrão do ruı́do
número de gerações
contador de ocorrências de cada estado s
factor de sensibilidade ao risco
função de transformação de acordo com o risco κ
taxa de decaimento do traço de contabilidade
função que mapeia um estado s numa entrada para a rede
probabilidade de escolher uma acção de acordo com o traço de contabilidade
xvii
xviii
Capı́tulo 1
Introdução
HAL: I’m sorry Frank, I think you missed it: Queen to Bishop three, Bishop takes
Queen, Knight takes Bishop. Mate.
Frank: Uh, huh. Yeah, looks like you’re right. I resign.
HAL: Thank you for a very enjoyable game.
Frank: Yeah. Thank you.
Do filme “2001: Odisseia no Espaço”.
Esta dissertação apresenta o Abalearn, um programa inspirado no famoso TD-G AMMON
de Tesauro (Tesauro, 1995), que mostrou como as redes neuronais treinadas por diferença
temporal podem ser práticas na auto-aprendizagem do Gamão por jogos contra o próprio.
O nosso objectivo é construir um agente capaz de aprender a jogar Abalone desta maneira,
usando métodos de Aprendizagem por Reforço.
O paradigma da Aprendizagem por Reforço tem sido de grande interesse na área da
Aprendizagem Automática, por não ser necessário um “professor” inteligente para o fornecimento de exemplos de treino, tornando-o particularmente adequado a domı́nios complexos onde a obtenção desses exemplos seja difı́cil ou até mesmo impossı́vel.
Tentativas anteriores de construção de um agente capaz de aprender a jogar outros jogos
por reforço (como o Xadrez, Go, Othello...) usam exemplos de treino rotulados por peritos
(Dahl, 1999), exposição a jogadores competentes (jogos de treino online contra humanos
experientes) (Baxter et al., 2000) ou aprendizagem através de jogos contra oponentes
heurı́sticos (Dahl, 1999; Leouski, 1995).
A dinâmica do Abalone representa um desafio acrescido para os métodos de Aprendizagem por Reforço, em particular para os métodos de treino contra o próprio. Pollack
e Blair (1998) demonstraram que a dinâmica do Gamão foi crucial para o sucesso do
TD-G AMMON, devido à natureza estocástica do jogo (os dados forçam a exploracão) e à
suavidade da função de avaliação. O Abalone, por outro lado, é um jogo determinı́stico
com um sinal de reforço muito fraco: na verdade, os jogadores podem facilmente repetir
1
Capı́tulo 1. Introdução
eternamente as mesmas jogadas e a partida pode não terminar nunca, se um dos jogadores
não arriscar.
É com base nessa observação que propomos, nesta dissertação, um método capaz de ser
bem sucedido no treino jogando contra o próprio para o jogo Abalone que é baseado
num modelo de Aprendizagem por Reforço que é sensı́vel ao risco (Mihatsch e Neuneier,
2002). Também propomos um conjunto de representações de estado e atributos para
aprender a jogar Abalone usando apenas o resultado do jogo como sinal de treino.
Na secção seguinte descrevemos um dos mais famosos trabalhos que mostrou as vantagens de utilizar os Jogos como terreno de teste às técnicas de Aprendizagem Automática.
O trabalho de Arthur Samuel impressiona não apenas pela idade (1959) como também
por ter servido de base às ideias que ainda hoje estão em voga.
1.1 O Legado de A. Samuel
Em 1947, Arthur L. Samuel, na altura Professor de Engenharia Electrotécnica na Universidade do Illinois, lembrou-se de construir um programa que jogasse às Damas. O jogo
das Damas, geralmente considerado mais simples que o Xadrez, parecia ser o domı́nio
perfeito para demonstrar o poder da computação simbólica através de um curto projecto
de programação. O plano era simples: escrever um programa que jogasse às Damas,
desafiar o campeão mundial e vencê-lo1 .
Samuel estava longe de imaginar que passaria as duas décadas seguintes a trabalhar nesse
programa, produzindo não apenas um programa ao nı́vel de um Mestre das Damas mas
também introduzindo importantes conceitos na teoria dos jogos e na aprendizagem automática. Os dois principais artigos resultantes da sua investigação (Samuel, 1959, 1967)
tornaram-se marcos simbólicos da Inteligência Artificial.
Nos seus trabalhos, Samuel não foi apenas pioneiro das inúmeras técnicas de procura
modernas, utilizadas em programas que jogam com alto desempenho, como os cortes
alfa-beta, mas também inventou um vasto leque de técnicas de aprendizagem para melhorar o desempenho dos programas ao longo do tempo. Samuel considerou as Damas um
domı́nio perfeito para o estudo das técnicas de aprendizagem automática porque nos jogos
muitas das complicações que surgem nos problemas da vida real são simplificadas, permitindo que os investigadores se foquem nos problemas de aprendizagem propriamente
ditos (Samuel, 1959). Como resultado disso, muitas das técnicas que contribuı́ram para o
sucesso da Aprendizagem Automática como ciência podem ser relacionadas a Samuel e
muitas das ideias de Samuel para Aprendizagem ainda são utilizadas hoje em dia, de uma
forma ou outra.
1
Com este pequeno projecto, Samuel esperava gerar interesse suficiente para a angariação de fundos
para um computador universitário (McCorduck, 1979)
2
1.2. Estrutura do Documento e Contribuições
Em primeiro lugar, o seu programa de Damas gravava as posições que encontrava frequentemente durante o jogo. Esta forma simplificada de rote learning permitia poupar tempo
e procurar com profundidade maior nos jogos subsequentes sempre que uma posição armazenada fosse encontrada no tabuleiro ou numa determinada linha de cálculo.
Em segundo lugar, o programa constituiu a primeira aplicação bem sucedida da área hoje
em dia conhecida como aprendizagem por reforço, para a afinação automática dos pesos
da sua função de avaliação. O programa treinava-se a si próprio jogando contra uma cópia
estável de si mesmo, um processo que designaremos por auto-treino. Após cada jogada,
os pesos da função de avaliação eram ajustados numa forma que movia a avaliação da
posição na raı́z da árvore de procura minimax mais perto da avaliação da posição raı́z
após procurar com vários nı́veis de profundidade. Esta ideia e outros aspectos do trabalho
de Samuel sugerem fortemente a ideia essencial do método conhecido actualmente por
aprendizagem por diferença temporal: o valor de uma posição deve igualar o valor de
posições semelhantes que surjam eventualmente mais tarde, partindo dessa posição.
Mais tarde, Samuel alterou ainda a função de avaliação de uma combinação linear de termos para uma estrutura que se parece fortemente com uma rede neuronal de três camadas.
Esta estrutura foi treinada com treino por comparação a partir de milhares de posições de
jogos de mestres gravados.
As áreas dos Jogos e de Aprendizagem Automática evoluı́ram muito desde os dias de
Arthur Samuel. Apesar dessa evolução, muitas das novas técnicas desenvolvidas nestas
duas áreas podem ser directamente relacionadas com algumas das suas ideias. O seu
jogador de Damas ainda é considerado um dos trabalhos mais influentes nas duas áreas, e
um exemplo perfeito de uma simbiose frutı́fera das duas áreas.
1.2 Estrutura do Documento e Contribuições
Este documento encontra-se organizado da seguinte forma:
Capı́tulo 1. Esta introdução.
Capı́tulo 2. Descrição do domı́nio onde se insere este trabalho, o jogo Abalone. Descrevese as regras, os programas já existentes, os problemas e desafios colocados por este jogo
no contexto da aprendizagem automática.
Capı́tulo 3. Um levantamento do estado da arte em programas que aprendem a jogar.
Capı́tulo 4. O fundamento teórico da Aprendizagem por Reforço, ilustrado com exemplos e algumas experiências.
Capı́tulo 5. Descrição da abordagem inicial ao problema utilizando a versão clássica do
algoritmo TD(λ). Descreve-se também as várias representações de estado estudadas, e
apresenta-se os resultados experimentais que demonstram que os atributos encontrados
são relevantes para a aquisição com sucesso de estratégias de Abalone.
3
Capı́tulo 1. Introdução
Capı́tulo 6. Descrição do fundamento teórico da aprendizagem por reforço sensı́vel ao
risco e apresentação da extensão do algoritmo TD(0) sensı́vel ao risco para o caso em que
λ 6= 0. Demonstração através de resultados experimentais de que a extensão pode levar a
um auto-treino mais eficaz.
Capı́tulo 7. Conclusões, limitações do trabalho e possı́veis linhas de investigação para
trabalho futuro.
Apêndice A. Descrição formal do algoritmo TD(λ) utilizado para o treino de redes neuronais por Retropropagação.
Apêndice B. Breve história do sistema de avaliação de jogadores inventado por Arpad
Elo e a sua contextualização a nı́vel do Abalone.
As principais contribuições que esta dissertação apresenta são as seguintes:
• O primeiro programa que aprende uma função de avaliação para o jogo Abalone.
O programa aprende unicamente através da sua própria experiência e do sinal de
reforço, não necessitando de exemplos de treino, registos de jogos, exposição a
jogadores competentes ou afinação humana.
• A primeira aplicação da aprendizagem por reforço sensı́vel ao risco (Mihatsch e
Neuneier, 2002) a um cenário complexo. Citando um dos avaliadores do artigo
(Campos e Langlois, 2003), “it is the first time the technique of risk-sensitive RL is
applied in a real scenario.”
• Extensão do algoritmo TD(0) sensı́vel ao risco (Mihatsch e Neuneier, 2002) para o
caso em que λ 6= 0.
• Atributos relevantes para a aprendizagem de estratégias para o Abalone.
• Uma arquitectura geral para o desenvolvimento de agentes que aprendem a jogar
por reforço, de acordo com a norma apresentada por (Sutton and Barto, 1998).
4
Capı́tulo 2
Abalone
“Abalone est le jeu universel par excellence avec un but du jeu simple: pousser
6 des 14 billes de son adversaire hors du plateau, selon le principe de supériorité
numérique.”
www.abalonegames.com
Neste capı́tulo descreve-se a versão standard do jogo Abalone e apresenta-se as regras
fundamentais, assim como algumas variantes.
O Abalone é um jogo estratégico com 4 milhões de unidades vendidas em 30 paı́ses. Foi
criado em 1989 por Laurent Lévi e Michel Lalet e é hoje em dia jogado por mais de
10 milhões de jogadores em todo o mundo1. Obteve o prémio de “Jogo da Década” no
“Festival International des Jeux” em 1998. A Figura 2.1 mostra o aspecto geral do mais
recente Torneio Internacional de Abalone que se realizou em Cannes.
2.1 Regras do Jogo
O Abalone é jogado num tabuleiro hexagonal onde se defrontam dois jogadores. Cada
jogador possui 14 peças. A Figura 2.2 mostra a posição inicial das peças no tabuleiro do
Abalone. O objectivo do jogo é empurrar seis peças do adversário para fora do tabuleiro.
Os jogadores alternam a vez, iniciando-se o jogo com uma jogada das peças pretas.
2.1.1 Movimentos das Peças
Uma, duas ou três peças da mesma cor podem mover-se uma casa em quaisquer seis
direcções, como mostra a Figura 2.3, desde que os espaços-alvo estejam vazios. No caso
1
Para mais informações, consultar www.abalonegames.com.
5
Capı́tulo 2. Abalone
2
Figura 2.1: Aspecto geral do mais recente Torneio Internacional de Abalone.
Figura 2.2: A posição do tabuleiro inicial no Abalone.
6
2.1. Regras do Jogo
de se mover mais do que uma peça, o grupo deve mover-se contı́guo e numa linha. Não é
possı́vel mover 4 ou mais peças da mesma cor numa só jogada.
Existem duas categorias de movimentos. Movimentos “Em linha” envolvem mover todas
as peças de um grupo numa linha recta, para a frente ou para trás, conforme se mostra na
Figura 2.4. Movimentos “Em flecha” deslocam as peças lateralmente em direcção a uma
linha adjacente. A Figura 2.5 ilustra este caso.
Figura 2.3: As seis direcções nas quais uma peça ou grupo de peças se pode mover.
Figura 2.4: Exemplos de jogadas “Em Linha”.
Figura 2.5: Exemplo de jogada “Em Flecha”.
7
Capı́tulo 2. Abalone
2.1.2 Empurrando as peças adversárias
Pode-se empurrar as peças adversárias apenas se estas estiverem directamente no caminho
de uma jogada “em linha”. Isto é, as peças adversárias devem estar dispostas na direcção
na qual o grupo de peças está orientado, e devem estar adjacentes a uma das peças no
grupo. Um jogador nunca é obrigado a empurrar.
Só é permitido empurrar as peças adversárias caso se supere numericamente o oponente
(3 peças podem empurrar 2 ou 1, 2 peças podem empurrar 1). Não é permitido empurrar
no caso de uma peça não-oponente se encontrar no caminho.
A Figura 2.6 exemplifica jogadas legais e a Figura 2.7 ilustra jogadas que não são permitidas.
Figura 2.6: Exemplos de jogadas legais.
2.1.3 “Bola Fora” e Fim do Jogo
Uma peça é atirada para fora quando, ao ser empurrada, é forçada a sair do tabuleiro. O
vencedor é aquele que conseguir empurrar para fora as primeiras seis bolas do adversário.
Não é permitido empurrar as próprias peças.
2.1.4 Notação dos Movimentos
Cada localização no tabuleiro pode ser denotada por uma coordenada da forma [a-i][19], como mostra a Figura 2.8. As letras indicam “linhas” horizontais do tabuleiro e os
números indicam colunas “diagonais”. Por exemplo, o canto superior esquerdo do tabuleiro constitui a posição a1. Note-se que nem todas as combinações da forma [a-i][1-9]
são coordenadas válidas: por exemplo, i1 não é uma posição no tabuleiro.
8
2.1. Regras do Jogo
Figura 2.7: Exemplos de jogadas ilegais.
a
e
d
f
c
2
2
1
b
3
4
5
6
7
8
9
g
h
i
Figura 2.8: Sistema possı́vel de legenda das posições do tabuleiro.
9
Capı́tulo 2. Abalone
2.1.5 Estratégia e Problemas
A forma de ataque ideal é em rhomb: 3 peças em linha em todos os ângulos constitui uma
forma fácil de destruir o oponente. Peças fora do rhomb podem ser usadas, por exemplo,
para criar armadilhas. O facto de ser necessário empurrar 6 bolas adversárias para fora do
tabuleiro faz assim sentido: quando um jogador só possui 8 peças (6 fora), não consegue
criar um rhomb, por isso o seu jogo não pode ser eficiente.
Ao defender-se, um jogador pode dar a forma de um trapézio ao seu jogo. Desta forma, o
jogo não pode ser destruı́do pelo atacante a não ser que este ataque pelos lados, correndo
os riscos inerentes.
O problema com o Abalone é que, assim que um certo nı́vel de jogo é atingido, o jogo
parece tornar-se muito estável e não é possı́vel mudar muito se nenhum dos jogadores
quiser correr riscos. Isto significa que é fácil jogar para o empate (uma noção que não
existe no Abalone).
Um outro facto curioso é o de que o jogo não está totalmente definido, pois existe pelo
menos uma posição para a qual o jogador que tem de efectuar o movimento fica impossibilitado de o fazer (Torrance et al., 1992). Além disso, deveria ser adicionada uma regra a
considerar o caso de empate sempre que uma posição fosse encontrada mais que um certo
número de vezes (empate por repetição).
2.2 Versões Existentes do Jogo
Todas as versões deste jogo (comerciais ou não) baseiam-se em procura heurı́stica. Normalmente, o que se usa é uma tabela de valores para cada uma das casas no tabuleiro,
sendo a avaliação uma soma pesada desses valores com as peças de cada jogador nessas
casas. Esses valores são mais ou menos afinados por bons jogadores humanos, baseandose na sua experiência de jogo e nas caracterı́sticas do tabuleiro. As melhores heurı́sticas
foram, portanto, encontradas à custa de muita análise humana.
O MIT dedicou uma mailing list inteira a este jogo. Nela discutiram-se heurı́sticas e algoritmos de procura para este jogo. Muitas versões foram construı́das, algumas delas bem
sucedidas no nı́vel de jogo. A mailing list culminou com a versão final de um programa
designado MITA BALONE. Outras versões podem encontrar-se na Web (V BALONE, A BA LONE JAVA ) e até no Sistema Operativo Linux (K ABALONE).
No contexto desta dissertação, é vantajosa a existência de programas de Abalone que utilizam as técnicas convencionais de procura heurı́stica, pois esses programas podem constituir uma medida de desempenho eficaz na avaliação de um programa como o Abalearn,
que aprende uma função de avaliação para o Abalone.
Na verdade, foram muito úteis dois programas em especial, por dois motivos distintos.
10
2.2. Versões Existentes do Jogo
Um deles foi baptizado de A BA -P RO pelo seu autor (Aichholzer et al., 2002).2
O programa A BA -P RO é um dos melhores jogadores de Abalone construı́dos até agora.
Baseia-se em algoritmos de procura sofisticados e numa função heurı́stica complexa e afinada manualmente. Utiliza procuras muito profundas (6-9 nı́veis) e altamente selectivas.
No Capı́tulo 6, descrevemos os resultados da avaliação do Abalearn contra este programa.
Outro programa interessante é o Abalone 1.5.1 para Macintosh (programa freeware), de
Peter Tax. Este autor explorou diversas heurı́sticas para este jogo e avaliámos o Abalearn
também contra este programa (ver Secção 6.3.1) visto que tem a vantagem de evitar que o
jogo entre em ciclo, pois o programa detecta se a jogada escolhida foi efectuada recentemente e escolhe outra com semelhante valor. A melhor heurı́stica, baptizada Terminator
III, baseia-se no valor posicional, conectividade e número de peças para cada jogador
ainda em jogo.
2
Para mais informações sobre este programa e sobre as técnicas utilizadas referimos o leitor para o
endereço http://www.cis.tugraz.at/igi/oaich/abalone.html.
11
Capı́tulo 2. Abalone
12
Capı́tulo 3
Estado da Arte
“There are two principal reasons to continue to do research on games. First, human fascination with game playing is long-standing and pervasive. Anthropologists
have catalogued popular games in almost every culture. [...] The second reason is
that some difficult games remain to be won, games that people play very well but
computers do not. These games clarify what our current approach lacks. They set
challenges for us to meet, and they promise ample rewards.”
Susan L. Epstein, Game Playing: The Next Moves
Neste capı́tulo, procurou-se condensar os aspectos actualmente mais relevantes do estado
da arte em programas que aprendem a jogar. A pesquisa centrou-se no problema da
afinação automática dos pesos da função de avaliação. A pesquisa bilbiográfica poderia
ter sido agrupada por tipo de jogo, ou por tipo de técnica de aprendizagem, mas optou-se
por seguir uma abordagem orientada aos diversos problemas que se colocam em diferentes
aspectos do jogo. Acredita-se que com este agrupamento se clarifica as técnicas mais
relevantes para os problemas que se colocam nos diferentes aspectos dos jogos, e também
se aponta os tópicos mais recompensadores na aplicação das técnicas de aprendizagem
aos cenários dos jogos.
3.1 Introdução
Os jogos definem domı́nios fáceis de representar e de avaliar. Contudo, jogar ao nı́vel de
um perito requer capacidades sofisticadas de planeamento, reconhecimento de padrões e
de memória (Boyan, 1992).
Os algoritmos utilizados em jogos usam normalmente uma função de avaliação que retorna a utilidade esperada de uma dada posição. Em jogos complexos, como o Go, Xadrez e Damas, utilizam-se regras simbólicas para obter uma aproximação da função de
13
Capı́tulo 3. Estado da Arte
avaliação. Tais programas usam técnicas de procura rigorosas onde milhões de posições
têm de ser avaliadas antes de ser encontrada uma solução razoável. Isto implica, obviamente, uma exigência grande em termos de velocidade de processamento da máquina.
Para dar um exemplo, o D EEP B LUE (Hsu, 1999), computador campeão de Xadrez, procura 200 milhões de posições por segundo!
A necessidade destas estratégias de procura provém das muitas descontinuidades (ou
excepções) na função de avaliação que são causadas pelas diferentes combinações de
contribuições de peças no tabuleiro. Para estes jogos, terı́amos de representar todas essas
descontinuidades no modelo da função de avaliação, o que é muito difı́cil, daı́ a utilização
de aproximações que utilizam regras simbólicas.
Desta forma, o programador do jogo tem de fornecer ao programa um conjunto de bibliotecas de rotinas que calculam importantes propriedades de uma posição do tabuleiro
(por exemplo o número de peças de cada cor em jogo, o tamanho do território controlado,
etc.) que nesta dissertação designaremos por atributos. O que se desconhece é a forma de
combinar estes atributos e a sua importância relativa.
As abordagens conhecidas para lidar com este problema podem ser categorizadas ao longo
de várias dimensões. No contexto desta dissertação, a categorização é feita de acordo
com o tipo de informação de treino que é recebida. Em aprendizagem supervisionada,
a função de avaliação é treinada sobre informação acerca dos valores correctos, isto é, o
agente recebe exemplos de posições ou jogadas rotuladas com a sua avaliação correcta.
Este valor pode ser obtido a partir da análise de registos de jogos ou a partir da opinião de
peritos. A dificuldade está na quantidade necessária de exemplos de treino que é exigida
para que a aproximação seja razoável, e também na subjectividade inerente à classificação
por parte de um jogador humano de uma boa ou má posição.
Em treino por comparação, fornece-se ao agente uma colecção de pares de jogadas e a
informação de qual das jogadas é melhor. Alternativamente, fornece-se uma coleção de
exemplos de treino (posições) e as jogadas seguidas para cada uma dessas posições.
Uma forma mais atractiva é o uso de aprendizagem por reforço (AR), na qual os exemplos de treino são gerados pelo próprio sistema. Aprendizagem por reforço (Sutton and
Barto, 1998) significa aprender a jogar de forma a poder, incrementalmente, testar e refinar a função de avaliação. O agente não recebe qualquer informação directa acerca do
valor absoluto ou relativo dos exemplos de treino. Em vez disso, recebe um sinal escalar
atrasado do ambiente que lhe indica a qualidade das jogadas efectuadas. No caso mais
simples, este sinal consiste em +1 se ganhou, 0 se empatou e −1 se perdeu. O paradigma
da AR é atractivo pois apenas é necessário explicitar as regras do jogo e um módulo de
aprendizagem, não sendo necessária a ajuda de peritos. Samuel (1967) foi o primeiro
a construir um sistema de aprendizagem por reforço. Utilizou um algoritmo complexo
para seleccionar ajustamentos nos parâmetros baseando-se na diferença entre as sucessivas avaliações de posições bem sucedidas num jogo, a fim de aprender a jogar às Damas
(Samuel, 1967).
14
3.2. Aprendizagem por Reforço
Aprendizagem por diferença temporal (Tesauro, 1995; Dayan, 1992; Dayan and Sejnowski, 1994) é um caso especial de AR que fornece um método eficiente para receber
exemplos de treino com uma precisão mais elevada, uma vez que a avaliação de uma
dada posição é ajustada usando as diferenças entre a sua avaliação e as avaliações de
posições sucessivas. Desta forma, a previsão do resultado do jogo a partir de uma certa
posição está relacionada com as previsões das posições seguintes. Sutton (1988) definiu
toda uma classe de algoritmos, TD(λ), que observam as previsões de posições sucessivas
mais à frente no jogo, pesadas de acordo com uma constante de decaimento exponencial,
λ. Dayan e Sejnowski (1994) provaram que os algoritmos TD convergem com probabilidade 1 quando uma representação linear das entradas é utilizada.
3.2 Aprendizagem por Reforço
No modelo conceptual da aprendizagem por reforço, um agente interage com o ambiente.
Esta interacção consiste na percepção do ambiente e na selecção de uma acção para executar nesse ambiente. A tarefa do agente consiste em aprender quais as melhores acções
para cada estado. Contudo, ao contrário da aprendizagem supervisionada, o agente não
recebe informação de treino por parte de um perito: em vez disso, explora as diferentes
acções e recebe do ambiente um sinal escalar de reforço que reflecte a qualidade das suas
acções.
No contexto dos jogos, as acções são, tipicamente, as jogadas legais a partir do estado
actual do jogo, e o sinal de reforço indica se o agente ganha ou perde o jogo (e/ou porque
margem de diferença é que ganha ou perde).
Uma das primeiras aplicações de técnicas de aprendizagem aos jogos usou uma forma de
aprendizagem por reforço ainda antes de esta ser considerada uma área cientı́fica: o famoso M ENACE, Matchbox Educable Noughts and Crosses Engine (Michie, 1963) aprendia o jogo do galo por reforço. O M ENACE tinha um peso associado a cada uma das 287
posições diferentes (variantes de rotação ou de simetria eram mapeadas para uma única
posição). Em cada estado, todas as possı́veis acções (todos os quadrados ainda não ocupados) tinham um peso atribuı́do. A acção seguinte era seleccionada de acordo com uma
distribuição de probabilidade correspondente aos pesos das diferentes escolhas. Dependendo do resultado do jogo, as jogadas da máquina eram penalizadas ou recompensadas
aumentando ou diminuindo o seu peso. Um empate era também considerado um sucesso
e também era recompensado (com um aumento menor do valor do peso).
O problema principal a ser resolvido pelo agente é o chamado problema da atribuição
dos créditos (Minsky, 1963), isto é, o problema de distribuir a recompensa recebida pelas acções responsáveis por essa recompensa. Por exemplo, num jogo perdido, apenas
uma jogada pode ter sido decisiva para a derrota. Apenas essa jogada deve receber a
recompensa negativa, pois todas as restantes jogadas podem ter sido boas.
15
Capı́tulo 3. Estado da Arte
Michie (1963) propôs duas técnicas para resolver o problema da atribuição dos créditos.
A primeira técnica simplesmente fornece o mesmo crédito a todas as jogadas de uma
partida. A segunda técnica assume que as posições que ocorrem mais tarde durante o jogo
possuem um impacto maior no resultado final do que as posições que ocorrem no inı́cio.
Esta técnica simples não impede que as boas jogadas recebam reforço negativo (quando
se comete um erro no fim do jogo) nem impede as más jogadas de receber reforço positivo
(quando o jogo é ganho porque o oponente não aproveitou o erro cometido). Contudo, a
ideia é que após muitos jogos, as boas jogadas terão recebido mais reforços positivos do
que negativos e vice versa, até que a função de avaliação eventualmente convirja para um
valor razoável.
Mais de três décadas após a criação do M ENACE, Sutton and Barto (1998) confirmariam
esta proposição com teoremas de convergência para a aprendizagem por reforço. Michie,
contudo, só pôde contar com a evidência experimental: a primeira máquina jogava contra
um professor humano. Posteriormente passou a jogar em torneios contra um oponente
aleatório e contra um cópia independente de si mesmo que também aprendia.
Apesar disto, M ENACE tinha muitas limitações óbvias. A primeira era o uso de uma
tabela com uma entrada para cada estado. Para um jogo simples como o jogo do galo
isto é possı́vel, mas para jogos mais complexos como o Xadrez é necessário uma forma
qualquer de generalização. Mais importante, ainda, é o facto de o treino baseado apenas
no resultado final do jogo ser muito lento e ser necessário um grande número de jogos
antes de as avaliações das posições convergirem para valores razoáveis. Aprendizagem
por diferença temporal apresentou um grande melhoramento a este respeito.
3.3 Diferença Temporal
Ocorreu uma pequena revolução no campo da Aprendizagem por Reforço quando Gerald
Tesauro apresentou os seus primeiros resultados do treino de uma função de avaliação do
usando o método da Diferença Temporal (Tesauro, 1995, 1993). O programa de Tesauro,
TD-G AMMON, era um jogador de gamão que necessitava de pouco conhecimento sobre o
gamão mas que, apesar disso, conseguiu atingir resultados ao nı́vel dos maiores jogadores
mundiais (Tesauro, 1992).
O algoritmo de aprendizagem utilizado no TD-G AMMON era uma combinação do algoritmo TD(λ) com uma função de aproximação não-linear baseada numa rede neuronal.
A rede neuronal possuı́a uma papel dual, na medida em que se assumia como previsora
do retorno esperado da posição do tabuleiro e como um meio de seleccionar jogadas. Em
qualquer posição, a jogada seguinte era escolhida de forma gananciosa, avaliando todas as
posições alcançáveis a partir do estado actual e seleccionando então aquela com o melhor
retorno. Os parâmetros da rede neuronal eram actualizados de acordo com o algoritmo
TD(λ) após cada jogo.
16
3.3. Diferença Temporal
Modelar a função de avaliação com uma rede neuronal coloca várias questões: por exemplo, que topologia da rede deve ser utilizada? E como deve ser feita a codificação do
estado que constitui a entrada da rede? Tesauro (1995) adicionou um número de atributos relevantes para o jogo do Gamão à informação que codificava a entrada da rede para
aumentar a informação imediatamente disponı́vel à rede neuronal. Com essa codificação
conseguiu um aumento de desempenho do seu programa.
Recentemente, Tesauro descreveu também o seu algoritmo de doubling (Tesauro, 2002).
Doubling consiste em decidir sobre se o oponente deve ou não aceitar um double. A
fórmula baseia-se numa generalização de trabalhos anteriores em teoria de estratégias
de doubling. A generalização para múltiplas utilidades também se encontra descrita em
(Tesauro, 2002).
Os resultados espantosos do TD-G AMMON não voltaram a ser repetidos, apesar de haver
muito esforço nesta área para outros jogos de tabuleiro, como o Go, Xadrez e Othello,
pelo que este campo continua em estudo aberto. Um dos objectivos deste trabalho reside,
por isso, em tentar descobrir métodos inspirados nestas tentativas para o Abalone.
Muitos autores, entre os quais (Schraudolph et al., 2001; Levinson, 1995; Pollack and
Blair, 1998), discutiram as peculiaridades do gamão que o tornam particularmente apto a
aprender baseando-se em Diferenças Temporais.
3.3.1 A Receita do Sucesso
Tendo em conta o objectivo deste trabalho, é conveniente analisar as principais caracterı́sticas do gamão que contribuı́ram para o sucesso de Tesauro. Entre estas, incluem-se:
a rapidez do jogo: TD-G AMMON aprendia a partir de vários milhares de jogos contra
si mesmo, a suavidade da representação: a avaliação de uma posição no gamão é uma
função razoavelmente suave de posição, facilitando uma boa aproximação por rede neuronal, e o factor estocástico do jogo: o gamão, sendo jogado com lançamento de dados,
força pelo menos uma quantidade mı́nima de exploração do espaço de estados.
Contudo, e apesar do sucesso do TD-G AMMON sobre os seus predecessores que foram
treinados por aprendizagem supervisionada ou treino por comparação, não se pode concluir que aprendizagem por diferença temporal seja a melhor solução para todos os jogos.
Por exemplo (Samuel, 1967) no seguimento do seu famoso artigo sobre o seu programa
de Damas chegou a um resultado diferente: treino por comparação a partir de 150 000
jogadas de peritos aparenta ser um método mais eficaz e fiável do que aprendizagem por
diferença temporal por auto-treino.
(Pollack and Blair, 1998) colocam, em 1998, a hipótese de o sucesso do TD-G AMMON
não derivar das técnicas de retro-propagação ou aprendizagem por diferença temporal,
mas sim de uma predisposição (bias) inerente à própria dinâmica do jogo do Gamão, assim como à natureza do próprio processo de treino, no qual a tarefa muda dinamicamente
17
Capı́tulo 3. Estado da Arte
à medida que a aprendizagem decorre.
Assim, os autores mostram que um método inicialmente considerado fraco – treinar uma
rede neuronal usando um simples algoritmo de “trepar a colina” – funcionou relativamente bem visto que evitou um equilı́brio de Nash sub-óptimo na auto–aprendizagem
(Pollack and Blair, 1998). Apesar de Tesauro (1998) não concordar inteiramente com as
conclusões que Pollack and Blair (1998) derivam desta experiência, o simples facto de
que este procedimento de treino funciona é notável.
Para o caso do Abalearn, em que se pretende treinar por Diferença Temporal um programa
a jogar Abalone, isto representa uma má notı́cia, uma vez que Pollack retira o mérito exclusivo às técnicas de aprendizagem por reforço no caso do TD-G AMMON. Apesar disto,
o artigo apresenta uma análise valiosa em questões como a capacidade de aprendizagem
e evolução versus co-evolução. Propõe também uma solução para evitar o equilı́brio subóptimo numa auto-aprendizagem. Em jogos determinı́sticos, como o Abalone ou o Xadrez, este problema é particularmente prevalente, inibindo o agente de explorar o espaço
de estados do jogo, logo, fazendo-o jogar os mesmos tipos de jogos repetidamente.
Avaliar a eficácia deste método no Abalone não só fornece uma indicação sobre a adequabilidade de métodos co-evolutivos simples em jogos determinı́sticos em geral, como
também permite uma fácil identificação daqueles que são os maiores problemas que se
colocam ao elaborar um agente que aprende a jogar Abalone. Por isso na próxima secção,
revisitamos esta experiência aplicando-a ao Abalone.
3.3.2 A experiência de Pollack e Blair revisitada
Para esta abordagem, utilizou-se a rede ilustrada na Figura 3.3.2. Tentou-se reproduzir
o mais possı́vel as condições experimentais de Pollack e Blair. Dada uma posição no
tabuleiro, a rede produz uma estimativa do seu valor aplicando uma função não-linear de
squashing à soma pesada das entradas com os correspondentes pesos. A saı́da da rede é
dada por:
2
−1
1 + enet
X
net =
wi xi
o(net) =
com
(3.1)
i
e está limitada ao intervalo [–1, 1]. As entradas são codificadas usando o valor –1 para
uma peça preta, 1 para uma peça branca e 0 para casas vazias. O jogo desenrola-se
gerando todos os tabuleiros resultantes da aplicação uma jogada legal, convertendo cada
um desses tabuleiros num vector de entrada para a rede e escolhendo, com probabilidade
(1 – ) a posição estimada como sendo a melhor pela rede. Inicialmente os pesos são
todos nulos. O algoritmo 1 descreve o processo de co-evolução.
18
3.3. Diferença Temporal
Figura 3.1: A rede utilizada nesta experiência. Constitui um mapeamento directo da posição do
tabuleiro.
Algoritmo 1 Co-Evolução
parâmetros: taxa de mutação α, número de gerações G, desvio padrão do ruı́do σ
Ct , Mt {redes neuronais do campeão C e do mutante M no instante t}
∀wi ∈ W (C0 ) : wi ← 0
para t = 0 até G fazer
∀wc ∈ W (Ct ), ∀wm ∈ W (Mt ) : wm ← wc + N (0, σ).
Ct joga N jogos contra Mt
se Mt vencer mais de N/2 jogos contra Ct então
∀wc ∈ W (Ct ), ∀wm ∈ W (Mt ) : wm ← wc + N (0, σ).
fecha se
fecha para
19
Capı́tulo 3. Estado da Arte
Percentagem de Vitórias (Média de 30 jogos)
3.3.3 Análise dos resultados
0.8
Percentagem de Vitórias contra Rede 1000
Percentagem de Vitórias contra Rede 2000
0.7
0.6
0.5
0.4
0.3
0.2
0
5
10
x100 Gerações
15
20
Figura 3.2: Percentagem de vitórias obtidas pelas redes amostradas de 100 em 100 gerações contra
as redes de referência 1000 e 2000. Cada ponto mostra a média de 10 séries de 30 jogos, com as
quais se construiu um intervalo de confiança a 95%.
O problema da aplicação desta estratégia ao Abalone provém do facto de as regras do
jogo permitirem a ocorrência de estados repetidos. Numa estratégia 100% gananciosa
o jogo tende a terminar quase sempre empatado devido à ocorrência cı́clica de posições
repetidas, assumindo até, por vezes, dimensões elevadas. Por isso foi necessário permitir
a escolha de uma jogada aleatória em detrimento de uma jogada gananciosa, de acordo
com uma dada probabilidade. Apesar disso, o jogo tende a entrar muitas vezes numa fase
de “ciclo”, tornando o algoritmo mais lento e dificultando a aprendizagem.
Nesta secção define-se os parâmetros da experiência e analisa-se os resultados obtidos.
Tal como (Pollack and Blair, 1998), a forma de avaliar o desempenho das redes foi compará-las umas em relação às outras, a fim de determinar se está a haver uma evolução
positiva na aprendizagem ou não (uma vez que se trata de simples hill-climbing).
Parâmetros da Experiência.
• N: número de jogos que o mutante tem de ganhar para que ocorra uma mutação ao
campeão;
• α: taxa de mutação, que representa a percentagem do valor dos pesos do mutante a
adicionar ao campeão;
• σ: desvio padrão do ruı́do adicionado ao campeão para criar o mutante;
20
3.3. Diferença Temporal
• G: número de gerações evoluı́das (iterações do algoritmo);
• : percentagem de acções escolhidas aleatoriamente por um jogador.
Para esta experiência, optou-se por fixar N em 4 jogos e α, a taxa de mutação, em 5%.
Substituir um campeão bem testado é perigoso sem que exista informação suficiente a
provar que o mutante é, de facto, um jogador melhor e não apenas um novato com sorte.
Por isso, em vez de substituir o campeão pelo mutante (quando este vence mais de N/2
jogos), efectua-se apenas um pequeno ajustamento de 5% nessa direcção.
Os valores de σ e de fixaram-se em 0.1 e 0.05 respectivamente. Estes foram os melhores
valores encontrados experimentalmente para o algoritmo. O valor de foi o mais baixo
possı́vel para evitar predisposições (bias) a influenciar o resultado do jogo. Obteve-se
resultados para 2000 gerações.
% Média de vitórias
Desvio Padrão
Confiança a 95%
10
0.310
0.036
0.0006
500
0.389
0.096
0.0018
1000
0.462
0.100
0.0019
1500
0.454
0.077
0.0014
2000
0.506
0.026
0.0004
Tabela 3.1: Alguns valores de confiança a 95% para os resultados apresentados
À medida que o algoritmo corria a co-evolução, as redes obtidas foram amostradas de
10 em 10 gerações. A Figura 3.2 mostra a percentagem de vitórias obtidas pelas redes
amostradas de 100 em 100 gerações contra as redes de referência 1000 e 2000. Construiuse um intervalo de confiança a 95% (Tabela 6-1) para cada um dos pontos no gráfico, que
representam um conjunto de percentagens médias de vitórias num conjunto de 30 jogos.
Excluı́ram-se os jogos que terminaram em empate.
Observa-se um ligeiro aumento na percentagem de vitórias, mas esse aumento é muito
ruidoso para que se possa concluir que a abordagem acabe por funcionar. As redes iniciais
(10-900 gerações) são muito fracas, e a rede mais evoluı́da (2000 gerações) é globalmente
mais difı́cil de ser vencida. De uma maneira geral, observa-se que há uma evolução
positiva, mas o tempo de treino elevado torna esta abordagem impraticável.
Conclusões. A abordagem co-evolutiva que foi bem sucedida no gamão não funcionou
neste jogo. Há três razões para este resultado:
• O facto de o jogo entrar frequentemente num ciclo de posições repetidas quando os
jogadores são ambos 100% gananciosos.
• A estratégia consiste num hillclimbing simples que conduz facilmente a esses ciclos
que impedem a aprendizagem.
• A rede utilizada é um perceptrão simples e constitui um mapeamento directo do
tabuleiro, o que diminui a velocidade do treino.
21
Capı́tulo 3. Estado da Arte
Este trabalho serviu não apenas para demonstrar a complexidade do jogo Abalone como
também para clarificar os problemas que se colocam na auto-aprendizagem deste jogo sem
qualquer tipo de afinação por parte de um perito humano. Esses problemas são, essencialmente, a necessidade de introduzir exploração eficiente (para que o computador não
aprenda apenas os mesmos tipos de jogos), e a possibilidade de ocorrência de posições
repetidas (que obrigam ao empate e diminuem a capacidade de aprendizagem). Estes
resultados sugerem que, em jogos determinı́sticos que permitam facilmente a ocorrência
de empates e posições repetidas, a abordagem co-evolutiva simples não seja a mais adequada. Uma melhor representação do estado ou a exposição a jogadores competentes
podem, em princı́pio, tornar esta abordagem viável.
3.3.4 Poderá o sucesso ser repetido?
Com a excepção do TD-G AMMON, os métodos de aprendizagem por diferença temporal
não demonstraram eficácia em programas de jogos de alto desempenho, a nı́vel mundial. Para jogos mais complexos, como o Xadrez, os programadores e investigadores
têm expresso grandes dúvidas sobre pesos afinados serem suficientes para exibir os mais
elevados nı́veis de desempenho.
C HINOOK é o actual campeão do mundo de Damas (Schaeffer, 1997). Os pesos da sua
função de avaliação foram afinados manualmente ao longo de 5 anos. Foram extensivamente testados em jogos contra si mesmo e em centenas de jogos contra os melhores
jogadores humanos (incluindo 96 jogos para o Campeonato do Mundo de Damas). Por
isso o seu autor, Jonathan Schaeffer, e outros investigadores colocaram recentemente a
hipótese de ser possı́vel substituir a afinação manual dos pesos da função de avaliação do
C HINOOK por aprendizagem por diferença temporal (Schaeffer et al., 2001). Os dados
experimentais obtidos indicam que a resposta é “sim”.
Além disso, apresentam novas pistas sobre aprendizagem por diferença temporal aplicada
aos programas que jogam, naquele que é o primeiro estudo detalhado que compara uma
função de avaliação treinada manualmente por peritos com uma função aprendida por
diferença temporal num jogo de alto desempenho (Schaeffer et al., 2001).
O problema da exploração (evitar que o programa efectue as mesmas jogadas em todos
os jogos, ver secção 4.5.2) é resolvido da seguinte forma: uma base de dados1 contendo
as 144 aberturas standard do jogo das Damas é utilizada. Durante o treino, os parâmetros
da aprendizagem são os valores escolhidos por Baxter et al. (2000) (ver Secção 3.6.2).
Contudo, a escolha dos melhores parâmetros continua a ser uma questão em aberto. Todos
os pesos são inicializados a zero.
A primeira abordagem consistiu em treinar os pesos jogando contra o C HINOOK para
1
Na gı́ria dos jogos, estas bases de dados contendo jogadas para a abertura designam-se por opening
books.
22
3.4. Complexidade dos Jogos
determinar a eficácia da aprendizagem face ao benefı́cio de um oponente de alto desempenho. O segundo conjunto de experiências envolveu o jogo contra o próprio. Em ambos
os casos, foi possı́vel treinar os pesos procurando 5, 9 e até 13 nı́veis!
Isto constitui uma vantagem muito significativa para a aprendizagem, computacionalmente impossı́vel (em tempo útil) noutros jogos mais complexos.
Os resultados do treino jogando contra si próprio evidenciam que não é necessário um
bom professor para que o programa aprenda um conjunto de pesos de uma função de
avaliação que alcance um desempenho ao nı́vel de um campeão mundial. Isto constitui
uma óptima notı́cia, já que sugere que a afinação manual dos pesos é uma coisa do passado
(pelo menos neste domı́nio especı́fico).
Apesar de a aprendizagem por diferença temporal prometer reduzir o esforço de construção
de um programa que jogue com alto desempenho, não é ainda possı́vel decidir automaticamente quais os atributos da função de avaliação que devem ser escolhidos. Alguns
dos atributos da função de avaliação do C HINOOK foram o resultado de uma extensa
análise humana ao jogo do programa para identificar as suas deficiências. Sempre que um
novo atributo era acrescentado, o processo de afinação manual recomeçava. O método de
diferença temporal torna este processo muito mais fácil. O programador identifica e adiciona o novo conhecimento, e o programa aprende o novo conjunto de pesos (Schaeffer
et al., 2001).
3.4 Complexidade dos Jogos
A pergunta que se impõe nesta altura tem a ver com a complexidade do domı́nio experimental que estamos a considerar. A Tabela 3.2 compara o factor de ramificação e o espaço
de estados de alguns jogos de soma zero e informação completa, para dois jogadores. A
coluna Resultados apresenta a comparação entre os melhores programas para esse jogo e
o campeão humano actual. Nesta tabela, > (e respectivamente >= e <<) significa “mais
forte que” (e respectivamente “mais forte ou igual a” e “claramente mais fraco que”).
A Tabela foi compilada após uma selecção de dados entre os vários artigos considerados. Incluiu-se o valor do Abalone para podermos ter uma ideia da complexidade deste
jogo face aos outros jogos mais conhecidos, pois até ao momento desconhece-se qualquer
tentativa de aplicação de métodos de aprendizagem no Abalone.
Todos os valores constituem aproximações, pois muitas vezes é difı́cil (ou mesmo impossı́vel) determinar com rigor a dimensão das variáveis em causa. O Abalone possui um
factor de ramificação superior ao do Xadrez, Damas e Othello, mas não atinge a complexidade do Go. O factor de ramificação do Gamão (400) provém do factor estocástico
dos dados e não significa que o jogo seja mais complexo que o Abalone ou outros jogos.
De facto, a função de avaliação do gamão é bastante suave, como foi referido. O grande
factor de ramificação é a razão principal pela qual a maioria dos investigadores tentou
23
Capı́tulo 3. Estado da Arte
descobrir outras técnicas de procura para este jogo.
Jogo
Xadrez
Damas
Gamão
Othello
Go 19×19
Abalone
Ramificação
30–40
8–10
±420
±5
± 360
±80
Estados
1050
1017
1020
< 1030
10160
< 361
Resultado
D EEP B LUE >= H
C HINOOK > H
TD-G AMMON <= H
L OGISTELLO > H
Melhor Programa << H
Melhor Programa < H
Referência
(Beal and Smith, 2000)
(Schaeffer et al., 2001)
(Tesauro, 2002)
(Yoshioka et al., 1999)
(Schraudolph et al., 2001)
(Aichholzer et al., 2002)
Tabela 3.2: Complexidade dos Jogos.
Em (Jaap van der Herik et al., 2002) encontramos uma análise exaustiva às caracterı́sticas
dos jogos que mais influenciam a sua complexidade, de uma maneira geral. Em particular,
definem-se duas medidas de complexidade: a complexidade do espaço de estados e a
complexidade da árvore do jogo. A complexidade do espaço de estados é definida como
o número de posições de jogo legais que podem ser atingidas a partir da posição inicial do
jogo. A complexidade da árvore do jogo é definida como o número de folhas na árvore de
procura da solução do jogo da posição inicial. A principal conclusão é a de que uma baixa
complexidade do espaço de estados é mais importante do que uma baixa complexidade
na árvore do jogo, como factor determinante ao resolver jogos.
A Tabela 3.3 apresenta uma previsão para o nı́vel de jogo que será apresentado pelos
programas na Computer Olympiad de 2010 (Jaap van der Herik et al., 2002). A previsão
diz que jogos como o Awari, Othelo e Damas serão solucionados por volta desse ano,
enquanto que os programas de Go 9 × 9 atingirão o nı́vel de campeão mundial.
Solucionado
Awari
Othello
Damas (8×8)
> Campeão
Xadrez
Damas (10×10)
Scrabble
Gamão
Campeão Mundial
Go (9×9)
Xadrez Chinês
Hex
Amazons
Grande Mestre
Bridge
Shogi
Amador
Go (19×19)
Tabela 3.3: Previsão da força dos programas para a Computer Olympiad de 2010 (Jaap van der
Herik et al., 2002).
Nesta recente análise aos jogos (Jaap van der Herik et al., 2002), coloca-se por fim
a questão de o actual estado da arte em aprendizagem automática de jogos admitir a
produção de muitas receitas ad hoc, sendo muitas delas dificilmente entendidas por humanos.
Aponta-se, portanto, para uma direcção de investigação que combine essas regras e receitas em agrupamentos de posições análogas a fim de formular uma regra compreensı́vel.
Em muitas ocasiões, essas regras produzidas pelos computadores corrigiram as estratégias
humanas, tão arduamente elaboradas por peritos. A ideia de que os jogadores humanos
24
3.5. Representações de Estado
podem aprender a partir dos desempenhos das máquinas é inequı́voca. O programa TDG AMMON, que já referimos, fez com que os jogadores de Gamão alterassem as suas
estratégias de jogo, assim como o programa Maven (Sheppard, 2002) fez com que os
jogadores de Scrabble aprendessem e modificassem as suas tácticas.
Poderão os métodos de aprendizagem ser transferidos entre os diferentes jogos? Frequentemente, os programadores fornecem conceitos elementares aos programas, os quais
então geram algumas relações, num processo de aprendizagem. Os métodos podem, com
efeito, ser transferidos entre jogos (Jaap van der Herik et al., 2002).
Contudo, até agora, não houve grande sucesso. Para obter estratégias precisas, é necessário compreender todos os detalhes e subtilezas escondidas no jogo. Isto significa que
compreender os detalhes intrincados do jogo em questão é um pré-requisito para aplicar
com sucesso um dos muitos métodos de aprendizagem automática existentes. Porém, esse
pré-requisito está ele próprio escondido, pelo que se conclui que cada jogo dita as suas
próprias leis. E assim continuará a ser durante muito tempo.
3.5 Representações de Estado
A representação do estado está no coração de qualquer sistema de aprendizagem, uma
vez que fornece a base para tudo o que o sistema poderá eventualmente aprender. Tem
sido, por isso, uma das questões mais investigadas e discutidas na área da aprendizagem
de jogos. Nesta secção aborda-se alguns dos trabalhos mais relevantes neste aspecto.
3.5.1 Explorando caracterı́sticas espaciais e temporais
A exploração de caracterı́sticas espaciais e temporais do tabuleiro de jogo pode conduzir
a uma representação de estado bastante eficiente, permitindo mais facilmente a aquisição
de boas estratégias de jogo.
Leouski (1995) apresenta uma alternativa aos programas de Othello tradicionais baseada em aprendizagem por diferença temporal e numa arquitectura em rede que reflecte a
organização espacial e temporal do jogo.
Nesta abordagem, uma rede neuronal foi treinada, e começando por ser aleatória evoluiu
através de jogos contra si própria, atingindo um nı́vel de jogo intermédio. Leouski observou que o tabuleiro do Othello era invariante no que diz respeito à simetria de reflexão
e rotação. Esta simetria foi incorporada numa rede neuronal de pesos partilhados. Ao
contrário do Gamão e à semelhança do Abalone, o Othello é um jogo determinı́stico, por
isso foi necessário introduzir um factor estocástico para assegurar exploração suficiente.
Neste caso, o computador escolhe uma jogada aleatória com 10% de probabilidade.
Este trabalho é relevante para o Abalearn, porque o jogo do Abalone também apresenta
25
Capı́tulo 3. Estado da Arte
simetrias e também é possı́vel incorporar caracterı́sticas espaciais e temporais do jogo
na estrutura da rede neuronal, sendo de esperar que dessa forma se crie uma função de
avaliação mais precisa, tornando o processo de treino mais veloz e estável.
Schraudolph et al. (2001) propõem uma aproximação baseada em redes neuronais que
reflecte as caracterı́sticas espaciais do jogo do Go (Schraudolph et al., 2001, 1994). Como
se mostrou na secção anterior, o Go possui um elevado factor de ramificação e interacções
espaciais e temporais que tornam a avaliação de posições extremamente difı́cil.
Os autores observam que a invariância da troca de cor implica que uma mudança na cor
de cada peça numa posição Go, trocando o jogador que possui a vez de jogar, representa
uma posição equivalente do ponto de vista do outro jogador. Esta restrição foi construı́da
directamente nas redes usando valores de entrada antisimétricos (+1 para pretas, –1 para
brancas) e funções de activação limitadas a esses valores (tangente hiperbólica), e ainda
alterando a entrada constante (bias) de +1 para –1 quando jogavam as brancas.
As posições Go são invariantes no que diz respeito à reflexão × rotação (eightfold) do
tabuleiro. Schraudolph et al. fizeram a rede obedecer a esta invariância criando grupos
de simetria de oito unidades escondidas, cada uma delas observando a mesma entrada
sob uma diferente rotação/reflexão, através de pesos partilhados. No entanto, relatam que
aparentemente esta arquitectura impedia o decorrer da aprendizagem, e usaram-na apenas
durante a fase de teste.
3.5.2 Representando relações entre as peças
Levinson and Weber (2001) construiram recentemente uma representação interessante
para as relações entre as peças de um tabuleiro de Xadrez. Um tabuleiro de Xadrez é
representado por 64 vizinhanças: uma para cada quadrado. Cada vizinhança possui um
centro e 16 “satélites” que correspondem às peças que estão imediatamente próximas nas
4 diagonais, 2 ranks, 2 filas e 8 movimentos de cavalo em relação ao centro em causa.
Levinson and Weber (2001) treinam uma rede de regressão de duas camadas usando o
método das diferenças temporais. Num nı́vel inferior, os valores (interpretados como estimativas das probabilidades de vitória) dessas vizinhanças são aprendidos e num nı́vel
superior são combinados, usando o seu produto e entropia.
Esta definição de vizinhanças de Xadrez encapsula conhecimento local sobre uma posição
de Xadrez. O uso de redes de regressão permite a aprendizagem de combinações nãolineares dos valores individuais de peças que constituem uma vizinhança para se atingir
um valor único referente a toda a vizinhança. Isto reduz dramaticamente o custo da aprendizagem de valores de padrões uma vez que se explora a redundância entre os diversos
padrões.
Para estimar o desempenho do agente desenvolvido, os autores treinaram-no jogando no
Internet Chess Club (ICC) e também a partir de várias centenas de jogos de Mestres do
26
3.6. Processos de Treino Utilizados
Xadrez, disponı́veis em bases de dados online. Esta última alternativa é a técnica de treino
claramente mais útil, já que o agente pode explorar activamente a consequência das suas
próprias conclusões.
O nı́vel de jogo alcançado em apenas alguns dias de treino no ICC fez com que o agente
com procura de 4 nı́veis alcançasse uma classificação de 1042, o que constitui um importante melhoramento sobre sistemas anteriores como o M ORPH IV (Levinson and Weber,
2000), que necessitou de meses de treino para alcançar o mesmo nı́vel. Este trabalho
ilustra a importância de um bom modelo com caracterı́sticas relevantes para acelerar a
aprendizagem e diminui a importância da procura.
3.6 Processos de Treino Utilizados
Um sistema de aprendizagem adquire o seu conhecimento através de uma fase de treino.
Nesta secção descreve-se algumas abordagens para o treino realizadas noutros trabalhos
e noutros domı́nios relevantes. A questão que se coloca é a de como fornecer ao agente
informação de treino que seja por um lado suficientemente focada para que se garanta a
convergência veloz para uma boa função de avaliação, e por outro lado forneça variação
suficiente para permitir a aprendizagem geral de todas as situações que surgem durante
um jogo.
Em aprendizagem por reforço, este problema é conhecido como o balanceamento eficaz
entre exploration, isto é, exploração de novas opções e exploitation, aproveitamento de
conhecimento já adquirido. Este problema assume especial relevância no caso do autotreino, pois é necessário assegurar que a função de avaliação seja sujeita a variedade
suficiente durante o treino a fim de prevenir que o agente fique “preso” num mı́nimo
local.
Schraudolph et al. (2001) verificaram que a eficiência da aprendizagem do Go usando
métodos de Diferença Temporal pode ser aumentada consideravelmente não apenas através
do uso de arquitecturas de rede com estrutura apropriada, mas também através de um sinal de reforço local, mais rico, e de estratégias de treino que incorporam o jogo contra o
próprio mas sem depender exclusivamente deste (Schraudolph et al., 2001).
Assim, além do sinal de reforço fornecido no fim do jogo, foi acrescentado um sinal r(t)
de ±1 aquando da captura de um prisioneiro durante o jogo. Contudo isto levou a que, de
modo a manter a implementação eficiente, o parâmetro λ se fixasse em 0. A experiência
mostrou que as vantagens de incorporar sinais de reforço locais compensam largamente a
desvantagem de fixar λ em 0.
As possı́veis estratégias de treino (geradores de jogadas legais como gravações de jogos,
programas de Go, redes-TD e jogadas aleatórias) foram também comparadas, e os autores
analisam as suas vantagens e desvantagens. Concluiu-se que, por forma a criar dados
de treino úteis, os dois adversários devem possuir um nı́vel de jogo semelhante, caso
27
Capı́tulo 3. Estado da Arte
contrário o processo de aprendizagem pode ser prejudicado. Foram identificadas então
três formas de assegurar que os oponentes são de igual perı́cia:
• usar o mesmo gerador de jogadas em ambos os oponentes (self-play),
• fazer com que os jogadores troquem de lado várias vezes durante o jogo, ou
• diluir o jogador mais forte, adicionando-lhe uma proporção adequada de jogadas
aleatórias.
Na última opção, a proporção de jogadas aleatórias pode ser alterada com base no resultado dos últimos jogos, fornecendo-nos uma medida de desempenho conveniente. Além
disso, a introdução de jogadas aleatórias garante variedade de jogo suficiente nos casos
em que a exploração pode ser um problema (nomeadamente self–play de jogos determinı́sticos).
Dahl (1999) sugere que uma abordagem hı́brida pode ser recompensadora. Nesta, uma
rede neuronal foi treinada para imitar as formas de jogo locais efectuadas por uma base de
dados de peritos via aprendizagem supervisionada. Uma segunda rede foi treinada para
estimar a segurança de grupos de peças usando TD(λ)-learning, e uma terceira rede foi
treinada também por TD(λ)-learning para estimar o potencial de pontos não ocupados.
Esta estratégia de imitar conceitos humanos teve algum sucesso, e as redes desenvolvidas
conseguiram capturar, até certo ponto, o significado dos conceitos. Contudo, modelação
baseada em conceitos humanos mostra que qualquer conceptualização errada assumida
pelo programador pode ser herdada e exacerbada pelo programa, causando fraquezas sistemáticas. No Abalearn é precisamente esta abordagem que se pretende evitar. A ideia é a
de que um sistema inteligente deve aprender pela sua própria experiência. O único conhecimento embebido no programa deve ser a capacidade de aprendizagem perante situações
novas.
O programa de Thrun, N EURO C HESS, também utilizou o TD(0) para o treino de uma
função de avaliação representada por uma rede neuronal, jogando contra o GNUC HESS
(Thrun, 1995). A sua inovação foi o uso de uma segunda rede neuronal treinada para
prever a posição do tabuleiro dois nı́veis a partir da posição actual (usando 120 000 jogos
de peritos para treino).
A função de avaliação foi então treinada com as suas próprias estimativas de previsões de
posições usando TD(0). O N EURO C HESS aumentou a sua percentagem de vitórias de 3%
para 25% em apenas 2000 jogos de treino.
Epstein (1994) apresenta alguns resultados que evidenciam o facto de que o auto-treino
não funciona bem no caso dos jogos determinı́sticos. O seu sistema de aprendizagem de
jogos Hoyle (Epstein, 2001) foi treinado jogando contra o próprio, contra um oponente
perfeito, contra um oponente aleatório, e contra oponentes falı́veis que efectuavam jogadas aleatórias n% das vezes e efectuavam jogadas perfeitas nas restantes. O seu resultado
28
3.6. Processos de Treino Utilizados
mostrou que nenhum destes métodos de treino foi capaz de produzir resultados óptimos.
Aumentar a percentagem de jogadas aleatórias dos treinadores falı́veis (encorajando a
exploração) usualmente aumentou o número de jogos que estes perdiam sem aumentar o
número de jogos ganhos contra um jogador perito benchmark.
Consequentemente, Epstein propôs lição e prática, uma metodologia de treino na qual
as fases de treino com um jogador perito são intercaladas com fases de auto-treino, e
demonstrou a superioridade deste método.
3.6.1 Ajustando automaticamente os parâmetros do treino
Uma das maiores dificuldades na implementação de sistemas de aprendizagem para jogos
consiste no ajustamento favorável dos parâmetros da aprendizagem. Recentemente, Beal
and Smith (2000, 1999) descreveram um novo sistema que ajusta os parâmetros do treino
automaticamente, nomeadamente a taxa de aprendizagem α e o parâmetro de decaimento
de eligibilidades λ (Beal and Smith, 2000, 1999).
Este sistema não requer conhecimento a priori sobre os valores mais adequados desses
parâmetros para um determinado domı́nio. O ajustamento é feito de acordo com a própria
experiência de aprendizagem, baseando-se no conceito de que a taxa de aprendizagem
deve ser mais elevada quando ocorre uma aprendizagem significativa, e deve ser mais
baixa quando as alterações se devem a ruı́do nos dados.
O método, designado Coerência Temporal, estima a significância dos movimentos nos
pesos de uma rede neuronal através da força dos ajustamentos de reforço em relação ao
ajustamento total. A taxa de aprendizagem é ajustada de acordo com a proporção de
ajustamentos de reforço como uma fracção de todos os ajustamentos (Beal and Smith,
2000).
Este método apresenta a desejada propriedade de a taxa de aprendizagem ser reduzida à
medida que os valores dos pesos se aproximam dos valores óptimos. Permite também
que a taxa aumente caso os ajustamentos aleatórios sejam seguidos de uma tendência ou
inclinação consistente.
São mantidas taxas de aprendizagem separadas para cada peso, por forma a que pesos
que chegaram perto do óptimo não flutuem desnecessariamente, adicionando com essa
flutuação um ruı́do que afecta as previsões.
O uso de uma taxa em separado para cada peso permite que diferentes pesos se tornem
estáveis em ocasiões diferentes no decorrer do processo de treino. Por exemplo, se um
peso a se torna relativamente estável após 100 actualizações, mas um peso b se encontra a
subir consistentemente, então é preferı́vel que a taxa de aprendizagem do peso b seja mais
elevada do que a taxa de aprendizagem do peso a.
Há ainda outra vantagem potencial das taxas de aprendizagem separadas: pesos individuais são independentes quando se adiciona novos pesos ao processo de treino. Caso se
29
Capı́tulo 3. Estado da Arte
adicionem novos termos ou nós ao aproximador existente, taxas de aprendizagem independentes fazem com que os novos pesos se ajustem rapidamente, enquanto que os pesos
já existentes apenas aumentam as suas taxas em função da necessidade estimada.
O algoritmo foi testado em dois domı́nios complexos: aprendizagem do valor das peças
de Xadrez e das peças de Shogi (Xadrez Chinês). Os resultados demonstraram: (a)
eliminação da necessidade de especificar parâmetros; (b) uma aprendizagem mais veloz
e (c) valores finais mais estáveis.
30
3.6. Processos de Treino Utilizados
3.6.2 Combinando a Aprendizagem com Procura Minimax
Uma abordagem interessante foi criada por Baxter et al. (1998), que apresenta um método
de treino chamado TD-Leaf(λ), uma variante do algoritmo TD(λ) que permite que este
seja usado conjuntamente com a procura Minimax. Este algoritmo simplesmente usa
a posição que surge na folha (daı́ o seu nome) da árvore de procura Minimax e usa a
diferença temporal entre essa posição e a posição raı́z para a actualização da função de
avaliação. O algoritmo foi aplicado num programa de Xadrez, K NIGHT C AP, o qual usava
o TD-Leaf(λ) para aprender a função de avaliação jogando contra humanos e computadores através da Internet. Conseguiu subir de uma classificação (ELO) de 1650 para 2100
em apenas 308 jogos, durante 3 dias.
Os ingredientes que contribuı́ram crucialmente para o sucesso do K NIGHT C AP foram a
disponibilidade de parceiros de treino em grande variedade no servidor de Xadrez e a
integração correcta da aprendizagem por TD(λ) nos procedimentos de procura do programa. À medida que o programa aprendia e ia ficando mais forte, eram atraı́dos jogadores humanos cada vez melhores que orientavam o programa para posições variadas numa
ordem crescente de dificuldade. Isto foi determinante para uma boa exploração do espaço
de estados, e seria difı́cil de obter com um treino por jogos contra o próprio.
Yoshioka et al. (1999) aplicam uma rede Gaussiana normalizada que aprende a jogar
Othello através de um esquema simples de aprendizagem que também utiliza a estratégia
minimax: MMRL (Min-max Reinforcement Learning) (Yoshioka et al., 1999).
No Othello, o estado do tabuleiro altera-se significativamente mesmo após uma só jogada.
Logo, a esses estados que se distanciam tanto uns dos outros são atribuı́dos valores de
avaliação semelhantes. Além disso, uma pequena variação no tabuleiro pode causar uma
diferença significativa na função de avaliação.
Estas caracterı́sticas tornam a função de avaliação do Othello mais difı́cil de aproximar do
que em jogos como o Gamão, Xadrez ou Go. É, por isso, um caso de estudo interessante
saber se um aproximador como uma rede neuronal consegue lidar com estas dificuldades.
O MMRL minimiza a diferença entre a avaliação presente e a avaliação prevista com base
na procura minimax, não utilizando o erro da diferença temporal. É por isso um método
independente da polı́tica, muito simples, apesar de a sua convergência não ser garantida.
Leouski (1995) utilizou no jogo Othello uma rede neuronal multi-camada e por isso esta
é comparada (Yoshioka et al., 1999) com a rede Gaussiana normalizada, para demonstrar
que esta última é mais adequada à tarefa que a anterior. Após vários milhares de jogos,
a rede adquire uma boa função de avaliação. O jogador treinado é avaliado jogando
contra um oponente que utiliza uma estratégia heurı́stica, acabando por vencer uma alta
percentagem de jogos.
Neste estudo, a simplicidade do jogo Othello (em termos do tempo de duração de um
jogo) é vantajoso, uma vez que os jogadores podem aprender através de muitos jogos
31
Capı́tulo 3. Estado da Arte
de treino. Nas abordagens de aprendizagem por reforço, o número de jogos de treino é
importante para o sucesso da aprendizagem. No jogo Abalone, que empata facilmente, é
difı́cil obter um sinal de treino forte.
3.7 Funções de Avaliação Lineares vs. Não-Lineares
A maioria dos programas que jogam dependem de algoritmos de procura velozes e requerem por isso mesmo uma função de avaliação que possa ser calculada rapidamente. Uma
combinação linear de atributos que caracterizam a situação do tabuleiro actual é uma escolha óbvia nestes casos. A afinação manual dos pesos de uma função de avaliação linear
é comparativamente simples, mas já um pouco incómoda. Não apenas porque os termos
de avaliação individuais dependem uns dos outros, visto que pequenas variações num dos
pesos podem afectar a correção dos valores dos outros pesos, mas também porque todos
os pesos dependem das caracterı́sticas do programa no qual são utilizados.
Contudo, os avanços nas técnicas de afinação automática tornaram possı́vel o uso de aproximadores de funções não-lineares. Samuel (1967) já tinha sugerido o uso de tabelas de
assinaturas, uma estrutura não-linear, em camadas, de tabelas de consulta. As técnicas
não-lineares possuem a vantagem de aproximarem um leque muito mais amplo de classes
de funções. Contudo, são muito mais lentas no treino e na avaliação. Logo, a questão
fundamental é saber se elas são necessárias para obter bons desempenhos. Em muitos
aspectos, este problema é reminiscente do conhecido problema de balanceamento entre
procura e conhecimento (Berliner, 1984; Junghanns and Schaeffer, 1997).
Lee and Mahajan (1988) interpretaram o grande melhoramento que alcançaram utilizando
aprendizagem Bayesiana em vez de uma função de avaliação linear construı́da manualmente como uma prova de que uma função de avaliação não-linear é melhor que uma
linear. Em particular, mostraram que as matrizes de covariância sobre as quais se baseia a
referida função de avaliação exibem correlações positivas para todos os termos na função,
o que refuta as hipóteses de independência que alguns métodos de treino são obrigados a
fazer.
Tesauro (1995) nota que as suas redes neuronais tendem a aprender conceitos elementares em primeiro lugar, e que estes podem ser expressos com uma função linear. De
facto, no seu trabalho anterior (Tesauro and Sejnowski, 1989), tinha reparado que um perceptrão de uma camada treinado por comparação pode obter um desempenho melhor que
um perceptrão não-linear multi-camada que é treinado por aprendizagem supervisionada.
Contudo, Tesauro (1998) está convencido que uma estrutura não-linear é eventualmente
necessária para atingir um bom desempenho. Tesauro afirma que as redes de Pollack
and Blair (1998), treinadas por um procedimento estocástico de “trepar a colina” são
inferiores às redes treinadas por diferença temporal, visto serem incapazes de capturar
não-linearidade.
32
3.8. Chips desafiando Campeões
Uma forma popular e comparativamente simples de obter não-linearidade, que também
foi originada por Samuel, é usar diferentes funções de avaliação para diferentes fases do
jogo. A primeira versão do TD-G AMMON, por exemplo, ignorava aspectos importantes
como o doubling ou o running game (fase do jogo onde as peças dos dois jogadores já
estão separadas) devido a já existirem algoritmos suficientemente poderosos para estas
partes do jogo.
Inspirado no trabalho de Boyan (1992), que utilizou conhecimento a priori para decompor o espaço de entrada em sub-espaços para os quais treinou redes peritas independentes,
Wiering (1995) descreve a eficiência dos métodos de Diferença Temporal e as vantagens
de usar arquitecturas neuronais modulares para a aprendizagem de funções de avaliação
de jogos. Este princı́pio de “dividir para conquistar” pode ser útil quando as funções apresentam muitas descontinuidades. Os resultados mostram que as arquitecturas modulares
aprendem mais rapidamente, uma vez que as redes independentes podem ser invocadas
para a avaliação de uma determinada posição sem necessidade de invocar constantemente
uma rede de elevada dimensão.
Existem vários problemas práticos que devem ser resolvidos ao utilizar estas abordagens.
Um deles é o chamado blemish effect (Berliner, 1984) que se refere ao problema de ter de
assegurar que os valores retornados pelas diferentes funções de avaliação sejam consistentes.
3.8 Chips desafiando Campeões
A construção de programas que jogam com alto desempenho tem sido um dos maiores
triunfos da IA. Isto deve-se em parte aos sucessos alcançados em jogos como o Gamão,
Xadrez, Damas, Othello e Scrabble. Contudo, o sucesso também se fica a dever aos
exemplos que foram dados à comunidade de investigadores. Estes incluem lidar com problemas difı́ceis (em vez dos domı́nios triviais frequentemente observados na investigação
em IA) e a ênfase nos resultados do sistema sem olhar para os métodos utilizados.
Entre esses métodos, a procura exaustiva tem sido das mais bem sucedidas técnicas da IA,
culminando com o sucesso do D EEP B LUE (Hsu, 1999) em 1997. Os computadores são
óptimos a procurar, considerando milhões de possibilidades por segundo, ao passo que os
humanos não procuram rapidamente nem de forma óptima.
Contudo, os humanos são muito bons a descobrir, generalizar e utilizar conhecimento,
ao passo que após 50 anos de investigação ainda ninguém compreende como representar
ou como manipular conhecimento eficientemente nos computadores. Aproveitar a grande
capacidade de memória dos computadores também tem sido uma técnica utilizada com
sucesso.
O programa de damas C HINOOK (Schaeffer, 1997) armazena o resultado teórico do jogo
(vitória, derrota ou empate) para aproximadamente 444×1011 posições. Este conheci33
Capı́tulo 3. Estado da Arte
mento permite que o programa jogue de forma perfeita sempre que encontre uma posição
que já esteja armazenada.
Estas duas técnicas, apesar de bem sucedidas, afastam-se da forma de simular o comportamento humano inteligente que constitui, em última análise, o grande ideal da IA.
Tem havido por isso uma crescente inclinação para a questão de como adquirir conhecimento de estratégias de jogo de uma forma autónoma, através da própria experiência. A
aquisição de conhecimento é feita, na Aprendizagem por Reforço, sem recorrer a procuras
extensas, ou a bases de dados que assumem o papel de “professor”, possuindo o potencial
de fornecer novos significados aos termos “ensino” e “treino”, mais próximos dos seus
significados na aprendizagem humana e animal.
34
Capı́tulo 4
Aprendizagem por Reforço
“The fact that I bet on myself and didn’t lose is a pretty deep reward.”
Jerry Seinfeld
Desenvolver técnicas de aprendizagem por reforço para a aquisição automática de estratégias de jogo constitui o objectivo desta investigação. Este capı́tulo apresenta o paradigma da aprendizagem por reforço (AR) e discute as várias abordagens existentes.
Exemplificam-se algumas aplicações e explicam-se os conceitos básicos e os algoritmos
mais conhecidos para resolver o problema da AR, recorrendo a experiências ilustrativas.
4.1 Modelo Conceptual
A ideia que está na base da aprendizagem por reforço é aquela que nos ocorre imediatamente quando pensamos na natureza da aprendizagem: aprende-se interagindo com o
ambiente (Sutton and Barto, 1998).
A definição de aprendizagem por reforço não passa pela caracterização de um algoritmo
de aprendizagem, mas sim de um problema de aprendizagem. Vários algoritmos podem
depois ser implementados de modo a resolver o problema.
No modelo da aprendizagem por reforço, o agente interage com o ambiente (Sutton and
Barto, 1998). Esta interacção consiste na percepção do ambiente e na selecção de uma
acção para executar nesse ambiente. A acção altera o ambiente de alguma forma e esta
alteração é comunicada ao agente através de um sinal de reforço. A Figura 4.1 ilustra a
interface agente-ambiente em questão.
Um estado caracteriza a situação do ambiente, sendo especificado por um conjunto de
variáveis que o descrevem. Os sistemas de aprendizagem por reforço aprendem um mapeamento de situações a acções através de interacções com um ambiente dinâmico. A
35
Capı́tulo 4. Aprendizagem por Reforço
Agente
estado
st
reforço
rt
rt+1
acção
at
Ambiente
st+1
Figura 4.1: A interacção agente-ambiente em aprendizagem por reforço.
execução de uma acção num determinado estado dá origem a um reforço, rt , recebido
pelo agente, na forma de um valor numérico. O agente aprende a executar acções que
maximizam a soma dos reforços recebidos, desde o estado inicial até ao estado final. A
escolha de uma função de reforço (ou recompensa) que transpareça, de uma forma apropriada, os objectivos do agente é fundamental.
O problema central da aprendizagem por reforço é, portanto, a escolha de acções. A
polı́tica define o comportamento do agente, determinando que acção deve ser executada
em cada estado. Quase todos os algoritmos que implementam este tipo de aprendizagem
se baseiam em estimar funções de avaliação (Sutton and Barto, 1998) – funções que determinam quão bom é um estado – função estado-valor V (s) – ou quão bom é executar
uma determinada acção num estado – função acção-valor Q(s, a).
4.2 Exemplos e Aplicações
Uma boa forma de compreender a aprendizagem por reforço é considerar alguns exemplos
e possı́veis aplicações que guiaram o desenvolvimento nesta área.
• Um robot móvel decide se há de entrar numa nova sala à procura de mais lixo para
recolher ou se, por outro lado, seria melhor tentar encontrar novamente o caminho
de volta à sua estação de recarga de bateria. O robot toma a sua decisão baseandose na sua experiência anterior (quão fácil e rápido tem sido encontrar a estação de
recarga no passado).
• Um controlador adaptativo ajusta, em tempo-real, os parâmetros de uma operação
numa refinaria de petróleo. O controlador optimiza a relação custo/qualidade tendo
como base uma especificação de custos marginais, sem se deixar ficar pelos valores
inicialmente sugeridos pelos engenheiros.
36
4.3. Conceitos Básicos
• Uma pequena gazela luta para tentar manter-se em pé, logo após ter nascido. Meiahora depois, consegue correr a velocidades de cerca de 20 milhas por hora.
Estes exemplos partilham caracterı́sticas básicas: todos eles envolvem interacção entre
um agente que toma decisões activamente e um ambiente no qual o agente procura atingir
um objectivo, apesar da incerteza presente.
A gama de aplicações bem sucedidas da AR é vasta e diversa, algumas delas de substancial significado económico. Vão desde aprender a jogar Gamão (Tesauro, 1995) até
problemas do mundo real, como por exemplo diagnóstico médico automático (Stensmo
and Sejnowski, 1995), controlo industrial adaptativo (Connell and Mahadevan, 1993), escalonamento de elevadores (Crites and Barto, 1996) e alocação dinâmica de canais em
sistemas de telefones celulares (Singh and Berteskas, 1997).
4.3 Conceitos Básicos
Como se viu na secção 4.1, no modelo conceptual da Aprendizagem por Reforço (AR),
o agente efectua uma observação do ambiente, ot , e selecciona uma acção at . Executa
então essa acção, havendo uma transição para um novo estado, st+1 , com a sua respectiva
observação, ot , e uma recompensa, rt+1 .
O objectivo é aprender uma polı́tica, π : O → A, que mapeia observações em acções.
Se assumirmos que o mundo é totalmente observável, isto é, ot = st , equivale a termos a
polı́tica π : S → A, mapeando estados em acções. No mundo real isto acontece poucas
vezes, sendo necessário lidar com o estado escondido (Tan, 1993).
Ao aprender polı́ticas de controlo, é necessário poder avaliá-las umas em relação às outras. Em Aprendizagem por Reforço, a métrica de avaliação é função das recompensas
recebidas pelo agente, chamada retorno. No caso mais simples, o retorno Rt é definido
como sendo a soma de todas as recompensas obtidas durante todo o tempo de vida1 do
agente,
Rt = rt+1 + rt+2 + ... + rT
(4.1)
onde T é o passo de tempo final. Geralmente a fórmula do retorno é escrita sob a forma
de somatório:
T
X
Rt =
rt+k+1
(4.2)
k=0
No caso de o tempo de vida ser infinito, usa-se um factor de desconto, 0 ≤ γ ≤ 1, para
dar mais peso às recompensas que surgem mais cedo (e que possuem, portanto, um menor
1
Denominado na literatura por horizonte.
37
Capı́tulo 4. Aprendizagem por Reforço
valor para t2 ) :
2
Rt = rt+1 + γrt+2 + γ rt+3 + ... =
∞
X
γ k rt+k+1
(4.3)
k=0
Os problemas em Aprendizagem por Reforço são normalmente definidos como processos
de decisão de Markov (designados por MDPs). Num MDP existe um conjunto finito de
estados, S, um conjunto finito de acções, A, e o tempo é discreto. A função de Recompensa (R : S × A → R) retorna uma medida imediata da qualidade de uma acção. O
estado seguinte, st+1 , depende da função de transição T : S × A → Π(S) que retorna
uma distribuição de probabilidade sobre os possı́veis estados seguintes. Uma importante
propriedade dos MDPs é que estas transições dependem apenas do último estado e acção.
Esta propriedade designa-se por Propriedade de Markov.
O problema consiste então em gerar uma polı́tica, π : S → A, baseada nas recompensas
imediatas que maximize a recompensa esperada a longo-prazo. Se T e R forem conhecidas, pode-se definir a função de avaliação óptima, V ∗ , sobre os estados:
V ∗ (s) = max[R(s, a) + γ
a
X
T (s, a, s0 )V ∗ (s0 )].
(4.4)
s0
Esta função atribui um valor a cada estado, valor esse que é a melhor recompensa imediata
que se pode obter para qualquer acção desse estado adicionado ao valor óptimo de cada
um dos possı́veis estados resultantes, pesados pelas suas probabilidades. Se esta função
for conhecida pode-se definir a polı́tica óptima, π ∗ , simplesmente seleccionando a acção
a que maximiza o valor:
π ∗ (s) = arg max[R(s, a) + γ
a
X
T (s, a, s0 )V ∗ (s0 )].
(4.5)
s0
Existem métodos para computar V ∗ (baseados em Programação Dinâmica), que levam a
um procedimento simples para aprender a função de avaliação óptima, e logo, a polı́tica
óptima. Primeiro aprende-se (se não forem dados) os modelos do ambiente, que correspondem às funções T e R. Isto permite calcular a função valor óptima e, a partir desta, a
polı́tica óptima. Contudo, aprender bons modelos requer uma grande quantidade de dados
e pode ser difı́cil num mundo em potencial mudança.
Em vez de aprender T e R, é possı́vel aprender incrementalmente a função valor óptima
de forma directa.
2
Se fixarmos γ em zero obtemos a polı́tica one-step greedy, em que a melhor acção é aquela que fornece
a melhor recompensa imediata. Valores maiores que zero reflectem a preocupação dada às acções que
acontecem no futuro. Neste trabalho utiliza-se como medida de optimalidade de uma polı́tica a soma de
recompensas descontada com horizonte infinito, visto que clarifica melhor os aspectos teóricos.
38
4.4. Ilustração dos Algoritmos
V1
V2
V3
V999
V1000
0.0 0.0 0.0 0.0
-1.0 -1.0 -1.0 -1.0
-2.0 -2.0 -2.0 -2.0
-59 -57 -54 -51
-59 -57 -54 -51
0.0 0.0 0.0 0.0
-1.0 -1.0 -1.0 -1.0
-2.0 -2.0 -2.0 -2.0
-57 -54 -49 -45
-57 -54 -49 -45
0.0 0.0 0.0 0.0
-1.0 -1.0 -1.0 -1.0
-2.0 -2.0 -2.0 -1.8
-54 -49 -40 -30
-54 -49 -40 -30
0.0 0.0 0.0 0.0
-1.0 -1.0 -1.0 0.0
-2.0 -2.0 -1.8 0.0
-51 -45 -30 0.0
-51 -45 -30 0.0
Figura 4.2: Policy Evaluation para estimar V (s).
4.4 Ilustração dos Algoritmos
Esta secção descreve alguns dos principais algoritmos para resolver o problema da Aprendizagem por Reforço, descrito anteriormente. Foi importante utilizar um domı́nio experimental simples e conhecido (neste caso o Grid-World), para poder validar os algoritmos
e obter uma boa compreensão destes.
4.4.1 Programação Dinâmica
Os métodos baseados em Programação Dinâmica requerem conhecimento da distribuição
de probabilidade completa para todas as possı́veis transições (Sutton and Barto, 1998).
Portanto, os recursos necessários aumentam exponencialmente consoante a dimensão do
problema. O algoritmo de Avaliação de Polı́tica (Policy Evaluation) estima iterativamente
a função de avaliação para uma dada polı́tica π, de acordo com:
X
X
Vk+1 (s) ←
π(s, a)
T (s, a, s0 )[R(s, a, s0 ) + γVk (t + 1)].
(4.6)
a
s0
Prova-se que a sequência Vk converge para V π quando k → ∞ se γ < 1. Uma vez
avaliada uma polı́tica, esta pode ser melhorada (Policy Improvement). Uma nova polı́tica,
π 0 , é definida de tal forma que π 0 (st ) = a onde maxa Qπ (st , a) e ∀s 6= st , π(s) = π 0 (s).
Portanto temos:
π
V (s) ≤ Qπ (s, a), s = st
(4.7)
V π (s) = Qπ (s, a), c.c.
π 0 melhora a polı́tica π. Usando Policy Evaluation e Policy Improvement alternativamente
obtemos uma sequência de polı́ticas que convergem para a polı́tica óptima. Este constitui
o algoritmo de Policy Iteration, porque iterativamente vamos melhorando a polı́tica.
O algoritmo de Iteração de Valor (Value Iteration) constitui um caso de Policy Iteration
em que só é feito um varrimento (backup) a cada estado. Pode ser escrito da seguinte
forma:
Vk+1(s) = max E{rt+1 + γVk (st+1 )|st = s, at = a},
(4.8)
a
39
Capı́tulo 4. Aprendizagem por Reforço
para todo s ∈ S. Para um V0 arbitrário, pode-se provar que a sequência {Vk } converge
para V ∗ , sob as mesmas condições que garantem a existência de V ∗ .
Para ilustrar e testar este algoritmo, vamos recorrer a um domı́nio experimental simples
e conhecido (Sutton and Barto, 1998), o Grid-World, ou Mundo em Grelha. Vamos primeiro supor que um robot vive num mundo em forma de grelha, com 20×20 células,
representado na Figura 4.4. Em cada célula, o robot dispõe de quatro acções possı́veis,
A={norte, sul, este, oeste}, as quais causam deterministicamente o robot moverse uma célula na respectiva direcção. Acções que fazem o robot chocar contra a parede
deixam a sua localização inalterada, mas também fornecem ao robot um reforço de –10.
Todas as restantes acções fornecem um reforço de –1. O estado terminal começa por ser
o estado correspondente à localização (0, 11) na grelha. Os estados não terminais são
S={(0,0),(0,1),...,(19,19)}\(0,11). Como este problema pode ser reduzido a um MDP, é
possı́vel aplicar os métodos de Programação Dinâmica.
A Figura 4.3 mostra a representação construı́da pelo agente usando 100 iterações da
Equação 4.8, para que a representação seja suficientemente expressiva (a convergência
dá-se muito mais cedo). Para cada célula apresenta-se o valor dado ao estado correspondente, através de uma escala de cinzentos em que os tons mais escuros são os valores de
V (s) mais altos, conforme a legenda. Como se pode verificar, à medida que se aproxima
do objectivo, o robot atribui um maior valor ao estado.
Goal
V(s)
Tunnel
0
-10
-20
-30
-40
Start
80
0
60
20
40
40
60
80
20
0
Figura 4.3: Value Iteration aplicada ao Mundo em Grelha 20×20 Simples.
4.4.2 Q-Learning
O algoritmo Q-Learning (Watkins, 1989) é dos mais centrais na área da Aprendizagem
por Reforço. Na sua forma mais simples, one-step Q-Learning, aproxima directamente
40
4.4. Ilustração dos Algoritmos
uma função de valor estado-acção óptima,
X
Q∗ (s, a) = R(s, a) + γ
T (s, a, s0) max
Q∗ (s, a0 )].
0
a
s0
(4.9)
independentemente da polı́tica seguida3. Os valores-Q são aproximados incrementalmente online, aprendendo-se eficazmente a polı́tica e a função-valor simultaneamente.
Começando com valores aleatórios, a aproximação é actualizada de acordo com
Q(st , at ) = Q(st , at ) + α[rt+1 + γ max
Q(st+1 , a0 ) − Q(st , at )]
0
a
(4.10)
No limite foi demonstrado (Watkins, 1989) que esta aproximação a Q(s, a) converge para
Q∗ (s, a), obtendo-se a polı́tica óptima, sob razoáveis condições técnicas (tais como um
decaimento apropriado para a taxa de aprendizagem α).
Para ilustrar o Q-Learning, vamos supor agora que o mundo onde o robot vive está cheio
de lagos. Existem 43 lagos colocados aleatoriamente no mapa, como na Figura 4.4. Sempre que o robot passa por um deles, recebe um reforço de -15, pois é necessário um esforço
maior para atravessar um lago do que ir normalmente por terra. Se não passar pelos lagos,
recebe um reforço de –5 até atingir o objectivo.
Vamos supor também que existe uma célula escondida, surpresa, mais perto do estado
inicial do que do objectivo, a qual constitui um túnel directo para o estado objectivo. Se
o robot utilizar esse túnel, recebe um reforço de 0, pois não lhe custa esforço nenhum,
e chega ao estado objectivo directamente. O estado inicial é o (1,1), o estado final é o
(18,18) e a posição do túnel é (1,18), como se vê na legenda da Figura 4.4.
Os resultados do algoritmo Q-Learning, após 100 episódios encontram-se ilustrados na
Figura 4.5. Os tons de cinzento vão escurecendo uniformemente à volta do estado final e
também à volta do túnel, sendo apenas manchados pelas células claras, que representam o
baixo valor dado aos lagos, pois o robot aprende que é preferı́vel contorná-los (recebendo
–5 de reforço) do que atravessá-los (recebendo –15).
4.4.3 Sarsa
Sarsa (Rummery, 1995) é semelhante ao Q-Learning na medida em que tenta aprender a função valor estado-acção, Q∗ (s, a). A principal diferença entre estes dois algoritmos, contudo, é a função de actualização incremental. Sarsa utiliza um quı́ntuplo,
(st , at , rt+1 , st+1 , at+1 ), em vez do quádruplo usado pelo Q-Learning. O elemento adicional, at+1 , é a acção tomada no estado resultante, st+1 , de acordo com a polı́tica de controlo
usada. A regra de actualização transforma-se em
Q(st , at ) = Q(st , at ) + α[rt+1 + γQ(st+1 , at+1 ) − Q(st , at )].
3
Devido a este facto é considerado um método off-policy.
41
(4.11)
Capı́tulo 4. Aprendizagem por Reforço
Figura 4.4: Mundo em Grelha 20×20 com Lagos e Túnel.
Goal
V(s)
Tunnel
0
-10
-20
-30
-40
Start
10
0
10
0
Figura 4.5: Q-Learning aplicado ao Mundo em Grelha 20×20 com Lagos e Túnel.
42
4.4. Ilustração dos Algoritmos
1400
Q−Learning
Duração Média do Episódio
1200
1000
800
600
400
200
0
0
50
100
150
200
250
300
Episódios
Figura 4.6: Performance do Q-Learning aplicado ao Mundo em Grelha 20×20 com Lagos e Túnel.
Sarsa aprende o valor para uma polı́tica fixa, sendo considerado, por isso, um método
on-policy).
4.4.4 TD(λ)
O algoritmo de Sutton, TD(0), descrito em (Sutton and Barto, 1998), aprende iterativamente uma função de valor para os estados, V (s), baseada nas transições e recompensas,
(st , rt+1 , st+1 ). Começando com um valor aleatório para cada estado, actualiza iterativamente a aproximação à função de valor de acordo com a regra:
V (st ) ← (1 − α)V (st ) + α(rt+1 + γV (st+1 )).
(4.12)
Existem dois parâmetros: a taxa de aprendizagem, α, e o factor de desconto, γ. A taxa de
aprendizagem controla o quanto se modifica a estimativa actual de V (s) baseando-se em
cada experiência nova. A regra também pode ser re-escrita na forma seguinte, que mostra
melhor a sua ligação com os algoritmos descritos acima:
V (st ) ← V (st ) + α(rt+1 + γV (st+1 ) − V (st )).
(4.13)
Uma versão mais geral do algoritmo TD(0) é o TD(λ). Neste, a regra acima descrita
modifica-se para
V (st ) ← V (st ) + α(rt+1 + γV (st+1 ) − V (st ))et (st ).
43
(4.14)
Capı́tulo 4. Aprendizagem por Reforço
e é aplicada a todos os estados, em vez de ser apenas aplicada ao estado visitado mais
recentemente. Cada estado é actualizado de acordo com a sua eligibilidade, et (st ). Todas
as eligibilidades começam por ser zero e são actualizadas em cada passo de acordo com
et (s) =
γλet−1 (s)
se
γλet−1 (s) + 1 se
s 6= st
s = st
(4.15)
onde γ é o factor de desconto e λ é o factor de decaimento da eligibilidade. Isto significa
que as eligibilidades decaem com o tempo, a menos que sejam visitadas (s = st ), caso
em que são incrementadas por 1.
TD aprende a função de valor para uma polı́tica fixa. Pode ser combinado com um aprendiz de polı́tica para se obter sistemas como o actor-critic ou o adaptive heuristic critic
(Barto et al., 1983). Assim alterna-se entre aprender a função de valor para a polı́tica
actual, e modificar a polı́tica com base na função de valor aprendida.
4.5 A Escolha das Acções
O aspecto mais importante que distingue a AR dos outros tipos de Aprendizagem Automática, é o facto de utilizar informação de treino que avalia as acções, em vez de ensinar, fornecendo acções correctas. Nesta secção, estuda-se este aspecto avaliativo da AR
num problema simplificado, que não envolve aprender em mais do que uma situação, o
problema do N-Armed Bandit. Descreve-se a experiência, os resultados e algumas conclusões.
4.5.1 O Problema do N-Armed Bandit
O problema do N-Armed Bandit tem este nome devido à analogia com as slot-machines
ou “one-armed bandit”, excepto no facto de possuir n alavancas, em vez de apenas uma.
Cada selecção da acção é como uma jogada numa das alavancas e as recompensas são o
resultado de cada jogada (na busca pelo jackpot). Através de jogadas repetitivas, tenta-se
maximizar as vitórias concentrando as jogadas nas “melhores” alavancas.
Na versão desenvolvida nesta experiência, considerou-se que cada acção possui uma recompensa (reforço) esperada (ou média) dada ao agente se este seleccionar a acção respectiva. Essa recompensa designa-se o valor da acção. Se o agente soubesse qual o
valor de cada acção seria trivial resolver o problema, seleccionando sempre a acção com
o maior valor. Assume-se, portanto, que o agente não conhece, com certeza, o valor das
acções, apesar de possuir estimativas.
44
4.5. A Escolha das Acções
4.5.2 Métodos Acção-Valor
Começou-se por experimentar alguns métodos simples para estimar os valores das acções
e usar os valores estimados para tomar decisões relativas à escolha das acções. Denotase por Q∗ (a) o real (actual) valor da acção a, e o valor estimado da acção a na n-ésima
iteração por Qt (a). Uma forma natural de estimar Qt (a) é efectuar a média dos reforços
recebidos na altura em que a é seleccionada. Por outras palavras, se na iteração t a acção
a foi escolhida ka vezes anteriormente a t, obtendo os reforços r1 , r2 , ... , rka , então
estima-se que o valor seja:
Qt (a) =
r1 + r2 + ... + rka
.
ka
(4.16)
A regra mais simples para a selecção de uma acção consiste em seleccionar aquela que
possui um maior valor de qualidade Q. Este método toma sempre partido do conhecimento actual para maximizar o reforço imediato. Contudo, não considera o facto de
que podem existir acções ainda não experimentadas, que conduzirão ao resultado melhor.
Além disso, em ambientes dinâmicos e portanto não-determinı́sticos, acções que obtiveram resultados menos bons no passado podem melhorar a sua prestação no presente.
De facto, para obter um reforço continuado e de elevado valor, o agente deve preferir
acções que tentou no passado e que descobriu serem eficientes na produção de reforços
(Sutton and Barto, 1998). Mas para as descobrir, ele tem de tentar acções que nunca
seleccionou antes. Este dilema leva à necessidade de um compromisso entre:
• Exploitation: tirar partido das acções que são consideradas boas;
• Exploration: explorar acções desconhecidas ou menos boas.
Para satisfazer este compromisso, duas polı́ticas para a escolha de acções são consideradas:
• ε-greedy: este método selecciona uniformemente, com probabilidade ε, uma acção
aleatória, e escolhe a melhor com probabilidade 1 - ε. De entre todas as acções
não-óptimas, a probabilidade de escolher acções boas e más é igual.
• Softmax: este método utiliza um grau de exploração τ (temperatura) para escolher
de entre todas as acções possı́veis, considerando a sua classificação (desta forma a
acção melhor tem maior probabilidade de ser escolhida). Quanto mais elevada for a
temperatura, mais equiprovável é a escolha das diversas acções (menos importância
têm as suas classificações). No limite τ → 0, é sempre escolhida a acção melhor.
Assim, este método escolhe a acção a no instante t com a probabilidade dada por:
eQt (a)/τ
P r(a|s) = Pn Qt (b)/τ
b=1 e
45
(4.17)
Capı́tulo 4. Aprendizagem por Reforço
4.5.3 Descrição da experiência
Com o objectivo de estudar a eficiência de um destes métodos, o Softmax, e o impacto que
alguns parâmetros possuem neste problema, fez-se variar o valor do parâmetro temperatura t e o valor de n. Note-se que o valor da temperatura está directamente relacionado
com a importância dada ao valor de uma determinada acção, Q∗ (a), aquando da escolha
das diversas acções.
O método usou a média simples dada por (4.16) para estimar os valores Q das acções.
Contudo o algoritmo usado, por motivos computacionais e de memória, usou uma versão
alterada da equação (4.16): uma implementação incrementacional que requer apenas uma
computação constante para processar cada recompensa adicional:
Qk+1 = Qk +
1
[rk+1 − Qk ]
k+1
(4.18)
O conjunto de testes desta experiência consiste em 2000 tarefas atribuı́das a 2000 agentes, geradas aleatoriamente para um dado valor de n (sendo n o número de acções disponı́veis).
Para cada acção a, as recompensas foram seleccionadas a partir de uma distribuição Normal com média 0 e variância 1. As 2000 tarefas foram geradas re-seleccionando Q∗ (a)
2000 vezes, cada uma de acordo com a distribuição Normal de média 0 e variância 1.
Fez-se a média, para cada instante de tempo, dos 2000 agentes e os resultados foram
apresentados em gráficos que mostram o desempenho dos agentes.
4.5.4 Resultados
Nesta secção apresenta-se e descreve-se, sumariamente, os resultados obtidos para a experiência descrita anteriormente. Analisou-se o impacto da variação do parâmetro Temperatura τ e a variação do número de acções n disponı́veis ao agente.
Variação da Temperatura. As Figuras 4.7 e 4.8 sumarizam os resultados obtidos com n
= 10. Os valores de τ testados foram 0.01, 0.1, 0.4 e 1.
A Figura 4.7 mostra a média das recompensas obtidas por 2000 agentes. Observa-se
que estes aprendem a maximizar as recompensas com a experiência conseguindo atingir
muitas vezes (com τ = 0.4) o valor máximo de recompensa previsto para este caso de
teste, que anda à volta de 1.5.
Neste primeiro gráfico nota-se que valores de temperatura baixos apresentam uma performance significativamente melhor. Isto deve-se ao facto de que, quando τ é elevado,
a escolha das acções torna-se praticamente equiprovável. Ora com n = 10 e uma temperatura alta, o agente explora muito (consegue portanto estimar bem todas as acções)
mas explora, neste caso, demais: não consegue aproveitar as recompensas das acções
46
4.5. A Escolha das Acções
Percentagem de Acções Óptimas
0.7
0.6
0.5
0.4
0.3
0.2
T=0.01
T=0.1
T=0.4
T=1
0.1
0
0
50
100 150 200 250 300 350 400 450 500
Jogadas
Figura 4.7: Variação da Temperatura (percentagem de acções óptimas escolhidas). Os dados
representam a média de 2000 agentes.
boas. Este valor de temperatura poderia adequar-se melhor a uma tarefa onde escolher
a pior acção fosse muito mau, o que não é bem o caso. Ou a tarefas onde o ruı́do nas
recompensas fosse maior.
Com valores de τ mais baixos, surge uma maior diferença na probabilidade de selecção
das acções que diferem nas suas estimativas de Q. Ou seja, entra-se mais em conta com
Qt (a) e o agente consegue atingir recompensas altas mais vezes. Note-se que no limite,
quando τ → 0, o método resume-se à estratégia greedy de selecção de acções.
No segundo gráfico, Figura 4.8, mostra-se a percentagem de acções óptimas escolhidas
pelos agentes. Verifica-se foi mais fácil ao agente com temperatura baixa escolher a
melhor acção do que ao agente com temperatura alta, o qual revelou uma performance
muito baixa.
Todos os agentes revelaram uma performance pior que a que se obteria com o método
ε-greedy, analisado em Sutton and Barto (1998). Isto é porque o método Softmax é muito
“prudente” ao escolher a acção: pode não escolher a óptima, mas muitas vezes (quando
explora) escolhe sempre a acção próxima da óptima e raramente escolhe a pior de todas.
Variação do Número de Acções. Fixando a temperatura num valor razoável e bastante
utilizado, por exemplo 0.4, fez-se variar o número de acções disponı́veis ao agente de
forma a analisar o impacto dado pelo aumento destas. Será intuitivo esperar que quanto
maior for o número de acções disponı́veis para escolha, maior será o tempo de aprendizagem, mas de qualquer forma não deixa de ser interessante o resultado obtido.
Na Figura 4.9, mostra-se a recompensa média obtida. Com maior número de acções à
47
Capı́tulo 4. Aprendizagem por Reforço
1.4
Recompensa Média
1.2
1
0.8
0.6
0.4
0.2
T=0.01
T=0.1
T=0.4
T=1
0
−0.2
0
50
100 150 200 250 300 350 400 450 500
Jogadas
Figura 4.8: Variação da Temperatura (recompensa média obtida). Os dados representam a média
de 2000 agentes.
escolha, é ligeiramente mais difı́cil de aprender no inı́cio da experiência, mas como há
maior probabilidade de o valor real de uma das acções, Q∗ (a), ser mais alto – pois Q∗ (a)
é retirado de uma distribuição Normal com média 0 e variância 1 – o agente acaba por
descobrir as acções melhores e obter recompensas mais elevadas.
Se só houver duas acções, não há grande probabilidade de Q∗ (a) ser alto (mesmo com
variância 1) e apesar de o agente aprender a maximizar a recompensa, está sempre limitado a uma acção cujo valor máximo de recompensa não se afasta muito da média zero.
Na Figura 4.10, mostra-se a percentagem de acções óptimas escolhidas pelos 2000 agentes. Aqui, a situação é simétrica à anterior. Como seria de esperar, com n = 2, é muito
mais fácil e muito mais provável ao agente escolher a acção óptima - e isto é independente
do método usado na selecção de acções. À medida que n sobe, é cada vez mais difı́cil ao
agente seleccionar a acção óptima, pois as variâncias presentes nas várias recompensas
obtidas causam um aumento do ruı́do directamente proporcional ao número de acções
existentes.
4.5.5 Conclusões
Apesar de o método ε-greedy ser um meio popular e eficaz de balancear exploitation e
exploration na aprendizagem por reforço, uma desvantagem deste método é que, quando
explora, escolhe de igual forma uma de entre todas as acções. Isto significa que tanto
pode escolher a pior acção de todas como pode escolher a acção quase óptima. Este facto
48
4.5. A Escolha das Acções
Percentagem de Acções Óptimas
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
N=100
N=2
N=5
0.1
0
0
50
100 150 200 250 300 350 400 450 500
Jogadas
Figura 4.9: Variação do número de acções (percentagem de acções óptimas escolhidas). Os dados
representam a média de 2000 agentes.
pode revelar-se determinante para o insucesso do agente em tarefas onde as piores acções
são muito más.
O método Softmax, dando à acção greedy a maior probabilidade de escolha, mas pesando
todas as outras acções de acordo com as respectivas estimativas de Q, consegue evitar a
escolha dessa acção pior, o que é bom consoante a tarefa.
Neste caso, o método Softmax revelou uma pior performance que o ε-greedy mas se a
diferença entre as acções fosse mais significativa, o custo de ter escolhido a pior acção
seria maior. Logo, o Softmax teria um desempenho melhor.
Conclui-se portanto que não é claro qual dos dois métodos é efectivamente melhor, pois
isso depende da tarefa e dos factores humanos: ambos os métodos possuem um parâmetro
que deve ser definido pelo programador. É mais fácil definir o parâmetro ε pois definir τ
requer conhecimento dos valores das acções esperados, assim como das potências de e.
Requer portanto um maior conhecimento sobre o domı́nio de acção do agente, o que nem
sempre é fácil ou até mesmo possı́vel.
4.5.6 Exploração Dirigida
Até agora temos falado de técnicas de exploração não-dirigida para resolver o problema
da exploração do espaço de estados. Estas técnicas, como as referidas anteriormente,
exploram o ambiente com base na aleatoriedade (Thrun, 1992). A Exploração Dirigida
difere desta na medida em que utiliza conhecimento especı́fico relativamente à exploração
49
Capı́tulo 4. Aprendizagem por Reforço
2
1.8
Recompensa Média
1.6
1.4
1.2
1
0.8
0.6
0.4
N=100
N=2
N=5
0.2
0
0
50
100 150 200 250 300 350 400 450 500
Jogadas
Figura 4.10: Variação do número de acções (recompensa média obtida). Os dados representam a
média de 2000 agentes.
para conduzi-la.
As técnicas de exploração dirigida são, por natureza, heurı́sticas: a selecção de acções
e/ou estados que foram seleccionados menos frequentemente, menos recentemente, os
que supostamente apresentam um alto erro de predição, ou uma combinação de todos
estes factores.
Exploração baseada em contabilidade (Thrun, 1992) baseia-se num mapa adaptativo c(·)
que conta as ocorrências de cada estado s. Um agente pode seguir a regra “visita o estado
vizinho menos visitado” seleccionando sempre a acção que maximiza
E(a) =
c(st )
c(st )
=
E[c(st+1 )|st , a]
c(st+1 , a)
(4.19)
Onde st denota o estado actual, E[·|·] denota o valor esperado e st+1 o estado seguinte.
Uma extensão directa a este tipo de exploração é a técnica de exploração baseada em
contabilidade com traço de decaimento. Em cada instante de tempo, cada contador é
multiplicado por um decaimento fixo λ ≤ 1:
∀s : c(s) ← λ · c(s)
(4.20)
O decaimento aumenta a eficiência da exploração, desde que a exploração resultante de
visitar um dado estado diminua ao longo do tempo, como é o caso da maioria dos sistemas
de aprendizagem que possuem dinâmicas de generalização. Também tem em conta a
50
4.5. A Escolha das Acções
idade de visita dos estados, pesando as ocorrências mais recentes de estados com um
maior valor.
Thrun provou a superioridade desta e de muitas outras técnicas para exploração dirigida,
mas na literatura a técnica mais frequentemente escolhida é a da exploração não-dirigida
devido à sua simplicidade. Nos casos onde a dimensão do espaço de acções e/ou estados
é muito grande (como no jogo Abalone) a aplicação destas técnicas torna-se impraticável.
51
Capı́tulo 4. Aprendizagem por Reforço
52
Capı́tulo 5
Treino por TD(λ) Clássico
Neste capı́tulo falamos sobre a primeira abordagem ao problema que foi desenvolvida.
O treino por TD(λ) na sua versão clássica já é bastante popular. Contudo, o problema
da representação do estado assume uma dimensão elevada, visto que fornece a base para
tudo o que um agente poderá aprender. Começamos por descrever o modelo experimental
e os agentes desenvolvidos, a forma como são utilizadas redes neuronais para aproximar
a função de avaliação e as representações de estado estudadas. Por fim apresentamos e
discutimos os principais resultados obtidos.
Mostramos que é possı́vel usar TD(λ) para construir um agente que aprenda a jogar Abalone, se for dada suficiente atenção aos procedimentos de treino e à representacão do
estado. Propomos uma arquitectura baseada nas caracterı́sticas espaciais do jogo e em
atributos relevantes para a obtenção de boas estratégias, demonstrando que essa arquitectura faz subir o desempenho do agente.
5.1 Modelo Experimental
Nesta secção descreve-se a arquitectura geral que foi implementada para realizar as experiências. Para garantir um total isolamento entre o agente e o ambiente, optou-se por
seguir a norma proposta por Sutton, que define uma interface para sistemas de AR. Há
duas vantagens:
• Garante-se que o agente só aprende recebendo o sinal de reforço, e não obtém
qualquer outro tipo de conhecimento do ambiente.
• O Simulador permite correr experiências sempre nas mesmas condições, evitando
possı́veis predisposições (bias) dos resultados obtidos.
53
Capı́tulo 5. Treino por TD(λ) Clássico
5.1.1 Os Agentes
O agente é a entidade que interage com o ambiente, recebendo sensações e recompensas e
seleccionando acções. Na norma de Sutton para sistemas de Aprendizagem por Reforço,
o agente pode ou não aprender, pode ou não construir um modelo do ambiente, pode
explorar ou ser ganancioso etc. Neste trabalho foram criados quatro tipos de jogadores:
1. Jogador Aleatório
2. Jogador Hill-Climbing Co-Evolutivo (descrito no capı́tulo 3)
3. Jogador Minimax
4. Jogador TD(λ)
Qualquer um destes jogadores pode ser diluı́do, isto é, a sua polı́tica de selecção de acções
é função de uma variável ε que representa a percentagem de acções aleatórias escolhidas
pelo jogador. Assim é possı́vel enfraquecer, por exemplo, o jogador Minimax para que,
durante o treino contra o jogador TD(λ) se modifique a perı́cia dos oponentes. Note-se,
no entanto, que na avaliação do desempenho (que se irá apresentar em 5.4) o jogador
Minimax não é enfraquecido.
O jogador Minimax baseia-se numa função heurı́stica que está, total ou parcialmente
presente na totalidade dos programas de Abalone existentes, e que tem em conta o número
de peças p existentes em cada casa especı́fica do tabuleiro:
h(x) = 256 − d(centro) × pagente + d(centro) × poponente
d(centro) calcula a distância hexagonal de uma peça em relação à casa central do tabuleiro. Observou-se que, de facto, esta heurı́stica é bastante eficaz neste jogo. O jogador
Hill-Climbing foi apresentado no capı́tulo 3, e não sofreu qualquer alteração. Finalmente,
o jogador TD(λ), que constitui o tema central desta dissertação, usa uma rede neuronal para aproximar o espaço de estados do jogo e é treinado combinando TD(λ) com
Retropropagação.
5.1.2 O Ambiente
O ambiente define o problema a ser resolvido. Mais concretamente, o ambiente define
a dinâmica do problema, as recompensas e o término dos episódios. Para o caso do
problema do Abalone, é natural definirmos uma especialização do Ambiente, onde os
elementos principais são o tabuleiro do jogo e o oponente (que pode ser um dos agentes apresentados na subsecção anterior). A Figura 5.1 sumariza o esquema essencial do
ambiente criado.
54
5.2. TD(λ) Clássico
Figura 5.1: O sistema dinâmico desenvolvido constitui uma especialização da Interface de Aprendizagem por Reforço apresentada no Capı́tulo 4.
5.1.3 A Simulação
A Simulação constitui a base da Interface de Aprendizagem por Reforço. Gere a interacção
entre o agente e o ambiente, e garante que as experiências são todas realizadas sob as mesmas condições e da mesma maneira, para um dado agente e um determinado ambiente.
Define, pois, o coração da Interface: a utilização uniforme a que todos os agentes e ambientes se devem submeter.
As simulações podem ser especializadas com o objectivo de alterar a forma de recolher
dados e mostrá-los ao utilizador.
Usando a arquitectura desenvolvida, é possı́vel correr experiências de treino de vários
tipos de agentes usando qualquer um dos jogadores como oponente, e o teste dos agentes
faz-se de uma maneira semelhante e uniforme. Também é possı́vel criar extensões às
classes implementadas para estudar outros jogos (alterando as regras do ambiente), assim
como criar agentes com outros parâmetros/representações de estado.
5.2 TD(λ) Clássico
Nesta secção começamos por discutir o problema da generalização. Os aproximadores de
funções tabulares, como os discutidos no Capı́tulo 4 (ver Mundo em Grelha com Lagos
e Túnel), sofrem da chamada maldição da dimensionalidade, a qual constitui um grande
obstáculo neste trabalho, uma vez que a dimensão do espaço de estados do jogo Abalone
– espaço sobre o qual se pretende aprender uma função de avaliação – é muito elevada
(ver Capı́tulo 3). Felizmente existem outros aproximadores de funções que podem ajudar
55
Capı́tulo 5. Treino por TD(λ) Clássico
a resolver este problema graças à sua capacidade de generalizar, por exemplo as redes
neuronais, que são aplicadas neste trabalho.
5.2.1 O Problema da Generalização
Definir o problema da generalização de forma precisa é uma tarefa muito subtil. O seguinte exemplo simples pode ajudar a explorar esta questão:
1 2 3 4 5 6 ? 8 9 10
Esta é uma curta sequência de números, um dos quais foi substituı́do por um ponto de
interrogação. Qual o valor deste número? Pode ser 2, 6 ou 29. Não há uma maneira de
saber. Contudo, é muito provável que muitas pessoas respondam “7” a esta questão. “7”
parece ser a resposta mais directa a dar, caso seja necessário dar uma resposta.
Porquê “7”? O princı́pio da lâmina de Occam1 pode explicar esta resposta: não se deve
aumentar, para além do que é necessário, o número de entidades necessárias à explicação
de uma qualquer questão. Apliquemos este princı́pio a alguns aproximadores de funções:
• tabela de valores: f (1) = 1, f (2) = 2, f (3) = 3, f (4) = 4, f (5) = 5, f (6) =
6, f (7) = 29, f (8) = 8, f (9) = 9, f (10) = 10.
• regressão linear: f (i) = i.
O princı́pio da lâmina de Occam diz que f (i) = i deve ser escolhido em vez da tabela de
valores porque é a explicação mais simples para os valores visı́veis. Portanto, descobrir
a melhor generalização consiste em encontrar a mais simples explicação para os dados
visı́veis. O grande problema desta perspectiva sobre a generalização é que a simplicidade
de um aproximador de funções não se define de forma precisa.
Por exemplo, imaginemos um universo cujas leis se baseiem na sequência “1 2 3 4 5 6
29 8 9 10”. Um habitante deste universo poderia achar que o 29 fosse a resposta mais
directa para o número em falta! Outra possibilidade (menos estranha) seria a de que,
independentemente desta sequência, outros números nos teriam sido apresentados no dia
anterior:
1 2 3 4 5 6 29 8 9 10
1 2 3 4 5 6 29 8 9 10
1 2 3 4 5 6 29 8 9 10. . .
Isto significa que a decisão sobre o que é uma boa generalizacão depende do conhecimento a priori. Este conhecimento a priori pode ser outros dados ou simplesmente uma
1
Este princı́pio é atribuı́do a William of Occam, um filósofo medieval (1280–1347).
56
5.2. TD(λ) Clássico
intuição acerca de que tipo de aproximador de funções é o mais adequado para um problema especı́fico.
Algumas teorias foram desenvolvidas para formalizar esta noção de generalização e para
produzir algoritmos eficientes. A sua complexidade vai muito além do âmbito desta
dissertação, mas os desenvolvimentos podem ser encontrados na literatura sobre Aprendizagem Automática. Em particular, a teoria de minimização do risco estrutural de Vapnik
constitui um grande resultado desta área (Vapnik, 1995). Muitas outras ideias importantes,
como as técnicas Bayesianas são explicadas de forma clara no livro de Bishop (Bishop,
1995).
Sem explorar mais estas teorias, é possı́vel estimar as capacidades de generalização de um
aproximador de funções paramétrico intuitivamente: deve ser o mais simples possı́vel, e
simultaneamente aproximar o maior número de funções “não-usuais”.
Figura 5.2: Esquema da rede neuronal multi-camada utilizada no Abalearn para aproximar a
função de avaliação.
A Figura 5.2 mostra a rede neuronal multi-camada utilizada pelo Abalearn na aproximação
da função de avaliação. O número de unidades de entrada varia entre 6 e 21 unidades, de
acordo com a representação em causa. O número de unidades escondidas varia entre 2 e
10 unidades, conforme a experiência.
5.2.2 O Processo de Treino
Durante o processo de treino utilizado neste capı́tulo, o agente começa por extrair conceitos básicos realizando 1000 jogos contra um oponente aleatório. Numa fase posterior, o
agente melhora o seu nı́vel de jogo sendo treinado jogando contra si próprio. O Algoritmo
57
Capı́tulo 5. Treino por TD(λ) Clássico
2 utilizado é uma versão online do gradiente descendente para TD(λ). Uma descrição formal e detalhada pode ser consultada no Apêndice A.
Um dos objectivos desta investigação consistiu em tentar que a aprendizagem se desenrolasse com o menor conhecimento a priori possı́vel. Daı́ termos utilizado o treino por
jogos contra o próprio como método-base nas experiências aqui descritas. Estes métodos
têm particular valor quando aplicados a domı́nios onde não exista conhecimento suficiente disponı́vel, ou onde o programa consiga atingir nı́veis de desempenho superiores ao
nı́vel do conhecimento já existente.
Como vimos no capı́tulo anterior, os métodos de aprendizagem por diferença temporal
constituem uma classe de procedimentos incrementais para aprender estimativas dos resultados finais de problemas de predição multi-passo, como o jogo Abalone.
O algoritmo TD(λ) de Sutton baseia-se no seguinte formalismo: seja {V1 , V2 , ..., Vt } um
conjunto de estimativas sucessivas desde o instante temporal 1 ao instante temporal t.
O algoritmo assume que cada estimativa é função de um vector de pesos ajustáveis, w,
~
pelo que uma estimativa no instante i pode ser escrita como Vi (w).
~ O algoritmo também
assume que a função de avaliação que representa essa estimativa é diferenciável, para que
existam derivadas parciais do valor da estimativa em relação a cada peso.
Os pesos da função de avaliação podem ser então ajustados de acordo com a fórmula
∆wt = α (Vt+1 − Vt )
t
X
λt−k ∇w Vk
(5.1)
k=1
TD(0) é o caso onde apenas o estado anterior ao estado actual é actualizado pelo erro da
diferença temporal (λ = 0). Para valores mais elevados de λ, mas ainda com λ < 1, cada
vez mais estados anteriores são actualizados, mas quanto maior a sua distância temporal,
menor é essa alteração, de acordo com o valor de λ (Sutton, 1988).
O parâmetro λ serve assim para determinar se o algoritmo está a aplicar predição de curto
ou longo alcance. O parâmetro α determina a velocidade com que estas alterações são
efectuadas.
Assim, o vector de parâmetros w
~ é constituı́do pelos pesos da rede neuronal descrita na
secção anterior. Existe também um vector de eligibilidades ~e, da mesma dimensão que
o vector w,
~ que é inicializado a zero. Existe uma eligibilidade para cada peso da rede.
Como a rede é constituı́da por duas camadas, na prática definiram-se dois vectores w:
~ um
para os pesos da camada escondida, e outro para os pesos da primeira camada. O mesmo
para as eligibilidades.
Usámos a função sigmóide como função de activação para as unidades da camada escondida e para a unidade de saı́da da rede. Os pesos são inicializados com valores muito
pequenos, entre –0.01 e +0.01. As recompensas são +1 sempre que o agente empurra
uma peça oponente do tabuleiro ou sempre que vence o jogo. Quando o agente perde, ou
58
5.3. Representação do Estado
quando o oponente lhe empurra uma peça, a recompensa é –1, caso contrário é 0.2
Algoritmo 2 Gradiente Descendente para TD(λ)
parâmetros: taxa de aprendizagem α, polı́tica π, factor de desconto γ, factor de decaimento de eligibilidades λ
Inicializar w
~ arbitrariamente e ~e = 0
repetir
s ← estado inicial
repetir
a ← jogada determinada por π para s
Realizar a jogada a, observar a recompensa r e o estado seguinte s0
δ ← r + γV (s0 ) − V (s)
~e ← γλ~e + ∇w~ V (s)
w
~ ←w
~ + αδ~e
s ← s0
até que s seja um estado terminal
até todos os jogos acabarem
Desta maneira, a rede pode aprender a jogar Abalone sem nunca ter sido treinada por
exemplos especı́ficos de jogadas boas/más. Isto significa que qualquer gerador de jogadas
legais – registos de jogos, programas Abalone comerciais, geradores de jogadas aleatórias
e a própria rede – pode ser utilizado para o treino.
Contudo, existe um problema tı́pico associado ao uso de redes multi-camada, que é o
facto de a convergência estar assegurada para um mı́nimo local do erro, e não necessariamente para o mı́nimo global do erro. Quando a superfı́cie de erro é boa (Figura 5.4)
isto não representa um problema, mas quando a superfı́cie é semelhante à Figura 5.3, com
muitos mı́nimos locais, a convergência não é assegurada para o melhor valor. Apesar
deste obstáculo, o algoritmo de Retropropagação tem produzido excelentes resultados em
muitas aplicações da vida real.
5.3 Representação do Estado
A representação do estado é uma das componentes mais crı́ticas de um agente que aprende,
visto que a sua definição acaba por definir o máximo que podemos esperar que o agente
aprenda. Daı́ que para o Abalone seja necessário escolher uma representação que repre2
Outra opção seria fornecer uma recompensa positiva apenas no final do jogo (quando seis peças estão
fora do tabuleiro). O agente seria capaz de aprender a “sacrificar” peças a fim de melhorar a sua posição.
Esta opção não foi experimentada, em parte por acreditarmos que uma função de avaliação que tem em
conta sacrifı́cios deve ser muito mais difı́cil de obter. Esta pode ser, contudo, uma interessante linha de
investigação para o futuro.
59
Capı́tulo 5. Treino por TD(λ) Clássico
1
0.8
0.6
0.4
0.2
0
-0.2
-0.4
-0.6
-0.8
-1
10
5
-10
0
-5
0
-5
5
10 -10
Figura 5.3: Uma má superfı́cie de erro, com muitos mı́nimos locais.
200
150
100
50
0
10
5
-10
0
-5
0
-5
5
10 -10
Figura 5.4: Uma boa superfı́cie de erro, cujo mı́nimo óptimo pode ser facilmente obtido, por
exemplo, por regressão linear.
60
5.3. Representação do Estado
senta de forma precisa e correcta a geometria do tabuleiro. Nesta secção apresentamos as
três principais representações de estado que foram estudadas.
5.3.1 Abalearn 1: Representação Directa
A representação do estado mais imediata e com o mı́nimo de informação a priori que
se pode imaginar é uma representação do estado directa: um mapeamento directo do
tabuleiro para a rede neuronal. O Abalearn 1, que designaremos por Abalearn-Directo por
ser mais intuitivo, utiliza uma representação deste tipo, em que as entradas são codificadas
usando o valor –1 para uma peça preta, +1 para uma peça branca e 0 para casas vazias. O
vector de entrada é constituı́do por 61 unidades (uma para cada casa do tabuleiro), mais
12 entradas (para as 12 peças possivelmente empurradas) e ainda uma unidade de bias.
Treinámos o Abalearn usando esta representação mas os resultados não foram bons: após
10000 jogos de treino contra si mesmo o agente apenas conseguiu aprender a empurrar as
peças do adversário e não revelou estratégias de jogo bem sucedidas. Daı́ a necessidade
de uma arquitectura que explorasse, de alguma forma, as caracterı́sticas do jogo, como a
que apresentamos de seguida.
5.3.2 Abalearn 2: Representação Espacial
Consideremos uma arquitectura em rede tı́pica que é treinada para avaliar estados do
jogo usando uma representação directa do tabuleiro, como aquela que foi apresentada na
subsecção anterior. Pretende-se que a rede aprenda quaisquer caracterı́sticas (atributos)
que possa necessitar. A complexidade desta tarefa pode ser reduzida explorando algumas
caracterı́sticas do jogo que se saiba serem relevantes para acelerar o processo de treino.
A Figura 5.5 apresenta a rede multi-camada que se utilizou. O número de unidades é significativamente pequeno em relação ao número de unidades habitualmente usadas (TDG AMMON tinha 198 unidades de entrada e 40-80 unidades na camada escondida). Devido
a isto, o treino torna-se muito mais veloz (estão em causa 27 pesos), o que permite correr mais experiências. Esta topologia foi encontrada após se ter determinado algumas
caracterı́sticas do jogo Abalone, as quais constituem um feature map bastante simples:
• Número de peças no centro do tabuleiro (ver Figura 5.5);
• Número de peças no meio do tabuleiro;
• Número de peças na borda do tabuleiro;
• Número de peças que estão fora do tabuleiro (foram empurradas).
61
Capı́tulo 5. Treino por TD(λ) Clássico
Figura 5.5: A arquitectura utilizada para o Abalearn 2, designado Abalearn-Espacial, tira partido
das caracterı́sticas espaciais do tabuleiro e codifica: o número de peças na borda do tabuleiro, no
centro e no meio. Também codifica o número de peças empurradas para fora do tabuleiro.
O estado é assim representado por um vector de 8 unidades, mais uma unidade de bias
colocada a 1.
Esta arquitectura em particular foi escolhida tendo em conta os resultados obtidos após
outras tentativas de construção. Apresentou o melhor desempenho sobre outras alternativas analisadas.
5.3.3 Abalearn 3: Representação com Atributos Relevantes
A arquitectura utilizada para o Abalearn 3, designado Abalearn-Atributos utiliza parte
da codificação do Abalearn-Espacial e acrescenta alguns atributos que descobrimos, após
várias tentativas, serem os mais relevantes para aprender a jogar Abalone (ver Figura 5.6):
• Protecção, número de peças totalmente rodeadas de peças da mesma cor;
• a distância média das peças ao centro do tabuleiro;
• o número de peças ameaçadas.
Um dos problemas que identificámos com o Abalearn-Espacial foi o facto de a codificação
das peças do agente na borda do tabuleiro fazia com que o agente aprendesse a empurrar
62
5.3. Representação do Estado
Figura 5.6: A arquitectura utilizada para o Abalearn 3, designado Abalearn-Atributos utiliza parte
da codificação do Abalearn-Espacial e acrescenta alguns atributos que descobrimos, após várias
tentativas, serem os mais relevantes para aprender a jogar Abalone: Protecção (número de peças
totalmente rodeadas de peças da mesma cor), a distância média das peças ao centro do tabuleiro e
o número de peças ameaçadas.
Figura 5.7: Exemplo de um dos jogos de treino. À esquerda, o Abalearn 2 (Abalearn-Espacial)
joga perto da borda, recebendo recompensas mas nunca explorando o centro do tabuleiro. À direita, vemos o Abalearn 3 (Abalearn-Atributos) empurrando com segurança as peças do oponente,
de uma forma compacta, graças ao atributo da Protecção.
63
Capı́tulo 5. Treino por TD(λ) Clássico
as peças do oponente, mas na ausência de exploração suficiente, o agente treinado jogando
contra si mesmo nunca explorava o centro do tabuleiro, visto que a recompensa é dada
sempre que o agente empurra uma peça do oponente. De forma a melhorar o nı́vel de
jogo, removemos esta entrada.
A Figura 5.7 mostra um exemplo retirado de um dos jogos de treino. À esquerda, o
Abalearn 2 (Abalearn-Espacial) joga perto da borda, recebendo recompensas mas nunca
explorando o centro do tabuleiro. À direita, vemos o Abalearn 3 (Abalearn-Atributos)
empurrando com segurança as peças do oponente, de uma forma compacta, graças ao
atributo da Protecção.
5.4 Resultados Experimentais - Método I
“If used properly, the clear performance measures in computer games can measure
progress in the development of learning algorithms, whereas a short-sighted attitude
would be to simply dismiss any learning algorithm that failed to outperform the best
competing technique on a given task.”
Gerald Tesauro, Programming Backgammon using Self-teaching Neural Nets.
Método de treino I - TD(λ) Clássico. O método designado I utiliza o procedimento de
treino já descrito: o algoritmo 2 usando a representação de estado designada por AbalearnEspacial. Os parâmetros da experiência são descritos nesta secção.
Método I(a): TD(λ) Clássico usando o Abalearn-Atributos. Este método é em tudo
semelhante ao anterior. A única diferença é a representação de estado, que passa a ser a
descrita em 5.3.3, designada Abalearn-Atributos. Este método é necessário para podermos demonstrar que os atributos acrescentados são, de facto, relevantes e fazem subir o
desempenho.
Métodos de Teste. O método mais directo para testar os nossos agentes consiste em medir a sua taxa de vitórias média contra um bom oponente heurı́stico que utilize procura
Minimax, como o agente que apresentamos na secção 5.1.1. Também comparamos amostras das redes ao longo do tempo de treino para verificar que estamos de facto a produzir
agentes melhores e não apenas agentes melhores contra o jogador Minimax.
No capı́tulo 6 apresentamos também resultados de jogos contra humanos experientes no
servidor oficial de Abalone usando o Método I. Inserimos esses resultados nesse capı́tulo
para facilitar a comparação entre os métodos. Também nesse capı́tulo testamos os agentes contra um programa comercial muito forte e contra um programa freeware que evita
jogadas repetidas.
Parâmetros da Rede Neuronal:
• Taxa de aprendizagem da primeira camada: α = 0.1
64
5.4. Resultados Experimentais - Método I
• Taxa de aprendizagem da segunda camada: β = 0.1
• Função de Activação: f (x) = 1/(1 + e−x )
• Número de unidades da primeira camada: 8
• Número de unidades da camada escondida: 3
• Número de unidades da camada de saı́da: 1
• Inicialização dos pesos: entre -0.01 e 0.01
Parâmetros do TD(λ):
• Factor de desconto de ganhos futuros: γ = 0.9
• Factor de decaimento das eligibilidades: λ ∈ {0.1, 0.3, 0.7}
• Recompensas: –1 em caso de derrota, +1 em caso de vitória, –1 em caso de peça
empurrada, +1 ao empurrar uma peça adversária, 0 nas restantes jogadas.
• Factor de exploração: ε = 0 (Polı́tica gananciosa)
5.4.1 Análise dos Resultados
Começamos por apresentar o gráfico relativo à fase inicial do treino do agente. A Figura
5.8 mostra que a Recompensa Média, definida como a Recompensa Total Acumulada
sobre o número de jogos de treino, aumenta. Esta medição é importante para termos a
certeza que o agente progride no treino.
Para termos uma ideia da evolução da “visão” do agente durante o treino, apresenta-se
de seguida a representação construı́da pelo agente após 10 jogos de treino (Figura 5.9),
comparando-a com a representação construı́da após 1000 jogos (Figura 5.10). A evolução
é nı́tida: o agente começa por aprender conceitos básicos (empurrar peças adversárias) e,
após 1000 jogos, tem uma representação que evidencia saber evitar a borda do tabuleiro,
evitar ser empurrado, tentar ocupar o centro e não deixar o adversário empurrar ou jogar
no centro.
Com o valor de λ=0.1, esta fase inicial de treino não é tão bem sucedida. A Figura 5.11
mostra que a representação construı́da não é tão boa como a da Figura 5.10. Como veremos de seguida, este facto foi determinante durante os torneios contra o jogador Minimax,
pois o desempenho com as redes em λ=0.7 foi superior.
A Figura 5.12 mostra os resultados das redes treinadas jogando 1000 jogos contra um
oponente aleatório. As redes foram amostradas em cada 50 jogos e efectuou-se, usando
o módulo de teste, 10 séries de 10 jogos contra um oponente 100% Minimax (procura 1
65
Capı́tulo 5. Treino por TD(λ) Clássico
150
Recompensa Média
Recompensa Média
145
140
135
130
125
120
0
10
20
30 40 50 60 70
Número de Jogos de Treino
80
90
100
Figura 5.8: Medição da recompensa média inicial (primeiros 100 jogos de treino).
Agente
Oponente
Peças no Centro
0.215
Peças no Centro
0.125
Peças Empurradas
0.102
Peças Empurradas
1.501
Peças no Meio
0.270
Peças no Meio
0.216
Peças na Borda
–0.037
Peças na Borda
0.197
Figura 5.9: Representação construı́da pelo agente após 10 jogos de treino (λ=0.7).
Agente
Oponente
Peças no Centro
0.836
Peças no Centro
0.139
Peças Empurradas
0.102
Peças Empurradas
1.556
Peças no Meio
0.888
Peças no Meio
0.381
Peças na Borda
–0.002
Peças na Borda
0.509
Figura 5.10: Representação construı́da pelo agente após 1000 jogos de treino (λ=0.7).
66
5.4. Resultados Experimentais - Método I
Agente
Oponente
Peças no Centro
0.065
Peças no Centro
0.060
Peças Empurradas
0.103
Peças Empurradas
1.665
Peças no Meio
0.130
Peças no Meio
0.074
Peças na Borda
–0.255
Peças na Borda
–0.037
Taxa de Vitórias contra Jogador Heurístico
Figura 5.11: Representação construı́da pelo agente após 1000 jogos de treino (λ=0.1).
0.7
0.6
0.5
0.4
0.3
0.2
Lambda=0.1
Lambda=0.3
Lambda=0.7
0.1
0
0
200
400
600
Jogos de Treino
800
1000
Figura 5.12: Percentagem de vitórias obtida contra um jogador Minimax. Cada ponto no gráfico
representa a média de 10 séries, cada série composta por 10 jogos, num total de 100 jogos. As
redes foram amostradas de 50 em 50 jogos de treino.
67
Capı́tulo 5. Treino por TD(λ) Clássico
nı́vel), num total de 100 jogos para cada rede. A percentagem de vitórias em cada série
foi calculada, obtendo-se valores com os quais se construiu um intervalo de confiança
(Tabela 5.1) para cada rede para verificar que os valores se encontram dentro do esperado.
Fez-se variar o parâmetro λ, como foi referido na secção anterior, entre 0.1 e 0.7.
λ=0.7
Média das Vitórias
Desvio Padrão
Confiança 95%
λ=0.3
Média das Vitórias
Desvio Padrão
Confiança 95%
λ=0.1
Média das Vitórias
Desvio Padrão
Confiança 95%
10
0.35
0.12
0.0046
10
0.39
0.09
0.0037
10
0.34
0.22
0.0087
250
0.41
0.13
0.0054
250
0.0.29
0.14
0.0058
250
0.23
0.17
0.0069
500
0.49
0.20
0.0082
500
0.41
0.17
0.0073
500
0.43
0.20
0.0080
750
0.39
0.17
0.0007
750
0.28
0.15
0.0062
750
0.39
0.14
0.0057
1000
0.61
0.09
0.0003
1000
0.29
0.15
0.0057
1000
0.09
0.06
0.0024
Tabela 5.1: Intervalos de confiança a 95% para alguns pontos no gráfico.
Durante o teste, o agente é ganancioso e usa uma procura superficial, considerando apenas
o nı́vel seguinte na árvore. Como se pode observar, algumas redes conseguem vencer mais
de 50% dos jogos contra o jogador Minimax. Os melhores resultados foram obtidos com
λ=0.7. O agente aprendeu os conceitos que desejávamos, e tornou-se mais agressivo que
o jogador baseado em procura heurı́stica.
Um valor baixo para λ (0.1) consegue aprender alguns conceitos básicos (empurrar peças,
aproximar-se do centro) mas ao longo do treino apresenta sempre um desempenho inferior, mergulhando na mediocridade e enfraquecendo após 750 jogos.
Com λ = 0.3, há uma subida inicial de desempenho notável, mas rapidamente – a partir
dos 200 jogos de treino – o processo de aprendizagem estabiliza à volta dos 30% de
vitórias.
A razão pela qual valores mais altos de λ apresentam uma melhor performance tem a ver
– neste caso – com o dilema que o jogo apresenta: para obter mobilidade e correr menos
riscos é bom jogar para o centro, mas para vencer é preciso empurrar peças adversárias, e
isso só pode ser feito se as peças do agente se aproximarem da borda do tabuleiro. Ora,
com λ=0, estamos no caso one-step temporal difference, onde só é alterado o estado visitado mais recentemente (ver secção 4.4.4). Isso faz com que os pesos da rede associados
ao número de peças que se encontram na borda seja aumentado positivamente sempre
que o agente ganha ou empurra uma peça (+1). Assim, o agente não consegue manter um
valor negativo nos pesos da borda do tabuleiro, e as experiências comprovam que isso é
68
5.4. Resultados Experimentais - Método I
suficiente para o nı́vel de jogo ser inferior.
Taxa de Vitórias Média sobre 500 jogos
0.8
0.75
0.7
0.65
0.6
0.55
0.5
0.45
0.4
Taxa de Vitórias contra Rede 10
Taxa de Vitórias contra Rede 250
Taxa de Vitórias contra Rede 2750
0.35
0.3
0
500
1000 1500 2000 2500
Número de Jogos de Treino
3000
3500
Figura 5.13: Comparação entre as Redes: cada ponto no gráfico mostra a percentagem média de
vitórias em 500 jogos que cada uma das redes no eixo X obteve contra as redes treinadas após 10,
250 e 2750 jogos. Observa-se nitidamente que a rede treinada após 2750 jogos só consegue ser
vencida por redes seguintes, e que a rede 250 é claramente inferior a todas as redes seguintes. A
rede treinada após 10 jogos é a mais facilmente derrotada.
Para obtermos uma ideia da evolução do treino, pode-se utilizar outra medida de validação
que indica que se está, de facto, a criar redes sucessivamente melhores. Tal como se
fez na experiência da Co-Evolução, escolheu-se três redes de referência e mediu-se a
percentagem de vitórias obtida por todas as redes, amostradas em cada 250 jogos de
treino contra cada uma dessas três redes.
As redes de referência escolhidas foram: as redes treinadas após apenas 10 e 250 jogos
(contra aleatório) e a rede treinada após 2750 jogos (jogando contra a própria). A Figura
5.13 mostra que existe, claramente, uma evolução no desempenho das redes, pois observase que a rede treinada após 2750 jogos só é vencida pelas redes com mais jogos de treino.
Observa-se também que a rede treinada apenas após 250 jogos apresenta um desempenho
inferior contra as redes com mais jogos de treino e que a rede após 10 jogos de treino é a
mais facilmente derrotada.
Estes resultados validam os resultados obtidos anteriormente, pois estabelece-se uma
comparação entre as várias redes que permite concluir que se está, efectivamente, a construir jogadores melhores, e não apenas jogadores melhores em relação ao jogador Minimax.
A Figura 5.14 sumariza o desempenho global do agente. O gráfico mostra o desempenho
do jogador, medido pela percentagem média de vitórias em 100 jogos contra o jogador
69
Taxa de Vitórias contra Jogador Heurístico
Capı́tulo 5. Treino por TD(λ) Clássico
1
0.8
0.6
0.4
0.2
Lambda=0.7
0
0
500
1000
1500
2000
2500
3000
3500
Jogos de Treino
Figura 5.14: Desempenho global das redes: dos 0 aos 1000 jogos, o treino foi efectuado jogando
contra um oponente aleatório, dos 1000 aos 3500 jogos, o treino é efectuado jogando contra a
própria rede. O valor de λ é fixo em 0.7 durante todo o treino. Estes resultados referem-se às redes
cujo treino foi o mais bem sucedido.
100% Minimax. Dos 0 aos 1000 jogos de treino, o oponente é aleatório. Nesta fase dá-se
a extracção dos conhecimentos básicos que por si só servem para conseguir alcançar o
nı́vel de jogo do Minimax. Dos 1000 aos 3500 jogos, o oponente é o próprio agente.
Apesar de o desempenho parecer instável, facto observado em muitos trabalhos (Schraudolph et al., 2001; Leouski, 1995), os resultados mostram que o treino contra a própria
rede faz aumentar o número médio de vitórias contra o jogador Minimax. Mas mais importante que isso, faz com que o agente cometa menos erros, sobretudo na fase inicial do
jogo, pois os pesos associados à borda do tabuleiro tornam-se mais negativos, inibindo o
agente de fazer certas jogadas iniciais que deixam as peças na borda.
É importante analisar estes aspectos, pois os jogos não são transitivos: se um jogador A
vence um jogador B, e se o jogador B vence o jogador C, isso não quer dizer que o jogador
A vença também o jogador C. Este aspecto é observado quando se avalia o agente contra
um jogador humano (capı́tulo seguinte).
A tabela 5.2 sumariza alguns dos resultados obtidos. O valor mais alto até agora registado
pertence à rede treinada após 2830 jogos, que atinge os 88.8% de vitórias em 100 jogos
contra o Minimax.
70
5.5. O valor dos Atributos
Agente:
Abalearn-Espacial treinado contra aleatório após 300 jogos
Abalearn-Espacial treinado contra aleatório após 1000 jogos
Melhor rede obtida treinada contra a própria após 2000 jogos (Método I)
Melhor rede obtida treinada contra a própria após 3000 jogos (Método I)
Melhor rede obtida treinada contra a própria após 3500 jogos (Método I)
Taxa de vitórias
27.7%
52.6%
57.8%
72.2%
70.5%
Tabela 5.2: Sumário de alguns resultados obtidos com λ = 0.7 (melhor valor de λ encontrado).
Chegou-se a registar taxas de vitória na ordem dos 88% contra o Minimax.
Jogos de Treino
500
1000
2000
3000
Método I
48%
52%
54%
71%
Método I(a)
68%
72%
76%
79%
Tabela 5.3: Comparação entre as representaç ões de estado (Taxa de Vitórias contra jogador Minimax).
5.5 O valor dos Atributos
Nesta secção, estudamos o valor dos atributos utilizados na representação de estado Abalearn 3 (Abalearn-Atributos). O método I(a), descrito anteriormente, é em todos os aspectos semelhante ao método I, excepto na representação de estado. A Tabela 5.3 sumariza
os resultados obtidos3.
Pode-se verificar que a diferença entre as versões é significativa. A representação de
estado com os atributos já descritos consegue uma taxa de vitórias superior. Durante a
elaboração desta versão, alguns atributos provaram ser ineficazes, pelo que foram abandonados. Esta representação, apesar de compacta, foi obtida após uma selecção baseada
em testes contra humanos e contra o jogador heurı́stico.
5.6 Treino por um oponente Perito
Nesta secção, descreve-se um outro processo, em tudo semelhante ao anterior, excepto em
relação ao oponente de treino que é, neste caso, um jogador perito: o jogador Minimax. O
objectivo é verificar que o treino contra um oponente perito é também igualmente eficaz
ou superior, uma vez que neste caso o adversário transmite conhecimento ao agente.
3
Para mais resultados sobre o método que usa a representação de estado Abalearn-Atributos, consultar
a secção 6.4.
71
Capı́tulo 5. Treino por TD(λ) Clássico
Taxa de Vitórias contra Jogador Heurístico
Numa abordagem inicial, treinou-se a rede 1000 (rede previamente treinada durante 1000
jogos contra um oponente aleatório). O oponente foi o jogador Minimax. O problema
que se observou foi que o jogo estabilizava muitas vezes, tornando o treino lento, pois
nenhum dos jogadores arriscava. Assim, foi necessário diluir o jogador Minimax, isto
é, acrescentar-lhe uma percentagem de comportamento aleatório (ε-greedy com ε=0.1).
Treinou-se o agente contra um oponente que é aleatório em 10% das jogadas e Minimax
nas restantes.
0.85
0.8
0.75
Auto−Treino
Treino contra Aleatório
Treino contra Heurístico
0.7
0.65
0.6
0.55
0.5
0.45
0.4
0.35
0.3
1000
1500
2000
2500
Número de Jogos de Treino
3000
Figura 5.15: Desempenho do Treino jogando contra vários tipos de oponentes.
Como seria de esperar, o treino contra o jogador Minimax permite criar um agente que
apresenta um desempenho superior em jogos contra esse mesmo jogador Minimax, convergindo muito mais cedo (com λ=0.7) para os mesmos valores que o agente treinado
jogando contra o próprio (Figura 5.15). Tal como nos resultados já analisados, o desempenho é inferior com valores de λ baixos.
Esta experiência espelha bem a natureza adaptativa dos processos de treino por reforço: o
sistema adapta-se rapidamente ao adversário, quando é exposto a este durante o treino. O
treino jogando contra o oponente aleatório e contra si próprio, apesar de ligeiramente mais
lento, é muito mais interessante, pois o agente descobre e afina a sua função de avaliação
de estados sozinho, não sendo exposto a peritos que, indirectamente, lhe fornecem o
conhecimento. Obtém-se um jogador que aprende e apresenta um nı́vel de jogo muito
bom sem recorrer a exemplos de treino, registos de jogos ou exposição a adversários
peritos.
No capı́tulo seguinte, apresentaremos um algoritmo de treino que ajuda a acelerar o treino
jogando contra o próprio e que conduz a agentes com desempenhos superiores.
72
Capı́tulo 6
Treino por TD(λ) Sensı́vel ao Risco
Calvin: Well. I’ve decided I do believe in Santa Claus, no matter how preposterous
he sounds.
Hobbes: What convinced you?
Calvin: A simple risk analysis: I want presents. Lots of presents. Why risk not
getting them over a matter of belief? Heck, I’ll believe anything they want.
Hobbes: How cynically enterprising of you.
Calvin: It’s the spirit of Christmas.
Bill Waterson, Calvin and Hobbes
Como se viu nos capı́tulos anteriores, polı́ticas conservadoras não são desejadas neste
domı́nio. Até no servidor oficial do Abalone foi necessário alterar a forma de avaliação
dos jogadores para sobrevalorizar aqueles com mais coragem (ver Apêndice B). Como
essa coragem envolve, invariavelmente, algum risco, fará também sentido envolver esse
risco na aprendizagem automática do Abalone.
Neste capı́tulo apresentamos o fundamento teórico da AR Sensı́vel ao Risco, recorrendo
a exemplos e baseando a descrição no artigo de Mihatsch and Neuneier (2002). Mostramos que a sensibilidade ao risco pode conduzir a um auto-treino mais eficaz e tentamos
explicar o porquê, analisando também os resultados obtidos.
6.1 Introdução
Os algoritmos de AR tipicamente optimizam o retorno esperado (ver secção 4.3) de um
processo de decisão de Markov. Na prática, contudo, este critério nem sempre é o mais
adequado. Muitas aplicações requerem estratégias de controlo robustas que também tenham em conta a variância do retorno (Mihatsch and Neuneier, 2002).
73
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
A literatura de controlo clássica fornece várias técnicas para lidar com problemas de
optimização sensı́veis ao risco. Coraluppi (1997) fornece uma pesquisa bibliográfica sobre estas técnicas. Uma abordagem é o chamado critério de optimalidade do pior caso.
Este critério foca-se exclusivamente em polı́ticas que evitam o risco, isto é, polı́ticas conservadoras. Na maior parte das aplicações da vida real, esta abordagem é demasiado
restritiva uma vez que tem totalmente em conta eventos muito raros (que na prática nunca
ocorrem).
Como exemplo, Mihatsch and Neuneier (2002) consideram um gestor de bens tipicamente
interessado não só em maximizar o retorno de um portfolio mas também em reduzir a sua
variância. Se o gestor investisse de acordo com o critério de optimalidade do pior caso,
nunca compraria bens de risco, como por exemplo acções, devido à elevada probabilidade
de perda.
Da mesma forma, um jogador conservador no Abalone não empurra as peças do oponente
devido à alta probabilidade de, ao fazê-lo, ver uma das suas peças que saı́ram do centro
para empurrar ser ela própria empurrada também. Mas, para aprender de forma eficaz
a jogar bem, ele deve ignorar esses casos e arriscar, pois só assim o jogo acabará e a
recompensa (sinal de treino do jogador-aprendiz) será útil, isto é, diferente de zero.
(Heger, 1994) desenvolveu um algoritmo de AR para o critério do pior caso. Na prática,
o seu algoritmo é menos pessimista do que o critério do pior caso puro, visto que eventos
extremamente raros que não ocorrem durante o tempo de treino (finito) não terão efeito
na polı́tica.
Outra abordagem, famosa na teoria de controlo, faz uso de funções de utilidade exponenciais. A ideia é transformar os retornos acumulados por funções de utilidade exponencial
e procurar polı́ticas óptimas em relação a esta medida de utilidade (Howard and Matheson, 1972). A desvantagem desta abordagem reside na ausência de uma forma óbvia de
desenhar um algoritmo de AR correspondente devido à estrutura das equações de optimalidade correspondentes não ser apropriada (Mihatsch and Neuneier, 2002).
A secção seguinte apresenta um método capaz de interpolar entre o pior caso e o mais
optimista possı́vel, ao mesmo tempo que evita as desvantagens das abordagens acima
referida: a AR sensı́vel ao risco, tal como descrita por Mihatsch and Neuneier (2002)
que parametriza a sensibilidade ao risco e transforma as diferenças temporais, requerendo
poucas alterações aos algoritmos de AR já existentes.
6.2 Fundamento Teórico
Nesta secção, formulamos o modelo conceptual da aprendizagem por reforço sensı́vel ao
risco (Mihatsch and Neuneier, 2002) e apresentamos a extensão ao caso do algoritmo
TD(λ), para o caso em que λ 6= 0.
74
6.2. Fundamento Teórico
O algoritmo de AR sensı́vel ao risco transforma as diferenças temporais durante o processo de aprendizagem. Nesta abordagem, κ ∈ (−1, 1) é um parâmetro escalar que
especifica a sensibilidade ao risco desejada. A função
(1 − κ)x se x > 0,
κ
χ : x 7→
(6.1)
(1 + κ)x c. c.
é chamada função de transformação, visto que é utilizada para transformar as diferenças
temporais de acordo com a sensibilidade ao risco. O algoritmo de aprendizagem TD
sensı́vel ao risco actualiza, no caso linear, a função de avaliação estimada, V , de acordo
com
Vt (st ) = Vt−1 (st ) + αχκ [R(st , at ) + γVt−1 (st+1 ) − Vt−1 (st )]
(6.2)
Quando κ = 0 estamos no caso clássico, neutro em relação ao risco. Se escolhermos κ
positivo, então sobrevalorizamos as diferenças temporais negativas,
R(st , at ) + γV (st+1 ) − V (st ) < 0
(6.3)
em relação às positivas. Isto é, sobrevalorizamos transições para os estados onde o retorno
imediato R(s, a) recebido foi inferior ao valor médio. Por outro lado subvalorizamos
transições para estados que prometem um retorno mais alto do que o médio. Por outras
palavras, o agente é averso ao risco quando κ > 0 e procura o risco quando κ < 0. Como
veremos na secção 6.3, valores negativos de sensibilidade ao risco, κ, conduzem a um
auto-treino mais eficiente.
Para melhor compreendermos o comportamento da função de avaliação sensı́vel ao risco
para valores diversos de κ, estudemos o seguinte exemplo simples.
Consideremos o MDP simples com dois estados dado pela Figura 6.1. No estado 0 temos
duas acções disponı́veis, fica ou move. Se escolhermos fica, recebemos, com 100%
de certeza um reforço imediato de 0. Por oposição, se escolhermos a acção move transitaremos para o estado 1, onde teremos a possibilidade de obter reforços futuros de +1 nos
passos seguintes. Contudo, existe uma (pequena) probabilidade de perda, θ, e teremos de
pagar o custo ρ ≥ 0 e retornar ao estado 0 outra vez.
Após alguns simples (mas longos) cálculos, obtém-se a seguinte função de avaliação Vκπ :
Vκf ica (0) = 0
Vκmove (0) =
γ
(1 − θ) (1 − κ) − ρθ (1 + κ)
·
1 − γ (1 − θ) (1 − κ) + (1 + γ) θ (1 + κ)
Conclui-se que a acção move é óptima se Vκmove (0) ≥ 0, i. é., se
ρ≤
1−θ 1−κ
·
θ
1+κ
75
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
p = 1, r = 0
a=
move
0
1
a = fica
p = 1, r = 0
p=θ
p = 1 – θ,
r=1
r=–ρ
Figura 6.1: Um MDP simples com 2 estados. As transições são representadas por setas. Os rótulos
r, p, a significam, respectivamente, o reforço, a probabilidade de transição e a acção. Exemplo
retirado de (Mihatsch and Neuneier, 2002).
Conclui-se então o seguinte: a acção move é óptima se o custo ρ não exceder um limite
que é decrescente em relação a ambos os parâmetros θ (probabilidade de perda) e κ (sensibilidade ao risco). Nos casos extremos θ = 1 (as perdas são inevitáveis), ou κ = 1
(critério de optimalidade do pior caso), move é sub-óptimo a menos que o custo ρ tenda
para zero. No outro extremo, se as perdas são impossı́veis (θ = 0) ou se usarmos um
critério de optimalidade que procure o risco (κ = −1) então o limite referido tende para
infinito, ou seja, move torna-se a acção óptima para todos os custos finitos ρ.
A fim de conseguirmos lidar com espaços de estados/acções de grande dimensão, é necessário estender o algoritmo de AR sensı́vel ao risco para o caso em que um aproximador
de funções paramétrico é utilizado. Isto é feito usando a função V (s; w) que produz uma
aproximação para V (s) envolvendo os parâmetros em w (os pesos de uma rede neuronal
implementam esta função).
Neste contexto, o algoritmo de aprendizagem TD toma a forma (Mihatsch and Neuneier,
2002)
t
X
κ
wt+1 = wt + αχ (dt )
∇w V (sk ; w)
(6.4)
k=1
onde
dt = R(st , at ) + γV (st ; w) − V (st−1 ; w)
No caso em que λ 6= 0, fazemos uma extensão directa do algoritmo para
κ
wt+1 = wt + αχ (dt )
t
X
λt−k ∇w V (sk ; w)
(6.5)
k=1
Desta forma o método pode lidar com espaços de estados de grande dimensão, usando
qualquer valor de λ, permitindo assim aplicações a domı́nios da vida real onde polı́ticas
76
6.3. Resultados Experimentais
conservadoras enfraquecem o sinal de reforço, ou – de uma maneira geral – a casos onde
a sensibilidade ao risco deva ser tida em consideração.
Os resultados de convergência para os métodos de aprendizagem por reforço envolvendo
aproximacão de funcões são muito mais difı́ceis de obter (Mihatsch and Neuneier, 2002).
Mesmo no caso clássico apenas alguns resultados que cobrem classes muito restritas de
problemas (por exemplo TD(λ) para aproximadores de funções lineares (Tsitsiklis and
Van Roy, 1996; Tsitsiklis and Roy, 2002)).
Apesar da falta de garantias de desempenho para muitos casos interessantes, as variantes
neutras ao risco do TD(λ) e do Q-Learning têm tido sucesso numa grande variedade de
contextos (Singh and Berteskas, 1997; Zhang and Dietterich, 1995; Tesauro, 1995).
Já existe alguma evidência de que a versão do algoritmo sensı́vel ao risco produza igualmente bons resultados na prática (Mihatsch and Neuneier, 2002). Neuneier and Mihatsch
(2000) conseguiram aplicar com sucesso o algoritmo de AR sensı́vel ao risco envolvendo
redes neuronais à tarefa de alocação de fundos no ı́ndice alemão DAX. Para um leque abrangente de valores para o parâmetro κ, o algoritmo convergiu para funções de
avaliação conducentes a polı́ticas de alto desempenho com bom comportamento. Contudo, as provas formais que estendam os resultados de convergência já mencionados continuam por ser feitas.
6.3 Resultados Experimentais
Método de treino II - TD(λ) Sensı́vel ao Risco. O método designado II utiliza o procedimento de treino descrito na secção anterior: a versão do algoritmo TD(λ) (algoritmo
2), sensı́vel ao risco, usando a representação de estado designada por Abalearn-Atributos.
Pretendı́amos obter um agente capaz de se treinar automaticamente jogando contra si
mesmo desde o inı́cio. O Método II consegue atingir este objectivo. A exploração é importante especialmente no inı́cio do treino, daı́ termos utilizado um esquema de treino
com ε decrescente: após cada jogo t, εt+1 = 0.99 × εt , com ε0 = 0.9 (treino com ε
decrescente). Após cerca de 60 jogos, ε é aproximadamente 0.1, e após 300 jogos é aproximadamente 0. Verificámos também que este esquema de exploração não é decisivo para
o sucesso da aprendizagem, pois apesar de melhorar a média das experiências de treino, é
possı́vel treinar um agente com ε = 0 fixo, desde que seja propı́cio ao risco, com κ → 1.
Métodos de Teste. Voltamos a testar os nossos agentes medindo a sua taxa de vitórias
média contra um bom oponente heurı́stico que usa procura Minimax (1 nı́vel), como
o agente que apresentamos na secção 5.1.1. Para uma melhor avaliação dos agentes,
testamo-los contra um programa comercial muito forte e contra um programa freeware
que evita jogadas repetidas. Também apresentamos resultados de jogos contra humanos
experientes no servidor oficial de Abalone.
Parâmetros da Rede Neuronal:
77
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
• Taxa de aprendizagem da primeira camada: α = 0.1
• Taxa de aprendizagem da segunda camada: β = 0.1
• Função de Activação: f (x) = 1/(1 + e−x )
• Número de unidades da primeira camada: 9
• Número de unidades da camada escondida: 10
• Número de unidades da camada de saı́da: 1
Parâmetros do TD(λ):
• Factor de desconto de ganhos futuros: γ = 0.9
• Factor de decaimento das eligibilidades: λ = 0.7
• Recompensas: –1 em caso de derrota, +1 em caso de vitória, –1 em caso de peça
empurrada, +1 ao empurrar uma peça adversária, 0 nas restantes jogadas.
• Factor de exploração: após cada jogo t, εt+1 = 0.99 × εt , com ε0 = 0.9 (treino com
ε decrescente.
• Parâmetro de sensibilidade ao risco: κ ∈ {−1, −0.8, −0.3, 0}
A Figura 6.2 mostra os resultados do treino para quatro diferentes valores de sensibilidade
ao risco: κ = −1 (o agente que mais procura o risco), κ = −0.8, κ = −0.3 e κ = 0 (o
caso clássico neutro ao risco). Repetimos as experiências de treino dez vezes, e para cada
amostra de agente testamo-lo fazendo-o jogar 100 partidas contra o jogador Minimax.
Com esses 10 treinos e 10 testes, construimos o gráfico da Figura 6.2, onde cada ponto
representa a taxa de vitórias média e cada barra representa o respectivo desvio padrão.
Podemos ver que o desempenho é melhor quando κ = −0.8. Também constatámos
que quando κ = −1, o processo de treino é muito estável, ao contrário do método de
treino descrito no capı́tulo anterior. Verificámos que após 10000 jogos de treino contra o
próprio usando κ = −1 o desempenho se mantia constante e elevado (ver Figura 6.3, que
apresenta os resultados para os primeiros 2000 jogos).
Treinámos o agente com κ = 0 e ele raramente aprendeu a empurrar as peças do oponente
(ver Figura 6.2), perdendo, por isso, muitos dos jogos quando testado contra o jogador
Minimax. Isto é porque a falta de sensibilidade ao risco conduz a polı́ticas conservadoras
onde o agente aprende a manter as suas peças no centro do tabuleiro e evita empurrar as
peças do oponente. Esta experiência ilustra a importância da sensibilidade ao risco na
aprendizagem por treino contra o próprio: no Método I, usando a mesma representação
de estado e os mesmos parâmetros experimentais excepto κ, apenas após 1000 jogos de
treino contra um fraco jogador aleatório era possı́vel o auto-treino ser bem sucedido.
78
Taxa de Vitórias contra Jogador Heurístico
6.3. Resultados Experimentais
1
0.8
0.6
0.4
0.2
0
0
200
400
600
800
1000
Jogos de Treino
k=−0.3
k=−0.8
k=−1
k=0
Figura 6.2: Desempenho dos agentes treinados por AR sensı́vel ao risco para diferentes valores de
κ. O auto-treino é bem sucedido para valores negativos (propı́cios ao risco).
Media contra Jogador Heurístico
6
5
4
3
2
1
Peças Perdidas
Peças Ganhas
0
10
100
Número de Jogos de Treino (K=−1)
1000
Figura 6.3: Aumento do desempenho do agente sensı́vel ao risco treinado jogando contra si mesmo
(κ = −1).
79
Valor do Peso Associado à Vantagem Material
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
0.25
Kappa=−0.8
Kappa=0
Kappa=−1
0.2
0.15
0.1
0.05
0
−0.05
0
200
400
600
800
1000
Número de Jogos de Treino
Figura 6.4: Valor do peso associado à Vantagem Material (peças ganhas – peças perdidas) para
diferentes valores de κ.
Nestas experiências, a configuração que funcionou melhor foi aquela (κ = −0.8) que
ignora quase completamente as diferenças temporais negativas, focando-se bastante em
obter um ganho positivo empurrando as peças do oponente “a todo o custo”. Apesar de
isto não parecer muito desejável a longo prazo, observámos que contribuiu decisivamente
para uma aprendizagem bem sucedida do Abalone.
A Figura 6.4 ajuda a entender melhor a natureza deste processo de treino. Nesta experiência particular de treino, o agente com κ = −1 conseguiu superar o agente com
κ = −0.8. Na Figura 6.4, apresentamos o valor do peso associado à Vantagem Material
(peças ganhas – peças perdidas) para diferentes valores de κ. Podemos ver que este valor mantém-se baixo (e constante) para o caso clássico neutro ao risco; o valor sobe mas
acaba por baixar ligeiramente no fim com κ = −0.8; quando κ = −1 o valor está sempre
a subir. Isto é porque no treino contra o próprio, o agente empurra uma peça e recebe
recompensa: essa recompensa é atribuı́da ao atributo da vantagem material, pois foi o
que registou a maior alteração. Logo o agente aprende que empurrar uma peça é bom. O
oponente (ele próprio) usa esse conhecimento e também empurra. Ao ser empurrado, o
agente recebe um castigo que anula a recompensa anterior. Ao admitir que não tem nada
a perder (κ = −1) o agente vai ignorar o castigo e o peso associado à vantagem material
vai subir, conduzindo o agente a um bom desempenho.
Para entendermos o valor relativamente a alguns outros atributos, mostramos três gráficos,
um para cada valor de κ, onde relacionamos os valores de três dos mais importantes
atributos: protecção, distância ao centro e vantagem material (Figuras 6.6, 6.5 e 6.7).
Podemos verificar que quando κ = 0, o peso (valor médio) associado ao atributo protecção
80
6.3. Resultados Experimentais
0.1
Valor do Peso Associado
0.08
0.06
0.04
0.02
0
Protecção
Distância ao Centro
Vantagem Material
−0.02
0
200
400
600
800
Número de Jogos de Treino (K=0)
1000
Figura 6.5: Valores de três dos mais importantes atributos para κ = 0.
0.22
Valor do Peso Associado
0.2
0.18
0.16
0.14
0.12
0.1
0.08
0.06
Protecção
Distância ao Centro
Vantagem Material
0.04
0.02
0
200
400
600
800
Número de Jogos de Treino (K=−0.8)
1000
Figura 6.6: Valores de três dos mais importantes atributos para κ = −0.8.
81
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
0.16
Valor do Peso Associado
0.14
0.12
0.1
0.08
0.06
0.04
Protecção
Distância ao Centro
Vantagem Material
0.02
0
0
200
400
600
800
1000
Número de Jogos de Treino (K=−1)
Figura 6.7: Valores de três dos mais importantes atributos para κ = −1.
é o mais elevado (Figura 6.5). Ou seja, com a polı́tica neutra ao risco, o agente é mais
conservador e aprende a proteger-se bem, não dando valor à vantagem material (peças
ganhas – peças perdidas), conforme já tı́nhamos referido.
Para os valores κ = −0.8 (Figura 6.6) e κ = −1 (Figura 6.7) isso já não acontece. O
valor da vantagem material é mais alto relativamente à protecção e à distância ao centro.
Com κ = −1, esse valor sobe coerentemente e de forma mais consistente do que com
κ = −0.8, o que explica a ligeira diferença de desempenho entre estas configurações
experimentais (ver Figura 6.3).
6.3.1 Desempenho face a outros Programas
Pretendı́amos avaliar o desempenho da aprendizagem por diferença temporal face a outros
métodos. O programa A BA -P RO (Aichholzer et al., 2002), uma aplicação comercial que
é um dos melhores jogadores de Abalone construı́dos até hoje, depende de técnicas sofisticadas de procura que utilizam heurı́sticas afinadas manualmente e que foram difı́ceis de
descobrir (Aichholzer et al., 2002). O programa emprega procuras altamente selectivas
(que podem variar entre 2 a 9 nı́veis de profundidade). Constitui, portanto, uma medida
de desempenho eficaz, pelo que fizemos jogar o Abalearn treinado pelo método II contra
o A BA -P RO.
A Tabela 6.1 mostra alguns resultados obtidos variando a profundidade da procura do
A BA -P RO e do Abalearn. Estes testes foram realizados da seguinte forma:
• Sempre que o jogo atinge uma fase em que ambos os jogadores repetem as mesmas
82
6.3. Resultados Experimentais
Método I Profundidade = 1 vs.:
Aba-Pro Profundidade = 4
Aba-Pro Profundidade = 5
Aba-Pro Profundidade = 6
Método II Profundidade = 1 vs.:
Aba-Pro Profundidade = 4
Aba-Pro Profundidade = 5
Aba-Pro Profundidade = 6
Método II Profundidade=3 vs.:
Aba-Pro Profundidade =1
Aba-Pro Profundidade =1
Aba-Pro Profundidade =2
Aba-Pro Profundidade =2
Aba-Pro Profundidade =4
Aba-Pro Profundidade =4
Peças Ganhas
0
0
0
Peças Ganhas
0
0
0
Peças Ganhas
3
0
1
0
0
0
Peças Perdidas
0
0
2
Peças Perdidas
0
0
0
Peças Perdidas
1
0
0
0
0
0
Jogadas
31
23
61
Jogadas
29
21
42
Jogadas
61
32
61
37
19
15
Jogada Inicial
Aba-Pro
Aba-Pro
Aba-Pro
Jogada Inicial
Aba-Pro
Aba-Pro
Aba-Pro
Jogada Inicial
Abalearn
Aba-Pro
Abalearn
Aba-Pro
Abalearn
Aba-Pro
Tabela 6.1: Desempenho do Abalearn contra o A BA -P RO, para vários nı́veis de profundidade.
jogadas por 20 vezes consecutivas, terminamos o jogo (empate por repetição).
• Esta experiência foi realizada manualmente, pois não foi implementada uma interface entre os dois programas.
• A versão freeware do programa A BA -P RO limita a profundidade da procura a 6
nı́veis (nı́vel máximo experimentado), e impõe um número limite (61) de jogadas
por jogo.
Como se pode constatar, o Abalearn apenas perde 2 peças quando a profundidade da
procura do seu oponente é 6 e a profundidade do Abalearn é 1. Isto demonstra que o
Abalearn adquiriu boas estratégias defensivas.
Na segunda secção da tabela, podemos ver que o método II apresenta um melhor desempenho (nunca perde). Os resultados também mostram que quando o Abalearn começa o
jogo, comporta-se melhor que o A BA -P RO, sobretudo quando o nı́vel de profundidade da
sua procura é mais elevado (terceira secção da tabela).
O problema com o método de avaliação anterior está no facto de os jogos entrarem, frequentemente, num ciclo de jogadas repetidas para ambos os jogadores, fazendo com que
o jogo não termine. Foi por isso que escolhemos avaliar o método II, mais promissor,
contra outro programa: Abalone 1.5.1 para Macintosh, um programa freeware desenvolvido por Peter Tax. Este autor explorou diversas heurı́sticas para este jogo. A melhor
delas, baptizada T ERMINATOR III, baseia-se no valor posicional, conectividade e número
de peças para cada jogador ainda em jogo. Este programa evita repetir a mesma jogada e
faz terminar o jogo com maior facilidade.
83
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
Método II Profundidade = 1 vs.:
Terminator III Profundidade = 1
Terminator III Profundidade = 2
Terminator III Profundidade = 3
Terminator III Profundidade = 4
Terminator III Profundidade = 5
Método II Profundidade = 3 vs.:
Terminator III Profundidade = 4
Terminator III Profundidade = 5
Peças Ganhas
6
6
6
0
2
Peças Ganhas
3
5
Peças Perdidas
3
4
3
2
6
Peças Perdidas
2
6
Jogadas
35
46
37
46
35
Jogadas
64
45
Jogada Inicial
Terminator
Terminator
Terminator
Terminator
Terminator
Jogada Inicial
Terminator
Terminator
Tabela 6.2: Desempenho do Abalearn usando o método II contra o T ERMINATOR III, para vários
nı́veis de profundidade.
A Tabela 6.2 mostra os resultados para diferentes nı́veis de profundidade. Podemos ver
que o Abalearn comporta-se melhor e apenas perde quando a profundidade do oponente
é 4 ou 5 e a do Abalearn é 1. Nas mesmas condições de procura, a função de avaliação
do Abalearn é claramente melhor que a função afinada manualmente do T ERMINATOR
III. O Abalearn ganha este oponente usando uma procura com um nı́vel de profundidade
mesmo quando o oponente procura até 3 nı́veis.
6.3.2 Desempenho contra Humanos Peritos
Método I Profundidade = 1 vs. Peças Ganhas Pecas Perdidas
ELO 1448
6
1
ELO 1590
3
6
ELO 1778
0
6
Tabela 6.3: Abalearn treinado pelo método I jogou online e conseguiu vencer alguns jogadores
intermédios.
Método II Profundidade = 1 vs. Peças Ganhas
ELO 1501
2
ELO 1500
6
ELO 1590
6
ELO 1590
6
ELO 1590
6
ELO 1590
6
Pecas Perdidas
0
1
1
3
4
4
Tabela 6.4: O desempenho contra jogadores peritos humanos é superior usando o Método II.
Para melhor determinar o nı́vel de Jogo do Abalearn, fizemo-lo jogar online no servidor
oficial do Abalone. Tal como em todos os jogos, a classificação dos jogadores é deter84
6.4. Comparação entre os Métodos
minada pelo sistema ELO. Para uma melhor compreensão deste sistema, a sua história,
descrição e contextualização a nı́vel do Abalone encontram-se no Apêndice B.
A Tabela 6.3 mostra os resultados de alguns jogos realizados pelo Abalearn online, contra
jogadores de diferentes ELO’s. O Método I vence um jogador com ELO 1448 por 6–1
e perde por 6–3 contra um jogador com ELO 1590. Jogando contra um ex-campeão de
Abalone, o Abalearn (método I) perdeu por 6–0, mas o campeão levou horas a derrotar o
Abalearn, sobretudo porque este defende-se bem e é necessário ir tentando desagrupar as
suas peças, numa lenta caminhada para a vitória.
O Método II é mais promissor devido aos seus atributos extra que foram incorporados
na respresentação de estado Abalearn 3 (Abalearn-Atributos), conforme foi descrito na
secção 5.3.31.
Como se pode verificar pela Tabela 6.4, o agente é capaz de vencer convictamente jogadores humanos intermédios com experiência.
6.4 Comparação entre os Métodos
A Tabela 6.5 compara, resumidamente, os mais importantes métodos de treino desenvolvidos. Apresenta a taxa de vitórias média contra o jogador Minimax sobre 100 jogos de
teste, usando o método I, I(a) e II.
Método I: TD(λ) Clássico usando o Abalearn-Espacial. Este método foi descrito na
secção 5.4: o agente é treinado durante 1000 jogos contra um oponente aleatório e só
então usa os jogos contra si mesmo como experiência de treino. A representação de
estado (Abalearn-Espacial) foi descrita em 5.3.2.
Método I(a): TD(λ) Clássico usando o Abalearn-Atributos. Este método é em tudo
semelhante ao anterior. A única diferença é a representação de estado, que passa a ser a
descrita em 5.3.3, designada Abalearn-Atributos. Este método é necessário para podermos demonstrar que os atributos acrescentados são, de facto, relevantes e fazem subir o
desempenho.
Método II: TD(λ) Sensı́vel ao Risco usando o Abalearn-Atributos. Este é o método
descrito neste capı́tulo, com κ = −1. O objectivo é mostrar que, além de a sensibilidade
ao risco tornar o auto-treino bem sucedido, um método que seja propı́cio ao risco usando
esta arquitectura consegue obter um desempenho superior aos outros métodos descritos
nesta dissertação.
O agente que usa o método I(a) possui a representação de estado com os atributos extra e após apenas 1000 jogos de treino já apresenta um melhor desempenho do que o
agente treinado pelo método I. Isto prova o benefı́cio dos atributos. O agente treinado
1
Para jogar contra a versão mais recente do Abalearn online, pedimos ao leitor que visite o endereço
http://neural.inesc.pt/Abalearn/index.html.
85
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
Jogos de Treino
500
1000
2000
3000
Método I
48%
52%
54%
71%
Método I(a)
68%
72%
76%
79%
Método II
81%
92%
91%
93%
Tabela 6.5: Comparação entre os métodos (Taxa de Vitórias contra jogador Minimax).
pelo método II, propı́cio ao risco, é, como se pode ver, o mais bem sucedido. É esse
agente que está, actualmente, a jogar no endereço oficial do Abalearn:
http://neural.inesc.pt/Abalearn/index.html.
6.5 Uma Abordagem Alternativa
Uma outra abordagem que parecia fazer sentido para resolver o problema de obrigar o
agente a empurrar peças seria usar uma forma de exploração dirigida, semelhante aquela
que foi descrita no Capı́tulo 4. De facto, chegámos a implementar uma extensão a esta
técnica de exploração na qual se tenta obrigar o agente a explorar os estados cujos pesos
se alteraram menos. O algoritmo utilizado é o algoritmo 3 e constitui uma extensão à
fórmula de exploração apresentada em 4.5.6.
Algoritmo 3 Exploração com Traço de Contabilidade
parâmetros: ρ, Φ, , V (s)
Com Probabilidade 1 − : at = arg maxa V (st )
Com Probabilidade : at = arg mina c(Φ(st ))Φ(st )
Aprender usando TD(λ)
c(Φ(st )) ← c(Φ(st )) + ρ · c(Φ(st )) · Φ(st )
Usámos o mesmo esquema de treino, com os mesmos parâmetros do método I(a), ou seja,
usando a representação de estado Abalearn-Atributos. A Figura 6.8 compara os resultados
apresentados anteriormente, com o Abalearn-Atributos na versão sensı́vel ao risco.
O algoritmo 3 descreve o método utilizado. ρ é a taxa de decaimento, Φ é a função que
mapeia um estado s numa entrada para a rede, é a probabilidade de escolher uma acção
de acordo com o valor do traço de contabilidade (em vez de escolher uma acção que
maximiza a saı́da da rede) e V (s) é a estimativa da função de avaliação (representada da
mesma forma que no método I(a)).
Podemos concluir que a exploração dirigida acaba por ser mais benéfica que a versão
neutra ao risco, mas o desempenho é muito inferior quando comparado com a versão
sensı́vel ao risco com valores negativos de κ. Mais uma vez esta experiência prova a
86
Taxa de Vitórias contra Jogador Heurístico
6.5. Uma Abordagem Alternativa
1
0.8
0.6
0.4
0.2
0
0
200
400
600
Jogos de Treino
800
1000
Traço de Contabilidade
Sensível ao Risco k=−0.8
Sensível ao Risco k=−0.3
Figura 6.8: Comparação entre o mesmo agente Abalearn-Atributos treinado na versão sensı́vel ao
risco e treinado com exploração por traço de contabilidade.
importância da sensibilidade ao risco: com a mesma representação de estado e com os
mesmos parâmetros de treino, um agente sensı́vel ao risco usando exploração não-dirigida
(ε-greedy) obtém um desempenho oito a nove vezes superior ao desempenho de um agente
neutro ao risco usando exploração dirigida.
87
Capı́tulo 6. Treino por TD(λ) Sensı́vel ao Risco
88
Capı́tulo 7
Conclusões
Nesta dissertação apresentam-se os primeiros resultados obtidos com o programa Abalearn. O agente aprende a jogar Abalone através de jogos contra si próprio. O método
de treino é baseado no algoritmo TD(λ). Se em jogos determinı́sticos, o treino por jogos contra o próprio já é difı́cil, no Abalone esse tipo de treino é ainda mais dificultado
pela estabilidade que a dinâmica do jogo apresenta quando nenhum dos jogadores está
disposto a arriscar.
Mostrámos que o uso de AR Sensı́vel ao Risco permite que o agente seja treinado de
uma forma mais eficiente. Descobrimos que a abordagem sensı́vel (e propı́cia) ao risco
é, para o Abalearn, responsável pelo sucesso do auto-treino na aprendizagem deste jogo.
Esperamos que este trabalho possa contribuir para que que esta observação venha a ser
tida em conta noutras aplicações e domı́nios, experimentais ou reais.
Estudámos o impacto de alguns parâmetros importantes na aprendizagem e propusemos
uma representação de estado que faz aumentar o nı́vel de desempenho do agente. Este
nı́vel de desempenho é medido através de jogos de teste contra um bom oponente Minimax que utiliza uma função de avaliação fixa, contra duas aplicações e também contra
jogadores humanos experientes.
Apesar de os campeões humanos vencerem claramente o nosso programa, em todos os
casos o Abalearn apresenta resultados muito promissores: os melhores agentes vencem
90% dos jogos contra o oponente heurı́stico e conseguem empatar contra oponentes muito
fortes, vencendo mesmo alguns jogadores humanos experientes. No entanto, a ênfase
não foi colocada em obter o melhor jogador do mundo recorrendo a todas as técnicas
possı́veis para vencer um campeão, mas sim em conseguir entender a natureza do processo
de treino e apresentar métodos que possam ajudar a desenvolver agentes que aprendem
necessitando do mı́nimo conhecimento a priori possı́vel.
Algumas das técnicas aqui apresentadas foram aplicadas à concepção de um jogador de
Gamão que, por auto-treino, se tornou campeão mundial. No entanto, tal como foi demonstrado por Pollack and Blair (1998), as causas do seu sucesso não foram bem com89
Capı́tulo 7. Conclusões
preendidas, pois há algo na dinâmica do jogo que o torna adequado ao auto-treino até
mesmo usando um hill-climbing simples.
Neste trabalho, essa abordagem simples não é bem sucedida, pelas razões já descritas.
Isto sugere que a dinâmica deste jogo seja muito menos propı́cia ao auto-treino que a do
Gamão. Apesar disso, a aprendizagem automática deste jogo pode ser bem sucedida, se
for dada suficiente atenção à arquitectura da rede neuronal e aos procedimentos de treino.
Também foi implementado um sistema de torneios de aprendizagem entre agentes, mas
essa abordagem ainda não foi testada para agentes sensı́veis ao risco, pelo que constitui
um tópico de investigação futura. Na secção seguinte, apresentamos outras direcções
possı́veis.
7.1 Trabalho Futuro
Apresentamos de seguida algumas linhas de investigação que podem ser seguidas no futuro. Algumas constituem extensões naturais ao trabalho já desenvolvido, outras representam palpites baseados em experiências que não foram concluı́das neste trabalho.
• Introduzir um esquema de escalonamento semelhante ao que foi usado para ε, mas
desta vez para o parâmetro κ, de sensibilidade ao risco. Mihatsch and Neuneier
(2002) sugerem iniciar o treino com κ = 0 e gradualmente aumentar (ou diminuir)
o valor deste parâmetro ao longo da aprendizagem. A vantagem provém do facto de
a sensibilidade das polı́ticas obtidas em relação a mudanças no parâmetro κ servir
como indicador da quantidade de risco inerente ao problema em causa. Quanto
maior essa quantidade (isto é, quanto maior a probabilidade de transições para o
pior caso) maior a sensibilidade dessas polı́ticas em relação ao parâmetro κ.
• Usar outras funções de transformação das diferenças temporais, além da função
dada por 6.1.
• Aplicar o algoritmo TD-Leaf(λ) de Baxter et al. (2000), pois é de esperar que aumentando o nı́vel de profundidade da procura durante o treino se consiga obter uma
função de avaliação mais precisa.
• Estudar outras formas de generalização além das redes neuronais (lineares ou nãolineares).
• Por fim, dada a importância da representação do estado, há que continuar a estudar
outros atributos e outras entradas que possam conduzir a um aumento do desempenho dos agentes.
Será necessário mais estudo a fim de determinar a utilidade da aprendizagem por reforço
sensı́vel ao risco noutros domı́nios. Também seria interessante criar um jogador “perito”
90
7.1. Trabalho Futuro
que use os mesmos atributos que o Abalearn-Atributos, mas com pesos afinados manualmente por um jogador humano bem classificado e experiente. Isso representaria um
desafio extra e clarificaria a qualidade dos pesos aprendidos pelo Abalearn.
Existem inúmeras aplicações da aprendizagem por diferença temporal fora do domı́nio
dos jogos, em particular na robótica, controlo industrial e estratégias de negociação financeiras. Acredita-se que as conclusões aqui apresentadas podem ser aplicadas a muitos
outros domı́nios por explorar. Por isso, tal como a ciência, também este trabalho está
condenado à risonha maldição de ser para sempre jovem.
91
Capı́tulo 7. Conclusões
92
Apêndice A
Diferenças Temporais
Neste apêndice faz-se a descrição formal do algoritmo TD(λ) utilizado para o treino por
Retropropagação, para o caso em que a rede possui múltiplas camadas e múltiplas unidades de saı́da. No trabalho, como vimos, a rede possui apenas duas camadas e apenas uma
unidade de saı́da (interpretada como uma estimativa da probabilidade de vitória).
A.1 TD(λ) para Retropropagação
Seja yit a saı́da no instante t da unidade i de uma rede multi-camada feed-forward. Seja O
o conjunto dos ı́ndices das unidades de saı́da da rede. Para k ∈ O, ykt é também designado
por Pkt . Para k ∈ O, zk é o componente do vector de saı́da da unidade k.
Idealmente, zk é estimado por cada Pkt , t = 1, ..., m, onde m é o número de vectores de
observação. Por definição, Pkm+1 = zk .
Seja wijt o peso no instante t da ligação da unidade i para a unidade j. Seja F Oj 1 o
conjunto dos ı́ndices das unidades com ligações a partir da unidade j.
De forma semelhante, F Ij seja o conjunto dos ı́ndices das unidades com ligações para a
unidade j.
Estas últimas unidades contribuem para a soma pesada stj da unidade j da seguinte forma:
stj =
X
wijt yit
i∈F Ij
Esta soma define então a saı́da da unidade j como
yjt = f stj =
1
Do termo anglo-saxónico Fan-Out.
93
1
t
1 + e−sj
Apêndice A. Diferenças Temporais
A.1.1 TD(0)
O caso em que λ = 0 apresenta uma implementação directa que se assemelha bastante
à da retropropagação convencional. Definimos a função do erro para cada passo como a
soma quadrática dos erros da diferença temporal:
X
2
Et =
Pkt+1 − Pkt
k∈O
Na derivação da regra de actualização, apenas pretendemos ter em conta os efeitos dos
pesos nas estimativas anteriores,Pkt , e não nas estimativas posteriores, Pkt+1 . A regra de
actualização dos pesos é então:
wijt+1
=
wijt
X ∂E t ∂P t ∂E t ∂Pkt
k
t
=
w
−
α
−α
ij
∂Pkt ∂wijt
∂Pkt ∂wijt
k∈O
= wijt − α
onde
δjt = −
∂E t ∂stj
= wijt + αδjt yit
t
t
∂sj ∂wij
∂E t
= Pit+1 − Pit yit 1 − yit
t
∂si
para i ∈ O, e
δjt = −
∂E t ∂stj ∂yit X
∂E t X
=
−
=
δjt wijt yit 1 − yit
t
t
t
t
j∈F Oi
j∈F Oi
∂si
∂sj ∂yi ∂si
caso contrário.
A.1.2 TD(λ)
O caso do TD(0) é muito semelhante ao da retropropagação convencional na medida em
que uma quantidade de erro – neste caso um erro TD – é retropropagado a cada unidade,
cada uma delas multiplicando essa quantidade pelo sinal em cada uma das suas ligações
de entrada para determinar a alteração aos pesos.
O caso geral para TD(λ) é um pouco diferente. Neste caso, o processo de retropropagação
produz um termo de “eligibilidade” para cada peso. Assim, uma diferença temporal é calculada em cada instante de tempo, sendo comunicada a todos os pesos, que a combinam
com as suas eligibilidades de eligibilidade para determinar as alterações aos pesos.
As eligibilidades realizam assim uma porção significativa da atribuição dos créditos: determinam que pesos são elegı́veis para que tipos de modificações, caso um erro TD geral
94
A.1. TD(λ) para Retropropagaç ão
ocorra.
A regra de actualização dos pesos é
wijt+1 = wijt + α
X
k∈O
Pkt+1 − Pkt etijk
onde etijk é a k-ésima eligibilidade no instante t do peso da unidade i para a unidade j. A
k-ésima eligibilidade corresponde à unidade de saı́da k, isto é,
etijk
=
t
X
λt−n
n=1
∂Pkn
.
∂wijn
Estas eligibilidades são calculadas da seguinte forma:
t
et+1
ijk = λeijk +
t+1
∂Pkt+1
∂Pkt+1 ∂sj
t
t
t+1 t+1
=
λe
+
ijk
t+1
t+1
t+1 = λeijk + δkj yi
∂wij
∂sj ∂wij
onde
t+1
δkj
=
∂Pkt+1
∂st+1
j
é calculada por um processo de retropropagação recursivo:
 t
 y (1 − yit) , k = i;
t  i
∂Pk
t
0, k ∈ O, k 6= i;
δki
=
P
∂Pkt ∂stj ∂yit
∂sti 
t t
t
t
 P
=
t
t
t
j∈F Oj ∂s ∂y ∂s
j∈F Oj δkj wij yi (1 − yi ) , c.c.
j
i
i
95
Apêndice A. Diferenças Temporais
96
Apêndice B
O Sistema ELO
A avaliação do Abalearn contra jogadores humanos tem em conta o ELO do jogador
em causa. O ELO mede, portanto, o grau de perı́cia dos jogadores. Neste Apêndice
contamos a história deste sistema inventado por Arpad Elo e a sua contextualização a
nı́vel do Abalone, não só por uma questão de curiosidade como também para melhor
entender a avaliacão dos jogadores humanos no site oficial do Abalone.
B.1 A Invenção de Arpad Elo
Muitos jogadores internacionais de Xadrez supõem que as letras ELO, usadas para classificar o grau de perı́cia de um determinado jogador, constituem algum acrónimo, tal como
TD está para Temporal Difference. Na realidade, são o nome de um dos jogadores de
Xadrez americanos mais influentes. As realizações de Arpad Elo no campo de rankings
cientı́ficos de xadrez colocaram a comunidade do mundo do xadrez em dı́vida para com
ele.
As classificações exactas eliminam a necessidade para avaliações subjectivas nos convites
para os vários eventos do Xadrez mundial, e tornam possı́vel ter pares justos, rápidos e
previsı́veis em torneios do sistema Suı́ço, o que fez aumentar extremamente a atractividade da competição do Xadrez para muitos.
Nascido perto de Papa, em 25 de Agosto de 1903, na Hungria, numa famı́lia que Elo
descrevia como “fazendeiros pacı́ficos”, Elo foi para os Estados Unidos quando tinha 10
anos de idade. Durante o tempo que viveu em Cleveland em 1913, Elo viu um jogo
de xadrez na montra de uma loja. Isto inspirou-o a aprender Xadrez sozinho, usando a
enciclopédia Britânica da biblioteca do Liceu local.
O Xadrez era um passatempo para Elo. Era cientista e professor. Após ter ganho uma
graduação e um mestrado da Universidade de Chicago, começou a ensinar fı́sica em
1926 na Universidade de Marquette, onde permaneceu até se aposentar em 1969, quando
97
Apêndice B. O Sistema ELO
começou a dar aulas na Universidade de Wisconsin em part-time. Durante toda a sua vida,
o professor Elo foi um homem de muitos interesses, incluindo a astronomia, a horticultura, a concepção do vinho e a música.
Um jogador mestre da força no seu pico, Elo ganhou o campeonato do estado de Wisconsin pela primeira vez quando tinha 32 anos e continuou a ganhá-lo num total de oito
vezes. Terminou empatado para o sétimo lugar no U.S. Open de 1940 e ganhou outros
quarenta torneios.
Elo foi o presidente da Antiga Federação Americana de Xadrez de 1935 a 1937 e foi um
dos fundadores da Federação de Xadrez dos Estados Unidos em 1939. Elo adquiriu um
interesse especial pelo xadrez académico, e o seu programa piloto conduziu ao desenvolvimento do programa extensamente publicitado do campo de jogos de Milwaukee que
atraiu milhares de jovens ao jogo. Começou uma das fundações isentas do primeiro imposto para a promoção do xadrez. Pelos anos 50, Elo organizava o Central and Western
Opens, nessa época dois dos torneios americanos mais prestigiados, e os U.S. Open de
1935 e 1953. Ajudou a desenvolver e popularizar o formato do torneio do sistema suı́ço.
A maior contribuição de Elo à organização de Xadrez foi o desenvolvimento do sistema
da avaliação que carrega agora o seu nome. Houve muitos sistemas de avaliação em
uso antes do Arpad Elo surgir, alguns numéricos e outros que usavam outros meios para
avaliar jogadores. A Correspondence Chess League da América tinha um sistema da
avaliação nos 1930s, e o sistema de Ingo era popular na Europa.
O USCF tinha o seu próprio sistema da avaliação, desenvolvido por Kenneth Harkness.
Não era muito exacto. A grande realização de Elo foi surgir com um sistema novo de
avaliação que retinha algumas caracterı́sticas superficiais (como o ponto 1500 da avaliação
designava um jogador médio, o ponto 2000 da avaliação designava um jogador forte do
clube e os 2500 pontos designavam um jogador ao nı́vel do grandmaster), mas planeou
uma fundação estatı́stica para o sistema. Isto era criticamente importante para a aceitação
do sistema. As avaliações não serão úteis a menos que sejam percebidas como sendo
exactas.
O sistema da avaliação do professor Elo foi adoptado pelo USCF em 1960 e pelo FIDE em
1970. Até 1980 fez todos os cálculos para o FIDE na sua calculadora da Hewlett-Packard.
A creatividade do professor Elo, a integridade e a habilidade estatı́stica garantiram-lhe o
respeito não apenas a nı́vel nacional mas também internacionalmente. Na sua função
como presidente do comité das qualificações do FIDE, por pelo menos quinze anos, era o
responsável por ver os jogadores que mereciam tı́tulos internacionais a recebê-los efectivamente, e aqueles que não demonstravam ter força para merecer um tı́tulo internacional
a não os receber.
Elo tinha sempre cuidado para manter o valor da sua invenção em perspectiva, e num artigo na revista “Chess Life” em 1962, surgiu com uma analogia memorável para descrever
a dificuldade da medição exacta da força da jogada: “Frequentemente as pessoas que não
são familiares com a natureza e as limitações de métodos estatı́sticos tendem a esperar
98
B.2. O ELO no contexto do Abalone
demasiado do sistema da avaliação. As avaliações fornecem meramente uma comparação
dos desempenhos, nada mais e nada menos. A medida do desempenho de um indivı́duo
é feita sempre relativamente ao desempenho dos seus concorrentes e tanto o desempenho
do jogador como o dos oponentes são sujeitos às mesmas flutuações aleatórias.”
A medida da avaliação de um indivı́duo pode muito bem ser comparada com a medida da
posição de uma cortiça que se sacode para cima e para baixo na superfı́cie da água agitada
com uma vara amarrada a uma corda e que está balançando no vento.
O livro do professor Elo em 1978, “A Avaliação de Jogadores de Xadrez – Passado e Presente”, fornece uma explicação das origens da teoria da avaliação do Xadrez, bem como
as intrigantes análises históricas e especulação sobre aspectos demográficos do Xadrez,
tais como o efeito da idade de um jogador que aprende a jogar, de influências genéticas
na habilidade do Xadrez, entre outras. O sistema do professor Elo foi adoptado para concorrentes em desportos tão diferentes como o Scrabble, o Bowling, o Golf e o Ténis de
Mesa. Como reconhecimento das suas significativas contribuições ao Xadrez americano,
Arpad Elo foi colocado no “Chess Hall of Fame” em 1988.
B.2 O ELO no contexto do Abalone
Após esta introdução histórica sobre a medida de avaliação dos jogadores, fazemos nesta
secção a contextualização dessa medida no jogo em causa: o Abalone.
Esta é a fórmula actualmente utilizada para o cálculo do ELO de um jogador no servidor
oficial de Abalone:
1 − 1/10(EloD−EloV /200)/200+1
× 15 + 30−ExpV [1−[(ExpD−ExpV )/(ExpD+ExpV )]]
(B.1)
onde EloD e EloV representam os valores iniciais do ELO para o jogador derrotado e
vencedor, respectivamente, e ExpD e ExpV quantificam a experiência até à altura do
jogo do derrotado e do vencedor.
O primeiro termo da fórmula pode ser visto como a probabilidade de o adversário ganhar.
O segundo termo é visto como a pontuação da partida. A pontuação média de um jogo
entre dois jogadores do mesmo ELO e experiência será 8.5. Os criadores do Abalone
escolheram balanceá-la por um relatório/rácio da experiência.
Uma partida entre um jogador favorito e respectivo adversário poderá ter 2 finais possı́veis:
o mais provável de acordo com sua experiência e o seu nı́vel, de que dá uma pontuação
0.1 a 7 pontos de acordo com os casos. Num caso menos provável, dá uma pontuação
de 7 a 15 pontos. No evento de uma vitória muito pouco provável, a pontuação poderá
chegar até 30 pontos.
99
Apêndice B. O Sistema ELO
Se for o “vencedor menos provável” a ganhar o jogo, o lucro de uma partida entre dois
jogadores do nı́vel equivalente (probabilidade em torno de 50%), a pontuação será entre
8.5 e 15 pontos. Se for o “vencedor mais provável” a ganhar o jogo (probabilidade de
ganhar > 50%), o lucro será disperso abaixo dos 7.5 pontos.
Foi aumentada a influência das variações da experiência para acelerar o “choque” de um
jogador comparado ao seu nı́vel verdadeiro, e para minimizar a pontuação para vitórias
demasiado prováveis. Um jogador sem “coragem” ou ambição ganhará, em média, menos
de 2 pontos por vitória, mas perderá mais de 8 se for derrotado.
Os dois modelos. No seguimento dos regressos da utilização de um modelo de cálculo
dos desafios, foi proposto um novo modelo no Site oficial do Abalone.
Um modelo deste tipo tem numerosas ambições:
• conduzir o mais rapidamente possı́vel um jogador ao seu “nı́vel” na grande escala
de valores ELO.
• propor uma escala de valor coerente entre os jogadores, uma hierarquia legı́tima
entre si.
• propor desafios de jogos coerentes com o nı́vel dos jogadores oponentes
Os principais defeitos do antigo modelo eram:
1. pouca ou nenhuma diferença do prémio entre uma saı́da provável (jogador iniciado/especializado que derrota um novato), e uma saı́da improvável (vitória do novato).
2. limite arbitrário de 400 pontos de desvio entre dois jogadores para que o jogo seja
integrado no cálculo de prémio, provocando a exclusão dos jogadores mais fracos.
3. pouca ou nenhuma diferença na hierarquia entre uma atitude de jogo corajosa (brincar contra jogadores mais elevado ou do seu nı́vel), e uma atitude mais “observadora” (brincar aos jogadores mais fracos).
No novo modelo, um jogo terá 4 saı́das prováveis ou possı́veis:
1. Mais provável (vitória do favorito), representa um desafio de 0.1 a 7 pontos de
acordo com os casos.
2. No caso de vitória equiprovável, um desafio de 8.5 pontos
3. Menos provável, que dá um desafio de 7 a 15 pontos de acordo com os casos.
4. No caso de vitória muito pouco provável (desvio muito grande de nı́vel e de experiência), o desafio poderá atingir 30 pontos.
100
B.2. O ELO no contexto do Abalone
É o principal risco deste novo modelo para os nossos jogadores, cair sobre um jogador
sem experiência online, mas com um nı́vel real...
Por conseguinte, os jogadores recém-chegados, com uma experiência < 30 jogos terão
cerca de trinta jogos para “fixar-se” em relação à comunidade. A partir destas noções de
probabilidade, considera-se como corajoso a vontade de um jogador de enfrentar jogadores que têm mais experiência e um nı́vel superior ao seu... E tenta-se incentivar esta
diligência.
Por oposição, um jogador sem coragem recusará jogar em posição de desafiador, ou jogar
contra jogadores do seu nı́vel. Com este novo modelo, ganhará, em média, menos de 2
pontos por vitória, e correrá o risco de perder mais de 8 se por acaso perde...
Falamos aqui em termos estatı́sticos, olhando o percurso de jogadores sobre uma amostra
de uma centena de partes, e não numa base causı́stica.
ELO de partida
1500
1500
1500
1500
1500
ELO de chegada 1
2250
2124
2375
2031
789
ELO de chegada 2
2010
2023
2239
1932
1250
Jogador sem coragem
Jogador corajoso
Jogador muito corajoso
Jogador médio
Jogador muito fraco
Tabela B.1: Modificações entre o Modelo 1 e Modelo 2.
Na Tabela B.1, tentamos resumir as modificações entre os nossos dois modelos para um
mesmo percurso de diferentes jogadores com comportamentos diferentes.
Um jogador muito corajoso joga quase apenas com jogadores melhores ou mais experientes que ele. Um jogador corajoso jogará 2 em cada 3 vezes com um adversário melhor ou
mais experiente. Os jogadores fracos e médios não fazem selecção sobre o seu oponente,
jogando contra adversários tomados aleatoriamente.
Vemos assim que um jogador sem coragem deverá alterar a sua atitude para poder ultrapassar jogadores de estatı́sticas menos perfeitas, com uma atitude mais voluntária e
mais em conformidade com o espı́rito do jogo. Os jogadores fracos ou muito fracos conservarão em contrapartida todas as possibilidades de subir à classificação se o seu nı́vel
melhorar...
Para as estatı́sticas de vitórias/derrotas equivalentes, um jogador muito corajoso obterá
logicamente um ELO superior a um jogador menos intrépido ou menos elitista. Com o
novo modelo, uma progressão na parte superior da classificação passa imperativamente
pela vitória contra jogadores melhores que ele...
101
Apêndice B. O Sistema ELO
102
Bibliografia
Aichholzer, O., Aurenhammer, F., and Werner, T. (2002). Algorithmic fun: Abalone. Technical
report, Institut for Theoretical Computer Science, Graz University of Technology.
Barto, A., Sutton, R., and Watkins, C. (1983). Neuronlike adaptive elements that can solve difficult
learning problems. In IEEE Transactions, volume 13.
Baxter, J., Tridgell, A., and Weaver, L. (1998). Knightcap: a chess program that learns by combining TD(λ) with game-tree search. In Proc. 15th International Conf. on Machine Learning,
pages 28–36. Morgan Kaufmann, San Francisco, CA.
Baxter, J., Tridgell, A., and Weaver, L. (2000). Learning to play chess using temporal differences.
Machine Learning, 40(3):243–263.
Beal, D. F. and Smith, M. C. (1999). Temporal coherence and prediction decay in TD learning.
In Proceedings of the 16th International Joint Conference on Artificial Intelligence, pages 564–
569.
Beal, D. F. and Smith, M. C. (2000). Temporal difference learning for heuristic search and game
playing. Information Sciences, 1(122):3–21.
Berliner, H. (1984). Search vs. knowledge: an analysis from the domain of games. In Elithorn, A.
and Banerji, R., editors, Artificial and Human Intelligence. Elsevier, New York, NY.
Bishop, C. M. (1995). Neural Networks for Pattern Recognition. Oxford Oxford University Press.
Boyan, J. B. (1992). Modular neural networks for learning context-dependent game strategies.
Master’s thesis, Cambridge University.
Connell, J. and Mahadevan, S. (1993). Robot Learning. Kluwer Academic, Boston.
Coraluppi, S. (1997). Optimal control of Markov decision processes for performance and Robustness. PhD thesis, University of Maryland.
Crites, R. H. and Barto, A. G. (1996). Improving elevator performance using reinforcement learning. In Touretzky, D. S., Mozer, M. C., and Hasselmo, M. E., editors, Advances in Neural
Information Processing Systems, volume 8, pages 1017–1023. The MIT Press.
Dahl, F. A. (1999). Honte, a go-playing program using neural nets. In Proceedings of the 16th
International Conference on Machine Learning.
103
Dayan, P. (1992). The convergence of TD(λ) for general λ. Machine Learning, (8):341–362.
Dayan, P. and Sejnowski, T. J. (1994). TD(λ) converges with probability 1. Machine Learning,
(14):295–301.
Epstein, S. (1994). Toward an ideal trainer. Machine Learning, 15:251–277.
Epstein, S. (2001). Learning to play expertly: A tutorial on hoyle. In Fürnkranz, J. and Kubat,
M., editors, Machines That Learn to Play Games, chapter 8, pages 153–178. Nova Science
Publishers, Huntington, NY.
Heger, M. (1994). Considerations of risk and reinforcement learning. In Cohen, W. W. and Hirsch,
H., editors, Machine Learning: Proceedings of the Eleventh International Conference, pages
105–111, San Francisco. Morgan Kaufmann Publishers.
Howard, R. A. and Matheson, J. E. (1972). Risk-sensitive markov decision processes. Management Science, 18(7):356–369.
Hsu, F. H. (1999). Ibm’s deep blue chess grandmaster chips. IEEE Micro, pages 70–81.
Jaap van der Herik, H., Uiterwijk, J. W., and van Rijswijck, J. (2002). Games solved: Now and in
the future. Artificial Intelligence, (134):277–311.
Junghanns, A. and Schaeffer, J. (1997). Search versus knowledge in game-playing programs revisited. In Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence
(IJCAI-97), pages 692–697, Nagoya, Japan.
Lee, K. F. and Mahajan, S. (1988). A pattern classification approach to evaluation function learning. Artificial Intelligence, (36):1–25.
Leouski, A. (1995). Learning of position evaluation in the game of othello. Technical Report
UM-CS-1995-023, University of Massachusetts at Amherst, Amherst, MA.
Levinson, R. (1995). General game-playing and reinforcement learning. Technical Report UCSCCRL-95-06, University of California, Santa Cruz.
Levinson, R. and Weber, R. (2001). Chess neighborhoods, function combination and reinforcement learning. In Marsland, T. A. and Frank, I., editors, Computers and Games: Proceedings of
the 2nd International Conference (CG-00), volume 2063 of Lecture Notes in Computer Science,
pages 133–150. Springer-Verlag, Hamamatsu, Japan.
Levinson, R. and Weber, R. J. (2000). Pattern-level temporal difference learning, data fusion and
chess. In SPIE’S 14th Annual Conference on Aerospace/Defense Sensing and Controls: Sensor
Fusion: Architectures, Algorithms and Applications IV.
McCorduck, P. (1979). Machines who think – A personal inquiry into the History and Prospects
of Artificial Intelligence. W. H. Freeman and Company, San Francisco, CA.
104
Michie, D. (1963). Experiments on the mechanization of game-learning – part i. characterization
of the model and its parameters. The Computer Journal, (6):232–236.
Mihatsch, O. and Neuneier, R. (2002). Risk-sensitive reinforcement learning. Machine Learning,
(49):267–290.
Minsky, M. L. (1963). Steps towards artificial intelligence. In Feigenbaum, E. and Feldman, J.,
editors, Computers and Thought, pages 406–450. McGraw-Hill, New York.
Neuneier, R. and Mihatsch, O. (2000). Risk-averse asset allocation using reinforcement learning.
In Proceedings of the Seventh International Conference on Forecasting Financial Markets: Advances for Exchange Rates, Interest Rates and Asset Management.
Pollack, J. B. and Blair, A. D. (1998). Co-evolution in the successful learning of backgammon
strategy. Machine Learning, 32(1):225–240.
Rummery, G. (1995). Problem Solving With Reinforcement Learning. PhD thesis, University of
Cambridge.
Samuel, A. (1959). Some studies in machine learning using the game of checkers. IBM Journal
of Research and Development, 3(3):211–229.
Samuel, A. (1967). Some studies in machine learning using the game of checkers. ii - recent
progress. IBM Journal of Research and Development, 6(11):601–617.
Schaeffer, J. (1997). One jump ahead. Springer-Verlag, New York.
Schaeffer, J., Hlynka, M., and Jussila, V. (2001). Temporal difference learning applied to a highperformance game-playing program. In Proceedings of the International Joint Conference on
Artificial Intelligence (IJCAI), pages 529–534.
Schraudolph, N., , Dayan, P., and Sejnowski, T. J. (2001). Learning to evaluate go positions via
temporal difference methods. In Baba and Jain, editors, Computational Intelligence in Games.
Springer Verlag.
Schraudolph, N., Dayan, P., and Sejnowski, T. J. (1994). Temporal difference learning of position
evaluation in the game of go. In Advances in Neural Information Processing Systems, volume 6.
Morgan Kaufmann Publishers, Inc.
Sheppard, B. (2002). World-championship-caliber scrabble. Artificial Intelligence, (134):241–
275.
Singh, S. P. and Berteskas, D. (1997). Reinforcement learning for dynamic channel allocation in
cellular telephone systems. In Advances in Neural Information Processing Systems: Proceedings of the 1996 Conference, pages 974–980, Cambridge, MA. MIT Press.
Stensmo, M. and Sejnowski, T. (1995). Using temporal-difference reinforcement learning to improve decision-theoretic utilities for diagnosis. In Proc. 2nd Joint Symposium on Neural Computation. University of California, San Diego.
105
Sutton, R. S. (1988). Learning to predict by the methods of temporal differences. Machine Learning, 3:9–44.
Sutton, R. S. and Barto, A. G. (1998). Reinforcement Learning: An Introduction Reinforcement
Reinforcement Learning: an Introduction. The MIT Press, 1st edition.
Tan, M. (1993). Multi-agent reinforcement learning: Independent vs. cooperative agents. In
International Conference on Machine Learning, pages 330–337.
Tesauro, G. (1992). Practical issues in temporal difference learning. In Moody, J. E., Hanson, S. J.,
and Lippmann, R. P., editors, Advances in Neural Information Processing Systems, volume 4.
Tesauro, G. (1993). TD-gammon, a self-teaching backgammon program, achieves master-level
play. In Proceedings of the AAAI Fall Symposium on Intelligent Games: Planning and Learning,
pages 19–23, Menlo Park, CA. The AAAI Press.
Tesauro, G. (1995). Temporal difference learning and TD-gammon. Communications of the ACM,
3(38):58–68.
Tesauro, G. (1998). Comments on “co-evolution in the successful learning of backgammon strategy”. Machine Learning, 3(32):41–243.
Tesauro, G. (2002). Programming backgammon using self-teaching neural nets. Artificial Intelligence, 134:181-199, 2002, (134):181–199.
Tesauro, G. and Sejnowski, T. J. (1989). A parallel network that learns to play backgammon.
Artificial Intelligence, (39):357–390.
Thrun, S. (1995). Learning to play the game of chess. In Tesauro, G., Touretzky, D., and Leen,
T., editors, Advances in Neural Information Processing Systems 7, pages 1069–1076. The MIT
Press, Cambridge, MA.
Thrun, S. B. (1992). Efficient exploration in reinforcement learning. Technical Report CMU-CS92-102, School of Computer Science, Carnegie Mellon University, Pittsburgh, Pennsylvania.
Torrance, M. C., Frank, M. P., and Witty, C. R. (1992). An abalone position for which the game is
undefined.
Tsitsiklis, J. and Roy, B. V. (2002). On average versus discounted reward temporal-difference
learning. Machine Learning, 49(2–3):179–191.
Tsitsiklis, J. N. and Van Roy, B. (1996). An analysis of temporal-difference learning with function
approximation. Technical Report IDS-P-2322, MIT.
Vapnik, V. N. (1995). The Nature of Statistical Learning Theory. Springer.
Watkins, C. J. C. H. (1989). Learning from Delayed Reward. PhD thesis, Cambridge, England.
Wiering, M. (1995). TD Learning of Game Evaluation Functions with Hierarchical Neural Architectures. Master’s thesis, University of Amsterdam.
106
Yoshioka, T., Ishii, S., and Ito, M. (1999). Strategy acquisition for the game othello based on
reinforcement learning. IEICE Transactions on Inf. and Syst., E82 D(12).
Zhang, W. and Dietterich, T. G. (1995). A reinforcement learning approach to job-shop scheduling.
In Proceedings of the International Joint Conference on Artificial Intellience.
107
108
Índice
ε-greedy, 45
blemish effect, 32
rote learning, 3
Hill-Climbing, 54
N-Armed Bandit, 44
actor-critic, 44
adaptive heuristic critic, 44
função de avaliação, 13, 17, 31, 57, 73
função de transformação, 73
função de transição, 38
função heurı́stica, 54
funções de avaliação, 31, 36
funções de utilidade exponenciais, 72
funções não-lineares, 31
acção, 15, 35
agente, 15, 35, 54
ambiente, 15, 35, 54
aplicações, 36
aprendizagem por reforço, 1, 14, 35
aprendizagem supervisionada, 28
atributos, 14
auto-treino, 3
avaliação de polı́tica, 39
Gamão, 1, 16
generalização, 16, 56
gradiente descendente, 58
horizonte, 37
interface para sistemas de AR, 53
iteração de valor, 39
maldição da dimensionalidade, 55
mundo em grelha, 40
co-evolução, 19, 21
coerência temporal, 29
critério do pior caso, 72
não-linearidade, 31
parâmetro de sensibilidade ao risco, 73
polı́tica, 36, 37
óptima, 38
polı́ticas conservadoras, 72
princı́pio da lâmina de Occam, 56
problema da atribuição dos créditos, 15
processos de decisão de Markov, 38
programação dinâmica, 39, 40
Propriedade de Markov, 38
protecção, 62
Damas, 22
diferença temporal, 3, 15, 22
eligibilidades, 44, 57
empate por repetição, 10
estado escondido, 37
exploração, 17, 22, 27, 45, 49
baseada em contabilidade, 50
dirigida, 49
factor
de decaimento da eligibilidade, 44
de desconto, 37, 43
de ramificação, 23
Q-Learning, 40
recompensa, 37
rede neuronal, 16, 57
109
redes neuronais, 1, 55
reforço, 15, 27, 35
representação do estado, 60
retorno, 16, 37
variância do, 71
risco, 71
sensibilidade ao, 72
Sarsa, 41
simulação, 55
Softmax, 45
tabelas de assinaturas, 31
taxa de aprendizagem, 43
TD(λ), 43, 53
TD(0), 43
TD-Gammon, 16
treino por comparação, 14
Xadrez, 29
110