Game Theory

Impartial Games, Nim, Composite Games,

Optimal Play in Impartial games

Telerik Software
Learning
&
Academy

http://academy.telerik.com
Development Team

Table of Contents (1)

1.

What is Game Theory?

2.

Types of combinatorial games and

plays
Impartial, Partisan
Normal & misre play

3.

Game States
Turns; P, N positions
Optimal play
"Scoring" game example

Table of Contents (2)

3.

The Game Nim

Gameplay, winning positions

4.

Composite games
Tweedledum & Tweedledee
principle
Sprague-Grundy Theorem

5.

Calculating Grundy Numbers

Minimal excludant
3

WTF Game Theory?

What are The Facts on Game Theory

What is Game Theory?

Study of decision making
Mathematical models

Of conflict
Of cooperation
Between intelligent decision makers

Started with study of zero-sum

games
One player winning leads to other
player losing

Evolved into "decision theory"

General decision making strategies

Game Theory
Concepts

Players, Actions, Payoffs,

Information (PAPI)

Key concepts to describing a game

Solution strategy is based on PAPI
Solution strategy + PAPI =
predictable, deterministic outcomes
to games

Game theory fields of application

Politics, Economics
Phycology, Biology, Logic
All fields needing info on behavioral

Game Theory Game

Types

Notable general game

classifications

Perfect vs. imperfect information

Cooperative vs. competitive
Symmetric vs. asymmetric
Combinatorial
Infinitely long
Discrete vs. continuous, differential,
population, stochastic,
metagames
7

Combinatorial Games
Impartial, Partizan and Play Types

Combinatorial Games

Definition of a combinatorial game

Two players move alternatively

No chance devices
Perfect information
The game must eventually end
Winner depends on who moves last no
draws

Perfect information players know at

any time:
Game state
All possible player moves
No chance devices
Actions are not random and do not
depend on random events

Combinatorial Game
Examples

Examples of combinatorial games

Chess (partly)
Hex 7
Checkers
Take-away & Subtraction games
Silver-dollar game

Partisan vs. Impartial

Partisan games
Different moves available to different
players
Chess, Checkers, Tic-Tac-Toe are
partisan

Impartial games
Different players have the same moves
Examples Nim, Quarto

Impartial games can be generalized

and analyzed
Very strong base for studying other
games

Combinatorial Games

Play types determine which player

wins
Based on who moves last
Normal play
Player which makes last possible
move wins
E.g. player who takes the last coin
and wins
Misre play
Player which makes last possible
move loses
12

Game States &

Positions
Turns, P and
N Positions in Optimal
Play

Game States Chips

Game chips (or pieces)

A chip is something a player
controls
E.g. figures in chess, stack(s) of
coins, numbers to operate on, etc.

Chips are always in some state (i.e.

position)
A position can be winning or losing

14

Game States Turns

Impartial games are played in turns

Turns can be broken down like so:
Blue
moves

Blue
"thinks
"

Yellow
moves

Yellow
"thinks
"

Blue
moves

Blue
"thinks
"

Yellow
"thinks
"

Positions are usually the "thinks"

stage
Impartial game states positions &

Game States Player

Position

Position of a player
Depends on the positions of all the
chips
Considered in the "think" stage
Immediately after the other player
moved
Immediately before the current
player moves

Two types of positions

