Transcript Probability and Bayesian Theory for Games

What is Probability?






Hit probabilities
Damage probabilities
Personality (e.g. chance of attack, run, etc.)
???
Probabilities are used to add a little
uncertainty into the game AI in terms of
decision making (most of the time), strategy
and tactics, and even spawn occurrences
We look at some examples…




Generation of random numbers
Common practice  Seeding random
numbers
Random numbers can be fed into various
game AI – movement, decision-making ,
strategy to provide a sense of randomness
May not reflect behaviors intelligently


Representing a character’s chances of hitting
and opponent in combat or battle
Typically, a game developer defines several
probabilities (RPG game e.g.)
◦ Moderate dexterity – 60% prob. of striking with
knife in melee
◦ High dexterity – 90% prob. of striking with knife

Probabilities can be adjusted given other
factors (High dex e.g.)
◦ 95% -- in possession of “Dagger of Speed”
◦ 85% -- opponent has magic armour

Design hit probability tables to calculate the
appropriate probability given the occurrence
or non-occurrence of any number of events
or conditions

Define abilities of character classes using
probabilities
Ability
Wizard
Fighter
Rouge
Ranger
Use magic 0.9
0.05
0.2
0.1
Wield
sword
0.1
0.9
0.7
0.75
Harvest
wood
0.3
0.5
0.6
0.8
Pick locks 0.15
0.1
0.05
0.5
Find traps 0.13
0.05
0.2
0.7
Read map 0.4
0.2
0.1
0.8
…
…
…
…
…

In practice, these probabilities can be further
conditioned on the overall class level
◦ A first-level wizard might have only 10% chance of
using magic
◦ The idea here is that as the player earns levels, his
proficiency in the craft increases (reflected by the
probabilities)

On the computer-side of the game AI, other
characters in the world can have their own set
of probability tables…

Combine probabilities with state transitions
in a FSM

Instead of deterministically selecting a state
to move to, assign certain probabilities to
each transition
◦ 50% chance of attacking, 20% chance of fleeing,
10% chance of hiding


For even more variability, assign different
probabilities to different types of characters,
making some more aggressive than others,
etc.
A step further  distinct personalities?

How do we implement this efficiently?

Update certain game probabilities as the
game is played to facilitate computercontrolled AI learning and adapting (Nondeterministic AI)
◦ E.g. Collect statistics on the number and outcome
of fights between different characters
◦ Probability of encounters resulting in a win (or
death) can be calculated real-time
◦ Use this change of probabilities to make future
decisions on whether to engage in battle or avoid
certain characters or flee battle, etc.

3 common interpretations of probability
◦ Classical Probability
◦ Frequency Interpretation
◦ Subjective Interpretation




Refers to events and possibilities, or possible
outcomes
Given an event E, which can occur in n ways
out of a total of N possible outcomes, the
probability p of occurrence of the event is:
p = P(E) = n/N
P(E): Probability of success of the event
Probability of failure of the event: 1-P(E)


E.g. Rolling a six-sided dice, the probability
that a 4 would show up is…?
Consider two six-sided dice, both rolled at
the same time, what is the probability that
the sum of the numbers that show up equal
to 5?




Also known as relative frequency or objective
probability
Considers events and samples or experiments
If an experiment is conducted N times and
some event E occurs n times, the probability
of E occurring is:
P(E) = n/N as N
For finite number of experiments, the
resulting probability will be approximate or
empirical  derived statistically

Frequentist approach: Coin tossed 1000
times
◦ Experimentally, the results could come to getting
heads 510 times (e.g.), so the probability of getting
heads is
P(heads) = 0.51 or 51%


Should “approach” 0.5 if number of
experiments increase…
Approximation by experiment


A measure, on a scale from zero to one, of a
person’s degree of belief that a particular
event will occur given their knowledge,
experience or judgment.
Useful when the event in question is not
repeatable (therefore, can’t use frequentist
approach)


“It probably will rain tomorrow”, “I have a
good chance of passing this subject”
More empirical e.g. “I have a 75% chance of
passing this subject”
◦ If you later did better in the next
homework/assignment, you might revise you belief
that you have a 90% chance of passing the subject

Bayesian theory
◦ Allows us to update our belief of some event given
the availability of new information
Odds
◦
◦
Common in betting scenarios
If we say the odds in favour of success of some
event E, are “a to b” (3 to 1 odds, e.g.), the
probability of success of that event, P(E)
P(E) = a / (a+b)
◦
Can work the opposite direction, given the
probability  work out the odds
Expectation
◦
Expected value of some discrete random variable X
that can take on any values, x0, x1,…xn with
probabilities p0, p1,…pn can be determined as:
◦
For such a distribution, you can think of
expectation as an average value
Measure of central tendency, measure of payoff
◦
Expectation
◦
◦
◦
◦
E.g. Online RPG – monitoring the
number of players who gather at a
local tavern/inn each evening –
collecting intelligence
Table shows the probabilities of
no. of players each evening
In this case, what is the expected
number of players in the tavern in
the evening?
What use is this information?
# Players
Probability
0
0.02
2
0.08
4
0.20
6
0.24
8
0.17
10
0.13
12
0.10
14
0.05
16
0.01


Difficult to pin down subjective probabilities
to a specific method or number
Fine-tuning or “hacks” can be used
When events are not independent, they are
“conditional”

◦
◦
◦
E.g. if you find your lawn wet, what is the
probability that it rained while you were at work? Is
it possible that someone turned on your sprinklers
while you were at work?
Outcome of your grass being wet is “conditional”
upon whether it rained, or whether someone
turned on your sprinkler.
Bayesian analysis
◦
If event A depends on whether event B occurred,
we can’t use typical probability calculations
P(A|B)
◦
◦
Probability of A occurring given B has occurred:
P(A|B)
Probability of B occurring given A has occurred:
P(B|A)
P(A|B)  P(B|A)
◦
To find the compound probability of both A and B
occurring, we say
P(A  B) = P(A) P(B|A)
◦
But usually we are interested in the probability of
an event given some other event has occurred
P(B|A) = P(A  B)/P(A)
= P(B) P(A|B) / P(A)
◦
Posterior = likelihood * prior
--------------marginal likelihood
Example 1: A melee attack by a wizard
character, with additional magical aid

◦
To determine the probability of a melee hit given
magical aid
P(hit) = 0.9, P(~hit) = 0.1
P(magic|hit) = 0.85
P(magic|~hit) = 0.15
P(hit|magic) = (0.9)(0.85) / [(0.9)(0.85)+(0.1)(0.15)]
= 0.765/0.78
Indicating stronger probability of
= 0.981
hitting given magical aid

Example 2: A 1-on-1 fight between a warrior
(fighting ability) and a wizard (magic ability)

To determine the attacking (hit) probability of the
warrior given the wizard’s magical ward defense
C1: P(A) = 0.8, P(~A) = 0.2
C2: P(D|A) = 0.3
P(D|~A) = 0.7
P(A|D) = (0.8)(0.3) / [(0.8)(0.3)+(0.2)(0.7)]
= 0.24/0.38
Indicating weaker warrior attack
= 0.632
probability given magic defense from
wizard

Bayesian inference, Bayesian networks for
adding uncertainty to decision making (refer
to textbook Chapter 13)