一个简单的手指游戏和逆向归纳法

小时候，即使是一个非常简单的游戏，也能沉浸其中。反倒是今天对游戏挑剔了起来，却也发现玩游戏的心情不在了，时间不在了，朋友不在了，快乐也不在了。

我倒是想起以前玩过的一个非常简单的小游戏，掰着指头两个人就能玩一局。规则如下：

甲乙两人伸出双手，分别摆一个“1”的手势。轮流进行，其中一方将自己任意一只手的数字与对方任意一只手的数字相加，替换掉自己原先的数字，如果超出了10，则减去10。变成0的手要背到身后去，之后就不能再用了。谁先将自己的手上的数字都变成0，谁就获胜。

（插一句，似乎全世界只有少数国家会用一只手表示一到十，所以这个游戏某种意义上讲也是中国特供。）

从知道这个游戏开始，我就一直很想知道，如果两个人计算力足够强，这个游戏会变成什么样子。也就是必胜策略，以及有没有看似卖个破绽实则绝地反击的技巧。由策梅洛定理可以知道双方或者有一方有必胜策略，或者一定平局。至于这个游戏里有趣的点，我们先用计算机把最优策略找出来再看吧。

这个游戏的状态空间很小，每个人从1-99，两个人不超过10000。再抛去左右手的对称性，每个人只有55种组合，两个人就是55*55=3025种，不过同样的局面轮到甲乙两人应该算两个状态，所以实际的状态数是6050。在其中其实也有些状态是没法到达的，比如双方四只手都是同一个数的状态。

写一下这个游戏吧：

A_WIN = 0
B_WIN = 1
DRAW = 2
UNKNOWN = 3

PLAYER_A = 0
PLAYER_B = 1

LEFT_TO_LEFT = 0
LEFT_TO_RIGHT = 1
RIGHT_TO_LEFT = 2
RIGHT_TO_RIGHT = 3


def tuple_to_index(i, j):
    if i > j:
        i, j = j, i
    index = (j + 1) * j // 2 + i + 1
    return index


def index_to_tuple(n):
    j = 1
    while n > j * (j + 1) // 2:
        j += 1
    prev_total = (j - 1) * j // 2
    i = n - prev_total
    return [i - 1, j - 1]

def state_to_index(state):
    i, j = state // 55 + 1, state % 55 + 1
    return index_to_tuple(i), index_to_tuple(j)


def index_to_state(tuple1, tuple2):
    i = tuple_to_index(*tuple1)
    j = tuple_to_index(*tuple2)
    return (i - 1) * 55 + j - 1


class Game:
    def __init__(self):
        self.state = 0
        self.a = [1, 1]
        self.b = [1, 1]

    def set_state(self, state):
        self.a, self.b = state_to_index(state)

    def get_state(self):
        return index_to_state(self.a, self.b)

    def is_terminal(self):
        return self.a == [0, 0] or self.b == [0, 0]

    def get_winner(self):
        if self.a == [0, 0] and self.b == [0, 0]:
            return UNKNOWN
        if self.a == [0, 0]:
            return A_WIN
        if self.b == [0, 0]:
            return B_WIN
        return UNKNOWN

    def update(self):
        self.a.sort()
        self.b.sort()

    def action(self, player: int, action: int):
        if self.a == [0, 0] or self.b == [0, 0]:
            self.a = [0, 0]
            self.b = [0, 0]
            return
        if player == PLAYER_A:
            if self.a[0] == 0 and action // 2 == 0:
                action += 2
            if self.b[0] == 0 and action % 2 == 0:
                action += 1
            a_action = action // 2
            b_action = action % 2
            self.a[a_action] += self.b[b_action]
            self.a[a_action] %= 10
        elif player == PLAYER_B:
            if self.b[0] == 0 and action // 2 == 0:
                action += 2
            if self.a[0] == 0 and action % 2 == 0:
                action += 1
            b_action = action // 2
            a_action = action % 2
            self.b[b_action] += self.a[a_action]
            self.b[b_action] %= 10
        self.update()

相当简单呢（笑）。

求解最优策略，可以用一个极大极小搜索，或者像我这里一样，用一个逆向归纳。核心思路如下：

• 如果轮甲走，他的四个动作后的新状态有一个是必胜态，那么他会选择这个动作，并且之前的动作也是必胜态。也就是“乙先甲胜的前一个是甲先甲胜”
• 如果轮甲走，他的四个动作后的新状态全部都是必败态，那么当前的状态是必败态。也就是“甲先乙胜的后面全部都是乙先乙胜”。

