Transcript View the final project presentation

Investigation of learning
Behavioural Functions in games
Jonathan Hitchcock
Supervisor: George Wells
Background
• Artificial Intelligence
– Very useful to automate different behaviors
• Games are a good model to test AI
• An investigation into general gameintelligence will have implications for all AI
• This project is a survey of what has been
done in these areas
Classification (1)
• Some games have very similar solutions
– A solution to one will work for others
– If a classification of these games can divide
them into categories, then each category can be
worked on
• Characteristics of games that are important
to their solution need to be found
Classification (2)
• I found three important characteristics:
– Number of options available at each move
– Size of search space for solution
– Necessity of context for game position
• Some characteristics seem important, but aren’t,
for this project:
– Number of players
– Perfect information
– Zero-sum
Graph of Characteristics
options
context
search space
• Note: characteristics are not independent, and
affect each other
Finite space, limited options,
non-contextual: RoShamBo
• Rock – Paper – Scissors
• Very simple: set of options
• Yet, huge tournaments held, with different
strategies tried out, etc
• Some very clever methods thought up
• Statistical, pattern matching, strategymatching
RoShamBo tournament results
•
•
•
•
•
•
•
•
•
1.
2.
3.
24.
28.
37.
38.
40.
41.
Iocaine Powder:
Phasenbott:
Simple Modeller:
Random(optimal):
Multi-strategy:
Beat Last Move:
Good Ole Rock:
Rotate R-P-S:
R-P-S 20-20-60:
W
L
D
30
26
24
2
12
5
3
1
1
0
1
2
2
21
27
27
26
27
11
14
15
37
8
9
11
14
13
Finite space, limited options,
contextual: Tic-Tac-Toe
• More complex than non-contextual:
– Addition of context increases the search-space
• Bean-playing, M.E.N.A.C.E
– Investigate all options, mark as good or bad
– After enough games, this will never lose
• Weighting may be necessary, rather than
simple boolean marking, due to size of
space
Infinite space, limited options,
non-contextual: Backgammon
• Game is of indefinite length, options vary
• A good move can be worked out from simply
examining the position
• Neural Nets have reached world-class level at
backgammon, with no external training
– Excel at strategic and positional judgment
– Not good at “technical”positions (“bearing in against an
anchor”) – we solve by probabilities
– 1,500,000 games needed to train
Infinite space, limited options,
contextual: Rubik Cube
• No indication that the solution is near
• Search is possible, but very expensive
– Search until solution: no evaluation function
• Externally taught solutions do well enough,
but are not extendible
• It seems a combination of searching and
rules is necessary:
– Search a little, and generate rules from results
Infinite space, unlimited options:
(1) Chess
• A very common problem
• Generally “solved” using space-searches, but these
are not perfect
– Can use evaluation functions to shorten search
• Methods such as pattern-matching have been tried,
but are not too successful
• Deep Blue uses very fast hardware, and highly
optimized searches, with very game-specific
evaluative functions
Infinite space, unlimited options:
(2) Robot Wars
• A fairly common concept, very general battle
simulator
• Closest to “real” situation: wide variety of actions,
no specific goal
• Rule-based solutions often do well (Quake bots)
• Neural Nets and Genetic algorithms have also
been successful
• Like Chess, no “real” solution other than searches
Findings
• There are some very good game-playing
programs in existence
• Deep Blue and Neural-Net Backgammon
programs have achieved world class status
• There are a number of very useful methods:
– Optimized space-searches, and neural nets the
most common, and apparently the most
powerful
The Future
• A method which would work for all eight of
my categories would be very useful
– Neural Nets seem to be the way forward in this
respect
• Extend the categories: Game Theory is a
huge field, and there is much that I have not
covered