小谈博弈论(其它游戏篇)

· · 个人记录

(观前提示:本人的语言风格偏啰嗦,请多见谅)

本篇为其它游戏篇,包括非公平组合游戏(事实上没有什么内容)、反常游戏和其它的经典博弈论问题。

总集篇在这里:小谈博弈论(总集篇)。

1.非公平组合游戏

这一部分在网络上可以找到的资料比较少,因为这种游戏比较复杂,难以像公平组合游戏这些构造出来的模型一样,用准确的语言来描述。

但这并不意味着生活中这样的游戏很少。事实上,非公平组合游戏是我们生活中最容易接触到的一类游戏,这是因为大部分棋类游戏如象棋,围棋等,都属于非公平组合游戏。

不过说到底,由于没有找到资料,所以我也很难多做介绍,希望各位读者能够提供一些资料,供大家参考学习。

2.反常游戏

反常游戏与公平组合游戏十分相似,大体规则都是完全一致的,只有在胜负的判定上有(da)点(xiang)不(jing)同(ting)。反常游戏规定,第一个无法行动的玩家为胜者。举个栗子,反常Nim游戏中取走最后一个物品的人为败者。接下来我们也将以这个最经典的反常游戏来进一步了解反常游戏。

反常Nim游戏:

既然规则都清楚了,那么废话不多说,赶紧来介绍一下必胜法吧:

如果每一堆物品的数量都为1,那么就比较简单了:我们只要点一下物品有几堆就行了,如果是偶数堆,那么恭喜你,你已经赢了;如果是奇数堆,那么你必输无疑。

如果存在物品数大于1的堆,那么处理方法就和Nim游戏有些相似了:把当前状态下每堆物品的数量异或起来。不过在反常Nim游戏中,如果这个值不为0,那么就是必胜状态,反之必败。

保持必胜状态也很简单(前提是你能飞快地进行异或运算)。就是让每堆物品数量的异或值为0。例如当前状态为(3,4,5)(3⊕4⊕5=2),那么我们就从第一堆中拿走两个物品,此时状态为(1,4,5),而1⊕4⊕5=0,对手就必败了。

那么怎么确定每次是在哪堆取,取几个呢?

首先,先计算当前状态每堆数量的亦或,设这个值为k,k不为零(你也不能在必败状态下保持必胜)

然后把每堆物品数量转为二进制,找和k的二进制最高位一样的堆(可能不止一堆,这时选哪一堆都行),然后计算这堆的数量和k的异或m,让这堆剩下m个即可。

关于反常Nim游戏,洛谷上有P4279 [SHOI2008] 小约翰的游戏等,洛谷以外还有蓝桥杯的小明的游戏2(事实上小明的游戏这一系列基本都和博弈论有关,不过洛谷上都没有)等等。

3.其它的一些经典博弈论问题

我觉得,要讲博弈论,如果不讲讲这些问题,是很不值当的,因此,以下的问题,虽然在oi中出现的可能性无限趋近于零,还是想稍微介绍一下。

【1】、囚徒困境——非零和博弈的代表

故事是这样的,两个嫌疑犯作案后被警察抓住,分别关在不同的屋子里接受审讯,两人无法交流。警察知道两人有罪,但缺乏足够的证据。警察告诉每个人:如果两人都抵赖,各判刑一年;如果两人都坦白,各判八年;如果两人中一个坦白而另一个抵赖,坦白的放出去,抵赖的判十年。

这时,两个人都开始思考,发现不管同伙选择什么,自己选择坦白结果都会更优。结果,两个嫌疑犯都选择坦白,各获刑八年。

但是,假如最初两人都选择抵赖,最后各判刑一年,显然这是对这两人更优的结果。但由于缺乏交流,两人没能做出这个更优决策。(改编自百度百科)

通过这个例子,我们可以了解到一种十分常见的博弈:非零和博弈。在这种博弈中,各方的收益或损失的总和不是零。这说明在这种博弈中各方是可以通过合作等方式获得双赢的,但实际上,由于信息的不对称,很多时候我们是认识不到这点的。

【2】、智猪博弈——纳什均衡的典例

假设猪圈里有一头大猪、一头小猪。猪圈的一头有猪食槽,另一头安装着控制猪食供应的按钮,按一下按钮会有10个单位的猪食进槽,但是谁按按钮就会首先付出2个单位的成本。按钮和猪食槽在相反位置,按按钮的猪要付出2个单位的成本,并且丧失了先到槽边进食的机会。

若小猪先到槽边进食,因为缺乏竞争,进食的速度一般,最终大小猪吃到食物的比率是6∶4;若同时到槽边进食,大猪进食速度加快,最终大小猪收益比是7∶3;若大猪先到槽边进食,大猪会霸占剩余所有猪食,最终大小猪收益比9∶1。

那么,在两头猪都有智慧的前提下,最终结果是:小猪选择等待,大猪去按按钮。(摘自百度百科)

这个故事,包括刚才的囚徒困境,都是纳什均衡极为经典的例子。所谓纳什均衡,是一种策略的组合,在这种策略组合下,每一位玩家的策略改变都是为了使当前局面对自己更优。纳什均衡可以分成两类:“纯策略纳什均衡”和“混合策略纳什均衡”。关于相应的概念,在这里就不再赘述了,有兴趣的读者可以自行了解。

一篇文章不可能涉及所有的方面,因此关于本文中没有提及的游戏,还请各位读者自行了解。另外,如果想了解公平组合游戏,请移步公平组合游戏篇:小谈博弈论(公平组合游戏篇)。