V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
gullitintanni
V2EX  ›  程序员

骑士决斗(面试题分享)

  •  
  •   gullitintanni · 1 天前 · 1869 次点击

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

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

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

    试问,该游戏是否存在必胜策略?


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

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

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

    坐等 V 站大佬的题解 ;)

    17 条回复    2025-09-04 23:02:39 +08:00
    laonger
        1
    laonger  
       1 天前
    怎么算“占据”?是”落点“,还是“跨越过的 L 型”,还是“跨越过的 2*3 矩形”?
    dssxzuxc
        2
    dssxzuxc  
       1 天前
    跨过的路径肯定不算占据啊。
    拿笔画了好久,感觉不存在必胜的策略,只要先手能走到中间后手怎么玩。
    mooyo
        3
    mooyo  
       1 天前
    先手占天元必胜?
    red13
        4
    red13  
       18 小时 57 分钟前
    有想这问题的功夫还不如去学学英语呢
    Felixchen1062
        5
    Felixchen1062  
       17 小时 41 分钟前   ❤️ 2
    这题的源头像不像这个 https://github.com/udacity/AIND-Isolation
    kiraskyler
        6
    kiraskyler  
       16 小时 37 分钟前
    先手玩家第一个落到中心点,这样剩下的点位重新是偶数点,且对手无法跟随自己落位中心,这样先手必胜
    ygtq
        7
    ygtq  
       16 小时 23 分钟前
    题目没说清,移动到底是怎么移动,是随意移动还是只能移动到周围 4 个或者 8 个格子? 能不能跳跃?
    wzwtt
        8
    wzwtt  
       16 小时 13 分钟前 via iPhone
    for1shot
        9
    for1shot  
       16 小时 3 分钟前
    如果是奇数格子的话,先手就有必胜策略啊,直接占了天元,然后模仿棋后手的人即可。先手的人天然能优先多占一个格子,然后后手就会最先无路可走。
    lawlyet666
        10
    lawlyet666  
       15 小时 34 分钟前
    "有想这问题的功夫还不如去学学英语呢"

    =>有学英语的功夫,还不如跑两单外卖呢(手动狗头
    mightybruce
        11
    mightybruce  
       15 小时 24 分钟前
    这个问题算是 one knight tour 的拓展, 给一个相关视频。
    BitGeek
        12
    BitGeek  
       14 小时 42 分钟前
    如果是奇数,先手玩家可以先占据中心点对,然后镜像方案就用不了了,如果不存在吃子的规则,因为先手可以多走一步,所以先手必胜
    BitGeek
        13
    BitGeek  
       14 小时 39 分钟前
    @BitGeek 及时说只要先手先占据了中心点,后手如果不能吃掉先手的棋子,所能走的位置一定比先手少,只要证明这个,先手就必胜,但前提条件是 n 和 m 都是奇数。
    vfs
        14
    vfs  
       10 小时 56 分钟前
    当 m = n = 1 时, 无路可走。 当 m=n=3 , 即使先手,也进入不了“天元“
    fdd92
        15
    fdd92  
       9 小时 8 分钟前
    @red13 #4 不是每件事都需要那么功利。想学英语你可以自己学,不需要发这种扫兴言论。
    fdd92
        16
    fdd92  
       8 小时 37 分钟前
    @for1shot #9 先手占据了中点后,如果后手下一步走到先手下一步走不到的位置,先手怎么继续执行模仿棋
    guyeu
        17
    guyeu  
       3 小时 3 分钟前
    双方是对角线,那先手一方把棋子移动到尽头卡死对方的象不就赢了?
    关于   ·   帮助文档   ·   自助推广系统   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1162 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 18:06 · PVG 02:06 · LAX 11:06 · JFK 14:06
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.