关于一加一碰手游戏的一点研究

本文主要是介绍关于一加一碰手游戏的一点研究，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

首先介绍 “一加一碰手游戏”。

具体规则是这样的：

1. 游戏有两个玩家，每个玩家有两只手。

2. 初始所有手上的数字都为 \(1\)。

3. 两个玩家轮流行动，轮到一个玩家时他可以选择对方任意一只手上的数字，将自己任意一只手上的数字加上这个数后对 \(10\) 取余数。

4. 若有一只手上的数字为 \(0\) 则收回这只手，这只手不再参与下面的游戏。

5. 先收回两只手的玩家胜。

我们定义一个满足无论双方如何行动都会循环出现的局面为平局。

那么该游戏状态数量有限，信息完备，且没有运气成分参与其中，适用 \(\text{Zermelo}\) 定理。

一只手对一只手

一对一时，双方均只有一种行动方式，结局仅与初始局面有关，设初始双方的数分别为 \(a,b\)，那么仅当存在 \(i(i>0)\) 使得 \(f_ia+f_{i+1}b\equiv 0\pmod{10}\) 时，其中 \(f\) 为斐波那契数列，才能够分出胜负，否则都为和局。

\((a,b)=(1,3),(1,8),(2,1),(2,6),(3,4),(3,9),(4,2),(4,7),(6,3),(6,8),(7,1),(7,6),(8,4),(8,9),(9,2),(9,7)\)（ \(a\) 方先手）时为和局。

两只手对一只手

设一只手的玩家为 \(A\)，两只手的玩家为 \(B\)，\(A=\{a\}\)，\(B=\{c,d\}\)，\(B\) 先手，下证 \(B\) 存在策略使得 \(A\) 无法直接胜利，局面一定可以进入到一对一。

首先证明一个引理，设 \(a,b\) 都是手上的数，则有 \(a+b\not\equiv a\pmod{10}\)。这点从 \(b\not\equiv 0\pmod{10}\) 来看显然。

接下来有另一个引理，\(B\) 永远都可以保持 \(c\not\equiv d\pmod{10}\)，这点也显然。所以接下来我们默认 \(c\not\equiv d\pmod{10}\)。

然后我们考虑 \(A\) 直接胜利时的的局面 \(F\)，它满足 \(a+c\equiv 0\pmod{10}\) 或者 \(a+d\equiv 0\pmod{10}\)，且轮到 \(A\) 行动。不妨设 \(d\) 满足上式。

倒退回上一局面 \(F'\)，此时 \(B=\{c,d'\},A=\{a\}\)，若局面要变成 \(F\)，则 \(B\) 一定选择将 \(d'\) 变为 \(d'+a\)，否则有 \(d'=d\)，\(a+d'\equiv 0\pmod{10}\)，在 \(F'\) 上一局面时 \(A\) 就会获胜。

那么我们有 \(d=d'+a\)，则 \((d'+a)+a\equiv 0\pmod{10}\)，由上面引理我们得到

又由于 \(c\not\equiv d'\pmod{10}\)，所以得到

注意上两个式子，这说明 \(B\) 如果在 \(F'\) 时不选择将 \(d'\) 变为 \(d'+a\) 而是将 \(c\) 变为 \(c+a\) 就可以避开局面 \(F\)，而在这个新的局面中，\(A\) 无法直接胜利。

这样就证完了，由于二对一的局面要么变为一对一，要么 \(A\) 直接赢，我们已经证明了 \(B\) 存在策略规避后者，也就是说一定可以进入到一对一，此时的胜负取决于初始数字。

两只手对两只手

显然，在经过有限次行动后只会变为二对一。

是否存在必胜策略？

根据上面的结论，游戏胜负其实取决于一对一时的初始数字，就目前来看，双方皆没有策略来确定进入一对一时的数字，那么根据 \(\text{Zermelo}\) 定理，双方不存在必胜策略，但存在必不败策略。

我们该如何行动？

实际上，我们并没有找出一个必不败的策略，这个有点难，不过我们可以打出一个 \(10\times 10\times 10\times 10\) 的表，确定下一步该如何行动，局面数 \(\leq 10^4\)，可以接受。

如果你想稳定进入一对一的情况，那么有一个策略：二对二时可以随意出，当对面收回一只手时，你只需要保证两只手的任意一只都满足加上两倍的对面数字不为 \(0\) 即可。

或许还可以穷举局面后算胜率后统计更优秀的行动方法，如果有空明天我会继续补。

这篇关于关于一加一碰手游戏的一点研究的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！