棋盘游戏和初步博弈论

chengni · 2018-09-30 19:54:35 · 个人记录

前置博客

在上文中，我们介绍了取石子游戏中蕴含的博弈论思想，那么接下来我们介绍另一种游戏模型，棋盘游戏(棋类游戏)。

棋类游戏有很多种，围棋、跳棋、象棋、国际象棋等等，是人类智慧的结晶。

棋类游戏可以益智，增强思维能力；也可以用来娱乐，是消磨时间的好方法；还可以用来zb(雾)。

总之，棋类游戏非常好。

好，游戏介绍结束。谢谢大家观看。

先来一道送分题

一个二维的棋盘长为 n 宽为 1，初始 A 和 B 各有一个棋子放在棋盘的某个位置，两个轮流将自己的棋子向左或者向右移动一格，谁不能移动谁就输了，请问谁会赢。

冷静分析，胜利方式就是把对方逼到一边的尽头。

那么我们怎么能把对方逼到一端呢，我们至少应该先接近对方。

因为我们每一步都要移动，所以事实上两个人的距离的奇偶性是不变的，而先一步和对手贴上的人就赢得了比赛。因为我这一步贴上对手之后，对手只能往另一个方向走，然后我们重复下去，对手就被逼到死角了。

而显然，当两个人之间距离为奇数的时候，先手必胜，反之后手必胜。

似乎这道题就这么被我们切了？

但我们很快就会发现，这道题跟后面的内容并没有什么关系。

这道题扔出来的目的只是想告诉大家，不要被博弈论的珂怕蒙蔽了双眼，要冷静分析，认真思考，再确定自己想不出来

题目1

设棋盘左下角为 (0,0)，在 (x,y) 处有一个卒(已过河)，两个人轮流行动，每次只能向下或者向左走，谁不能动谁就输了，请问谁会赢？

emmmmmm

好我们换一道题

题目2

设棋盘左下角为 (0,0)，在 (x,y) 处有一个车，两个人轮流行动，每次只能向下或者向左走，谁不能动谁就输了，请问谁会赢？

实际上这题我们已经做过了，只是看你能不能够想到。

没有印象的去看看我的前一篇博客吧。

我们把棋子的两维坐标看成是两堆石子，结束状态是坐标均为 0 ，一次可以使某一维的坐标减少若干。这个问题是不是眼熟了

我们的结论是，当棋子的横坐标和纵坐标不相等时先手必胜，反之后手必胜。

如图，标记点必败。(excel画的图见谅)

题目3

好现在那个棋子是国王(国际象棋)

我们再次尝试把这个问题转化为取石子游戏，我们一次可以从某一堆石子中拿走一个石子，或者从两堆石子中各拿走一个石子

当然也可以 DP ，然后就会得到这样的一个图

可以证明，当对手处在必败点时，无论他怎么走，我们都能使他回到必败点。

题目4

现在那个棋子是马或者相(中国象棋)或者相(国际象棋)

首先我们要明确，并不是所有的点都能得到结果，因为有些点是不能到达结束点的。

其次由于只能向左下走，这种情况处理起来很简单。

题目5

好现在那个棋子是后(国际象棋)

我们先要知道后的移动方式，在本游戏中，后可以向下、左或者左下移动任意格

由于后非常强大，我们标记它的必胜点

那么很明显这些地方都能一步到达结束点

这个时候我们发现出现了两个非常惨淡的点，它们无论怎么走都会到达必胜点，于是他们是必败点，以他们为基础扩展

重复过程，懒得画更大了自行体会吧。

空出来的点都是必败点。

这个“挪动皇后”的游戏是由 Rufus Isaacs 在 1960 年左右提出来的，但这个问题其实早就出现了。1907 年，荷兰数学家 Willem Abraham Wythoff 提出了一个双人对弈游戏，后来人们把它叫作 Wythoff 游戏。游戏规则是这样的。地上有两堆石子，其中一堆有 m 个石子，另外一堆有 n 个石子。两名玩家轮流取走石子，规定每次要么从其中一堆石子中取走任意多个石子，要么从两堆石子中取走相同数量的石子。等到谁没有石子可取了，谁就输了。也就是说，取到最后一个石子的玩家获胜

Wythoff 给出的答案异常简单——所有这样的数对从小到大依次为：

其中 φ = (\sqrt5 + 1) / 2 ， [x] 表示不超过 x 的最大整数（当 x ≥ 0 时， [x] 可以简单地理解为取 x 的整数部分）。于是我们得到了一个数列

看起来似乎和那个图很符合(左下角是(0,0))

熟悉斐波那契通项公式的人看到这个 φ ，是不是会感到一丝熟悉？

不熟悉的看一下这道题

月落乌啼算钱

关于斐波那契公式和Wythoff 游戏的爱恨纠纷，可以看这篇文章

本篇文章的内容基本就是这样了

希望大家能通过这篇博文对棋类游戏更感兴趣(雾)，在面对棋类博弈的时候能够有一种意识将其转化为已知的模型，并通过 DP 和找规律解题。

好吧其实主要目的就是觉得那篇博文很牛逼，想让你们去看

看起来内容有点扯淡。还请谅解