算法刷题系列（五十五）：博弈论——从可达后继判断胜负状态

算法刷题系列（五十五）：博弈论——从可达后继判断胜负状态

许多双人轮流游戏都可以抽象成状态图：轮到当前玩家时，他可以走向若干后继状态。若双方都采用最优策略，当前状态是必胜还是必败，取决于这些后继的胜负属性。

本文讨论一个有限取石游戏：桌上有 n 颗石子，每回合可以拿 1、3 或 4 颗，拿走最后一颗者获胜。假设不能拿超过剩余数量的石子。

一、必胜态与必败态

以“轮到当前玩家”作为视角：

• 必胜态：存在一个合法后继是对手的必败态。当前玩家可以把对手送入必败局面。
• 必败态：所有合法后继都是对手的必胜态；若没有合法步，也属于必败态（无步可走者输）。

因此：

win[n] = 存在可拿数量 x，使得 x <= n 且 win[n - x] 为 false

空局面 win[0] = false，因为轮到玩家时没有合法操作。

二、例子：可拿 1、3、4 颗

逐步计算：

剩余石子	判断	状态
0	无合法操作	必败
1	拿 1 后给对手 0	必胜
2	只能拿 1，留下 1（必胜）	必败
3	拿 3 后给对手 0	必胜
4	拿 4 后给对手 0	必胜
5	拿 3 留 2（必败）	必胜

所以 5 颗石子时，先手可以拿 3 颗，把 2 颗留给对手。选择某个看起来“拿得最多”的动作并不重要；重要的是是否能到达对手的必败态。

三、正确性

对剩余数量按从小到大归纳。若某数量存在合法动作能到达一个已知必败态，对手接手后无论如何都不能避免失败，所以当前态必胜。若不存在这样的动作，那么每个合法动作都把对手送到必胜态，当前态必败。没有合法动作时后一条也成立。由此递推完整覆盖所有较小状态。

这个定义依赖游戏规则：本文是有限、无随机、双方信息完全且不能跳过回合的游戏。若可以平局、随机行动或存在循环，就需要不同的状态分类与分析方法。

四、Java 实现

public class GameTheoryDp {
    public static boolean firstPlayerWins(int stones, int[] moves) {
        if (stones < 0 || moves == null) {
            throw new IllegalArgumentException("invalid game input");
        }
        for (int move : moves) {
            if (move <= 0) {
                throw new IllegalArgumentException("moves must be positive");
            }
        }

        boolean[] win = new boolean[stones + 1];
        for (int remaining = 1; remaining <= stones; remaining++) {
            for (int move : moves) {
                if (move <= remaining && !win[remaining - move]) {
                    win[remaining] = true;
                    break;
                }
            }
        }
        return win[stones];
    }

    public static void main(String[] args) {
        int[] moves = {1, 3, 4};
        if (firstPlayerWins(0, moves)
                || !firstPlayerWins(1, moves)
                || firstPlayerWins(2, moves)
                || !firstPlayerWins(5, moves)) {
            throw new AssertionError("game DP test failed");
        }
    }
}

五、Python 实现

def first_player_wins(stones, moves):
    if stones < 0 or moves is None:
        raise ValueError("invalid game input")
    if any(move <= 0 for move in moves):
        raise ValueError("moves must be positive")

    win = [False] * (stones + 1)
    for remaining in range(1, stones + 1):
        for move in moves:
            if move <= remaining and not win[remaining - move]:
                win[remaining] = True
                break
    return win[stones]

assert first_player_wins(0, [1, 3, 4]) is False
assert first_player_wins(1, [1, 3, 4]) is True
assert first_player_wins(2, [1, 3, 4]) is False
assert first_player_wins(5, [1, 3, 4]) is True

六、复杂度与其他状态图

若最大目标状态为 n，可选动作数为 m，时间复杂度为 O(nm)，空间复杂度为 O(n)。如果动作列表有重复值，结果不会改变但会做重复检查；有需要时可在输入侧去重。

不一定所有游戏都能按单一数字递增计算，但只要状态转移图无环，就可以按拓扑顺序做同样的胜负标记。若每个状态只需知道胜负而不需要最优分数，布尔状态往往比完整博弈树更简洁。

七、边界与常见错误

1. 把“没有合法动作”误判为必胜：在本规则中无步可走者输，因此是必败态。
2. 视角不统一：win[s] 始终表示轮到当前玩家时的状态，不能有时改成“先手最终是否赢”。
3. 把必胜定义成“多数后继获胜”：理性玩家只需找到一个胜利选择；必败才要求所有选择都无法获胜。
4. 忽略动作可行性：不能拿超过剩余石子的数量。
5. 只看当前位置的数值奇偶：只有特定动作集合下才可能出现简单规律；一般应由规则推导。
6. 循环状态未处理：若游戏允许无限循环，单纯按递归记忆化可能遇到循环依赖，需要识别平局或使用图博弈算法。

小结

对有限无环的轮流游戏，必胜态的判据是“存在一个必败后继”，必败态则是“所有合法后继都是必胜”。先固定状态视角、终止条件和合法操作，再从小状态向大状态递推。