Game Theory: Bash and Nim

Game Introduction

现在进行一个游戏，两位玩家 A 和 B 分别一次从一堆球堆中取球，获胜规则是取完所有球堆中所有球的玩家获胜，具体的规则如下：

• 总球堆 S 被分为若干子球堆 $(s_1, s_2, \dots, s_n)$, n 为总球堆的总个数，而 $s_i$ 为一个正整数。
• 每次拿球的时候每个人允许拿的球数是 $[1, k]$，不可以多拿也不可以不拿。
• 每次拿球只允许从一个子球堆中取球，不允许在一次取球中取多个子球堆中的球。

根据策梅洛定理，表示在二人的有限游戏中，如果双方皆拥有完全的信息，并且运气因素并不牵涉在游戏中，那先行或后行者当中必有一方有必胜/必不败的策略。

问题：假设初始球堆状态 $S$ 给定，A 为先手，B 为后手，在初始球堆状态 $S$ 为何种情况下，A 存在必胜策略？（反正 B 存在必胜策略，因为这个游戏不存在平局）。从整体来看，谁的赢面更大？

数学理论分析

显然，对于一种特殊情况，如果当前每一个球堆的球的个数都是 $k+1$ 的倍数，那后手存在必胜策略。

更进一步的，推导致一般的情况，定义初始异或和：

$$G = (s_1 \pmod{k+1}) \oplus (s_2 \pmod{k+1}) \oplus \dots \oplus (s_n \pmod{k+1})$$

我们阐述定理：

• 当且仅当初始异或和 $G \neq 0$ 时，先手必胜。
• 当且仅当初始异或和 $G = 0$ 的时候，后手必胜。

异或运算的性质

• 归零性： $A \oplus A = 0$
• 恒等性： $A \oplus 0 = A$
• 交换律与结合律： $A \oplus B = B \oplus A$。
• 自反性： 如果 $A \oplus B = C$，那么 $C \oplus B = A$。

证明

引理证明

我们首先需要证明如下三条定理：

• 终局状态： 当所有球被取光时，$g_1 = g_2 = \dots = g_n = 0$，此时异或和 $G = 0$。根据规则，最后取球的人获胜。（易证）

• 从 $G \neq 0$ 到 $G = 0$ 的可达性： 只要 $G \neq 0$，玩家总能通过某种合法动作修改球堆状态使得新的异或和变为 $0$。

• 从 $G = 0$ 到 $G \neq 0$ 的必然性： 如果当前 $G = 0$，任何合法的取球动作，都会导致新的异或和 $G'$ 不为 0。

引理 2 证明

我们已知初始状态的异或和为 $G$：

$$\quad g_1 \oplus g_2 \oplus \dots \oplus g_i \oplus \dots \oplus g_n = G$$

我们的目标是找到一个新的 $g_i'$，使得新的异或和为 $0$：

$$\quad g_1 \oplus g_2 \oplus \dots \oplus g_i' \oplus \dots \oplus g_n = 0$$

在等式 2 的左右两边同时异或同一个值：$g_i \oplus G$。根据异或运算的性质，可以推导出：除了 $g_i$ 以外的其他所有项的异或和等于 $G \oplus g_i$：

$$(g_1 \oplus \dots \oplus \text{ 除去 } g_i \oplus \dots \oplus g_n) = G \oplus g_i$$

代回目标等式将这个结果代入到我们想要达成 $0$ 的等式 $(2)$ 中：

$$(G \oplus g_i) \oplus g_i' = 0$$

根据异或运算的最后一条性质，我们可以推导出：$g_i' = g_i \oplus G$

注意：上述式子中的 $i$ 是任取的，因此关键在于找到一个 $i$，使得 $g_i \to g_i'$ 的操作是合法的！

证明目标： 找到一堆 $g_i$，使得将其改变为 $g_i' = g_i \oplus G$ 后，新的异或和为 $0$，且该操作合法（即 $g_i' < g_i$）。

新的异或和为 0 已经在上述式子中证明。

设 $G$ 的二进制表示中，最高位的 $1$ 在第 $m$ 位。
根据异或定义，既然 $G$ 的第 $m$ 位是 $1$，那么在所有堆 $\{g_1, g_2, \dots, g_n\}$ 中，必然存在至少一堆 $g_i$，其第 $m$ 位也是 $1$（否则 $1$ 的个数为偶数，异或后该位应为 $0$）。我们令 $g_i' = g_i \oplus G$。

