三个博弈论算法分析

48 阅读 0 评论 32 点赞

我是靠谱客的博主喜悦电话，最近开发中收集的这篇文章主要介绍三个博弈论算法分析，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

主要讨论三个比较常见的博弈游戏

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*φ时，当前局势为奇异局

从胜负概率角度，如果堆中数量随机，先手一方优势很大

（相应经典题目是POJ-1067）

三个十分相似的游戏，但局势的判断和必胜策略差异却很大，但却又都来自数的性质，这不得不说是一件让人惊奇的事情。