class BackwardSolver:
    def __init__(self, game):
        self.game = game
        self.N = 3025  # 总状态数
        self.num_actions = 4  # 总动作数
        self.status = [
            [UNKNOWN] * 2 for _ in range(self.N)
        ]  # [state][player]  表示当前状态的胜负情况
        self.transitions = [
            [[-1 for _ in range(self.num_actions)] for _ in range(2)]
            for _ in range(self.N)
        ]
        # transitions[state][player][action] = next_state
        # 表示在状态state下player走action会得到next_state

    def initialize(self):
        # 初始化，给必胜策略的state打上标记
        for state in range(self.N):  # 全体状态
            self.game.set_state(state)
            if self.game.is_terminal():
                winner = self.game.get_winner()
                if winner == PLAYER_A:  # 乙先甲胜
                    self.status[state][PLAYER_B] = A_WIN
                elif winner == PLAYER_B:  # 甲先乙胜
                    self.status[state][PLAYER_A] = B_WIN

            # 写状态转移表 此后game就没用了
            for player in [PLAYER_A, PLAYER_B]:
                for action in range(self.num_actions):
                    self.game.set_state(state)
                    self.game.action(player, action)
                    next_state = self.game.get_state()
                    self.transitions[state][player][action] = next_state

    def solve(self):
        queue = deque()

        # 终局状态入队
        for state in range(self.N):
            for player in [PLAYER_A, PLAYER_B]:
                if self.status[state][player] in [A_WIN, B_WIN]:
                    queue.append((state, player))

        while queue:
            current_state, current_player = queue.popleft()
            prev_player = 1 - current_player

            for prev_state in range(self.N):
                for action in range(self.num_actions):
                    if (
                        self.transitions[prev_state][prev_player][action]
                        == current_state
                    ):

                        if self.status[prev_state][prev_player] != UNKNOWN:
                            continue  # 已判定就不管

                        # 乙先甲胜的前一个是甲先甲胜
                        if current_player == PLAYER_B and self.status[current_state][PLAYER_B] == A_WIN:
                            self.status[prev_state][PLAYER_A] = A_WIN
                            queue.append( (prev_state, prev_player) )
                        # 甲先乙胜的前一个是乙先乙胜
                        elif current_player == PLAYER_A and self.status[current_state][PLAYER_A] == B_WIN:
                            self.status[prev_state][PLAYER_B] = B_WIN
                            queue.append( (prev_state, prev_player) )
                        # 甲先甲胜的前一个，如果其后继全是甲先甲胜，那么它是乙先甲胜
                        elif current_player == PLAYER_A and self.status[current_state][PLAYER_A] == A_WIN and all([self.status[self.transitions[prev_state][PLAYER_B][a]][PLAYER_A] == A_WIN for a in range(self.num_actions)]):
                            self.status[prev_state][PLAYER_B] = A_WIN
                            queue.append( (prev_state, prev_player) )
                        # 乙先乙胜的前一个，如果其后继全是乙先乙胜，那么它是甲先乙胜
                        elif current_player == PLAYER_B and self.status[current_state][PLAYER_B] == B_WIN and all([self.status[self.transitions[prev_state][PLAYER_A][a]][PLAYER_B] == B_WIN for a in range(self.num_actions)]):
                            self.status[prev_state][PLAYER_A] = B_WIN
                            queue.append( (prev_state, prev_player) )

感觉这个难度放到LeetCode能当个小题出出。

来看结果吧：结果是——平局，双方都有必不败策略。仔细看过一遍后，其他地方也没有给我什么惊喜。那么这个游戏想要好玩点，就是趁对方不注意把对方骗进一个必败状态了。

我决定把距离获胜的步数也记录下来，最后得到的是这么一个东西。

old = self.status[prev_state][prev_player]

# 乙先甲胜的前一个是甲先甲胜
if current_player == PLAYER_B and self.status[current_state][PLAYER_B] > 0:
    self.status[prev_state][PLAYER_A] = min(self.status[prev_state][PLAYER_A], self.status[current_state][PLAYER_B] + 1) if self.status[prev_state][PLAYER_A] != 0 else self.status[current_state][PLAYER_B] + 1
# 甲先乙胜的前一个是乙先乙胜
elif current_player == PLAYER_A and self.status[current_state][PLAYER_A] < 0:
    self.status[prev_state][PLAYER_B] = max(self.status[prev_state][PLAYER_B], self.status[current_state][PLAYER_A] - 1) if self.status[prev_state][PLAYER_B] != 0 else self.status[current_state][PLAYER_A] - 1
# 甲先甲胜的前一个，如果其后继全是甲先甲胜，那么它是乙先甲胜
elif current_player == PLAYER_A and self.status[current_state][PLAYER_A] > 0 and all([self.status[self.transitions[prev_state][PLAYER_B][a]][PLAYER_A] > 0 for a in range(self.num_actions)]):
    self.status[prev_state][PLAYER_B] = max([self.status[self.transitions[prev_state][PLAYER_B][a]][PLAYER_A] for a in range(self.num_actions)]) + 1
