骑士决斗（面试题分享）

[gullitintanni]

今天下午面试的时候被问到了一个很有意思的博弈论问题。 网上搜了一下没有找到原题，应该是面试官原创。现在发来分享给大家：

现有两名玩家进行一场名为“骑士决斗”的游戏，规则如下：

国际象棋棋盘上有两枚“骑士”棋子，在游戏开始时位于棋盘的两个对角。 两名玩家各控制一枚“骑士”，按照常规国际象棋对局的规则轮流移动棋子， 但有一条额外规则：棋子的落点必须是双方棋子均未曾占据过的格子。 若一名玩家无法按规则移动棋子，则对手获胜。

试问，该游戏是否存在必胜策略？

---

这个问题听起来有点唬人，但读懂题干后就会朴素地发现，后手玩家存在简单的必胜策略： 不论先手玩家如何移动棋子，后手玩家只需要将自己的棋子移动到与之中心对称的位置即可。也就是所谓的“模仿棋”。 如此，先手玩家必然率先走投无路。

这时，面试官说，那我们把棋盘扩展一下，对于 m*n 的棋盘（ m, n 均为奇数），答案又是如何呢？

这下把我难住了。但很明显，在这种情况下，先手方可以占据“天元”以破解“模仿棋”。

坐等 V 站大佬的题解 ;)

[laonger]

怎么算“占据”？是”落点“，还是“跨越过的 L 型”，还是“跨越过的 2*3 矩形”？

[Ketteiron]

跨过的路径肯定不算占据啊。
拿笔画了好久，感觉不存在必胜的策略，只要先手能走到中间后手怎么玩。

[mooyo]

先手占天元必胜？

[red13]

有想这问题的功夫还不如去学学英语呢

[Felixchen1062]

这题的源头像不像这个 https://github.com/udacity/AIND-Isolation

[kiraskyler]

先手玩家第一个落到中心点，这样剩下的点位重新是偶数点，且对手无法跟随自己落位中心，这样先手必胜

[ygtq]

题目没说清，移动到底是怎么移动，是随意移动还是只能移动到周围 4 个或者 8 个格子？ 能不能跳跃？

[wzwtt]

有点像这个
https://github.com/assafcarlsbad/Joust

[for1shot]

如果是奇数格子的话，先手就有必胜策略啊，直接占了天元，然后模仿棋后手的人即可。先手的人天然能优先多占一个格子，然后后手就会最先无路可走。

[lawlyet666]

"有想这问题的功夫还不如去学学英语呢"

=>有学英语的功夫，还不如跑两单外卖呢(手动狗头

[mightybruce]

这个问题算是 one knight tour 的拓展, 给一个相关视频。

[BitGeek]

如果是奇数，先手玩家可以先占据中心点对，然后镜像方案就用不了了，如果不存在吃子的规则，因为先手可以多走一步，所以先手必胜

[BitGeek]

@BitGeek 及时说只要先手先占据了中心点，后手如果不能吃掉先手的棋子，所能走的位置一定比先手少，只要证明这个，先手就必胜，但前提条件是 n 和 m 都是奇数。

[vfs]

当 m = n = 1 时， 无路可走。 当 m=n=3 ， 即使先手，也进入不了“天元“

[fdd92]

@red13 #4 不是每件事都需要那么功利。想学英语你可以自己学，不需要发这种扫兴言论。

[fdd92]

@for1shot #9 先手占据了中点后，如果后手下一步走到先手下一步走不到的位置，先手怎么继续执行模仿棋

[guyeu]

双方是对角线，那先手一方把棋子移动到尽头卡死对方的象不就赢了？

[WithoutSugarMiao]

有这空，不如刷点算法，比这有意思

[mmdsun]

@WithoutSugarMiao
这就可以当算法题目来解了，动态规划博弈问题