Transcript Computational Intelligence in Games

Computational Intelligence in Games: An
Overview
Zahid Halim
Faculty of Computer Science and Engineering
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi.
[email protected]
Layout
•
•
•
•
•
•
What is AI/CI and ML
Why Computer Games?
How CI helps computer Games?
Some Examples
Key venues to publish work
Future directions
12/19/2012
Computational Intelligence in Games: An Overview
2
AI vs. CI vs. ML
•
•
•
Artificial Intelligence (Think like human, learn from experience, recognize patterns, make
complex decisions based on knowledge and reasoning)
– Machine learning
– Knowledge representation
– Natural Language Processing
– Planning Robotics etc.
Machine learning
– Branch of AI
– Construction and study of systems that can learn from data
– Email messages to learn to distinguish between spam and non-spam messages
– There is difference between ML and Data Mining too 
Computational Intelligence (www.ieee-cis.org)
– Integrating the fields
• Artificial Neural Networks
• Evolutionary Computation
• Fuzzy Logic
12/19/2012
Computational Intelligence in Games: An Overview
3
They are related… But they are all different…
I hope all of us understand difference between hard and soft computing
CI
ML
AI
12/19/2012
Computational Intelligence in Games: An Overview
4
Why Computer Games?
49% of U.S. households own a dedicated game console
32%
37%
Female
47%
Male
53%
Under 18
31%
18-32
36 or more
The average game player age is:
12/19/2012
Computational Intelligence in Games: An Overview
30 years
5
Why Computer Games?
•
42% of game players believe that computer and video games give them the most value for
their money, compared with DVDs, music or going out to the movies
•
Gamers who are playing more video games than they did three years ago are spending less
time:
– 59% playing board games
– 50% going to the movies
– 47% watching TV
– 47% watching movies at home
•
•
62% of gamers play games with others, either in-person or online
78% of gamers who play with others do so at least one hour per week
12/19/2012
Computational Intelligence in Games: An Overview
6
Money Matters! But its not every thing!
Total:
$24.75
Billion
16
16.9 16.6
Consumer Spend on Games Industry
2011
Accessories
Dollars (Billions)
Hardware
Contents
11.7
11%
9.5
6
6.9
7
7.3
6.9
7.3
22%
67%
2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011
12/19/2012
Computational Intelligence in Games: An Overview
7
What can Computational Intelligence do?
•
•
•
•
•
•
•
Generate complete game
Creation of intelligent game characters
Creation of entertaining game characters
Generating tracks for racing games.
Adaptable player experience.
Levels for action games.
Generating maps for games.
12/19/2012
Computational Intelligence in Games: An Overview
8
Procedural Content Generation
•
•
•
•
Lindenmayer system: A variant of a formal grammar, most famously used to model the
growth processes of plant.
Consists of:
– An alphabet of symbols that can be used to make strings
– A collection of production rules which expand each symbol into some larger string of
symbols
– An initial "axiom" string from which to begin construction
– A mechanism for translating the generated strings into geometric structures.
PCG can also generate weapons that player might require in a game
Search based PCG is different
12/19/2012
Computational Intelligence in Games: An Overview
9
Some of the PCG based Games
12/19/2012
Game
Content
Year
ToeJam & Earl
The random levels were procedurally generated.
1991
The Elder Scrolls III: Morrowind
Water effects are generated on the fly."Water
Interaction" demo.
2002
RoboBlitz
XBox360 live arcade and PC
2006
Borderlands
Weapons were generated depending upon the levels
2009
Terraria
2D landscape was generated that a player can travel
around.
2011
Computational Intelligence in Games: An Overview
10
Automated Game “entertaining” Generation
Search Space
Dimension
Play Area
Types of Pieces
Number of
pieces/type
Initial position
Movement direction
Step Size
Capturing Logic
Game ending logic
Conversion Logic
Mandatory to capture
Turn passing allowed
12/19/2012
Possible Values
Checkers
Chess
Only black squares are
Both white & black
used
squares are used
Initially 1, maximum 2
6
12, variable (but max.
16
12)
Black squares of first 3
Both white & black
rows
squares of first 2 rows
Diagonal forward and
All directions, straight
Diagonal, forward
forward, straight
backward
forward and backward,
L shaped, diagonal
forward
One Step
One Step, Multiple
Steps
Step over
Step into
No moves possible for
No moves possible for
a player
the king
Checkers into king
Soldiers into queen or
any piece of choice
Yes
No
No
No
Select Values
Gene
Title
Value
Placement of gene of each type
0-6
Movement logic of each type
1-6
Step Size
0/1
Capturing logic move into cell or jump over 0/1
0/1
Piece of honour
0-6
Conversion Logic 0-6
0-6
Mandatory to capture or not
0/1
1
Both white & black squares are
used
6
variable but at maximum 24
:
24
25
:
Both white & black squares of
first 3 rows
All directions, straight forward,
straight forward and backward,
L shaped, diagonal forward
30
31-36
37
:
42
43
One Step, Multiple Steps
Step over, step into
No moves possible for a player,
no moves possible for the king
Depends upon rules of the game
44
:
49
50
Depends upon rules of the game
No
Computational Intelligence in Games: An Overview
11
I = (
n
K 0 k
I )/n
Objective Function
D = ( nK0Lk )/n
Duration of game (D)
n
m
Dyn = ( (( (Ci ) / Li )/m))/n
1
Scaled value of D
j1
1.2
i 1
0.8
0.6
0.4
0.2
n
m
i 1
k 0
0
1
U = ( ((  (C k )) / | Cu |))/n
•
•
•
•
•
4
7 10 13 16 19 22 25 28 31 34 37 40 43 46 49 52 55 58 61 64 67 70 73 76 79 82 85 88 91 94 97 100
1+1 Evolutionary Strategy (ES)
10 chromosomes are randomly initialized
The evolutionary algorithm is run for 100 iterations
Mutation only with probability of 30 percent
One parent produce one child
– Fitness difference is calculated
– If it is greater than 4 (at least half times better) child is promoted to the next population
FitnessDif ference 
 (1  (( fitness
p
 fitnessc ) / fitness p ))
