基于递归的C++减至零博弈AI：寻求必胜策略通用递归算法

首先我们得拆解清楚这个游戏的核心逻辑：当前玩家能赢的关键，是找到一个操作，把局面变成让对手必败的状态。反之，如果所有操作都只能让对手进入必胜状态，那当前玩家必输。我们先从状态定义入手，再推导递归公式，最后给出可运行的递归实现。

1. 状态定义：必胜态 vs 必败态 #

先明确两个核心概念：

• 必胜态（Winning Position）：当前玩家存在至少一个合法操作，操作后让对手陷入必败态。
• 必败态（Losing Position）：当前玩家所有合法操作，都会让对手进入必胜态；或者没有操作可做（比如n=0，轮到你时数字已经是0，说明对手已经赢了）。

我们先手动推导前几个数字的状态，帮你理解规律：

2. 递归公式推导 #

和斐波那契数列基于前序项计算当前项类似，这个游戏的状态也可以通过前面的状态递归推导：

基准情况 #

• 当n == 0：必败态，返回False（没有操作可做，直接输）
• 当n == 1：必胜态，返回True，必胜操作是1

递归逻辑 #

对于n > 1：
首先确定合法操作列表：

• 无论n多大，都可以选1（因为规则要求剩余数字小于所选数时只能选1，n>1时1肯定小于等于n）
• 如果n >= 3，可以选3
• 如果n >= 4，可以选4

然后，当前状态的递归公式为：

is_winning(n) = NOT (所有合法操作后的n-x都是必胜态)

展开成具体的逻辑表达式：

• 若n < 3：只能选1，所以is_winning(n) = NOT is_winning(n-1)
• 若3 <= n < 4：可选1和3，所以is_winning(n) = NOT (is_winning(n-1) AND is_winning(n-3))
• 若n >= 4：可选1、3、4，所以is_winning(n) = NOT (is_winning(n-1) AND is_winning(n-3) AND is_winning(n-4))

简单来说：只要存在一个操作，让n-x是必败态，当前n就是必胜态；否则就是必败态。

3. 带记忆化的递归实现（Python） #

因为直接递归会重复计算大量相同的n值（比如计算is_winning(7)会用到is_winning(6)，计算is_winning(8)又会用到is_winning(7)），所以我们用记忆化来缓存已经计算过的状态，避免重复计算，提升效率。

from functools import lru_cache

# 记忆化缓存已经计算过的n的状态
@lru_cache(maxsize=None)
def is_winning(n):
    if n == 0:
        return False  # 必败态：没有操作可做
    # 生成合法操作列表
    valid_moves = [1]
    if n >= 3:
        valid_moves.append(3)
    if n >= 4:
        valid_moves.append(4)
    # 检查每个操作：只要有一个操作能让对手必败，当前就是必胜态
    for x in valid_moves:
        next_n = n - x
        if not is_winning(next_n):
            return True
    # 所有操作都让对手必胜，当前必败
    return False

@lru_cache(maxsize=None)
def get_best_move(n):
    if n == 0:
        return None  # 没有操作可做
    valid_moves = [1]
    if n >= 3:
        valid_moves.append(3)
    if n >= 4:
        valid_moves.append(4)
    # 优先选大的数（可选，只是让游戏更快结束，不影响胜利结果）
    for x in reversed(valid_moves):
        next_n = n - x
        if not is_winning(next_n):
            return x
    # 如果是必败态，随便选1（反正怎么选都输）
    return 1

4. 代码验证（对应你的示例） #

你的示例：初始n=7，玩家1选1后n=6，AI需要选4。我们来验证：

• 调用get_best_move(6)：遍历反转后的操作[4,3,1]，检查6-4=2，is_winning(2)返回False（对手必败），所以返回4，和示例一致。
• 之后n=2，玩家1选1到n=1，AI调用get_best_move(1)返回1，减到0，AI获胜。

5. 递归逻辑的通俗解释 #

如果你对递归还不太熟悉，可以把这个过程想象成“回溯”：

1. 要判断当前n能不能赢，就先看“我减x之后，对手能不能赢”。
2. 如果对手减x之后不能赢（必败），那我选x就能赢。
3. 如果所有x都让对手能赢，那我必输。
4. 记忆化的作用就像“笔记本”，把已经算过的n的结果记下来，下次不用再重新算一遍，节省时间。

内容的提问来源于stack exchange，提问作者Dante