Transcript 7. Decision Trees and Decision Rules

國立雲林科技大學
National Yunlin University of Science and Technology
Evolution Neural Network Agents in the
NERO Video Game
Advisor ：Dr. Hsu
Presenter： Chien-Shing Chen
Author: Kenneth O. Stanley
Bobby D.Bryant
Risto Miikkulainen
CON. IEEE Symposium on Computational Intelligence and Games, April 2005
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Outline






Motivation
Objective
Introduction
Experimental Results
Conclusions
Personal Opinion
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Motivation
game market
Game characters can learn through interacting with
the player, keeping it interesting.
autonomous computer-controlled agent in the game
intelligent agents
Adapt and change in real-time
the behavior of agents in current games is often
repetitive and predictable
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Objective
In NERO, the player takes the role of a trainer,
teaching skills to a set of intelligent agents
controlled by rtNEAT.
agent behavior improves visibly during gameplay
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Introduction
Real-time NEAT(rtNEAT) is able to complexify
neural networks as the game is played, making it
possible for agents to evolve increasingly
sophisticated behaviors in real time.
Agent behavior improves visibly during gameplay.
NEAT, rtNERO
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Background
NERO need to learn online as the game is played,
predetermined training targets are usually not
available.
Traditional techniques have posed significant
challenges.
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Background
1. Large state/ action space
High-dimensional, real-time game
2. Diverse behaviors
same behavior in a homogeneous population
3. Consistent individual behaviors
players don’t want to see an individual agent periodically…
4. Fast adaptation
don’t want to wait hours for agents to adapt
5. Memory of past states
agents remember past events
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
rtNEAT
if agents could be evolved in a smooth cycle of
replacement, the play could interact with evolution
during the game and the many benefits
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
rtNEAT
A technique for evolving neural networks for
complex reinforcement learning tasks using a
genetic algorithm(GA)
Online, real-time, interact
1.
2.
3.
NEAT is based on three key ideas:
Historical markings
Speciation(物種形成)
Starting from minimal structure
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
rtNEAT
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
rtNEAT
1. Historical markings
Evolving network structure requires a flexible genetic encoding
Each genome includes a list of connection genes, each of which refers
to two node genes being connected.
Each connection gene specifies the in-node, the out-node, the
connection weight, and an innovation number, which allows finding
corresponding genes during corssover.
Mutation can change both connection weights (perturb) and network
structures (add a new connection or a new node to the network).
Through mutation, genomes of varying sizes are created.
Each unique gene in the population is assigned a unique innovation
number, and the numbers are inherited during crossover.
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
rtNEAT
2. Speciation(物種形成)
物競天擇適者生存
Explicit fitness sharing, where organisms in the same species must
share the fitness of their niche, preventing any one species from taking
over the population
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
rtNEAT
3. Starting from minimal structure
New structure is introduced incrementally as structural
mutations occur, and only those structures survive that are
found to be useful through fitness evaluations.
This way, NEAT searches through a minimal number of weight
dimensions and finds the appropriate complexity level for the
problem.
Intelligent Database Systems Lab
Running NEAT in Real Time
1.
Remove the agent with the worst adjusted fitness from the
population assuming one has been alive sufficiently long so
that is has been properly evaluated.
too old, too young
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Running NEAT in Real Time
2. Re-estimating
Was an agent old enough to be removed, its species now has one less
member and therefore its average fitness
has likely changed
used in choosing the parent species in the next step
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Running NEAT in Real Time
3. Choosing the parent species
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Running NEAT in Real Time
4. Dynamic Compatibility Thresholding
5. Replacing the old agent with the new one
6. Determining Ticks Between replacements
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Running NEAT in Real Time
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
N.Y.U.S.T.
I. M.
NeuroEvolving Robotic Operatives(NERO)
The robots begin the game with no skills and only the ability
to learn.
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Training Mode
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Training Mode
Training begins by deploying 50 robots on the field.
Each robot is controlled by a neural network with random
connection weights and no hidden nodes, as is the usual starting
configuration for NEAT.
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Playing NERO
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Playing NERO
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Playing NERO
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Playing NERO
Intelligent Database Systems Lab
N.Y.U.S.T.
I. M.
Conclusions
Drawback
evaluation
Application
game domain
Future Work
implement
Intelligent Database Systems Lab