for _ all _ metrics
12/19/2012
Computational Intelligence in Games: An Overview
12
Making Racing Fun Through Player Modelling and
Track Evolution
•
We have one or several car racing tracks with
– Walls, Waypoints, Staring position of the car
•
Car consist of
– Sensor model to sense the environment
– Discrete set of control commands
•
Objective of the game is to pass as many waypoints in given timesteps.
•
Car has 6 sensors, Speed of the car and Angle to the next waypoint
•
•
•
•
Fully connected feedforward nets (MLPs) with the tanh transfer function.
Only the weights of the networks are changed by evolution or back propagation
Nine inputs (sensors and a bias input), Six hidden neurons
Two output neurons are used.
– The First output is interpreted as driving command
– Second as steering command.
12/19/2012
Computational Intelligence in Games: An Overview
13
Learning Behaviour: Backpropagation
•
•
•
•
•
Human player drove a number of laps around a track, while the inputs from sensors and
actions taken by the human were logged at each timestep.
This log was then used to train a neural network controller to associate sensor inputs with
actions using a standard backpropagation algorithm.
Several variations on this idea were tried with very little success.
Training often achieved low error rates (typically 0.05), none of the trained networks
managed to complete even half a lap.
A small amount of noise that is applied to sensors guarantees that the car does not simply
replay the human action.
12/19/2012
Computational Intelligence in Games: An Overview
14
Evolving Neural Network Agents in the NERO Video Game
– real-time NeuroEvolution of Augmenting Topologies (rt-NEAT) method for evolving
increasingly complex artificial neural networks in real time, as a game is being
played.
– rtNEAT makes possible a new genre of video games in which the player teaches a
team of agents through a series of customized training exercises.
– In NEAT, the population is replaced at each generation.
• Everyone’s behaviour would change at once.
• Behaviours would remain static during the large gaps between generations
– In rtNEAT, a single individual is replaced very few game ticks
12/19/2012
Computational Intelligence in Games: An Overview
15
Conferences and Journals
•
•
IEEE Computational Intelligence and Games
IEEE Transactions on Computational Intelligence and AI in Games (IF 1.8)
•
•
•
International Journal of Computer Games Technology
International Conference on Computer Games (CGAMES)
CGamesUSA International Conference on Computer Games
12/19/2012
Computational Intelligence in Games: An Overview
16
Where are the opportunities?
•
•
•
•
CIG for health care
CIG for education
Neuro Computer interface for games
Physicological study via games
12/19/2012
Computational Intelligence in Games: An Overview
17
Thanks for your patience
Presentation available at: http://ming.org.pk/zahid.htm
Bibliography
•
Halim, Zahid, A. Rauf Baig, and Hasan Mujtaba. "Measuring entertainment and automatic generation of entertaining games."
International Journal of Information Technology, Communications and Convergence 1.1 (2010): 92-107.
•
Halim, Zahid, A. Rauf Baig, and Mujtaba Hasan. "Evolutionary Search For Entertainment In Computer Games." Intelligent
Automation & Soft Computing 18.1 (2012): 33-47.
•
Halim, Zahid, and A. Raif Baig. "Evolutionary Algorithms towards Generating Entertaining Games." Next Generation Data
Technologies for Collective Computational Intelligence. Springer Berlin Heidelberg, 2011. 383-413.
•
http://tim.hibal.org/blog/wp-content/uploads/2010/01/speciesChange.png
•
http://www.sennir.co.uk/Journal/178
•
ESA 2012 Sales, Demographic and Usage Data
•
Evolving Neural Network Agents in the NERO Video Game, Stanley et. al
•
Acquiring Visibly Intelligent Behavior with Example-Guided Neuroevolution, Bryant et. al.
•
Making Racing Fun Through Player Modeling, Togelius et. al.
•
Evolutionary Search for Entertainment in Games, Halim et. al.
12/19/2012
Computational Intelligence in Games: An Overview
19