Transcript Final Presentation

The Game of Nim on Graphs:
NimG
Gwendolyn Stockman
Alan Frieze and Juan Vera
The Game of Nim
2 players
n piles of disks, with a1, a2, … an disks on
each pile
Players take turns removing disks from
each pile
A player loses when there are no disks left
Impartial Games
Geography, Nim, and NimG are impartial
games
A game in which the only difference
between the two players is which one
goes first
Every position of an impartial game has a
Grundy Number or Nim-Value
Sprague-Grundy Numbers (Nim-Sums)
 Used to represent wining and losing positions
 Given a game tree T = (V,E)
 Recursively define:
0
x is a sink

g ( x)  

mex( ( x)) otherwise
with   ( x)  g ( y) : y V s.t. ( x, y)  E x V
x
y
 A player is in a winning position if at the end of
his/her turn the playing piece is on
x such
V
g ( x)  0
that
w
z
Grundy Numbers (cont.)
 Let a1, a2, … an be the binary representations of
the number of disks on each of the n piles
 In the game of Nim the Grundy number for a
setup is the bit-wise sum (mod 2) of the ai‘s
 Example:
1
10
11
00
The Grundy number is 0 so this is a winning position!
Proposed Versions of NimG
 2 players
 1 piece is moved along an undirected graph with no selfloops, and discs are removed
 If discs on vertices:
 Could move first and then remove discs
 Could remove discs and then move
 Possibly allow moves to empty verticies
 If discs on edges:
 Remove discs as you go along an edge
 Players take turns removing disks from piles
 How to win:
 The other player can’t complete their turn
Example of Vertex NimG
7
15
9
5
6
4
21
10
8
5
13
2
Geography
 Two players alternately move a piece on a graph until one loses by
being unable to make an legal moves
 Directed or Undirected
 Edge Geography
 No edge repeated
 Vertex Geography
 No vertex repeated
 Undirected Vertex Geography
 Contained in a version of Vertex NimG with:
 1 chip on each vertex
 Not allowed to move to empty vertices
 Solvable in polynomial Time
 Second player has a winning strategy IFF the graph has a perfect matching
(Fraenkel 1993)
 Undirected Edge Geography
 PSPACE-complete (Fraenkel 1993)
Previous Work: Nim on Graphs
 In A Nim game played on Graphs I and II (Fukuyama
2003) Edge NimG was examined
 Proved that the Grundy Numbers can be found
completely on:
Bipartite Graphs
Trees
Cycles
 Main Method: matchings on graphs
 Contains normal Nim
 2 vertices with n edges with a1, a2, … an disks on each edge
 Contains Undirected Edge Geography
1 disk on each edge
The Game: Vertex NimG
 The game from now on:
Vertex NimG
Moves to empty vertices allowed
 Notation for Vertex NimG on a path of length N
(a0,a1,…,an-1,an):0 represents:
a0
a1
disks
Where
disks
disks
disks
v0
an
an-1
v1
…
vn-1
is the piece being moved
vn
Theorem 1: Vertex NimG on path of length 2
Given non - negative integers a, b, c :
0
1

g (( a, b, c) : 0)  
0
1
0
1

g (( a, b, c) : 1)  
2
0
0
1

g (( a, b, c) : 2)  
0
1
a0
a  0 and b  0
a  b or c  b  1
otherwise
b0
a  0 and c  0 and b  0
a  b or c  b
otherwise
c0
c  0 and b  0
c  b or a  b  1
otherwise
NimG on a Path of Length 3
 Not so simple on longer paths
 Grundy Numbers bounded by a function of d, the
number of disks on the graph
 First note that g 0, x, x,0 : 1  2 x 
Easy to see that g 0, x, x,0 : 1  0
 0, x , x,0 : 0 is a child for x  [0, x  1] and g 0, x , x,0 : 0  0
Easy to see that g 0, x, x,0 : 1  1
 0,0, x,0 : 2 is a child and g 0,0, x,0 : 2  1
Rest omitted for brevity
0
x
0
x
0
x
x
0
0
0
x
0
NimG on a Path of Length 3 (cont.)
 Will prove that given a,b such that a>b then
g 0, a, b,0 :1  b  2
0
a
b
0
 Because
g 0, a , b,0 : 2   0, a, b,0 : 1 a [0, b]
with a  b
(0,a,b,0):1
(0,0,b,0):2
(0,1,b,0):2
(0,2,b,0):2
(0,b-1,b,0):2
(0,b,b,0):2
NimG on a Path of Length 3 (cont.)
 Take a and we want to know the value of
g 0, a  1,1,0 : 1  3
 Examine the children of that position in the game
tree and find   0, a  1,1,0 : 1
a+1
a
1
g 0,10a,1,,11,,0,00:::220210
1
0    0, a  1,1,0 : 1
1   0, a  1,1,0 : 1
2    0, a  1,1,0 : 1
NimG on a Path of Length 3 (cont.)
 Take a and we want to know the value of
g 0, a  2,2,0 : 1  4
 Examine the children of that position in the game
tree and find   0, a  2,2,0 : 1
a+2
a+1
2
1
g 0,10
2a,,22,,010,2::,22
0:0312  0
2
0    0, a  2,2,0 : 1
1   0, a  2,2,0 : 1
2    0, a  2,2,0 : 1
3    0, a  2,2,0 : 1
NimG on a Path of Length 3 (cont.)
 So given a,b such that a>b then
