主要讨论三个比较常见的博弈游戏
bash game,nim game和wythoff game,较为领人惊叹的是,他们最后都是通过数论或者自然数性质完美解决:
bash game:同余理论
nim game:异或理论
wythoff game:黄金分割
(1)bash game:一堆n个物品,两人轮流取,每次取1至m个,最后取完者胜
比如10个物品,每次只能取1到5个,则先手方必赢
1.面对[1…m]个局面,必胜
2.面对m+1个局面,必输
3.如果可以使对手面临必输局面,那么是必赢局面
4.如果不能使对手面临必输局面,那么是必输局面
基础:1 , 2, …, m是必赢局面, m+1是必输局面
递推:m+2,m+3, … ,2m+1是必赢局面,2m+2是必输局面
…
k(m+1)是必输局面,应该允许k=0,因为0显然也是必输局面
在必输局和必赢局中,赢的一方的策略是: 拿掉部分物品,使对方面临k(m+1)的局面
例如上例中10个物品,只能拿1到5个,先手方拿4个即可,对手无论拿多少个,你下次总能拿完
从另一个角度思考这个问题,如果物品数量随机,那么先手一方胜利的概率是m/(m+1),后手方胜利的概率是1/(m+1)
(2)nim game: m堆n个物品,两人轮流取,每次取某堆中不少于1个,最后取完者胜
详细分析见:poj-2234:matches game
所有物品数目二进制异或 为0,则先手必输
所有物品数目二进制异或不为0,则后手必输
从另一个角度思考这个问题,如果物品数量随机,那么每个数目的每一位上1或0概率相同,
如果有奇数个堆,那么1的个数为偶数或者奇数的概率相同,
如果有偶数个堆,那么1的个数为偶数的概率略大1/(m+1),
也就是说异或结果的每一位为0或1的概率几乎差不多,而先手必输要求异或结果每一位都为0,其实输的概率很小
(3)wythoff game:两堆(ak,bk)(ak<=bk)个物品,两人轮流取,每次从一堆中取k个或者从2堆中同时取k个,最后面对(0,0)局面的输(设ak<=bk是为了忽略顺序的影响)
1.面对(0,0)局面必输
2.面对(1,1)(2,2)…(n,n)局面必赢
(0,1)(0,2)…(0,n)局面必赢
3.如果可以使对手面临必输局面,那么是必赢局面
4.如果不能使对手面临必输局面,那么是必输局面
基础:(0,0)是必输局面;(0,1)(0 ,2)…(0,n)是必赢局面,
递推:(1,2)是必输局面;(1,1)是必赢局面
(1,3)(1 ,4)…(1,n)是必赢局面
(2,2),(2,3)…(2,n)是必赢局面
(3,5)是必输局面;(3,3)(3,4)是必赢局面
(3,6)(3,7)…(3,n)是必赢局面
(5,5)(5,6)…(5,n)是必赢局面
(4,7)是必输局面;(4,4)(4,5)(4,6)是必赢局面
(4,8)(4,8)(4,9)…(4,n)是必赢局面
(7,7)(7,8)(7,9)…(7,n)是必赢局面
(6,10)是必输局面;(6,6)(6,7)(6,8)(6,9)是必赢局面
(6,11)(6,12)(6,13)…(6,n)是必赢局面
(10,10)(10,11)(10,12)…(10,n)是必赢局面
首先发现规律:(必输局面的规律比较容易找到)
ak是前面必输局未出现的数中最小者,bk=ak+k( k=0,1,2,3,…n)
下面介绍必输局(奇异局)的最重要性质:
1,2,…,n中每一个自然数,出现且只出现在一个奇异局中。
推导:1.由于ak总是选择未出现的数,所以每个数总能出现在奇异局中
且ak不会选择到重复的数
2.bk=ak+k,所以bk总是比前面所有奇异局出现的数都大,
所以bk不会选择到重复的数
必赢一方的策略是:始终让对手面对必输局(奇异局)
给定任意局势(a,b),判定(a,b)是否为必输局的方法是:
k=0,1…n 记黄金比例是φ=1.618033
ak=[k*φ],bk=ak+k=[k*φ*φ]
如k=0,ak=0,bk=0
k=1,ak=1,bk=2
k=2,ak=3,bk=5 k=3,ak=4,bk=7
更好的一种判断策略是 k = bk-ak ,如ak=k*φ时,当前局势为奇异局
从胜负概率角度,如果堆中数量随机,先手一方优势很大
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603973.html