Games on Posets - CiE 2008

Background Information
Translating Chomp to Geography
Chomp and Proof Complexity
Concluding Remarks
References
Games on Posets
Craig Wilson
McMaster University
June 22, 2008
Based on the paper “On the Complexity of Computing Winning Strategies for Finite Poset Games” by Michael
Soltys and Craig Wilson
Craig Wilson McMaster University Games on Posets

Concluding Remarks
References
Outline
1 Background Information
2 Translating Chomp to Geography
3 Chomp and Proof Complexity
4 Concluding Remarks
5 References

Concluding Remarks
References
Context of Poset Games
Posets
Poset Games
The Game of Chomp
Simple to describe
Computing winning strategies appears intractable in all but
simplest cases
Proof of 1st player having a winning strategy does not
immediately yield a feasible algorithm for computing the
strategy

Concluding Remarks
References
Posets
Poset Games
The Game of Chomp
Partially Ordered Sets (Posets)
Set U together with ordering relation
satisﬁes following properties:
Anti-Symmetry: If a b, then b a
Transitivity: If a b and b c, then a c
If a b and b a, then a||b (incomparable)

Concluding Remarks
References
Posets
Poset Games
The Game of Chomp
(Finite) Poset Games [1]
Games between 2 players
From ﬁnite Poset (U, ), Poset Game (A, ) is played as
follows:
1 Initialize A = U
2 Select an x ∈ A, remove all y ∈ A such that x y
3 Game ends when A = ∅, player unable to select an element
loses
A round is a sequence of two consecutive moves (ﬁrst player,
then second)

Concluding Remarks
References
Posets
Poset Games
The Game of Chomp
Chomp[2]
x
Special case of poset game.
Ordering relation can be thought of as a chocolate bar.
Don’t eat the poisoned square!

Concluding Remarks
References
Posets
Poset Games
The Game of Chomp
More Formally. . .
Set of pairs (“cells”) {(i, j) |1 ≤ i ≤ n, 1 ≤ j ≤ m}
Select pair (i0, j0)
Remove all (i, j) such that i ≥ i0 and j ≥ j0
Player left with only (1, 1) loses

Concluding Remarks
References
Posets
Poset Games
The Game of Chomp
Chomp Configurations
Represent as binary strings X:
x
Figure: Chomp configuration with X = 00101101
1s delimit rows, 0s indicate difference in rows lengths.

Concluding Remarks
References
Chomp ∈ PSPACE (Part 1)
Geography
Gadget Construction
Challenges
Simple, direct polynomial-time translation from Poset Games
to Geography, which shows Poset Games ∈ PSPACE
Translation from restricted form of Geography to Chomp also
attempted
Limitations of poset games revealed - not PSPACE-complete?

Concluding Remarks
References
Geography
Gadget Construction
Challenges
Mathematically...
GeneralizedGeography(GG):
GG = { G, s | Player 1 has a winning strategy for the Generalized
Geography game played on graph G starting at node s}

Concluding Remarks
References
Geography
Gadget Construction
Challenges
Graph Construction: Part 1
x yz
Figure: Base Construction of a poset game in Geography

Concluding Remarks
References
Geography
Gadget Construction
Challenges
Complications...
Once a node x ∈ G has been visited, must not be able to visit
any y such that x y
Need system of checks and balances
x x1x2
y
x4
x3z
incoming moves
incoming challenges
outgoing moves
Figure: 5-node gadget

Concluding Remarks
References
Geography
Gadget Construction
Challenges
Gadget Construction
x x1x2
y
x4
x3z
incoming moves
incoming challenges
outgoing moves
Figure: Construction of the 5-node gadget

Concluding Remarks
References
Geography
Gadget Construction
Challenges
Preventing Illegal Moves
Additional nodes prevent players from making illegal moves.
If player moves to node that “shouldn’t exist”, they will lose.
Challenges to legal moves also result in a loss.

