在Python中生成重复囚徒困境的所有唯一一致策略

一、策略的表示方式 #

因为要求是一致策略（给定历史输出固定），每个策略本质就是从历史状态到动作（+1/-1）的映射。在Python里有两种直观实现方式：

• 字典存储：用(己方历史元组, 对方历史元组)作为键，对应的值就是下一步要出的动作（元组可哈希，适合当字典键）。
• 函数实现：直接接收my_history（己方历史列表）和opp_history（对方历史列表），返回下一步动作。

比如经典的Tit for Tat策略，用函数写就是：

def tit_for_tat(my_history, opp_history):
    if not opp_history:  # 首步无历史记录
        return 1
    return opp_history[-1]  # 后续复制对手上一步

二、生成所有唯一策略的核心思路 #

要生成所有唯一策略（存在对战场景下行为不同），本质就是枚举所有可能的历史状态映射：

1. 先枚举固定深度n下的所有历史状态：
   • 每回合t（从0到n-1，对应第t+1步），历史长度为t，己方和对方的历史各有t个元素（每个元素是+1或-1），所以每个t对应的状态数是4^t。
   • 总状态数是等比数列求和：(4^n - 1) // 3。
2. 每个状态有2种动作选择，因此总策略数是2^总状态数。

三、Python代码实现 #

1. 生成所有可能的历史状态 #

先写个函数遍历出深度n内的所有历史组合：

def generate_all_histories(n):
    all_histories = []
    for t in range(n):  # t是当前历史长度，对应第t+1回合
        # 生成所有长度为t的动作序列（元素为1或-1）
        def gen_seq(length):
            if length == 0:
                yield ()
            else:
                for seq in gen_seq(length-1):
                    yield seq + (1,)
                    yield seq + (-1,)
        my_seqs = list(gen_seq(t))
        opp_seqs = list(gen_seq(t))
        # 笛卡尔积生成所有(己方历史, 对方历史)组合
        for my_seq in my_seqs:
            for opp_seq in opp_seqs:
                all_histories.append((my_seq, opp_seq))
    return all_histories

2. 生成所有策略（函数形式） #

通过枚举所有动作组合，把每个组合包装成可调用的策略函数：

import itertools

def generate_all_strategies(n):
    all_histories = generate_all_histories(n)
    # 生成所有可能的动作组合（每个状态对应1或-1）
    all_action_combs = itertools.product([1, -1], repeat=len(all_histories))
    strategies = []
    for actions in all_action_combs:
        # 构建历史到动作的映射字典
        strategy_dict = dict(zip(all_histories, actions))
        # 包装成可直接调用的策略函数
        def make_strategy(d):
            def strategy_func(my_history, opp_history):
                key = (tuple(my_history), tuple(opp_history))
                return d[key]
            return strategy_func
        strategies.append(make_strategy(strategy_dict))
    return strategies

3. 示例验证 #

比如生成n=1时的所有策略（共2种，分别是首步出1和首步出-1）：

strategies_n1 = generate_all_strategies(1)
print(strategies_n1[0]([], []))  # 输出1
print(strategies_n1[1]([], []))  # 输出-1

再比如从n=2的策略中筛选出Tit for Tat：

def is_tit_for_tat(strategy_func):
    # 验证首步
    if strategy_func([], []) != 1:
        return False
    # 验证所有长度为1的历史场景
    test_cases = [([1], [1]), ([1], [-1]), ([-1], [1]), ([-1], [-1])]
    for my_h, opp_h in test_cases:
        if strategy_func(my_h, opp_h) != opp_h[-1]:
            return False
    return True

strategies_n2 = generate_all_strategies(2)
tft_list = [s for s in strategies_n2 if is_tit_for_tat(s)]
print(len(tft_list))  # 输出1，说明n=2时Tit for Tat是唯一的

四、注意事项 #

• 当n较大时，策略数会指数级爆炸（比如n=3时总策略数是2^(1+4+16)=2097152），仅适合小n的测试场景。
• 策略函数接收的是列表，必须转成元组才能作为字典键（列表不可哈希）。
• 这里的“唯一策略”指的是深度n内行为完全不同的策略——如果两个策略在所有可能的历史状态下输出都一致，那它们就是同一个策略。

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