文档章节

博弈论

jit-hakase
 jit-hakase
发布于 2017/09/03 16:29
字数 1181
阅读 4
收藏 0

博弈论

奇异局势: 面对此局势, 不管做出任何动作, 都将输掉最终比赛.

巴什博奕(Bash Game)

问题:一堆n个物品, 两个人轮流从这堆中取物品, 规定每次至少取一个, 最多取m个, 最后取光者胜, 先取如何必胜?(n>m+1) 思路:当n%(m+1)==0时为奇异局势, 第一次通过取n%(m+1)个到达奇异局势, 接下来对手取x个, 取m+1-x个继续达到奇异局势, 重复此步骤.

  • 判断能否取胜
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)

问题:两堆物品分别有m, n个, 两个人轮流从某一堆或同时从两堆中取同样多的物品, 规定每次至少取一个, 多者不限, 最后取光者得胜, 先取如何必胜?(n>0, m>0) 思路:(1, 2), (3, 5), (4, 7), (6, 10)...这些局势是奇异局势, 称为(ak, bk), 非奇异局势可以通过一次操作达到奇异局势(ak<bk) k代表第k个, 也正好是b-a, 而奇异局势不能通过一次操作来得到另一个奇异局势.

局势取法
a==b2堆同取a个
a==ak且b>bkb堆取b-bk个
a==ak且b<bk2堆同取a-aj(j==b-a)个
a>ak且b==bka堆取a-ak个
a==aj(j<k)<ak且b==bkb堆取b-bj个
a==bj(j<k)<ak且b==bkb堆取-aj个

奇异局势公式: (ak=[k(1+√5)/2], bk=ak+k)

  • 判断能否取胜
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)

问题:有3堆物品, 各若干个, 两个人轮流从某一堆取任意多的物品, 规定每次至少取一个, 多者不限,先取如何必胜? 思路: 任意局势(a, b, c), 当a^b^c=0时, 为奇异局势, 面对局势(a, b, c)时(a>b>c), 当a^b^c不为0时, 可以通过让c=c-a^b(c>a^b)来达到奇异局势, 这个结论可以扩充到N堆物品.

  • 判断能否取胜
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个物品, 两个人轮流从这堆中取物品, 规定每次至少要取的物品是2的幂, 最后取光者胜, 先取如何必胜? 思路:使用sg函数.

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)

通过打印sg数组发现规律(N%3==0出现奇异局势) 简化后的程序

N = 16

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

尼姆博奕加强版

问题:有3堆物品, 各若干个, 两个人轮流从某一堆取F个物品, F为菲波那契数列中的任意一个数(F(1)=1), 先取如何必胜? 思路: 使用sg函数, 分离成三个子问题, 最后将sg值异或求出最终sg值.

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')

© 著作权归作者所有

上一篇: MySQL(1)
下一篇: 贪心算法
jit-hakase
粉丝 3
博文 26
码字总数 30408
作品 0
南京
程序员
私信 提问
观点 | 理性强化学习遭遇瓶颈,进化算法会成为接替者吗?

  选自medium   作者:Elena Nisioti   机器之心编译   参与:Geek AI、刘晓坤      人工智能和博弈论的交集催生了强化学习,但在博弈论基础上的问题求解通常依赖于理性和完美信...

机器之心
2018/06/17
0
0
让AI来一场“简单”的黄金点游戏

     编者按:前不久,2018微软学生夏令营圆满落幕,带着像夏日温度般的编程热情,23组同学组队开发了AI程序,并在黄金点游戏上展开PK。作为博弈论的经典案例之一,黄金点游戏中的心理博...

微软亚洲研究院
2018/09/11
0
0
[NBOJ0031][Nim-B* Sum]

[题目要求] http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/showproblem.php?problem_id=31 [题目涉及的相关理论与算法] 1,博弈论中的NIM游戏。虽然题目中求的Nim和是Nim游戏中的策...

小弘
2012/10/13
116
0
7位大咖齐聚CCF ADL计算经济学课程,探索算法博弈论,区块链、人工智能与经济学的交叉

2017 年10月19——21日,最新一期的中国计算机学会学科前沿讲习班(CCF Advanced Disciplines Lectures,简称 ADL)在上海财经大学举办。 本期主题是《计算经济学的理论与应用》,邀请了七位...

北丐09
2018/04/16
0
0
读书replay《博弈与社会》.2.20190527

前情 《美丽心灵》,一部讲数学家约翰·福布斯·纳什的电影,我第一次听到博弈理论就是在这部电影里。看过电影之后就一直想知道,博弈论究竟讲了什么。很久之后,20190417这天,我刷JD的购物...

wanxiangming
05/26
6
0

没有更多内容

加载失败,请刷新页面

加载更多

Blockstack-2 :Blockstack ID注册

本篇文章主要记录Blockstack ID注册的流程; 在介绍注册流程之前,先简单的介绍一下Blockstack ID; 相对于传统互联网来说,Blockstack ID更像是统一的账号系统;即一个账号即可登录和授权所...

Riverzhou
今天
19
0
面试官问:平时碰到系统CPU飙高和频繁GC,你会怎么排查?

处理过线上问题的同学基本上都会遇到系统突然运行缓慢,CPU 100%,以及Full GC次数过多的问题。当然,这些问题的最终导致的直观现象就是系统运行缓慢,并且有大量的报警。本文主要针对系统运...

Java高级架构师n
今天
33
0
面向对象编程

1、类和对象 类是对象的蓝图和模板,而对象是实例;即对象是具体的实例,类是一个抽象的模板 当我们把一大堆拥有共同特征的对象的静态特征(属性)和动态特征(行为)都抽取出来后,就可以定...

huijue
今天
30
0
redis异常解决 :idea启动本地redis出现 jedis.exceptions.JedisDataException: NOAUTH Authentication required

第一次安装在本地redis服务,试试跑项目,结果却出现nested exception is redis.clients.jedis.exceptions.JedisDataException: NOAUTH Authentication required错误,真是让人头疼 先检查一...

青慕
今天
42
0
Spring 之 IoC 源码分析 (基于注解方式)

一、 IoC 理论 IoC 全称为 Inversion of Control,翻译为 “控制反转”,它还有一个别名为 DI(Dependency Injection),即依赖注入。 二、IoC方式 Spring为IoC提供了2种方式,一种是基于xml...

星爵22
今天
37
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部