Concluding Remarks
References
Geography
Gadget Construction
Challenges
Example: Challenging an Illegal Move
x x1x2
y
x4
x3z
incoming moves
incoming challenges
outgoing moves
Figure: Challenging an illegal move

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Construction of Formula Φ(X, n, m)
Existence of Winning Strategy
Second proof of Chomp ∈ PSPACE
Use theorems of W1
1 to show the existence of a winning
strategy ∈ PSPACE
Introduce segments X[i] of a conﬁguration string X:
X =
X[1]
01
X[2]
10
X[3]
11
X[4]
00

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Proof Complexity
Main idea:
ΓC ∀x∃yα(x, y)
∃f ∈ C such that α(x, f (x))
Diﬀerent bounded arithmetic theories capture diﬀerent classes

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Variables of a Diﬀerent “Sort”
Three types of variables called sorts:
1 Natural numbers (x, y, z, . . . )
2 Strings (X, Y , Z, . . . )
3 Sets of strings (X, Y, Z, . . . )
Concerned with formulas from class ΣB
1 :
(∃X) (∀Y ) (∃Z) . . . (∀y) A (X, Y , Z, . . . , y)

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Description of W1
1 [3]
Third-sorted theory for reasoning in PSPACE
Symbols taken from set L3
A = {0, 1, +, ×, ||2, ∈2, ∈3, ≤, =}
Axioms [3]:
B1. x + 1 = 0 B7. (x ≤ y ∧ y ≤ x) → x = y
B2. (x + 1 = y + 1) → x = y B8. x ≤ x + y
B3. x + 0 = x B9. 0 ≤ x
B4. x + (y + 1) = (x + y) + 1 B10. x ≤ y ∨ y ≤ x
B5. x × 0 = 0 B11. x ≤ y ↔ x < y + 1
B6. x × (y + 1) = (x × y) + x B12. x = 0 → ∃y ≤ x(y + 1 = x)
L1. X(y) → y < |X| L2. y + 1 = |X| → X(y)
SE. [|X| = |Y | ∧ ∀i < |X|(X(i) ↔ Y (i))] → X = Y

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Achieving the Goal - Step 1
Want to give formula Φ(X, n, m) which decides whether X is
valid Chomp game of size n × m
X is string of length (n × m)(n + m), with (n × m) segments
Φ is conjunction of three formulas: φinit, φﬁnal, and φmove

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Formulas φinit and φfinal
φinit asserts X[1] to be the initial configuration of the game:
φinit(X[1]
, n, m) = ∀i ≤ (n + m)((i > m) → X[1]
(i) = 1)
φfinal asserts X[n×m] to be the final configuration of the game:
φfinal(X[n×m]
, n, m) = ∀i ≤ (n + m)((i > n) → X[n×m]
(i) = 0)

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
The φyields formula
φyields asserts that each segment of X can be obtained from
one legal move on the previous one:
φmove(X, n, m) = ∀i < (n × m)(X[i]
“yields” X[i+1]
)
Defining “yields” is where the fun begins!
Attempt to discern what square(s) could have been played
between X[i] and X[i+1]
Ensure differences between configs correspond to played
square

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Complete Yields Formula
(∃j ≤ NumOnes)(∃k ≤ NumZeros)[F0(1, k, X) < F1(1, j, X)
∧(∃p < |X[i]
|)(∃q ≤ |X[i]
|)(p = F0(1, k − 1, X[i]
) + 1 ∧ q = F1(p, j, X[i]
))
∧(∀r ≤ |X|)[(r < p ∨ r > q → X[i+1]
(r) = X[i]
(r))
∧(r < p + j → X[i+1]
(r) = 1)
∧(r ≥ p + j → X[i+1]
(r) = 0)]]
Where
NumOnes = |X[i]
| − numones(1, X[i]
)
NumZeroes = numones(1, X[i]
)

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Achieving the Goal, Step 2
Strategy function S from configurations to configurations
Formula for either player having winning strategy:
∀C∃S [WinP1 (S, C) ∨ WinP2 (S, C)]
where WinP1 (S, C) is a ΣB
1 formula
Manipulate this to get formula for first player having a
winning strategy:
(C = 0m
1n
) → ∃S [WinP1 (S, C)]

Concluding Remarks
References
The Goal
Bounded Arithmetic
Description of W1
1
Applying the Witnessing Theorem
With
W1
1 (C = 0m
1n
) → ∃S [WinP1 (S, C)]
we have that the function for computing the winning strategy is in
PSPACE.

Concluding Remarks
References
Concluding Remarks
Is the problem of computing winning strategies for Poset Games
PSPACE-complete?

Concluding Remarks
References
References I
Steven Byrnes.
Poset Game Periodicity.
Integers: Electronic Journal of Combinatorial Number Theory,
3(G03), November 2003.
David Gale.
A Curious Nim-Type Game.
The American Mathematical Monthly, 81(8):876–879,
October 1974.
Alan Skelley.
A Third-Order Bounded Arithmetic Theory for PSPACE.
In CSL, pages 340–354, 2004.

Games on Posets - CiE 2008

Recommended

Recommended

More Related Content

What's hot

What's hot (20)

Viewers also liked

Viewers also liked (18)

Similar to Games on Posets - CiE 2008

Similar to Games on Posets - CiE 2008 (20)

Recently uploaded

Recently uploaded (20)

Games on Posets - CiE 2008