Transcript single-chip games

Basic Game Theory
IMPARTIAL GAMES, NIM, COMPOSITE GAMES,
OPTIMAL PLAY IN IMPARTIAL GAMES
Table of Contents (1)
• What is Game Theory?
• Types of combinatorial games and plays
•
•
Impartial, Partisan
Normal & misère play
• Game States
•
•
Turns; P, N positions
Optimal play
• "Scoring" game example
2
Table of Contents (2)
• The Game Nim
•
Gameplay, winning positions
• Composite games
•
•
Tweedledum & Tweedledee principle
Sprague-Grundy Theorem
• Calculating Grundy Numbers
•
Sprague-Grundy function
3
What is 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
5
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 relations
•
6
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, PARTISAN 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
9
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
• Many partisan games, but with similar principles
10
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 wins
• Misère play
•
•
Player which makes last possible move loses
Aim to force the other player into the last move
11
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
In other words, good for next or for previous player
13
Game States - Turns
• Impartial games are played in turns
•
Positions are usually the "thinks" stage
Blue
moves
Blue
"thinks"
Yellow
moves
Yellow
"thinks"
Blue
moves
Blue
"thinks"
Yellow
"thinks"
• Impartial game states – positions & count of chips
14
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 just moved)
Usually noted P (previous) and N (next/current)
15
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:
•
•
N – Winning positions
P – Losing position
16
How to Play Optimally
• 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 can’t win
•
if other player plays optimally
17
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
•
•
0 (zero) is the leftmost position
•
•
Move chip by no less than 1 and no more than 3
Can’t move from that position
Player which cannot move is the loser
18
Game of Scoring – Demo
• Let’s try to determine P and N positions
•
Max step is 3
0
1
2
3
4
5
6
7
8
9
P
N
N
N
P
N
N
N
P
N
19
Game of Scoring – Positions
• 0 – losing (P-position)
• 1, 2, 3 – winning positions (N-positions)
•
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 (N-positions)
•
Can place other player in a losing position (4)
• Scoring has a direct formula for P-positions
20
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 an N-position
There is always at least one option
that leads to a P-position
21
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
• Normal play – player taking last element wins
•
23
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
•
In normal play
24
Nim - Demo
• Let's play Nim
index
0
1
2
3
4
5
25
Nim – Observations
• What happens for Nim with 1-element 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
26
Nim – More Observations
• What happens for Nim with 1-element 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
(2, 2) – other player wins (losing position)
b)
•
•
•
First player’s moves are to (1, 2) or (0, 2) *
First option leads second player to case a)
Second option – second player takes the heap
27
Nim – General Observations
• We could go on generating positions
•
That would take too much (exponential) time
• Another pattern can be noticed
Even same-sized heap count – bad position
Odd same-sized heap count – good position
b) + one larger heap – good position
a)
b)
c)
•
d)
can move to position a) by reducing larger heap
Other similar even-odd considerations
• Can we easily filter through good/bad positions?
28
Nim-Sum
• Nim-sum (aka XOR, ^, addition modulo two)
• The Nim-sum of a position (n0, …, nk) is
n0 ^ n1 ^ … ^ nk
A non-zero Nim-sum denotes a winning 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 nimbers
29
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 (k > 0)
• 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 > 0
• At least one change leading to Nim-sum = 0
• So, we can always force a losing position
•
From a winning position
30
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 Nim-sum > 0
•
Achieve even number of 1’s in each bit column
Calculate the current Nim-sum
Finds its leftmost bit equal to 1
(denotes a column with an odd number of 1’s)
Find any 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
31
Solving Nim in C#
LIVE DEMO
Nim Importance
• What’s the big deal with Nim?
•
The Sprague-Grundy theorem
• Who?
•
•
R. P. Sprague & P. M. Grundy in 1935 & 1939
Independently discovered the theorem
• The Sprague-Grundy theorem states:
Every impartial game, under normal play is
equivalent to a nimber
• I.e. every impartial game is a Nim in disguise or some variant of it
33
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
•
0
•
1
2
3
4
5
6
7
8
9
Seem familiar?
34
Nim Importance
• How about now?
•
•
index
The solutions of Nimble and Nim are equivalent
After indices are turned into heap sizes
0
1
2
3
4
5
35
More General Nim?
• In standard Nim, we can take any number of elements from 1 pile
• We can generalize Nim for K piles
•
Take any number of elements from at least 1 pile and at most K piles
• This is called Moore's Nim
•
•
More formally, for K piles it is Nimk
So normal Nim is actually Nim1
• Can you think of a way to edit the Nim solution to work for Moore's
Num?
36
More General Nim (Moore's Nim) – Solution
• We need to change the Nim-sum operator
• For Nim1 (Standard Nim) we convert piles to binary and use "sum
modulo 2"
• So for Nimk we again convert piles to binary, but instead use "sum
modulo k+1"
•
E.g. if we can take from at most 2 piles, Nim-sum is "sum modulo 3"
• The remaining part of the solution is the same
•
•
Positions with Nim-sum > 0 are winning
Positions with Nim-sum < 0 are losing
37
Composite Games
DIVIDING INTO SUBGAMES,
TWEEDLEDUM & TWEEDLEDEE PRINCIPLE,
SPRAGUE-GRUNDY
Composite Games
• Generally, composite games can be broken down into subgames
• Usually composite games can be formed from any game
•
By adding more chips
• Examples:
•
•
•
Game of Scoring with N Chips
Nim with N groups of piles
Etc.
39
Game of Scoring – Demo 2
• Let’s play Scoring again
This time with 2 chips
• Max step is 3
• Are the marked P/N positions correct in this case?
•
0
1
2
3
4
5
6
7
8
9
P
N
N
N
P
N
N
N
P
N
40
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 singlechip game
Losing positions remain losing, problem is with winning ones
• Similar cases occur in games with more chips
•
And more equivalent positions
41
Composite Games – Solving
• Composite impartial games
• Equivalent to nimbers (as other impartial games)
• 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
• How do we get those numbers/nimbers?
42
Calculating the
Sprague-Grundy Function
FOLLOWER POSITIONS,
MINIMAL EXCLUDENT
Calculating SG function
• The nimbers we needed to describe a composite game's state can
be calculated with the Sprague Grundy function
•
Yep, those guys again
• Sprague-Grundy (SG) function
•
•
Recursively generates "Grundy" values/numbers
Numbers correspond to heap sizes in Nim
• SG function a has "helper" functions to adapt to a specific game
•
The "Follower" function
44
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
•
45
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
46
Calculating SG function
• So, this g(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
•
47
Calculating SG – example
• Grundy values
with Scoring
• Losing
positions in
a game have
g() = 0
g(0)
g(1)
g(2)
g(3)
=
=
=
=
0, by definition.
1 since g(F(1)) = {0}.
2 since g(F(2)) = {0, 1}.
3 since g(F(3)) = {0, 1, 2}.
g(4) = 0 since g(F(4)) = {1, 2, 3}.
- The values of g on F(4) are {1, 2, 3} and
the minimum that does not appear there is 0.
g(5) = 1 since g(F(5)) = {2, 3, 4}.
- The values of g on F(5) are {2, 3, 0} and
the minimum that does not appear there is 1...
Index
0
1
2
3
4
5
6
7
8
9
SG value
0
1
2
3
0
1
2
3
0
1
48
Calculating SG – pseudocode
• Grundy values
pseudocode
• Walk positions
recursively
• Generate set
of Grundy
values for
followers
• Take the Mex
of the Grundy
values of the followers
int GrundyNumber(position pos)
{
moves[] = Followers(pos);
set s;
for (all x in moves)
{
s.insert(GrundyNumber(x));
}
//Mex – return smallest non-zero
//integer, not in s;
int mexCandidate=0;
while (s.contains(mexCandidate))
{
mexCandidate++;
}
return mexCandidate;
}
49
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 position
If it is non-zero, we are in a winning position
50
Solving 2-Chip Scoring with Sprague-Grundy and Nim
• Say we have the following position, with SG numbers below
0
1
2
3
4
5
6
7
8
9
0
1
2
3
0
1
2
3
0
1
• We have to 2 chips at position 7 and g(7) = 3
• So, this is equivalent to a Nim with heaps (g(7), g(7)) = (3, 3)
•
which is a losing position because 3 xor 3 = 0
51
More Game Examples
AND THEIR SOLUTIONS
Northcott's Game – (click to play on cut-the-knot.org)
• Rectangular board, 2 checkers per row, 1 per player
• Move rule: move exactly
1 checker anywhere on
it's row,
without jumping over
an opponent's checker
• Lose rule: first player
which cannot move
loses
1
2
3
4
5
6
7
8
9 10 11
1
2
3
4
5
6
• Video: Solution of a task with this game @ Telerik Algo Academy
53
Corner the Lady – (click solution on cut-the-knot.org)
• Rectangular board, 1 checker, players take turns moving
• Move rule: move left, down
or left-down diagonally
by any amount of cells.
You can't move from
the bottom-left
position (1, 1)
• Lose rule: first player
which cannot move
loses
9
8
7
6
5
4
3
2
1
1
2
3
4
5
6
7
8
9
* This is actually a "visual adaptation" version of Wythoff's Nim – read the description at the cut-the-knot link above
54
Other Impartial Combinatorial Games
• Northcott's Game with moving chips in more than 1 row
•
Spolier:
This is a variant of Moore's Nim
• Corner the Lady with more than 1 chip
•
Spoiler:
Composite game – calculate SG values and Nim-sum to solve
• Dots and Boxes, with "first player to make a box wins" rule
•
See this article on composite mathematical games at Oxford
• The Knights game in this TopCoder article
• A lot of games on www.cut-the-knot.org
55
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
•
56
Conclusion
• What we haven’t covered
Misère play
• Partisan 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 you’ve understood the
logical base of the problem.
57
Questions?
58