Transcript An Artificial Intelligence System for Playing the Game of Ms. Pac-Man

An Artificial Intelligence System for
Playing the Game of Ms. Pac-Man
by Jason Tate
Master’s Design Project
Louisiana State University
April 2, 2009
Pac-Man
• Developed by Namco
in 1980
• One of the most
famous games of all
time
Ms. Pac-Man
• Sequel to Pac-Man
• Released in 1981
Gameplay
Ms. Pac-Man
Maze
Gameplay
Ghosts
Fruit
Power Pill
Scoring
Regular Pill
10
Power Pill
50
Cherry
100
1 Ghost
200
Strawberry
200
Orange
500
Pretzel
700
Apple
1000
Pear
2000
Banana
5000
2 Ghosts
400
3 Ghosts
800
4 Ghosts
1600
Ms. Pac-Man AI Contest
• First appeared at 2007 IEEE Congress on
Evolutionary Computation
• 2008 IEEE World Congress on Computational
Intelligence
• 2008 IEEE Symposium on Computational
Intelligence and Games
Contest Rules
•
Microsoft Windows
• Screen Captures
• Keyboard Events
• Highest score
Microsoft Revenge of the Arcade
Ms. Pac-Man AI .NET
• Software toolkit developed for Ms. Pac-Man
AI contest
• Created by Jonas Flensbak and Georgios
Yannakakis
• Developed using Microsoft C# .NET
Ms. Pac-Man AI .NET
Screen Reader and Game State
Ms. Pac-Man AI .NET
Control Program
Ms. Pac-Man .NET
Read Screen
Send Joystick
Direction to Game
Determine Game
State
Process AI
Ms. Pac-Man Analysis
• High score
–Maximizing pills, ghosts, and fruit
–Avoiding death
• Ghost chasing – risk vs. reward
– “Luring” Ghosts
PEAS
• Performance
– Score
• Environment
– Maze, pills, ghosts, fruit
– Dynamic, non-deterministic, fully observable
• Actuators
– Up, down, left, right
• Sensors
– Screen Reader
Ms. Pac-Man Controller
• Multi-tiered Architecture
–Strategy
–Node weighting
–Graph search
Game State
Save Data
Overview
New
Direction
Determine State
Memory
Determine
Direction (Graph
Search)
Determine Node
Weights
Graph
Graph Search
• 3-D space-time graph
• Finds best paths
through time and
space
• Adapted from David
Silver’s “Cooperative
Pathfinding” (2006)
Dijkstra’s Algorithm
• Finds shortest of all paths within a certain
range of Ms. Pac-Man
• Determines direction toward shortest path
• Input: 3D space-time graph, maximum search
depth
• Output: best direction
A*
• Finds shortest path from Ms. Pac-Man to a
given goal node
• Uses an approximated distance to the goal
node to find shortest path
– Manhattan distance: |x1 – x2| + |y1 – y2|
• Input: space-time graph, goal node
• Output: direction to goal
Strategy Layer
• High level decision making
• Two level approach
–Behaviors
–Finite State machine
Behaviors
• Atomic components
• Independently control controller
behavior
• Used by node weighting
Behaviors
• Avoid Ghosts
• Avoid Power Pills
• Favor Pills Over Empty
Finite State Machine
• Determines…
– Active behaviors
– Which search algorithm to use
– Destination node (if any)
• Choosing a state…
– Ordered by priority
– Test preconditions
Finite State Machine
Chase Ghost
State
Eat Power Pill
State
Go To Nearest
Pill State
Eat Pills State
Chase Ghost State
• Behaviors: Avoid Ghosts, Avoid Power Pills
• Search Algorithm: A*
• Destination: The node of the ghost nearest to
Ms. Pac-Man
• Precondition: Ms. Pac-Man is near an edible
ghost
• Priority: 1
• Description: Steers Ms. Pac-Man towards the
nearest edible ghost.
Eat Power Pill State
•
•
•
•
Behaviors: Avoid Ghosts
Search Algorithm: A*
Destination: Nearest power pill node
Precondition: Ms. Pac-Man is near a power pill
and at least 3 ghosts are near to Ms. Pac-Man
• Priority: 2
• Description: Steer Ms. Pac-Man towards the
nearest power pill.
Go To Nearest Pill State
• Behaviors: Avoid Ghosts, Avoid Power Pills, Favor
Pills Over Empty
• Search Algorithm: A*
• Destination: Nearest pill node
• Precondition: The nearest pill node is outside
the max depth range
• Priority: 3
• Description: Steer Ms. Pac-Man towards the
nearest pill.
Eat Pills State
• Behaviors: Avoid Ghosts, Avoid Power Pills, Favor
Pills Over Empty
• Search Algorithm: Dijkstra
• Destination: none
• Precondition: Always true
• Priority: 4
• Description: Analyzes many different possible
paths Ms. Pac-Man can take and chooses the best
path among them.
Node Weighting
• Communicates between strategy and graph
search
• Creates 3-D, weighted, space-time graph
• Uses active behaviors
• Favorable nodes have a lower weight
Pill Weighting
• Breadth first traversal from Ms. Pac-Man’s
current node
• Nodes given weight based on type
– Walls: ignored
– Pills: 1
– Empty: 1 or 10 (Favor Pills Over Empty)
– Power Pill: 1 or 100 (Avoid Power Pills)
Power Pill Avoidance
• Weights power pills as
100 when parent node
is empty
• Will travel over all
nodes near power pill
Ghost Avoidance Weighting
• Avoid Ghosts behavior enabled
• Breadth first traversal for each ghost
• Weighted based on depth
– Weight = 1000 * (1 – t / max depth)
• Gives more weight to nodes closer to Ms. PacMan
• Accounts for imprecision in prediction as time
passes
Ghost Node Weighting
Results
• Highest score achieved: 14470
• Top 3 of IEEE WCCI 2008 contest
• Biggest Issues:
– Inaccuracies in screen reader
– Lag between screen captures
Future Work
– Improved Determination of Ghost to Chase
• Proximity to other ghosts
• Predict ghost movement
• Likelihood of catching ghost
– Improved Ghost Avoidance
• Predict by velocity of ghosts
• Account for power pills
– Improved Node Weighting
• Account for “dangerous” nodes
• Avoid “stranding” pills
Appendix
A*
100
100
20
Goal
60
10
60
10
Start
50
100
100
A*
100
100
20
Goal
60
10
60
10
Start
50
100
100
F(x) = 60 + 4 = 64
F(x) = 50 + 4 = 54
A*
100
F(x) = 60 + 4 = 64
100
20
Goal
F(x) = 60 + 3 = 63
60
10
60
10
Start
50
100
100
F(x) = 150 + 3 = 153
A*
F(x) = 160 + 2 = 162
100
100
F(x) = 60 + 4 = 64
20
Goal
F(x) = 120 + 2 = 122
60
10
60
10
Start
50
100
100
F(x) = 150 + 3 = 153
A*
F(x) = 160 + 3 = 163 F(x) = 160 + 2 = 162
100
100
20
Goal
F(x) = 120 + 2 = 122
60
10
60
10
Start
50
100
100
F(x) = 150 + 3 = 153
A*
F(x) = 160 + 3 = 163 F(x) = 160 + 2 = 162
100
100
20
Goal
F(x) = 140 + 1 = 141
F(x) = 130 + 1 = 131
60
10
60
10
Start
50
100
100
F(x) = 150 + 3 = 153
A*
F(x) = 140 + 0 = 140
F(x) = 160 + 3 = 163 F(x) = 160 + 2 = 162
100
100
20
Goal
10
F(x) = 140 + 1 = 141
60
10
60
10
Start
50
100
100
F(x) = 150 + 3 = 153
A*
Found Goal
100
100
20
Goal
10
60
10
60
10
Start
50
100
100