题解 P6991 【[NEERC2014]Gomoku】

写一个能与任意策略对局取胜的程序是很困难的,所以从先手的策略入手。首先,分数最大等价于分数的增加量最大,如果先手的一次下子能破坏一个后手有 kk 个棋子的胜利组合,分数的增加量是 0(502k)=502k0-(-50^{2k})=50^{2k}。如果这次下子能形成一个先手有 k+1k+1 个棋子的胜利组合,分数的增加量是 502k+1502k150^{2k+1}-50^{2k-1},可以近似地认为是 502k+150^{2k+1}。对于任意一个位置,包含它的胜利组合最多只有 2020 个,而计分使用的底数是 5050,因此多个 50x50^x 的增加量也不会超过 50x+150^{x+1}。因此先手下子的优先级是:扩展先手 44 个子 >> 破坏后手 44 个子 >> 扩展先手 33 个子 >> 破坏后手 33 个子 >> 扩展先手 22 个子 >> 破坏后手 22 个子 >> 扩展先手 11 个子 >> 破坏后手 11 个子。注意到在形如下图的情况中,黑点所示位置具有较高的优先级。然而这一位置下子实际上作用不大,几乎是浪费的。我们可以构造出这种情况引诱先手浪费手数来取得优势。

分析了先手的策略之后,我们来构造具体方案。本题较为开放,能够构造出的获胜方案可能很多,这里只讲其中一种。

我们的前两手选择一个远离中心,又不太接近边界的地方,在两个对角线相邻的地方下子,例如 (5,16)(5,16)(4,15)(4,15)。根据上面的优先级,先手会选择靠近其中心第一个子的位置下子,并连成一行。此时,先手会在中心形成一行相邻的三个子。这时我们需要防守,在这一行相邻两侧的任意一侧下子。先手会下在另一侧,我们继续防守,下在这一侧相邻的位置。一种可能的情况如下图所示。

此时先手会在后手两个子所在的那一行,相邻的两侧之中的一侧下子。无论先手选择哪侧我们都下在另一侧,这样会形成上面所说的情况,引诱先手“浪费”一手。我们选择在中间那个子另一个对角线方向相邻的位置下子,如下图:

此时,可以计算出红点的分数增加量超过 3×504+2×5033\times 50^4+2\times 50^3,黑点和蓝点的分数增加量均为 3×504+7×502+x×5013\times 50^4+7\times 50^2+x\times 50^1(其中 x×501x\times 50^1 表示由单个先手棋子带来的贡献),所以先手会一定会选择红点。我们可以在两个黑点中任选一个,这样我们会形成一行三个棋子相邻,先手会在某一侧防守。接下来我们在另一个黑点旁边的位置下子,先手会下在那一行三个棋子的另一侧。然后我们下在另一个黑点上,形成一个十字。一种可能的情况如下:

形成十字之后,我们已经必胜。无论先手选择哪里,我们都有办法找到一个位置形成一行四个相邻棋子,且两侧都可扩展。接下来先手下在任何一侧我们下在另一侧即可胜利。