当前位置：首页 > news >正文

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

news 2026/4/19 5:47:41

从石头剪刀布到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个，取走最后一个者胜。

必胜策略：保持对手面对的物品数总是(m+1)的倍数

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 石头剪刀布的博弈论视角

虽然石头剪刀布看似随机，但可以通过博弈矩阵分析：

石头	剪刀	布
石头	0	+1	-1
剪刀	-1	0	+1
布	+1	-1	0

import random from collections import defaultdict def rps_strategy(n=1000): """石头剪刀布策略模拟""" 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 counter

4.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_val

5. 博弈论在算法竞赛中的应用

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 "后手胜")

理解这些基础博弈模型后，可以尝试解决更复杂的问题，如：