Transcript Blondie24

Blondie24
Presented by
Adam Duffy and
Josh Hill
Overview






Introduction to new concepts
Design of Blondie24
Testing and results
Other approaches to checkers
Other approaches to evolutionary
computation
Why is this important?
Neural Networks

Nodes connected by links
–
–
–

Input nodes
Hidden nodes
Output nodes
Links have weights
Evolutionary Computation

Based on natural selection
–
–
–
–
–
Initialize population
Fitness function
Selection
Cross-over
Mutation
Design of Blondie24


Checkers neural network
Values for input nodes
–
–
–

Red – positive
White – negative
Empty – zero
Piece differential
Design of Blondie24


Connections between squares
Subsections
Design of Blondie24

Search methods
–
–
–
–
–
Minimax
Alpha-beta pruning
Iterative deepening
Quiescent
Hash table of previously evaluated positions
(maximum of 270,000)
Design of Blondie24


Initial population of 30
Each neural network plays 5 games as red
–
–
–


+1 for a win
0 for a draw
-2 for a loss
Top 15 kept, lowest 15 eliminated
Copy top 15 and mutate the weights
Blondie24: Advantages


Can learn new strategies
Doesn’t have human biases
Blondie24: Disadvantages


Long time
Doesn’t make use of expert knowledge
Tests




400 MHz Pentium II
840th generation
Played games on zone.com
165 games total (84 as red, 81 as white)
Results



zone.com rating: 2045.85
In top 500 of over 120,000
Better than 99.61% of registered players
Chinook






Primary feature - piece count
Looks for certain features
Over 40,000 opening lines of play
Every ending with <= 8 pieces
Higher value to positions with more pieces
Rated 2,814 at retirement in 1996
Different Evolutionary Approach


Particle Swarm Optimizers (PSO)
Each particle is moved closer to
–
–
Global best
Personal best so far
Other applications



Industry, medicine, and defense
Pattern recognition
Cancer
More information




Blondie 24: Playing at the Edge of AI by David B.
Fogel
Learning to play games using a PSO-based
competitive learning approach by L. Messeischmidt
and A.P. Engelbrecht
The Advantages of Evolutionary Computation by
David B. Fogel
Solving the Game of Checkers by Jonathan
Schaeffer and Robert Lake