比较 $g_i$ 和 $g_i' = g_i \oplus G$ 的二进制位：

• 对于高于第 $m$ 的位：因为 $G$ 在这些位上全是 $0$，所以 $g_i'$ 和 $g_i$ 在这些位上完全相同。
• 对于第 $m$ 位：$g_i$ 该位是 $1$，$G$ 该位也是 $1$，异或结果 $g_i'$ 在该位变为 $0$。
• 对于低于第 $m$ 的位：无需比较。

因此，$g_i' < g_i$ 必然成立。玩家只需从第 $i$ 堆中取走 $(g_i - g_i')$ 个球即可实现。并且因为 $g_i = (s_i \pmod{k+1}) \in [0, k]$，因此此次取球符合条件！

从算法上来说，玩家只需要挑选一个球堆，其余数 $g_i$ 的最高位的 1 和当前 $G$ 的最高位的 1 所在的位数相同（这样的球堆保证存在），并且从该球堆中取出计算好数量的球，就可以保证调整后的 $G' \neq 0$。

引理 3 证明

初始状态 $g_1 \oplus g_2 \oplus \dots \oplus g_n = 0$。假设玩家操作了第 $j$ 堆，将其数量从 $g_j$ 变为 $g_j'$。

新的异或和 $G'$ 可以写成：

$$G' = g_1 \oplus \dots \oplus g_j' \oplus \dots \oplus g_n$$

如果 $G' = 0$，定义 $M = g_1 \oplus \dots \oplus \dots \oplus g_n$ （不包含 $g_j$ 和 $g_j'$），则可以写成：

$$M \oplus g_j = 0$$

$$M \oplus g_j' = 0$$

则意味着 $g_j \oplus g_j' = 0$。根据异或性质，只有当两个数完全相等时，异或结果才为 $0$，即 $g_j = g_j'$。而这与取球规则相矛盾：

• 不可以不取球。
• 不可以取超过 $k$ 的球，这样导致 $s_j \to s_j'$ 的数量变动在取余之后 $g_j \ne g_j'$。

先手必胜的局面

当且仅当初始异或和 $G \neq 0$ 时，先手必胜。

• 假设初始 $G \neq 0$：
• 第一次博弈：
  • A 面对 $G \neq 0$，他可以执行一个动作，将局面变成 $G = 0$ 留给后手。
  • B 面对 $G = 0$，留给 A 的局面必然是 $G \neq 0$。
• 循环：只要游戏没结束，A 总是拿到 $G \neq 0$ 并把它变成 $0$；B 总是拿到 $0$ 并把它变成非 $0$。
• 收敛性：由于每次操作球的总数都在严格递减，而球数不能为负，游戏必须在有限步内结束。
• 根据定理 1，最终的结束局面必定为 $G \neq 0$ 的情况，因此此时先手 A必胜。

后手必胜的局面

当且仅当初始异或和 $G = 0$ 的时候，后手必胜。

证明过程完全类似，可以使用策略窃取的想法，先手 A 的第一步棋无论如何会导致$G \neq 0$，此时先后手交替，B 获胜。

实验验证

Dynamic Programming

我们也可以使用动态规划进行高效的穷举计算：

• 首先，我们对初始球堆进行取余操作（问题是等价的）
• 接下来，对于表示的状态 S，我们定义 dp 状态：
  • dp[S][0] 代表当前状态下，为 A 的拿球轮次，是否存在 A 的必胜策略？1 for true, 0 for false.
  • dp[S][1] 代表当前状态下，为 B 的拿球轮次，是否存在 A 的必胜策略？1 for true, 0 for false.
• 状态转移：
  • dp[S][0] 的计算: 如果存在一个可达的状态 $S'$，如果 dp[S'][1] 为 1，我们就认为 dp[S][0] = 1（注意，只需要找到可达状态就可以）
  • dp[S][1] 的计算：如果对于每一个可达状态 $S'$，dp[S'][0] 均为 1，则认为 dp[S][1] = 0（要穷尽全部的可达状态）
• 最终判断初始状态下 dp[S_0][0] 是否为 1？
• 简单情况：定义结束状态 S*（球已经被取完），dp[S*][0] = 0, dp[S*][1] = 1。

Results

胜负的关键在于随机生成的初始化球堆状态，对于一个完全随机生成的球堆，很显然 A 的赢面远大于 B，换句话说，在随机初始化的条件下，先手具有绝对的先发优势。

============================================================
STATISTICS
============================================================
Total cases: 1000
A wins: 821 (82.1%)
B wins: 179 (17.9%)
============================================================

