从石头剪刀布到Nim游戏：用Python代码理解博弈论里的必胜策略

从石头剪刀布到Nim游戏用Python代码理解博弈论里的必胜策略博弈论并非遥不可及的数学理论它隐藏在我们熟知的童年游戏里。想象一下当你和朋友玩石头剪刀布时是否曾思考过是否存在必胜策略或者在井字棋游戏中先手是否真的占据绝对优势这些日常游戏背后都蕴含着博弈论的深刻原理。1. 博弈论基础概念博弈论研究的是理性决策者之间的策略互动。在组合游戏中我们需要理解几个核心概念必胜态N-position当前玩家可以采取策略使对手处于必败态必败态P-position无论当前玩家如何操作对手都能获胜的状态SG函数用于量化游戏状态的数学工具让我们用Python实现一个简单的状态判断函数def is_winning_position(n, moves): 判断当前是否为必胜态 if n 0: return False # 游戏结束当前玩家输 return any(not is_winning_position(n - move, moves) for move in moves if move n)2. 经典游戏实例分析2.1 巴什博弈Bash Game游戏规则有一堆n个物品两人轮流取走1到m个取走最后一个者胜。必胜策略保持对手面对的物品数总是(m1)的倍数def bash_game(n, m): 巴什博弈胜负判断 return 先手胜 if n % (m 1) ! 0 else 后手胜 # 示例17个物品每次可取1-3个 print(bash_game(17, 3)) # 输出先手胜2.2 尼姆游戏Nim Game游戏规则有若干堆石子玩家每次可从一堆取任意数量至少1个取最后一个者胜。必胜策略计算所有堆石子数的异或值Nim和import functools import operator def nim_game(piles): 尼姆游戏胜负判断 nim_sum functools.reduce(operator.xor, piles) return 先手胜 if nim_sum ! 0 else 后手胜 # 示例三堆石子分别为3,4,5 print(nim_game([3, 4, 5])) # 输出先手胜3. SG函数与游戏组合SG函数是分析博弈论问题的强大工具它能为每个游戏状态分配一个非负整数值SG值为0必败态SG值非0必胜态def calculate_sg(max_n, moves): 计算SG函数值 sg [0] * (max_n 1) for i in range(1, max_n 1): reachable set() for move in moves: if i move: reachable.add(sg[i - move]) # mex运算找最小的未出现非负整数 mex 0 while mex in reachable: mex 1 sg[i] mex return sg # 示例计算取1,3,4个石子时的SG值 sg_values calculate_sg(10, [1, 3, 4]) print(SG值表:, sg_values)4. 从简单游戏到复杂策略4.1 石头剪刀布的博弈论视角虽然石头剪刀布看似随机但可以通过博弈矩阵分析石头剪刀布石头01-1剪刀-101布1-10import random from collections import defaultdict def rps_strategy(n1000): 石头剪刀布策略模拟 counter defaultdict(int) choices [石头, 剪刀, 布] for _ in range(n): # 简单策略检测对手偏好后调整 if counter[石头] counter[剪刀] counter[布]: my_choice 布 elif counter[剪刀] counter[布] counter[石头]: my_choice 石头 elif counter[布] counter[石头] counter[剪刀]: my_choice 剪刀 else: my_choice random.choice(choices) opponent random.choice(choices) # 模拟随机对手 counter[opponent] 1 # 判断胜负 if (my_choice 石头 and opponent 剪刀) or \ (my_choice 剪刀 and opponent 布) or \ (my_choice 布 and opponent 石头): pass # 获胜 return counter4.2 井字棋的必胜策略分析井字棋作为有限步数的游戏可以通过博弈树完全分析def is_win(board, player): 检查当前玩家是否获胜 wins [(0,1,2),(3,4,5),(6,7,8),(0,3,6), (1,4,7),(2,5,8),(0,4,8),(2,4,6)] return any(all(board[i] player for i in line) for line in wins) def evaluate_tic_tac_toe(board, player): 评估井字棋局面 if is_win(board, X): return 1 if is_win(board, O): return -1 if not in board: return 0 # 递归评估所有可能走法 best_val -float(inf) if player X else float(inf) for i in range(9): if board[i] : board[i] player val evaluate_tic_tac_toe(board, O if player X else X) board[i] if player X: best_val max(best_val, val) else: best_val min(best_val, val) return best_val5. 博弈论在算法竞赛中的应用ACM/ICPC等编程竞赛中常出现博弈论题目掌握SG函数和经典模型能显著提升解题效率。以下是常见解题框架判断游戏类型公平组合游戏/非公平游戏分析游戏状态转移图计算SG函数或寻找模式处理游戏组合情况Nim和def solve_game_problem(piles, k): 解决一般博弈问题的框架 # 步骤1预处理特殊情况 if all(p 0 for p in piles): return False # 步骤2计算SG函数或应用已知定理 if k 1: # 巴什博弈变种 return sum(piles) % 2 1 else: # Nim游戏变种 return functools.reduce(operator.xor, piles) ! 0 # 示例使用 piles [3, 4, 5] print(游戏结果:, 先手胜 if solve_game_problem(piles, 2) else 后手胜)理解这些基础博弈模型后可以尝试解决更复杂的问题如威佐夫博弈Wythoffs Game斐波那契博弈Fibonacci Nim图游戏与SG定理的应用在实际编码练习中建议从简单游戏入手逐步构建对博弈论的直观理解再过渡到数学证明和算法实现。记住博弈论的精髓在于逆向思维——要想获胜必须让对手处于必败的位置。