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