Java教程

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

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

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

具体规则是这样的:

  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}\),由上面引理我们得到

\[d'+a\not\equiv 0\pmod{10} \]

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

\[(c+a)+a\not\equiv 0\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\) 即可。

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

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