南数棋舍 | 道不尽的点格棋(进阶篇)

半心半意的施舍

半心半意的施舍（half-hearted handout）：这又是什么情况？别急，和上面一样，这也是针对2-链提出的概念。如果先手像下面这么走的话，相当于放弃了控制权，因为后手总是可以走出某一步谢绝这2个格子，从而取得控制权。

在起始局中，双方如果都想要下出最优的一步，首先应当遵循下面的几条原则：

1

当对方为你开启了一条链（一个环）时，你应该立刻占领它，至少占领除谢绝的2个（4个）格子外的全部格子。

2

当对方为你开启了一条短链时，立刻全部占领它。

3

不要给出半心半意的施舍。

理由很简单，对于前两条，如果你不占领链或环而能够在接下来的局势G中作为先手取胜，那么占领它们便更加确保了胜利；而如果不占领它们导致你的失败，那就更要占领它们啦！

至于最后那条，是因为这步棋会将选择权交给对手，他可以根据之后的局势中自己净收入的大小决定是否掌握控制权，使得自身利益最大化，而这当然是你不想看到的！

下面我们给出指导起始局走向的一个十分重要的等式：

Thm1

设开局时棋盘上点的数量为 ，终局时所有一箭双雕的总数量为 ，双方共经过了 轮对弈（一方下完包括所有得分后的“奖励”性一步后交给对方来下，这算做一轮），则等式： 恒成立。

Proof

设棋盘总点数为 ，总格子数 ，则终局时双方共画出 条竖线， 条横线，那么终局时总步数

考虑到当 走的一步未占领任何格子时，一步代表一轮；占领一个格子时，一步对应一格；占领两个格子时，算作一箭双雕数，并且最后一轮的最后一步占领了格子但不需走出下一步，那么：

这个等式的重要性在于它揭示了谁可以首先在标准决胜局中掌握控制权!由于掌握控制权的一方在标准决胜局中是后手，所以刚开始下点格棋时，先手会努力使得标准决胜局之前双方总轮数为 奇数，后手则会使其为 偶数。

考虑到一个环可以提供两个一箭双雕步数，而一条长链只能提供一个，并且在最后的一条链（或环）中R会选择全部占领，会少一个一箭双雕步数，所以总的来看，点数与最终长链数之和与总轮数的奇偶性相反！这样在起始局中， 先手可以努力地使得点数与最终长链数之和为偶数，后手则相反，这就为局势发展提供了借鉴！

当然，仅有上面的准则还不够细致，起始局仍有极大的不确定性。为了寻找到更多参考走法，我们可以考虑和点格棋十分相近的 尼姆串游戏（Nimstring game），详细的介绍可以参考[5]。

起始局下到最后，已经十分接近标准决胜局了，差别只是前者多了一些长度为1或2的短链。我们将所有这些短链合在一起看做另一个局势H，称之为 前哨战（short chain’s exchange）。

由于此时谁掌握控制权已经可以通过上面的等式计算出来了，所以H可以看做是独立于标准决胜局的另一个游戏，我们不妨假设双方首先完成H，其次再进入标准决胜局。

双方在前哨战中能抢到的格子数量由下面的定理给出：

Thm2

设在前哨战中 R 和 L 分别能够抢到 和 个格子，则 。

证明可以参考[5]，这里就不给出了。从这里可以看到，想要取得控制权的一方在前哨战里是占不到便宜的。

标准决胜局

游戏进行到这个阶段，基本上大局已定，剩下的就是双方如何通过细致地计算使自身利益最大化了。R可以在剩下的格子中获得至少其中的一半，而L可以决定双方在剩下的这些结构中按照什么顺序依次进行抢夺。

有趣的是，L如果想要在标准决胜局中领先R，只有其在起始局中获得比R多的格子才行（要么是R故意牺牲的，要么是L在前哨战中抢到的）。

R的最优策略

对于R而言，在这一阶段其唯一需要考虑的问题就是何时选择放弃控制权（或是一直保持控制）。对此我们先来定义一下 局势的值v(G)：

局势G在标准决胜局中的值v(G)指R在G中的净收入。

我们在初级篇中已经证明了相应策略，现在把它重新描述一下：

Thm3

假设在标准决胜局中L开启了一条链，那么R应保持控制，当且仅当 ，否则应放弃控制权；假设L开启了一个环，那么R应保持控制，当且仅当 ，否则应当放弃控制。

现在我们知道了，v(G)很重要！！！

那么问题来了，如何计算v(G)呢？对此已经有各路强者大显神通了，详细计算方法可以参考[3]、[4]、[5]。不过，对于小型棋盘，我们完全可以枚举每一种情况，选择最有利的那条进行计算。

L的最优策略

由于L在标准决胜局中不占优势，所以他能做的就是使得v(G)的值最小，这又一次提醒我们：

v(G)很重要！！！

经过一通计算猛如虎，L可以采取下面的最优策略（设标准决胜局为G）：

1

如果G不含长链，L应开启最短的环；如果G不含环，L应开启最短的链。

2

如果G含环但是不包含3-链，L应开启最短的环。

3

L应当尽量使得环的数量最大（这一策略同样适用于一般的决胜局中）

其他的策略由于太过复杂，这里就不展示了，详细资料可参考[3]和[4]。

不得不承认，点格棋的确是说不完道不尽呢，那么对于本期介绍大家是否满意呢？

南数棋舍期待您下一次的拜访哦~

参考文献

[1] Elwyn R. Berlekamp, “The Dots-and-Boxes Game: Sophisticated Child’s Play”, A K Peters Ltd. (2000).

[2] Elwyn R. Berlekamp, John H. Conway, Richard Guy, “Winning ways for your Mathematical Plays, 2nd edition”, A K Peters Ltd., volumes 1 (2001) & 3 (2003).

[3] Elwyn R. Berlekamp, Katherine Scott, “Forcing Your Opponent to Stay in Control of a Loony Dots-and-Boxes Endgame”, in “More Games of No Chance”, edited by Richard J. Nowakowski, MSRI Publications - Volume 42, Cambridge University Press (2002).

[4] Kevin Buzzard, Michael Ciere, “Playing Simple Dots and Boxes Endgames Optimally”, in Integers: Electronic Journal of Combinatorial Number Theory, volume 14 (2014).

[5] Alexandre S. Ballarín, “Combinatorial Game Theory: The Dots-and-Boxes Game”, Master’s thesis, Universitat Politecnica de Catalunya, 2015.

文编 王睿智

美编 赵世驹

责编 卜一凡返回搜狐，查看更多