Transcript - Machine Intelligence Research Group (MInG)

Computational Intelligence, Analytics and
Computer Games
Dr. Zahid Halim
Faculty of Computer Science and Engineering
Ghulam Ishaq Khan Institute of Engineering Sciences and Technology, Topi.
[email protected]
Layout
• Why Computer Games ?
• Computational Intelligence and Computer Games
• Game analytics basics
• Game data mining
– Clustering
– Classification
– Association Rules Mining
2
Why Computer Games?
49% of U.S. households own a dedicated game console
32%
37%
Female
47%
Male
53%
Age
Under 18
31%
18-32
36 or more
The average game player age is:
30 years
3
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
4
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
5
Predator/prey Games
Search Space
• 14 X 14 grid excluding the boundary walls.
– No movement
• Couple of walls at fixed positions and of
– Clockwise
size 7 cells
– Counter clockwise
• There is one player controlled by the
– Random
human player.
• There are N (0-20)other pieces of M (1,2
– Random direction
•
and 3) types
– no effect
• Maximum duration 100 game steps
– random relocation to a new
• Finish game
location on the grid
– Agent dies
– Maximum score is achieved
– Maximum game steps utilized
•
Movement logic
Collision logic
– death.
•
Scoring logic
– +1, -1, 0
Chromosome Encoding for Genetic Algorithm
Number of predators
Movement logic
Collision logic
Red
0-20
Blue-Green
0-2
Green
0-20
Blue-Blue
0-2
Blue
0-20
Blue-Agent
0-2
Red
0-4
Agent-Red
0-2
Green
0-4
Agent-Green
0-2
Blue
0-4
Agent-Blue
0-2
Red- Red
0-2
Red- Red
-1,0,+1
Red- Green
0-2
Green-Green
-1,0,+1
Red-Blue
0-2
Blue-Blue
-1,0,+1
Red- Agent
0-2
Agent-Red
-1,0,+1
Green-Red
0-2
Agent Green
-1,0,+1
Green-Green
0-2
Agent-Blue
-1,0,+1
Green-Blue
0-2
Green-Red
-1,0,+1
Green-Agent
0-2
Blue-Red
-1,0,+1
Blue-Red
0-2
Blue-Green
-1,0,+1
Collision logic
Score logic
Entertainment Metrics
• Duration of the Game
D = ( nK0Lk )/n
(
• Appropriate Level of Challenge
• Diversity
• Usability
C=e
|S m  S a |
)
Sm
n
m
i 1
k 0
Div = ( ( (d k )))/n
n
m
i 1
k 0
U = ( ((  (C k )) / | Cu |))/n
Rule Based Controller
•
•
The controller looks up, down, left and right. It notes the nearest piece (if any) in each of
the four directions, and then it simply moves one step towards the nearest score
increasing piece
If there are no score increasing piece present it determines its step according to the
following priority list
– Move in the direction which is completely empty
– If more than one directions are empty move towards the farthest wall
– Move in the direction which contains a score neutral piece
– Move in the direction which contains a score decreasing piece
– Move in the direction which contains a death causing piece
Neural Network Based Controller
•
•
•
•
•
•
Multi-layer fully feed forward
6 neurons in the input layer
5 neurons in the hidden layer
4 output layer neurons
Sigmoid activation function ∆xr
Edges weights -5 to +5.
∆
yr
∆xg
∆yg
∆xb
∆yb
C
o
n
n
e
c
ti
o
n
E
d
g
e
s
C
o
n
n
e
c
ti
o
n
E
d
g
e
s
C
o
n
n
e
c
ti
o
n
E
d
g
e
s
Nu
Nd
Nl
Nr
Experimentation Setup
• 10 chromosomes are randomly initialized by the GA
• One offspring is created for each chromosome
– Duplicating it
– Mutating any one of its gene
• Results in 20 chromosomes from which 10 best chosen
• 100 generations
Duration of game
Predators
Movement logic
G
B
R
G
B
17
13
3
0
3
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
2
2
2
0
0
2
R
3
Predators
Movement logic
G
B
R
G
B
18
10
0
1
3
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
1
1
1
1
0
2
R
0
R-R
2
R-G
1
R-B
1
R-R
-1
G-G
-1
B-B
0
R-R
2
R-G
2
R-B
1
R-R
0
G-G
1
B-B
0
Collision logic
R-A
G-R
G-G
0
0
1
Scoring logic
A-R
A-G
A-B
-1
0
0
Collision logic
R-A
G-R
G-G
1
2
0
Scoring logic
A-R
A-G
A-B
1
-1
-1
G-B
0
G-A
2
B-R
1
G-R
-1
B-R
-1
B-G
0
G-B
0
G-A
1
B-R
1
G-R
1
B-R
-1
B-G
-1
(a)
(b)
Appropriate level of challenge
Predators
Movement logic
G
B
R
G
B
0
11
0
0
3
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
2
2
2
2
0
2
R
10
Predators
Movement logic
G
B
R
G
B
7
8
2
4
3
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
0
0
0
2
0
2
R
7
Diversity
Predators
Movement logic
G
B
R
G
B
10
0
2
4
2
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
1
0
2
1
0
2
R
0
Predators
Movement logic
G
B
R
G
B
17
0
4
4
4
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
1
1
2
1
0
2
R
0
R-R
0
R-G
1
R-B
2
R-R
-1
G-G
0
B-B
-1
R-R
1
R-G
2
R-B
0
R-R
-1
G-G
-1
B-B
0
Collision logic
R-A
G-R
G-G
1
2
0
Scoring logic
A-R
A-G
A-B
1
0
-1
Collision logic
R-A
G-R
G-G
0
0
1
Scoring logic
A-R
A-G
A-B
0
-1
-1
G-B
2
G-A
0
B-R
1
G-R
0
B-R
-1
B-G
-1
G-B
2
G-A
2
B-R
1
G-R
-1
B-R
1
B-G
0
(a)
(b)
R-R
1
R-G
2
R-B
1
R-R
1
G-G
1
B-B
-1
R-R
2
R-G
0
R-B
2
R-R
-1
G-G
0
B-B
0
Collision logic
R-A
G-R
G-G
1
0
0
Scoring logic
A-R
A-G
A-B
0
1
-1
Collision logic
R-A
G-R
G-G
2
0
0
Scoring logic
A-R
A-G
A-B
0
1
1
G-B
2
G-A
0
B-R
2
G-R
-1
B-R
1
B-G
0
G-B
2
G-A
1
B-R
2
G-R
1
B-R
1
B-G
0
(a)
(b)
Usability
Predators
Movement logic
G
B
R
G
B
18
19
1
2
2
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
2
2
0
2
0
2
R
20
Predators
Movement logic
G
B
R
G
B
20
20
4
4
2
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
2
0
2
2
0
2
R
19
R-R
2
R-G
0
R-B
0
R-R
1
G-G
-1
B-B
0
R-R
2
R-G
0
R-B
2
R-R
-1
G-G
-1
B-B
1
Collision logic
R-A
G-R
G-G
2
2
1
Scoring logic
A-R
A-G
A-B
1
0
0
Collision logic
R-A
G-R
G-G
2
2
2
Scoring logic
A-R
A-G
A-B
-1
1
1
G-B
2
G-A
0
B-R
2
G-R
-1
B-R
0
B-G
0
G-B
0
G-A
2
B-R
2
G-R
0
B-R
-1
B-G
-1
(a)
(b)
Predators
Movement logic
G
B
R
G
B
8
3
1
1
0
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
2
2
0
0
0
0
R
15
Predators
Movement logic
G
B
R
G
B
20
3
2
4
2
Collision logic
B -G
B-B
B-A
A-R
A-G
A-B
1
1
2
0
0
2
R
11
Combined Fitness
R-R
1
R-G
2
R-B
0
R-R
1
G-G
1
B-B
-1
R-R
2
R-G
2
R-B
0
R-R
0
G-G
1
B-B
1
Collision logic
R-A
G-R
G-G
0
1
0
Scoring logic
A-R
A-G
A-B
-1
-1
1
Collision logic
R-A
G-R
G-G
2
2
2
Scoring logic
A-R
A-G
A-B
-1
1
0
G-B
1
G-A
2
B-R
0
G-R
-1
B-R
-1
B-G
-1
G-B
0
G-A
1
B-R
1
G-R
-1
B-R
0
B-G
1
(a)
(b)
Controller Learning Ability
Random
Combined-ANN
Combined-RB
Usability-ANN
Challenge-ANN
Duration-ANN
Diversity-ANN
Usability-RB
Challenge-RB
Duration-RB
Diversity-RB
0
DiversityRB
No. Of Iterations
3
200
400
Duration- Challenge- UsabilityRB
RB
RB
5
6
1000
600
DiversityANN
71
800
1000
1200
Duration- Challenge- Usability- Combined- CombinedRandom
ANN
ANN
ANN
RB
ANN
1000
1000
64
320
310
63
Human User Survey
ANN Based Controller
Random
0%
Duration
4%
User Survey
• 10 subjects
• Conducted in two different sets on different days
–
–
–
–
Rule based controller
ANN based controller
Each individual was given 6 games
Play 2 times
Random
0%
Combine
d Fitness
40%
Challenge
32%
Usability
24%
Diversity
0%
Human User Survey
Rule Based Controller
Duration
12%
12
10
8
6
4
2
0
Combined
Fitness
47%
Rule Based Controller
ANN Based Controller
Challenge
23%
Usability
18%
Diversity
0%
Research in Computer Games
• Game User Research (GUR)
• Game analytics is becoming and increasingly important area of BI for
industry
• Key terms
– Game analytics
– Metrics
– Telemetry
– Used interchangeably
• Games released in patches
– Based on telemetry release subsequent patches
16
Game data mining
• Modern digital games
– Simple applications
– Incredibly sophisticated information systems
– Common for all is that need to keep track of the actions of players and
calculate a response
• Telemetry data
17
Few examples of game data mining
•
•
•
•
•
•
•
•
•
Find weak spots in a games’ design
Figure out how to convert non-paying to paying users
Discover geographical patterns in our player community
Figure out how players spend their time when playing
How much time they spend playing
Predict when they will stop playing
Which assets that are not getting used
Develop better AI-controlled opponents
Explore and use of social grouping
18
Data Formats
• Game telemetry is importantly concerned about how data are stored and
accessed.
• SQL has problems with scaling up
– SSD enhancements
– More “elastic” means of data storage on cloud computing
– These new database formats are commonly referred to as “NoSQL”
(and NewSQL) and have become popular in big data contexts due to
the need for fast, efficient data access.
• MongoDB
• Cassandra
• Couch
• HBase (Hadoop)
19
Tools
•
•
•
•
www.gameanalytics.com
www.playtomic.com
www.honeytracks.com
www.kontagent.com
20
Clustering Players – Battlefield 1/3
•
First person shooter with tactical wargame elements,
– Online multiplayer
– Up to 32 players
– Including off-line capability.
•
•
•
BF2BC2 (battlefield 2 bad company)
Each player controls one character in a team, playing against another team.
Modes of play = “kits”
– Assault, Demolition, Specialist, Recon and Support
•
Drachen et al. ( 2012 ) used behavior telemetry data from randomly selected 10,000 BF2BC2 players, all
playing on PC.
A total of 11 variables (features) were included in their analysis
– Score
– Skill level
– Total playtime
– Kill/Death ratio
– Accuracy
– Score per minute
– Deaths per minute/Kills per minute
– Rounds played
– Kit stats
– Vehicle use
•
21
Clustering Players – Battlefield 2/3
•
•
•
•
Pre-processing and normalization of the telemetry data
Applied Clustering
K-means
Simplex Volume Maximization (SIVM)
– Does not look for commonalities between players, but rather extreme
profiles that do not reside in dense cluster regions
– Both algorithms resulted in seven clusters.
22
Clustering Players – Battlefield 3/3
•
•
•
•
•
•
•
Assassins
– Extremely high Kill/Death ratios but surprisingly low-middle playtime.
Veterans
– Are the all-round elite.
– Represent a small fraction of the players, 2–4%.
Target dummies
– Opposite of the Veterans.
Assault-Recon
– High performance with some of the kits
– They also exhibit low accuracy
– About 1.5% of the players are included in this cluster
Medic-Engineer
– Very high skill levels and accuracy, score, drive in vehicles a lot.
Assault
– They die a lot
– Have invested a lot of playtime into the game, with low skill, K/D ratio and accuracy.
Driver Engineers
– Have extremely high vehicle times - driving, sailing or flying the various kinds
– They have high playtimes, scores and accuracy, very high K/D ratio but kill very few
players, and also die rarely
23
Classification --Tomb Raider: Underworld 1/2
• Self-Organizing Map
– A form of ANN looks for lowdimensional representations of the
input data
• Used gameplay metrics data from 1,365
players of Tomb Raider: Underworld
• SOM used to classify players into distinct
groups based on their behavior. The
analysis revealed four distinct classes of
behavior.
24
Classification --Tomb Raider: Underworld 2/2
• Class 1 (Veterans)-(8.68%)
– Very few death events
– Fast completion times. Generally perform very well in the game
• Class 2 (Solvers)-(22.12%)
– Die rarely
– Take a long time to complete the game
• Class 3 (Pacifists)-(46.18%)
– Dying primarily from enemies
– Completion time relatively fast and help requests minimal
• Class 4 (Runners)-(16.56%)
– Die often and by enemies & environment
– Often use of help system but complete the game very fast
25
Frequent Pattern Mining
• Frequent Sequence Mining
• By virtue of being discrete-time systems, computer games constantly
generate large amounts of sequential data.
26
Thank you for your patience
This presentation is uploaded at
http://ming.org.pk/zahid.htm
Questions
Bibliography
• Halim, Z., R. Baig, and K. Zafar. "Evolutionary Search in the Space of Rules
for Creation of New Two-Player Board Games." International Journal on
Artificial Intelligence Tools (2013).
• Entertainment Software Association. "Essential facts about the computer
and video game industry." (2012).
• El-Nasr, M. S., Drachen, A., & Canossa, A. (2013). Game
analytics:Maximizing the value of player data. Springer.
28