[算法问题]这个游戏有没有先手（后手）必胜的策略呢？

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

V2EX 提问指南

这是一个创建于 3243 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

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

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

11 条回复 • 2016-01-11 14:23:03 +08:00

sumhat

2016-01-07 20:13:35 +08:00

感觉先手有优势，但是不是必胜就不知道了。

txx

2016-01-07 20:29:28 +08:00 via iPhone

9 的阶乘次枚举看一下先手胜率就知道了

nichijou

2016-01-07 20:58:39 +08:00

直觉看起来先手劣势啊，不要看随机落子的概率，看熟悉规则厚之后的下棋策略，好复杂，好问题，坐等高人

Bryan0Z

2016-01-07 21:12:45 +08:00 via Android

@txx 这里枚举没什么用吧

Bryan0Z

2016-01-07 21:23:26 +08:00 via Android

我觉得后手有优势，每个棋子占一横行和一个纵行。把棋子分为 123 456 789 三组，分别对应小中大，如果先手填的是大数，则后手往同列填大数。如果先手填的是小数，则后手往同列填小数。总之尽量保证 123 456 789 在同一列，并且在行上尽量分散

Bryan0Z

2016-01-07 23:00:07 +08:00 via Android

写了两个程序试了一下…确实先手占优势

nichijou

2016-01-07 23:17:16 +08:00

@Bryan0Z 别闹，程序怎么运行的，讨论优势与否，设定至少得是两个会玩的人对局吧

Bryan0Z

2016-01-07 23:44:43 +08:00 via Android

@nichijou 我现在的算法是:
每次用随机数决定防守还是进攻及位置
当可能出现对手乘积超过中位数 4*5*6 的 1.2 倍时，必然防守
当自己乘积可能超过这个数时，必然进攻
填满 5 个数的时候，双方每次遍历所有可能性，找出最优解

Bryan0Z

2016-01-07 23:46:36 +08:00 via Android

@nichijou 在防守和进攻的选择上，人为去掉了一些必输的情况，比如:
先手选 9 ，后手防守，同一行填 1 ，先手尽可能保证最小数在同一行，在不同列，在同一行填 2
这种情况下，后手接下来必输

tianshuo

2016-01-08 14:04:02 +08:00

@Bryan0Z 随机不合理吧，这个得靠 minmax(alpha beta 剪枝)来算吧……这不应该是一个概率问题呢

tianshuo

2016-01-11 14:23:03 +08:00

这个知乎大神们给出答案了，先手必胜： https://www.zhihu.com/question/39250173