Case 994:
  Piles: (73450, 90734, 98402, 66011, 88128)
  Max balls per take (k): 8
  Winner: A
  XOR sum: 4

Case 995:
  Piles: (46699, 67526)
  Max balls per take (k): 10
  Winner: A
  XOR sum: 12

Case 996:
  Piles: (90439,)
  Max balls per take (k): 1
  Winner: A
  XOR sum: 1

Case 997:
  Piles: (88568, 47236, 57665, 49095)
  Max balls per take (k): 6
  Winner: A
  XOR sum: 6

Case 998:
  Piles: (78228, 55220, 83127)
  Max balls per take (k): 7
  Winner: A
  XOR sum: 7

时间复杂度分析

• DP: $O(\text{状态数} \times n \times K)$，哪怕在一开始已经做了取余的操作，随着每次可以拿球数量的快速上升，状态数成指数爆炸式增长，时间复杂度高。
• 理论解法：只需要求解一个异或和即可，时间复杂度为 $O(n)$

Codes

"""
Game solver for the ball taking game using dynamic programming.

This module implements a solver for a two-player game where players take balls
from piles. The player who takes the last ball wins.
"""

from functools import lru_cache
from typing import Tuple, List, Dict


class GameSolver:
    """Solver for the ball taking game using dynamic programming."""

    def __init__(self, max_balls_per_take: int):
        """
        Initialize the game solver.

        Args:
            max_balls_per_take: Maximum number of balls allowed to take per turn (k).
        """
        self.max_balls = max_balls_per_take
        self.modulo = max_balls_per_take + 1

    def calculate_xor_sum(self, piles: Tuple[int, ...]) -> int:
        """
        Calculate the XOR sum of pile sizes modulo (k+1).

        According to the mathematical theory, the winner is determined by
        whether the XOR sum is zero or not.

        Args:
            piles: Tuple representing the current pile sizes.

        Returns:
            XOR sum of (pile_i % (k+1)) for all piles.
        """
        xor_sum = 0
        for pile in piles:
            xor_sum ^= pile % self.modulo
        return xor_sum

    def get_next_states(self, piles: Tuple[int, ...]) -> List[Tuple[int, ...]]:
        """
        Generate all valid next states from current pile configuration.

        Args:
            piles: Current pile sizes as a tuple.

        Returns:
            List of all possible next states (pile configurations).
        """
        next_states = []

        for i, pile_size in enumerate(piles):
            # Try taking 1 to min(k, pile_size) balls from pile i
            max_take = min(self.max_balls, pile_size)

            for balls_taken in range(1, max_take + 1):
                new_piles = list(piles)
                new_piles[i] -= balls_taken

                # Remove empty piles to reduce state space
                if new_piles[i] == 0:
                    new_piles.pop(i)

                next_states.append(tuple(new_piles))

        return next_states

    @lru_cache(maxsize=None)
    def _dp_solve(self, piles: Tuple[int, ...], is_a_turn: bool) -> bool:
        """
        Core DP solver using memoization.

        Args:
            piles: Current pile sizes as a tuple.
            is_a_turn: True if it's A's turn, False if it's B's turn.

        Returns:
            True if A can force a win from this state, False otherwise.
        """
        # Base case: no piles left, game over
        if not piles:
            # If it's A's turn and no balls, A loses (B took the last ball)
            # If it's B's turn and no balls, A wins (A took the last ball)
            return not is_a_turn

        next_states = self.get_next_states(piles)

        if is_a_turn:
            # A's turn: A wins if there exists ANY move that leads to A's victory
            for next_state in next_states:
                if self._dp_solve(next_state, False):
                    return True
            return False
        else:
            # B's turn: A wins only if ALL moves lead to A's victory
            for next_state in next_states:
                if not self._dp_solve(next_state, True):
                    return False
            return True

    def solve_with_dp(self, piles: Tuple[int, ...]) -> str:
        """
        Solve the game using dynamic programming.

        Args:
            piles: Initial pile sizes.

        Returns:
            'A' if A (first player) has a winning strategy, 'B' otherwise.
        """
        # Normalize piles: remove zeros and sort for consistency
        normalized_piles = tuple(sorted([(p % (self.max_balls + 1)) for p in piles if p > 0]))

        result = self._dp_solve(normalized_piles, True)
        return "A" if result else "B"

    def solve_with_theory(self, piles: Tuple[int, ...]) -> str:
        """
        Solve the game using mathematical theory (XOR sum).

        According to the theorem:
        - If XOR sum != 0, first player (A) wins
        - If XOR sum == 0, second player (B) wins

        Args:
            piles: Initial pile sizes.

        Returns:
            'A' if A (first player) has a winning strategy, 'B' otherwise.
        """
        xor_sum = self.calculate_xor_sum(piles)
        return "A" if xor_sum != 0 else "B"

    def predict_winner(self, piles: Tuple[int, ...], method: str) -> Dict[str, any]:
        """
        Predict the winner for given initial pile configuration.

        Args:
            piles: Initial pile sizes.
            method: 'theory' for mathematical solution, 'dp' for dynamic programming.

        Returns:
            Dictionary containing:
                - winner: 'A' or 'B'
                - xor_sum: XOR sum of the position
                - method: Method used for prediction
        """
        normalized_piles = tuple(sorted([p for p in piles if p > 0]))
        xor_sum = self.calculate_xor_sum(normalized_piles)
        
        if method == "theory":
            winner = self.solve_with_theory(normalized_piles)
        if method == "dp":
            winner = self.solve_with_dp(normalized_piles)

        return {
            "winner": winner,
            "xor_sum": xor_sum,
            "piles": normalized_piles,
        }

    def clear_cache(self):
        """Clear the memoization cache."""
        self._dp_solve.cache_clear()