Good for current player (i.e. next to
move)
Good for previous player (i.e. who

16

Game States Optimal

Play

Impartial games are deterministic

Optimal play always exists
Player position either winning or
losing
Optimal play in impartial games
Best actions by player, in order to
win
Optimal play + winning position =
victory
So, N and P positions for the current
player:
17

How to Play Optimally

Which positions to choose to win?

Impartial games are zero-sum
Positions are either winning or
losing
Try to force other player into losing
position
i.e. a P-position (good for previous
player -> us)

If we are in a losing position, we

cant win
if other player plays optimally
18

Game of Scoring

Scoring is a game where a single chip

is moved
Right to left, starting at a
numbered position
Moves have maximal step e.g. 3
positions
Move chip by no less than 1 and no
more than 3

0 (zero) is the leftmost position

Cant move from that position

Player which cannot move is the

loser

19

Game of Scoring
Demo

Lets try to determine P and N

positions
Max step is 3
0

20

Game of Scoring
Positions

0 losing (P-position)
1, 2, 3 winning positions (Npositions)
We can immediately move the chip
to 0
4 losing position (P-position)
We place chip at 1, 2 or 3 and other
player wins
5, 6, 7 winning positions (Npositions)
Can place other player in a losing
position (4)

21

Generalization of
Positions

For all impartial games

A position is winning if it can lead
to at least one losing position
A position is losing, if it leads only
to winning positions
This regards single-chip games
P-position

N-position

Every option leads

to anN-position

There isalwaysat
least one option
that leads to aPposition
22

Solving Scoring in C+
+
Live Demo

The Game Nim

Gameplay, Positions,
Nimbers and Nim-sum

Nim

Ancient, but fundamental game

Impartial, Many variations
Nim theory developed early 20th
century
Important related terms nimbers,
Nim-sum
Rules
Several heaps (piles) of stuff
(coins/stones/...)
Player takes 1 or more elements
from 1 pile
25

Nim formal notation

Nim state is easy to express formally

If the number of heaps is k
Then (n0, n1, , nk) is the state
n0 is the number of items in the first
heap, etc.

State is often referred to as position

If we have 3 heaps of sizes 3, 4 and
2
Then we are at
position (3, 4, 2)
Position (0) is losing
26

Nim Demo

Lets play Nim

index

5
27

Nim Observations

What happens for Nim with 1element heaps?

a) (1) obviously, first player wins (N)
b) (1, 1) first player takes a heap,
second wins (P)
c) (1, 1, 1) first player forces second
player to case b), so second player
will lose (N)
d) (1, 1, 1, 1) first player goes into
case c), so second player will win (P)

Nim with k 1-element heaps

)Winning position if k is odd

28

Nim More
Observations

What happens for Nim with 1element heaps mixed with 2-element
heaps?
a) (1, 2) first player wins (winning
position)
first player can reduce 2 to 1
player 2 forced into (1, 1), which is
losing

b) (2, 2) other player wins (losing

position)
First players moves are to (1, 2) or
2) and (2, 1)(0,
are also
but with the same outcome, so we will not consider them
2)possible,
*
29

Nim General
Observations

We could go on generating positions

That would take too much
(exponential) time
Another pattern can be noticed
a) Even same-sized heap count bad
position
b) Odd same-sized heap count good
position
c) b) + one larger heap good
position
can move to position a) by reducing
larger heap

30

Nim-sum

Nim-sum (aka XOR, ^, addition

modulo two)
The Nim-sum of a position (n0, , nk)
is
A n0
non-zero
denotes a winning
^ n1 Nim-sum
^ ^ nk
position
A zero Nim-sum denotes a losing position

Accredited to Charles L. Bouton as

part of the solution of the game
Mathematical notation typically:
n0 n1 nk
Heap sizes are usually called

31

Nim-sum Why it
Works

Position (0) has a Nim-sum = 0

No moves can be made position is
losing

Position (k) has a Nim-sum > 0

> 0)

