V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tianshuo
V2EX  ›  问与答

[算法问题]这个游戏有没有先手(后手)必胜的策略呢?

  •  
  •   tianshuo · 2016-01-07 19:38:12 +08:00 · 2437 次点击
    这是一个创建于 3244 天前的主题,其中的信息可能已经有所发展或是发生改变。

    在 3X3 的方格里,两人轮流不重复地填数字 1-9 。填的顺序和位置随意。
    填满后,先手算每一个横排三个数相乘然后再把三个数相加为最终得分,后手算每一个数列三个数相乘然后再把三个数相加为最终得分。谁的分数越高谁赢。

    请问谁获胜?最优方案是什么?

    一个简单的 demo: http://tianshuo.github.io/Matrix-Game
    (之后可能做成网络对战+人机对战版)

    11 条回复    2016-01-11 14:23:03 +08:00
    sumhat
        1
    sumhat  
       2016-01-07 20:13:35 +08:00
    感觉先手有优势,但是不是必胜就不知道了。
    txx
        2
    txx  
       2016-01-07 20:29:28 +08:00 via iPhone
    9 的阶乘次 枚举 看一下先手胜率 就知道了
    nichijou
        3
    nichijou  
       2016-01-07 20:58:39 +08:00
    直觉看起来先手劣势啊,不要看随机落子的概率,看熟悉规则厚之后的下棋策略,好复杂,好问题,坐等高人
    Bryan0Z
        4
    Bryan0Z  
       2016-01-07 21:12:45 +08:00 via Android
    @txx 这里枚举没什么用吧
    Bryan0Z
        5
    Bryan0Z  
       2016-01-07 21:23:26 +08:00 via Android
    我觉得后手有优势,每个棋子占一横行和一个纵行。把棋子分为 123 456 789 三组,分别对应小中大,如果先手填的是大数,则后手往同列填大数。如果先手填的是小数,则后手往同列填小数。总之尽量保证 123 456 789 在同一列,并且在行上尽量分散
    Bryan0Z
        6
    Bryan0Z  
       2016-01-07 23:00:07 +08:00 via Android
    写了两个程序试了一下…确实先手占优势
    nichijou
        7
    nichijou  
       2016-01-07 23:17:16 +08:00
    @Bryan0Z 别闹,程序怎么运行的,讨论优势与否,设定至少得是两个会玩的人对局吧
    Bryan0Z
        8
    Bryan0Z  
       2016-01-07 23:44:43 +08:00 via Android
    @nichijou 我现在的算法是:
    每次用随机数决定防守还是进攻及位置
    当可能出现对手乘积超过中位数 4*5*6 的 1.2 倍时,必然防守
    当自己乘积可能超过这个数时,必然进攻
    填满 5 个数的时候,双方每次遍历所有可能性,找出最优解
    Bryan0Z
        9
    Bryan0Z  
       2016-01-07 23:46:36 +08:00 via Android
    @nichijou 在防守和进攻的选择上,人为去掉了一些必输的情况,比如:
    先手选 9 ,后手防守,同一行填 1 ,先手尽可能保证最小数在同一行,在不同列,在同一行填 2
    这种情况下,后手接下来必输
    tianshuo
        10
    tianshuo  
    OP
       2016-01-08 14:04:02 +08:00
    @Bryan0Z 随机不合理吧,这个得靠 minmax(alpha beta 剪枝)来算吧……这不应该是一个概率问题呢
    tianshuo
        11
    tianshuo  
    OP
       2016-01-11 14:23:03 +08:00
    这个知乎大神们给出答案了,先手必胜: https://www.zhihu.com/question/39250173
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   6108 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 06:16 · PVG 14:16 · LAX 22:16 · JFK 01:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.