import random
from game_solver import GameSolver
from typing import List


def generate_random_piles(generate_nums: int) -> List:
    """
    Generate random test cases for the game.

    Args:
        generate_nums: Number of test cases to generate.

    Returns:
        List of tuples, each containing (max_balls_per_take, piles).
    """
    test_cases = []

    for _ in range(generate_nums):
        max_balls_per_take = random.randint(1, 10)
        num_piles = random.randint(1, 5)
        piles = tuple(random.randint(40000, 100000) for _ in range(num_piles))

        test_cases.append((max_balls_per_take, piles))

    return test_cases


def solve(test_cases: List):
    """
    Solve test cases and print results with statistics.

    Args:
        test_cases: List of (max_balls_per_take, piles) tuples.
    """
    a_wins = 0
    b_wins = 0

    print("\n" + "=" * 60)
    print("GAME SOLVER RESULTS")
    print("=" * 60 + "\n")

    for i, (max_balls_per_take, piles) in enumerate(test_cases, 1):
        game_solver = GameSolver(max_balls_per_take=max_balls_per_take)
        result_1 = game_solver.predict_winner(piles=piles, method="theory")
        result_2 = game_solver.predict_winner(piles=piles, method="dp")
        if result_1["winner"] != result_2["winner"]:
            raise ValueError("Error! The methods computation is wrong!")
        result = result_1

        print(f"Case {i}:")
        print(f"  Piles: {piles}")
        print(f"  Max balls per take (k): {max_balls_per_take}")
        print(f"  Winner: {result['winner']}")
        print(f"  XOR sum: {result['xor_sum']}")
        print()

        if result["winner"] == "A":
            a_wins += 1
        else:
            b_wins += 1

    # Print statistics
    print("=" * 60)
    print("STATISTICS")
    print("=" * 60)
    print(f"Total cases: {len(test_cases)}")
    print(f"A wins: {a_wins} ({a_wins / len(test_cases) * 100:.1f}%)")
    print(f"B wins: {b_wins} ({b_wins / len(test_cases) * 100:.1f}%)")
    print("=" * 60 + "\n")


if __name__ == "__main__":
    num_cases = 1000
    print(f"Generating {num_cases} random test cases...\n")
    test_cases = generate_random_piles(num_cases)

    solve(test_cases)

About Game Theory

巴什博弈 (Bash Game)

规则：有一堆 $n$ 个物品，两个人轮流取，每次取 $[1, m]$ 个，取走最后一个的人获胜。

必胜态：如果 $n \pmod{m+1} \neq 0$，先手必胜；否则后手必胜。

尼姆博弈 (Nim Game)

规则：有 $n$ 堆物品，每堆数量任意。每次可以从某一堆中取走任意数量（最少 1 个，最多不限），取走最后一个的人获胜。

核心逻辑：通过异或运算计算所有堆的“尼姆和”（Nim-sum）。

$$G = s_1 \oplus s_2 \oplus \dots \oplus s_n$$

必胜态：如果 $G \neq 0$，先手必胜。

本游戏本质上就是巴什博弈和尼姆博弈的混合体，计算方式也是天然的相似。