Summaries for Game Theory

By | January 16, 2016
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

I came across some problem regarding game theory. I studied for a little bit. Here are some of my summaries. Even though it is still superficial.

Impartial Game: In combinatorial game theory, an impartial game is a game in which the allowable moves depend only on the position and not on which of the two players is currently moving, and where the payoffs are symmetric. In other words, the only difference between player 1 and player 2 is that player 1 goes first.

Normal Play: The player who takes the last move wins.

Misere Play: The player who takes the last move loose.

In a normal play impartial game, we define P are the positions where previous player can win; N is the position where the next player can win. From P, it can only reach N state. From N, it can reach either N or P state. P is like a balanced position:
gt1

For most of a problem, we are asked if there is a MUST-WIN strategy for a given state.

Assume A is a set of integers. mex(A) is minimum integer number(greater than or equal to 0) which doesn’t appear in set A. g(x) = mex{g(y) : y ∈ F(x)}

For example, mex({2,4,5,6}) = 0, mex({0,1,2,6}) = 3. Consider a state graph like below:
gt4
We can get the g(x) for each point:
gt5
We can know that the point with value 0 are the P points.

For example, in Subtraction Game, we have a pile of stones. And each time, a player can only remove 1, 3 or 4 stones. The player who get the rest is the winner. In this game, it has N, P position like below:

0 1  2  3  4  5  6  7  8  9  10  11  12  13  14

0 1  0  1  2  3  2  0  1  0   1    2    3    2    0     <— mex values

P N P  N N N  N P N  P  N   N   N    N   P

Nim game is that there are n piles of stone. Each player can take any number of stones from each pile. When n = 2, a set of state graph is like below:
gt2

We can see the P position are marked red. We see it is a P position if it complies formula gt3

Wythoff’s Game. There are 2 piles of stones. A player either take same amount of stones from 2 piles, or any number of stones from one pile. It has below solution:
gt6

Sample points are like: (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), …
Besides, golden cut rate has a beautiful formula: gt7

Here are some nice articles for game theory:
http://web.mit.edu/sp.268/www/nim.pdf
https://math.mit.edu/research/highschool/primes/materials/2014/conf/12-2-Xiong.pdf
https://www.youtube.com/watch?v=iyA6y6PKiC4