Combinatorial Game. Who wins if both players play optimally
Players A and B play a game optimally and move alternately. They start with 1. Each player in his turn multiplies the current number with any integer from [2,9]. If after a player's turn, the number is more than or equal to n , he wins.
A starts. Given n , who wins?
For example,
Numbers 2,3..,9 are winning numbers (Player A will win)
Numbers 10,11,..,18 are losing numbers (Player A will lose)
Numbers 19,20,..,162 are winning numbers
What would be the winning strategy? How can the Sprague-Grundy theorem be applied to solve this?
According to Sprague-Grundy theorem each state of an impartial game can be assigned a non-negative integer called Grundy number, such that the player who moves in this state will lose iff this number is 0, and win iff this number is non-zero.
If the Grundy numbers for the states are known, then the winning strategy is to always make a move to a state in which Grundy number is 0.
The algorithm for computing Grundy number for some state of a general game is as follows:
if current player can't make a valid move:
Grundy number := 0 (this player has lost)
else:
for each move in this state:
for each sub-game the game splits into after that move:
compute Grundy number of the sub-game
compute XOR of Grundy numbers of the sub-games
Grundy number := MEX of those XORs
MEX is minimum excludant function. MEX of a set of non-negative integers is equal to the smallest non-negative integer, that does not belong to this set.
For example:
MEX(0) = 1
MEX(0, 1) = 2
MEX(0, 2) = 1
MEX(0, 1, 2) = 3
MEX(0, 1, 3) = 2
MEX(1, 2, 3) = 0
MEX(10, 100, 1000) = 0
Naive implementation of this algorithm for this game in Python 3 may look like this:
import functools
from itertools import count
def mex(s):
for i in count():
if i not in s:
return i
@functools.lru_cache(10000)
def sprague_grundy(n, cur=1):
if cur >= n:
return 0
move_results = {sprague_grundy(n, cur*move) for move in range(2, 9+1)}
return mex(move_results)
for i in count(1):
print(sprague_grundy(i))
Often the easiest way to understand the general formula for the Grundy number is to just look at the sequence and try to notice the relationships. In this game you can figure out the general formula by simply looking at n numbers for games in which player A wins in inital state, without actually calculating Grundy numbers.
But we can still look at the counts of Grundy numbers of the initial state of the game for consecutive n (0 means player A loses in the initial state, 1,2,3,4 mean player A wins):
$ python3 sprague_grundy.py | uniq -c
1 0
1 1
2 2
4 3
1 4
9 0
18 1
36 2
72 3
18 4
162 0
324 1
648 2
1296 3
324 4
2916 0
It is possible to notice that for player A all the losing initial states are for
Or in other words the initial state for player A is losing iff
Basically you make an array A[] where A[i] stores whether number i is a winning position or losing with respect to the player who starts the game.Let it be player A . Basic rule, from a losing position you can go only to a winning one and a winning position is such that there is always a losing position reachable from it.Following code is explanatory ( 1 means winning wrt to A and 0 means losing).
for each i from 1 to 9
A[i]=1
for each i from 10 to n
flag=0
A[i]=0
for each j from 2 to 9
if i is divisible j and A[i/j] is 0
flag=1
if flag is 1
A[i]=1
Now if A[n] is 1 it is winning for him else he loses.
This is an O(n) solution both in time and memory.You can reduce memory, but time I can't come up with a better solution. There might be a O(1) solution but I am unaware of it.
上一篇: 特殊的矩形矩形平铺