Python中任意长度嵌套字典生成游戏树可行移动集合

问题背景 #

给定一棵双方交替移动的游戏树（我方→对手→我方→对手…），双方的移动次数及序列均不固定，需要提取所有我方可行移动集合，每个集合对应我方在对手所有可能路径下的选择组合，同时保留对应信息。

输入输出示例 #

输入游戏树：

input_tree = {
    '1': {
        'a': {
            '1': {'a': 'some_info_1'},
            '2': {'a': 'some_info_2'}
        },
        'b': {
            '1': {
                'a': {
                    '1': {'a': 'some_info_3'},
                    '2': {'a': 'some_info_4'}
                }
            }
        }
    },
    '2': {'a': 'some_info_5'}
}

期望输出（每个键对应一种我方移动集合）：

output = {
    1: {'1': {'a': {'1': {'a': 'some_info_1'}},
              'b': {'1': {'a': {'1': {'a': 'some_info_3'}}}}},
    2: {'1': {'a': {'2': {'a': 'some_info_2'}},
              'b': {'1': {'a': {'1': {'a': 'some_info_3'}}}}},
    3: {'1': {'a': {'1': {'a': 'some_info_1'}},
              'b': {'1': {'a': {'2': {'a': 'some_info_4'}}}}},
    4: {'1': {'a': {'2': {'a': 'some_info_2'}},
              'b': {'1': {'a': {'2': {'a': 'some_info_4'}}}}},
    5: {'2': {'a': 'some_info_5'}}
}

解决方案代码 #

通过递归遍历+笛卡尔积组合的方式，适配任意规模的游戏树：

from itertools import product
import pprint

def generate_player_moves(tree, is_player_turn=True):
    # 叶子节点（信息节点）：返回空字典标记路径结束
    if isinstance(tree, str):
        return [{}]
    
    if is_player_turn:
        # 我方回合：遍历每个移动选项，合并后续路径组合
        player_options = []
        for move, subtree in tree.items():
            for sub_comb in generate_player_moves(subtree, is_player_turn=False):
                player_options.append({move: sub_comb})
        return player_options
    else:
        # 对手回合：对每个对手移动下的我方选择做笛卡尔积，生成覆盖所有对手路径的组合
        opponent_move_options = []
        for move, subtree in tree.items():
            opponent_move_options.append(generate_player_moves(subtree, is_player_turn=True))
        
        result = []
        for combo in product(*opponent_move_options):
            combined = {}
            for move, sub_comb in zip(tree.keys(), combo):
                combined[move] = sub_comb
            result.append(combined)
        return result

# 处理输入并生成输出
input_tree = {
    '1': {
        'a': {'1': {'a': 'some_info_1'}, '2': {'a': 'some_info_2'}},
        'b': {'1': {'a': {'1': {'a': 'some_info_3'}, '2': {'a': 'some_info_4'}}}}
    },
    '2': {'a': 'some_info_5'}
}

player_combinations = generate_player_moves(input_tree)
output = {i+1: combo for i, combo in enumerate(player_combinations)}

# 验证输出
pprint.pprint(output)

逻辑说明 #

1. 递归遍历区分回合：函数通过is_player_turn参数判断当前层级是我方还是对手回合，递归处理子树。
2. 我方回合处理：每个我方移动对应后续所有可能的路径组合，直接将当前移动与子组合合并，生成单个移动路径。
3. 对手回合处理：对手的每个移动都是独立分支，需要对每个分支下的我方选择做笛卡尔积，确保生成的每个集合都覆盖对手所有可能的移动选择。
4. 叶子节点处理：遇到字符串类型的信息节点时，返回空字典作为路径结束的标记，方便上层合并结构。

该方案无需预先指定树的深度或移动次数，可自适应任意规模的交替回合游戏树。

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