迭代囚徒困境：Python策略生成与模拟详解

本教程探讨如何在Python中为固定深度的迭代囚徒困境游戏生成和模拟策略。文章首先将策略简化为在给定深度下的确定性行动序列，并展示如何通过递归方法枚举所有可能的单玩家策略。接着，我们将介绍一种基于二叉树结构的方法来模拟双玩家互动产生的游戏路径，从而理解不同策略序列间的潜在交互。最后，讨论此方法的适用性、局限性及其与更复杂适应性策略的区别。

策略在迭代博弈中的定义与挑战

在迭代博弈中，一个“策略”通常被定义为一个函数，它根据游戏的历史状态（即玩家自身和对手过去的所有行动）来决定当前回合的行动。例如，“以牙还牙”策略就是一种典型的适应性策略，它在第一回合选择合作，之后模仿对手上一回合的行动。

对于固定深度为 n 的迭代博弈，每个玩家将进行 n 次行动。理论上，一个策略需要为每个可能的游戏历史状态提供一个确定的行动。然而，随着游戏深度的增加，可能出现的历史状态数量呈指数级增长，导致枚举所有适应性策略变得极其复杂。

为了简化问题并实现“生成所有可能的独特且一致的策略”这一目标，我们可以将“策略”的定义限制为在固定游戏深度 n 下，玩家将采取的一系列确定性行动序列。在这种解释下，一个策略不再是根据历史动态调整的函数，而是预先确定的 n 个行动的序列。由于每个回合有两个可能的行动（例如 +1 或 -1），对于深度为 n 的游戏，一个玩家将有 2^n 种可能的行动序列。这些序列中的每一个都代表了一个“独特且一致”的策略。

使用二叉树生成所有固定深度的单玩家策略

由于每个回合的行动只有两种选择（例如 +1 或 -1），这天然地构成了一个二叉决策树。我们可以通过递归遍历这棵树来生成所有可能的行动序列。

以下Python代码演示了如何生成一个玩家在给定深度 n 下的所有可能行动序列：

def generate_single_player_strategies(depth):
    """
    生成一个玩家在给定深度下所有可能的行动序列。
    每个行动序列代表一个固定策略。

    参数:
        depth (int): 游戏的深度，即玩家将进行的行动次数。

    返回:
        list: 包含所有行动序列的列表，每个序列是一个由 +1 和 -1 组成的列表。
    """
    strategies = []

    def build_sequences(current_sequence, current_depth):
        # 当达到目标深度时，将当前序列添加为一种策略
        if current_depth == depth:
            strategies.append(current_sequence)
            return

        # 递归生成两种可能的行动分支
        # 选择行动 +1
        build_sequences(current_sequence + [1], current_depth + 1)
        # 选择行动 -1
        build_sequences(current_sequence + [-1], current_depth + 1)

    # 从空序列和深度0开始构建
    build_sequences([], 0)
    return strategies

# 示例：生成深度为3的所有单玩家策略
max_game_depth = 3
all_fixed_strategies = generate_single_player_strategies(max_game_depth)
print(f"深度为 {max_game_depth} 时，一个玩家的所有固定策略（行动序列）有 {len(all_fixed_strategies)} 种:")
for i, strategy in enumerate(all_fixed_strategies):
    print(f"策略 {i+1}: {strategy}")

# 预期输出 (顺序可能略有不同):
# 深度为 3 时，一个玩家的所有固定策略（行动序列）有 8 种:
# 策略 1: [1, 1, 1]
# 策略 2: [1, 1, -1]
# 策略 3: [1, -1, 1]
# 策略 4: [1, -1, -1]
# 策略 5: [-1, 1, 1]
# 策略 6: [-1, 1, -1]
# 策略 7: [-1, -1, 1]
# 策略 8: [-1, -1, -1]

这段代码通过深度优先搜索（DFS）的方式，递归地探索了所有可能的行动路径，从而生成了 2^n 个长度为 n 的行动序列。每个序列都代表了一个玩家在游戏过程中可能采取的一种固定策略。

模拟双玩家互动产生的游戏路径

除了生成单玩家的固定策略，我们还可以构建一个二叉树来模拟两个玩家在迭代博弈中所有可能的互动路径。这种方法不是直接生成策略函数，而是生成在特定初始条件下，两个玩家可能产生的 所有游戏结果序列。每个从树根到叶子的路径都代表了一次完整的博弈过程，其中交替包含了玩家X和玩家Y的行动。

以下是实现这种模拟的Python代码：

leaves = [] # 全局列表，用于存储树的所有叶子节点

class Node:
    """
    表示游戏树中的一个节点。
    每个节点存储当前回合的行动值，并链接到其父节点和子节点。
    """
    def __init__(self, parent, remaining_depth, current_move_value, initial_moves_sequence):
        self.value = current_move_value  # 当前节点的行动值（+1 或 -1）
        self.left = None  # 左子节点（通常代表 -1 行动）
        self.right = None # 右子节点（通常代表 +1 行动）
        self.parent = parent # 父节点

        # 如果还有预设的初始行动序列，则根据序列构建子节点
        if len(initial_moves_sequence) > 0:
            next_move = initial_moves_sequence[0]
            if next_move == -1:
                self.left = Node(self, remaining_depth - 1, next_move, initial_moves_sequence[1:])
            elif next_move == 1:
                self.right = Node(self, remaining_depth - 1, next_move, initial_moves_sequence[1:])
        else:
            # 如果没有预设行动，且深度未达0，则递归生成所有可能的子节点
            if remaining_depth == 0:
                leaves.append(self) # 达到叶子节点，将其添加到全局列表
                return
            else:
                # 生成左子节点（行动 -1）
                self.left = Node(self, remaining_depth - 1, -1, [])
                # 生成右子节点（行动 +1）
                self.right = Node(self, remaining_depth - 1, 1, [])

def print_tree(node, level=0, prefix="Root: ", connector="    "):
    """
    辅助函数：打印树的结构以便可视化。
    """
    if node is not None:
        print(" " * (level * 4) + prefix + str(node.value))
        if node.right is not None:
            print_tree(node.right, level + 1, "├──R: ", "│   ")
        if node.left is not None:
            print_tree(node.left, level + 1, "└──L: ", "    ")

def traverse_to_parent