g 0, a , b,0 : 2   0, a, b,0 : 1 a [0, b]
(0,a,b,0):1
1
(0,0,b,0):2
3
(0,1,b,0):2
4
(0,2,b,0):2
2
b+1
(0,b-1,b,0):2
(0,b,b,0):2
 And g 0, a, b,0 : 1  b  2 if a  b  0
 Further suppose we have a,b,c,e {0} such that
(0,1,b,0):0
a  b  c  e  d  max number of disks
then
d 
max g a, b, c, e  : 1     1
2
0
Vertex NimG on Any Graph
 Represent positions of NimG as (G, A):v where G is the
graph, A is the amount function for G, and marker is at
vertex vV(G)
 A reduced game tree is used to find if a winning
strategy exists from a given position, and if one does,
what it is
 Create the reduced game tree, T, where each node is a
position, by
 making (G,A):v the root
 For each uN(v) such that A(u)< A(v) add node (G,A’): u as
a child to (G,A):v where
u
wv
 A( w)  1
A' ( w) : 
w V (G )
otherwise
 A( w)
(G, A):v
 Repeat once for each node added to T
(G, A’):u
v
x
y
Example: Create T
Player P1 starts with setup (G,A):v
v
12 h
d
4
9
v
2
6
a
5
a
3
c
e
1
b
f
b
c
Example: Create T
Start with setup (G,A’):a
v
12 h
d
4
8
v
2
6
a
5
a
3
c
b
e
1
b
f
b
d
c
Example: Create T
Start with setup (G,A’’):b
v
12 h
d
4
8
v
2
5
a
5
a
3
c
b
e
1
b
f
b
d
c
Example: Create T
Start with setup (G,A’’):b
v
12 h
d
4
8
v
2
5
a
5
a
3
c
b
d
e
1
b
f
e
b
f
c
Example: Create T
Start with setup (G,A’’’):e
v
12 h
d
4
8
v
2
5
a
4
a
3
c
b
d
e
1
b
f
e
f
b
f
c
Example: Create T
Start with setup (G,A’’’):e
v
12 h
d
4
8
v
1
5
a
4
a
3
c
b
d
e
1
b
f
e
f
b
f
c
Example: Create T
v
12 h
d
4
9
v
1
5
a
4
a
3
c
b
b
d
e
c
f
e
e
1
b
f
e
f
f
f
f
f
Labeling T
 If it is player P1’s turn then label all even levels, including
0, of T, P1, and all odd levels P2
 Label each node either P1 or P2
 Player P1 has a winning strategy from nodes labeled P1
 Player P2 has a winning strategy from nodes labeled P2
 Label all nV(T), with labeling function L:V(T){P1,P2},
using a depth first labeling starting with the n=root of V(T)
 Apply the depth first labeling to all children of n in T
 Label n with L(n)
 The root of T is labeled P1 IFF there is a winning strategy
for player P1
Example: Labeling T
Depth First Labeling of T :
L(n):=
n a leaf and on a P2-level
P1 or n on a P1-level and at least one child of n labeled P1
or n on a P2-level and all children of n labeled P1
n a leaf and on a P1-level
P2 or n on a P2-level and at least one child of n labeled P2
or n on a P1-level and all children of n labeled P2
w = A node labeled P1
w = The node currently being
examined
v
a
w = A node labeled P2
w = A node whose subtree is being
labeled
P1 does NOT have a
winning strategy from
(G,A):v!
b
e
f
b
d
f
P1
e
f
c
f
e
f
P2
f
P1
P2
P1
Why P1 can’t win
 Assume that players will always follow a winning
strategy if one exists
 If P1 moves to a, b, or c then P2 will win
 What if P1 moves to h? P1 still loses!
v
P1
12
10
11
8 h
d
a
4
9
8
6
2
5
b
2
a
5
c
P2
3
c
v
6
b
e
f
e
f
P1
e
1
b
d
f
e
f
f
f
f
P2
P1
The Winning Strategy: Case 1
 If player P2 just moved from vertex u to vertex v,
creating setup (G, A):v, and (G, A’):u is a child of
(G, A): v labeled P1
Remove r[1, A(v)- A(u)] disks from vertex v and
move to vertex u, creating setup (G, A ' ) : u with
wv
 A( w)  r
A ' ( w) : 
w V (G )
otherwise
 A( w)
Replace the sub-tree with root (G, A’):u with the tree
of root
as described before
(G, A 'created
):u
(G, A):v
(G, A’):u
(G, A):v
(G, A ' ) : u
The Winning Strategy: Case 2
 Otherwise, given setup (G, A):v pick any child
(G, A’):u of node (G, A):v in T that is labeled P1
remove r[1, A(v)- A(u)] disks from vertex v and
move to vertex u, creating setup (G, A ' ) : u with
wv
 A( w)  r
A ' ( w) : 
otherwise
 A( w)
w V (G )
Replace the sub-tree with root (G, A’):u with the
tree of root (G, A ' ) : u created as described before
 The alterations to T insure that T maintains the
property that for any node y=(G, A):w V(T)
A( w)  A( x)
z  (G, A' ) : x  children of y in T
(G, A’):x
(G, A):w
NimG on any Graph: Analysis
1 node
 Tree T is exponential in size
 What if there is a maximum
number of disks allowed on each
vertex?
 n-1 nodes
 n-2 nodes
Polynomial – at most nd number of
 n-d nodes
nodes, where d is the maximum
number of disks allowed on a
root of T
vertex and n=V(G)
(G, A) : v
There does not exist any path
starting from the root with a node
~
(G,A):v and a node (G, A) ~: v for any
amount functions A and A
~
(G, A) : v
Questions???