# 乙先乙胜的前一个，如果其后继全是乙先乙胜，那么它是甲先乙胜
elif current_player == PLAYER_B and self.status[current_state][PLAYER_B] < 0 and all([self.status[self.transitions[prev_state][PLAYER_A][a]][PLAYER_B] < 0 for a in range(self.num_actions)]):
    self.status[prev_state][PLAYER_A] = min([self.status[self.transitions[prev_state][PLAYER_A][a]][PLAYER_B] for a in range(self.num_actions)]) - 1

if old != self.status[prev_state][prev_player]:
    queue.append( (prev_state, prev_player) )

做些无味的分析吧。首先是如果双方都有两个数字时，轮到谁走，他必不可能输。图上右下角的格子里都是正数，进入这些格子代表甲赢。右上角正数多，左下角负数多。也就是说先消掉一个数字的人是有优势的。左上角则正负参半，不过注意到这个时候双方其实是唯一动作的，也就是进入双方各只有一个数字的状态时，结局就已经确定了。

甲有两个数字，乙有一个数字，如果轮到甲，甲发现自己一个数字和乙互补，则他必须消掉，不然下一回合乙就获胜了，甲没有主动选择不消的选择。同样，甲一个数字乙两个数字时，甲没有不消的理由。那么甲乙双方都是两个数字时，是否会有不消的理由呢？有的，乙先甲一乙二甲必败有不少，但甲先甲二乙二则无必败。因此存在可以凑10但不凑的情况。譬如乙先甲03乙18甲必败，甲之前可能会是39或者23，这种时候不去凑10才是正确的。

反过来看，乙先乙胜的局面，都必须先消掉一个数字，所以甲能如果防止乙先消一个数，就一定必不败。有没有无论甲怎么操作，都会让乙消一个数呢的状况呢？有的，大约48种，大多数是因为自己两只手数字相同，剩下四种是1627/2749/4938/3816。不过即使是让对方先消一个数也输不了。只有8种情况，其中只有4种会出现：

1136->1736
3389->1389
7712->7912
9947->3947

我们假设对手遵循以下的简单策略：

• 如果自己有可以凑10的数字，就凑10
• 自己不选择下回合会让对手凑10的动作

这个简单策略会掉进一些凑10而必败的局面。列举如下，排除掉了一些不可能到达的局面：

1 1 2 9 -> 0 1 2 9
1 1 4 9 -> 0 1 4 9
1 1 5 9 -> 0 1 5 9
1 3 6 7 -> 0 1 6 7
1 4 6 7 -> 0 1 6 7
1 6 9 9 -> 0 6 9 9
1 7 2 9 -> 0 7 2 9
1 8 5 9 -> 0 8 5 9
2 2 7 8 -> 0 2 7 8
2 2 8 9 -> 0 2 8 9
2 3 1 8 -> 0 3 1 8
2 5 1 5 -> 0 2 1 5
2 7 3 3 -> 0 2 3 3
2 9 1 5 -> 0 2 1 5
3 3 2 7 -> 0 3 2 7
3 3 5 7 -> 0 3 5 7
3 3 6 7 -> 0 3 6 7
3 4 5 7 -> 0 4 5 7
3 8 7 7 -> 0 8 7 7
3 9 1 8 -> 0 3 1 8
4 4 3 6 -> 0 4 3 6
4 4 6 9 -> 0 4 6 9
4 5 5 7 -> 0 4 5 7
4 9 1 1 -> 0 4 1 1
5 5 1 5 -> 0 5 1 5
5 5 3 5 -> 0 5 3 5
5 5 5 7 -> 0 5 5 7
5 5 5 9 -> 0 5 5 9
5 6 3 5 -> 0 6 3 5
5 8 5 9 -> 0 8 5 9
6 6 1 4 -> 0 6 1 4
6 6 4 7 -> 0 6 4 7
6 7 3 5 -> 0 6 3 5
6 9 3 4 -> 0 9 3 4
7 7 3 4 -> 0 7 3 4
7 7 3 5 -> 0 7 3 5
7 7 3 8 -> 0 7 3 8
7 8 2 9 -> 0 7 2 9
7 9 3 4 -> 0 9 3 4
8 8 1 2 -> 0 8 1 2
8 8 2 3 -> 0 8 2 3
9 9 1 5 -> 0 9 1 5
9 9 1 6 -> 0 9 1 6
9 9 1 8 -> 0 9 1 8

