Computer Science
excercises
Game Models.
A1.
Give a full analysis of the game from Donald Duck shown in class.
Game
Description:
There is a pile of n matches on the table. In the
example
n = 15.
Players in turn pick 1, 2 or 3 matches until no
matches
remain.
The player who at this time has an odd number
of
matches wins the game.
Issues to be
answered: who wins the game for n = 15 ? Who wins the
game for
general n when you adapt the
winning condition for even n in a reasonable way.
Show that the behavior
of
the game is periodic.
What happens if
we change the rules requiring that the number of matches
removed by a player is a positive square number ?
Bonus
Extension:
One can modify the game by changing either the set of numbers of matches
both players can pick up
on their turn, or the condition selecting the winner when the game
terminates.
Show that as long as the
set of numbers of matches a player can pick-up is fixed and finite
and the winning condition
is expressed by simple congruences the behavior of the game is
periodic in the number of
matches in the initial position of the game.
A2.
Consider a positive number
N and consider the following game played on the set {1,
2, .... , N}:
Players in turn select a number a[i] in this set, i =
1, 2, .... . The first player to pick a number
a[i] such that some difference a[i] -
a[j] for j < i already occurs on the list of
differences
a[k] - a[l] , 0 < k,l < i
looses the game.
Analyse this game for N = 25.
What is the best upper bound on the
duration of this game you can prove for general N ?
A3.
Napoleon Patience (at least under this
name
I learned this solitaire game when I was a kid)
is played according to the following rules:
Take a deck of cards and place all 52
of
them open on a table in 4 rows of 13 cards. The actual
length of the rows however is 14 since there is
an empty place at the end of every row.
Legal moves are to place in an empty
position
behind a card its successor in the same suit;
for example you may place the 4 of spades
behind
the 3 of spades but not behind the 3 of clubs.
An empty place in the first column may be
filled
by an ace of any suit, but this ace should not
be placed in the first
column already.
Purpose of the game is to rearrange by
legal
moves the initial arrangement into a completely
well ordered deck: each row contains an entire
suit in its natural order. However, if an
empty position is created behind a king there
is
no successor to place at this position,
and you are in trouble. Consequently, when all
holes follow one or more kings you
are stuck.
Evidently the rules of the game describe a huge graph (positions, connected by legal moves).
Frequently a pair of legal moves can be
interchanged - the order in which the moves
are executed doesn't matter. However it could
also be the case that performing a move
prohibits another move which you might have
wanted to perform. Show by means of an
example that selection of the right order is
important: give a position which you can win,
which becomes a lost position by performing the
wrong (legal) move.
How can you generalize the game so that
you can play it with a pair of decks ? And how does
this generalization affect the analysis of the game?
Bonus exercise:
From the description it
is
not evident that the game-graph is acyclic. Prove that it is (and
thereby prove termination
of the game).
A4. A game escaping from standard
BI analysis, and yet easy to analyse.
Consider
the following game: a position is given by a finite list of
nonnegative integers.
A move consists of selecting a number on the list and replacing this
number by a (possibly empty)
finite collection of smaller numbers. In particular if 0 is
selected the move amounts to removing
this occurrence of 0. The player faced with the empty list
looses the game.
(This game is easily seen to be a special case of playing multisets as
described in class).
i) Give an
induction proof that this game terminates.
ii)
Why is it impossible to perform traditional Backward Induction on a
given starting position
in order to determine which player wins the game?
iii)
Prove that if some starting position is won (lost) for the first
player,
adding two copies of the
same number to the list will yield another position won (lost) for the
first
player. Is the same true for
positions won by the first player?
iv)
Give a complete analysis of this game.
The Tiling Game and its use in Reduction Theory
B1.
Design a variant
of
the reduction of Turing Machine computations to the tiling game
where a legal tiling simulates the computation
of
a two tape Turing Machine. It is no longer
required that the hight of the resulting tiling
is
equal or proportional to the time of
the computation, but its width should be
proportional
to the space used.
(Hint: invent a
suitable planar two dimensional representation of the time-space
diagram of a two tape TM;
in fact you can do it in such a way that the hight of the
tiling remains proportional to the time of the computation).
Can you
generalize this construction for the k-tape model ?
The relation
between
PSPACE, the Alternating Machine model and
logic description
languages and games.
C1.
Chlebus' reduction of Alternating
Turing
Machine computations to
the 2-person tiling ame uses the restrictions
on
the ATM model involved that
the states alternate between Universal and
Existential and that each instruction
moves the head of the ATM. Design a variant of
this reduction which doesn't use
these restrictions on the ATM.
C2.
Consider two person games of the block
moving
type. Players move in turn. There is an intitial stage where
both players place blocks on empty positions on
the board. Subsequently there is a stage where blocks which have
placed previously are moved around to other
legal
positions. There is a collection of target configurations and the first
player to reach a target position wins the
game.
Blocks are never to be removed from the board.
Additional restrictions on legality of moves may be introduced but
should
be minimized.
What is the upper bound on the
complexity
of endgame analysis for this type of games which can be
obtained by aplication of the general theory on
backward induction?
Show how one can reduce the solitaire
version
of a block moving game to this two person version.
(hint: tweak the rules of the two person
version
in such a way that Urgat is forced to blindly copy
Thorgrim's moves at the penalty of immediate
loss). Which lower bound on the complexity of the
endgame analysis of these games follows from
this reduction?
Show how to express the two person
tiling
as a game of the above type.
The pebble game.
D1.Prove that
a complete binary
tree of depth k > 1 with 2k leafs
requires k+2
pebbles in the standard version of the pebble game
(no shifts allowed).
Game Theory
excercises
Chapter
1.
1.10.2 & 7 & 10
Construction game tree and Backward Induction Analysis from simple
description of
a combinatorial finite game. Contrary
to the excercise in the book you are asked to perform this analysis on
a 2 by 4 board.
Extra question: Give examples of boards
such that the winner of the game doesn't depend at all on the
strategies used by the players.
A trivial
example is the 1 by 1 board: nobody can move so the first player
always looses the game.
1.10.3
Game
tree construction - add missing information.
Assume that every player has a
different favourite candidate and will be disappointed if that
candidate is not selected. Show that
in this case no player has a winning strategy.
1.10.5 An Infinite Game based on Real Number expansion.
Bonus question: Prove
that the second player has a winning strategy in the case that
E is the set of rational numbers in the unit interval [0,1] . And how
about countable
sets E in general ? What happens if E is
an interval [0,x) for some x in (0,1) ? (cf.
excercise 1.10.17)
Bonus question: Give a rough back-of-the-enveloppe estimate of the size of the game tree and the size of the strategic form of Chess.
Chapter
2.
2.6.4
A Bookie unlikely to make any profit.....
2.6.5 How the Bookie makes money....
2.6.7 The role of independence in the model.
2.6.25
Alternative set of Gale's Roulette wheels.
Chapter 3.
3.7.9 Definition von Neuman Morgenstern Utility function
3.7.11 Risk Aversion
3.7.14 Modifying the lotteries in Allais' paradox
Outside
Book:
Assume that the utility of $ x.-- for an agent equals
x2/3 . Evaluate the amount of money this
agent is willing to pay for participating in the St. Petersburg Lottery.
Show that the Paradox is not solved for an agent ascribing
utility
x/log(x) for an amount of $ x.-- (for x > 1).
Chapter 4.
4.8.1
Strategy removal analysis for an alternate version
of the Duel game
4.8.16
One of the recurring Blotto-Baloney campaigns
Chapter 5.
5.9. 6-8 Computation of a simple payoff region
5.9.11-14 Continuation of the above exercise
5.9.27 Another Divide the Dollar Game
Chapter 6.
6.10.14
Dominance by mixed strategies.
6.10. 15 Computation of a mixed security strategy
6.10. 34 A game on distributed warfare.....