这是一个创建于 36 天前的主题，其中的信息可能已经有所发展或是发生改变。
今天下午面试的时候被问到了一个很有意思的博弈论问题。 网上搜了一下没有找到原题，应该是面试官原创。现在发来分享给大家：
现有两名玩家进行一场名为“骑士决斗”的游戏，规则如下：
国际象棋棋盘上有两枚“骑士”棋子，在游戏开始时位于棋盘的两个对角。 两名玩家各控制一枚“骑士”，按照常规国际象棋对局的规则轮流移动棋子， 但有一条额外规则：棋子的落点必须是双方棋子均未曾占据过的格子。 若一名玩家无法按规则移动棋子，则对手获胜。
试问，该游戏是否存在必胜策略？
这个问题听起来有点唬人，但读懂题干后就会朴素地发现，后手玩家存在简单的必胜策略： 不论先手玩家如何移动棋子，后手玩家只需要将自己的棋子移动到与之中心对称的位置即可。也就是所谓的“模仿棋”。 如此，先手玩家必然率先走投无路。
这时，面试官说，那我们把棋盘扩展一下，对于 m*n 的棋盘（ m, n 均为奇数），答案又是如何呢？
这下把我难住了。但很明显，在这种情况下，先手方可以占据“天元”以破解“模仿棋”。
坐等 V 站大佬的题解 ;)
 | 1 laonger 36 天前 怎么算“占据”？是”落点“，还是“跨越过的 L 型”，还是“跨越过的 2*3 矩形”？ |
 | 2 Ketteiron 36 天前 跨过的路径肯定不算占据啊。 拿笔画了好久，感觉不存在必胜的策略，只要先手能走到中间后手怎么玩。 |
 | 3 mooyo 36 天前 先手占天元必胜？ |
 | 4 red13 36 天前 有想这问题的功夫还不如去学学英语呢 |
 | 5 Felixchen1062 36 天前  2 这题的源头像不像这个 https://github.com/udacity/AIND-Isolation |
 | 6 kiraskyler 35 天前 先手玩家第一个落到中心点，这样剩下的点位重新是偶数点，且对手无法跟随自己落位中心，这样先手必胜 |
 | 7 ygtq 35 天前 题目没说清，移动到底是怎么移动，是随意移动还是只能移动到周围 4 个或者 8 个格子？ 能不能跳跃？ |
 | 8 wzwtt 35 天前 via iPhone |
 | 9 for1shot 35 天前 如果是奇数格子的话，先手就有必胜策略啊，直接占了天元，然后模仿棋后手的人即可。先手的人天然能优先多占一个格子，然后后手就会最先无路可走。 |
 | 10 lawlyet666 35 天前 "有想这问题的功夫还不如去学学英语呢" =>有学英语的功夫，还不如跑两单外卖呢(手动狗头 |
 | 11 mightybruce 35 天前 这个问题算是 one knight tour 的拓展, 给一个相关视频。 |
 | 12 BitGeek 35 天前 如果是奇数，先手玩家可以先占据中心点对，然后镜像方案就用不了了，如果不存在吃子的规则，因为先手可以多走一步，所以先手必胜 |
 | 14 vfs 35 天前 当 m = n = 1 时， 无路可走。 当 m=n=3 ， 即使先手，也进入不了“天元“ |
 | 17 guyeu 35 天前 双方是对角线，那先手一方把棋子移动到尽头卡死对方的象不就赢了？ |
 | 18 WithoutSugarMiao 34 天前 有这空，不如刷点算法，比这有意思 |
 | 19 mmdsun 34 天前 via iPhone @WithoutSugarMiao 这就可以当算法题目来解了，动态规划博弈问题 |
Select Language