这是另一种排序方式，包括了左下角36种可以到达的必胜局面：

4 9 1 1 -> 0 4 1 1
8 8 1 2 -> 0 8 1 2
6 6 1 4 -> 0 6 1 4
2 5 1 5 -> 0 2 1 5
2 9 1 5 -> 0 2 1 5
5 5 1 5 -> 0 5 1 5
9 9 1 5 -> 0 9 1 5
9 9 1 6 -> 0 9 1 6
2 3 1 8 -> 0 3 1 8
3 9 1 8 -> 0 3 1 8
9 9 1 8 -> 0 9 1 8
8 8 2 3 -> 0 8 2 3
3 3 2 7 -> 0 3 2 7
1 1 2 9 -> 0 1 2 9
1 7 2 9 -> 0 7 2 9
7 8 2 9 -> 0 7 2 9
2 7 3 3 -> 0 2 3 3
7 7 3 4 -> 0 7 3 4
6 9 3 4 -> 0 9 3 4
7 9 3 4 -> 0 9 3 4
5 5 3 5 -> 0 5 3 5
5 6 3 5 -> 0 6 3 5
6 7 3 5 -> 0 6 3 5
7 7 3 5 -> 0 7 3 5
4 4 3 6 -> 0 4 3 6
7 7 3 8 -> 0 7 3 8
6 6 4 7 -> 0 6 4 7
1 1 4 9 -> 0 1 4 9
3 3 5 7 -> 0 3 5 7
3 4 5 7 -> 0 4 5 7
4 5 5 7 -> 0 4 5 7
5 5 5 7 -> 0 5 5 7
1 1 5 9 -> 0 1 5 9
5 5 5 9 -> 0 5 5 9
1 8 5 9 -> 0 8 5 9
5 8 5 9 -> 0 8 5 9
1 3 6 7 -> 0 1 6 7
1 4 6 7 -> 0 1 6 7
3 3 6 7 -> 0 3 6 7
4 4 6 9 -> 0 4 6 9
3 8 7 7 -> 0 8 7 7
2 2 7 8 -> 0 2 7 8
2 2 8 9 -> 0 2 8 9
1 6 9 9 -> 0 6 9 9

即使手里比对方少一个数字也未必能保证必不败，下面是甲先甲必败的状态：

0 1 7 7
0 2 3 5
0 3 1 1
0 4 1 5
0 6 5 9
0 7 9 9
0 8 5 7
0 9 3 3

最后，简单列举一下甲乙双方都只有一个数字时的必胜和必败情况：

甲先甲必胜：两个数字互补（九倍）、相同（一倍），以及5和偶数，奇数的六倍和七倍，偶数和5以及用15去减（四倍加五）
1 6、1 7
2 3、2 5
3 1、3 8
4 1、4 5
5 2、5 4、5 6、5 8
6 5、6 9
7 2、7 9
8 5、8 7
9 3、9 4
甲先甲必败：5和奇数，奇数的二倍、四倍和5（五倍），偶数的一倍加五和两倍加五
1 2、1 4、1 5
2 7、2 9
3 2、3 5、3 6
4 3、4 9
5 1、5 3、5 7、5 9
6 1、6 7
7 4、7 5、7 8
8 1、8 3
9 5、9 6、9 8
甲先必平：奇数的三倍和八倍，偶数的三倍加五
1 3、1 8
2 1
3 4、3 9
4 7
6 3
7 1、7 6
8 9
9 2、9 7

至于这些倍数，基本上就是因为所有奇数（除了5）都和十进制的10互质，所有偶数都和10只有一个2因子有关。如果你是一个16进制或者24进制使用者，这个游戏或许就是另一个样子了。

似乎也没有找到这个游戏其他有意思的地方了。最后就说一下从“1111”开始，这个游戏到达不了的状态吧。

首先是全偶数的状态；其次是数字都相同的状态，包括四个数字相同（开局的1111除外）、甲先甲有一个数字，乙有两个同样的相同数字、甲乙都只持有5的状态；最后是甲持有两个x，乙持有一个x和一个2x的状况。具体而言是诸如一下的类型：

全偶数：
2 4 6 8
0 2 4 6
2 4 0 6
0 2 0 4
0 2 0 0
数字相同：
3 3 3 3
0 3 3 3
5 5 0 5
5 5 0 0
0 5 0 5
0 5 0 0
两倍的情形：
7 7 4 7

最后，也不知道这个游戏叫什么名字，姑且就叫QuadAce吧（笑）。

其他可能的方向有：

1. 不同进制下的表现，说不定某进制下有必胜策略
2. 加法换成乘法之类，胜利条件也换成两只手数字相同，开局可以自己选数字等等。
3. 加入隐藏数字