人机博弈——获胜的最佳策略 ｜ Man vs Machine Game - Best Strategy for Winning

一 问题概述

现有100个球，两个人参与游戏，每人每次可以拿走1-2个球，轮流拿球，你先开始，拿走最后一个球的人获胜，你怎么拿才能必胜？

二 思路

因为拿走最后一个球的人才能获胜，故我们可以由后往前进行递推（反推法）：

当还剩 1 个球时，到你开始拿球，必胜；
当还剩 2 个球时，到你开始拿球，必胜；
当还剩 3 个球时，到你开始拿球，你拿走 1-2 个球后，必输；
当还剩 4 个球时，到你开始拿球，你拿走 1 个球后，必胜；
当还剩 5 个球时，到你开始拿球，你拿走 2 个球后，必胜；
当还剩 6 个球时，到你开始拿球，你拿走 1-2 个球后，必输；
当还剩 7 个球时，到你开始拿球，你拿走 1 个球后，必胜；
当还剩 8 个球时，到你开始拿球，你拿走 1 个球后，必胜；
当还剩 9 个球时，到你开始拿球，你拿走 1-2 个球后，必输；
…
我们递推到还剩9个球时发现了规律：
**当你剩3的倍数（n % 3 == 0）个球时总是必输：3, 6, 9, …

三 最佳策略

因此，我们可以与别人取球博弈的过程中：
只要在你回合剩下的球数不是 3 的倍数（n % 3 ！= 0），你就是必胜的状态。

四 算法实现

这里用纯Python实现了一个也会同样策略的机器人来模拟人机博弈的过程：

"""机器人的最佳策略"""
def best_move(n):
    if n % 3 ==0:    #遇到剩下的球是3的倍数（失败态）
        return 1     #既然要输，拿慢点，等待对手失误
    else:
        return n % 3   #使对手剩下的数是3的倍数

def game_start(start_number):
    print(f"一共有{start_number}个球要被拿走！")
    remain_number = start_number
    tag = "human"
    while True:
        if tag == "human":
            while True:
                try:
                    print('-'*20)
                    task = int(input("请输入你要拿走的个数[1或2]："))
                    if task not in [1, 2] or task > remain_number:
                        raise ValueError
                    break
                except ValueError:
                    print("输入错误，请输入 1 或 2，且不能超过剩余球数。")
            remain_number -= task
            print(f"现在你拿走{task}后，还剩{remain_number}个球！")
            if remain_number == 0:
                print("恭喜你🎉拿到最后一个球，你赢了！！！")
                break
            tag = "computer"
        else:
            move = best_move(remain_number)
            print('-'*20)
            print("机器人思考中。。。。")
            remain_number -= move
            print(f"现在机器人拿走{move}后，还剩{remain_number}个球！")
            if remain_number == 0:
                print("很遗憾🤖️机器人拿到最后一个球，你输了！！！")
                break
            tag = "human"

if __name__ == "__main__":
    game_start(100)

情况如下：
因为频繁交互浪费时间，这里假定有10个球：