2017/09/03 16:29

# 博弈论

### 巴什博奕(Bash Game)

• 判断能否取胜
``````n, m = 20, 6

if n%(m+1) == 0:
print('no')
else:
print('yes')
``````
• 第一步先手的取法
``````n, m = 20, 6

if n%(m+1) == 0:
print('no')
else:
print('take ' + str(n%(m+1)))
``````

### 威佐夫博奕(Wythoff Game)

a==b 2堆同取a个
a==ak且b>bk b堆取b-bk个
a==ak且b<bk 2堆同取a-aj(j==b-a)个
a>ak且b==bk a堆取a-ak个
a==aj(j<k)<ak且b==bk b堆取b-bj个
a==bj(j<k)<ak且b==bk b堆取-aj个

• 判断能否取胜
``````import math

a, b = 2, 1

if a > b:
a, b = b, a

k = b - a
ak = (math.sqrt(5)+1)*k//2

# bk==ak+k
if ak == a:
print('no')
else:
print('yes')
``````

### 尼姆博奕(Nim Game)

• 判断能否取胜
``````L = [5, 10, 12]

nim = 0

for item in L:
nim ^= item

if nim == 0:
print('no')
else:
print('yes')
``````
• 第一步先手可以的取法
``````L = [5, 10, 12]

nim = 0

for item in L:
nim ^= item

if nim == 0:
print('no')
else:
for idx, item in enumerate(L):
if nim^item < item:
print('from index {0} take {1}'.format(idx, item-(nim^item)))
``````

### SG函数

sg函数是解决复杂博弈问题的通用方法, 将博弈问题的原始解法(N/P)抽象成初始状态为顶点, 后继结点为后继状态的有向无环图. 定义一种运算mex({...}), 计算集合中最小的非负整数. 可以将一个复杂博弈问题抽象成几个博弈小问题 最后的sg值为所有博弈小问题的sg值的异或 sg(x)=mex(sg(y)|y是x的后继结点)

#### 巴什博奕加强版

``````N = 16
sg = [0 for i in range(N+1)]

def mex(x):
global N, sg
vis = [False for i in range(N+1)]

i = 1
while x+i <= N:
vis[sg[x+i]] = True
i *= 2

i = 0
while True:
if not vis[i]:
return i
i += 1

for i in range(N-1, -1, -1):
sg[i] = mex(i)

win = 'lose'

i = 1
while i <= N:
if sg[i] == 0:
win = 'win, take %d .' % i
break
i *= 2

print(win)
``````

``````N = 16

if N%3 == 0:
print('lose')
else:
print('win, take {0} .'.format(N%3))
``````

#### 尼姆博奕加强版

``````N = 15
fib = [0 for i in range(N)]

def calc_fib():
global fib
fib[1], fib[2] = 1, 2
for i in range(3, N):
fib[i] = fib[i-1] + fib[i-2]

calc_fib()

L = [3, 4, 5]

sg = [0 for i in range(N)]

def mex(x):
global N, sg
vis = [False for i in range(N)]

i = 1
while fib[i] <= x:
vis[sg[x-fib[i]]] = True
i += 1

i = 0
while True:
if not vis[i]:
return i
i += 1

for i in range(1, N):
sg[i] = mex(i)

nim = 0
for item in L:
nim ^= sg[item]

if nim == 0:
print('lose')
else:
print('win')
``````

0
0 收藏

0 评论
0 收藏
0