(k

Player takes the entire heap position

is winning

Changes to a position with Nim-sum

=0
Always lead to positions with Nim-sum
>0

Changes to a position with Nim-sum

32

Nim-sum Finding
Positions

Considering we are in a winning

position
Need to search for positions with
Nim-sum zero
Finding a zero Nim-sum position
Decrease numbers, which make the
Calculate
the current
Nim-sum
> 0 Nim-sum
Finds its leftmost bit equal to 1
(denotes
Achieve
evenwith
number
of 1sofin1s)
each
a column
an odd number
Findbit
any column
number N (heap size) having a 1 at that
bit
Nullify that number N
Calculate the Nim-sum again
Set the nullified number N to the new Num-sum

33

Solving Nim in C++

Live Demo

Nim Importance

Whats the big deal with Nim?

The Sprague-Grundy theorem
Who?
R. P. Sprague & P. M. Grundy in
1935 & 1939
Independently discovered the
theorem
EverySprague-Grundy
impartial game, under
normal states:
The
theorem
play is equivalent to a nimber

Laymans terms: every impartial

game is a Nim in disguise or some

35

Nim Importance

Consider the game Nimble

Several coins, at some positions
Must move exactly one coin at least
1 position
Coins move only right to left
(towards zero)
Player who moves the last coin to 0
wins

36

Nim Importance

How about now?

The solutions of Nimble and Nim are
equivalent
After indices are turned into heap
sizes

index

5
37

Composite Games
Dividing into Subgames,
Tweedledum & Tweedledee
Principle, Sprague-Grundy

Game of Scoring
Demo

Lets play Scoring again

This time with 2 chips
Max step is 3
Are the marked P/N (make them
win/lose if you want) positions
correct in this case?

39

Composite Games 2
Chips

Tweedledum & Tweedledee Principle

2-chip game, the second player can
mimic moves
If the two chips are in the same position
Leading to victory for the second player
In positions which would be winning for
the first player in a single-chip game
Losing positions remain losing, problem
is with winning ones

Similar cases occur in games with

more chips
And more equivalent positions

40

Composite Games
Solving

Composite impartial games

Equivalent to nimbers (as other

impartial games)
As per the Sprague-Grundy theorem
Yep, these guys again

A game has k chips, each with a

position,
Game position set of k numbers (n0,
, nk)
Equivalent to a position in Nim, hence
Nim-sum of the position = 0 -> position is
losing
41

Calculating the
Sprague-Grundy
Function
Follower positions,
Minimal excludent

Calculating SG function

Sprague-Grundy function
Recursively generates "Grundy"
values/numbers
Numbers correspond to heap sizes
in Nim
Adapt to specific game through
Follower function
Mex function

43

Calculating SG function

Sprague-Grundy function formal

description:
g(p) = Mex(g(q)); q
F(p)

g Sprague-Grundy function
F follower function
Mex minimal excludant
p and q two game positions

44

Calculating SG function

Follower function F(position)

Returns positions, reachable in 1
move from given position
i.e. "followers" of that position
Minimal excludant Mex(numbers)
Returns the minimal non-negative
number
Not belonging to a given set

i.e. first number different than any

of the given numbers
45

Calculating SG function

So, thisg(p) = Mex(g(q)); q

F(p)
reads as
follows:
The Grundy value of position p
Is the minimal non-negative integer
Which is NOT a Grundy value of
Any of the followers of position p

46

Calculating SG
example

Grundy values
g(0)
with Scoringg(1)

= 0, by definition.
= 1 since F(1) = {0}.

Losing
g(2) = 2 since F(2) = {0,
positions in
g(3) = 3 since F(3) = {0,
a game have
g(4) = 0 since F(4) = {1,
g() = 0
- The values of g on F(4)
Here, cant and the minimum that does
there is 0.
move from 0,
so we lose g(5) = 1 since F(5) = {2,
- The values of g on F(5)
there and and the minimum that does
there is 1...
g(0) = 0
Index
0
1
2
3
4
SG value

1}.
1, 2}.
2, 3}.
are {1, 2, 3}
not appear
3, 4}.
are {2, 3, 0}
not appear
5

1
47

Calculating SG
pseudocode

Grundy valuesint GrundyNumber(position pos)

pseudocode { moves[] = Followers(pos);
s;
Walk positions set
for (all x in moves)
{
recursively
insert into s GrundyNumber(x);
Generate set }
//Mex return smallest non-zero
of Grundy
//integer, not in s;
int mexCandidate=0;
values for
while (s.contains(mexCandidate))
followers
{
mexCandidate++;
Take the Mex
}
of the Grundy return mexCandidate;
values of the }followers
48

Solving Composite
Games Using SG & Nim

Determining a position as winning or

losing
We have the positions of the chips
in the game
We have the Grundy values of those
positions
Hence, we have the Nim position:
(g(p0), g(p1), g(pk))
Where p0 p1 are the chip positions

So, we can compute the Nim-sum

If it is zero, we are in a losing

49

Solving
Multi-Chip Scoring
in C++
Live Demo

Conclusion

What we covered
Impartial games
Winning and losing positions (N and
P)
Nim and representing impartial
games as Nim
Sprague-Grundy theorem & function
Solving composite games

51

Conclusion

What we havent covered

Misre play
Partizan games
Non-deterministic games
The above share some characteristics
with impartial games
Most games are describable by mathematical
models, which are based on similar concepts to
those in the lecture. Just take your time to
unravel the model here, programming is the
easy part once youve understood the logical
base of the problem.
52

Game Theory
?

?
?

BG Coder - - online judge

,
ASP.NET - , , C#, .NET, ASP.NET
ASP.NET MVC HTML, SQL, C#, .NET, ASP.NET MVC
,
iPhone, Android, W P7, PhoneGap
-
-
C# , ,

?
,



SEO -
,
, HTML, CSS, JavaScript, Photoshop
free C# book, C#, Java, C#
" "
" cloud "

Questions?

http://algoacademy.tele