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