作业4：极小极大搜索求解博弈问题

发布时间: 第7周
截止时间: 11月23日 23:59
权重: 10%

最终评测数据： assignment4_test_cases.zip

📋 作业概述

本次作业要求实现极小极大（Minimax）搜索算法，求解一个双人博弈问题。

🎯 问题描述

游戏规则

一开始有 n 张扑克牌（5 ≤ n ≤ 50），点数为 1 到 n。这些扑克牌排成若干行，每行若干个扑克牌正面向上排布，每个人都能看见牌的点数。

示例初始状态：

n = 7
第1行: 1, 2, 5, 7, 3
第2行: 4, 6

小红和小蓝轮流行动：

1. 小红先手，从某行的最左端或最右端拿走一张扑克牌
2. 小蓝后手，从剩余排堆中某行的最左端或最右端拿走一张扑克牌
3. 重复以上步骤，直到所有扑克牌被拿完

目标：每位玩家都希望最大化自己手中扑克牌的点数之和。

博弈假设

1. 理性人假设：小红和小蓝都是完全理性的玩家，每位玩家都会根据当前局面做出最优决策
2. 共同知识假设：双方都知道对方是理性的，且双方都知道对方知道自己是理性的

在这些假设下，双方玩家会采用最优博弈策略进行游戏。

📝 作业要求

输入格式

从 input.txt 文件读取初始游戏状态：

• 第一行：一个整数 n（扑克牌总数）
• 后续若干行：每行是逗号分隔的扑克牌序列

示例 input.txt：

7
1,2,5,7,3
4,6

输出格式

输出到 output.txt 文件，包含两部分：

1. 第一步最优移动：格式为 第X行 左端/右端 牌点数Y
2. 完美博弈下双方最终得分：格式为 小红: X 小蓝: Y

示例 output.txt：

第1行 右端 牌点数3
小红: 15 小蓝: 13

输出格式必须跟上述示例完全一致，文件末可以有多余的换行符（也可以没有）。 如果某一行只有一张牌而且最优策略是拿这一行，那么拿左边和右边都算对

提交内容

1. 代码文件：main.py（必须使用 Python 实现）
2. 提交位置：~/assignments/assignment4/ 目录下

注意：

• 程序需要能够读取 input.txt 并输出到 output.txt
• 我们将使用 20 个测试数据（n 从小到大递增）来检验你的程序

📊 评分标准

程序将在 20 个测试数据上进行检验，测试数据的 n 从小到大递增（5 ≤ n ≤ 50）：

• 正确性 (100%)：每个测试点通过得 5 分，共 100 分
• 超时限制：每个测试点运行时间不超过 10 秒

数据保证

• 当 n ≤ 30 时，保证扑克牌序列的行数 ≤ 4
• 当 30 < n ≤ 50 时，保证扑克牌序列的行数 ≤ 3

测试方法

1. 下载测试脚本：assignment4.zip
2. 解压后将你的 main.py 放在同一目录下
3. 运行 python3 run_tests.py 进行测试

测试包内包含 20 个样例数据及其标准答案，你可以用它来验证你的程序是否正确。最终评测数据与样例数据不同，会采取一组新的数据。

💡 技术提示

核心算法

实现 Minimax 搜索算法，递归搜索所有可能的游戏路径：

def minimax(state, is_red_turn):
    # 基础情况：游戏结束
    if is_terminal(state):
        return evaluate(state)
    
    if is_red_turn:
        # 小红回合：选择让自己得分最大的移动
        ...
    else:
        # 小蓝回合：选择让自己得分最大的移动
        ...

优化策略

为了在限定时间内通过所有测试，你可以借助各种优化技巧，比如：

• 记忆化搜索：缓存已计算过的游戏状态，避免重复计算
• Alpha-Beta 剪枝：减少需要搜索的分支数量
• 其他优化技术：高效的数据结构、代码级优化（如循环优化、避免重复计算）或其他 Python 加速库

📚 参考资料

• 课程讲义：7-16.对抗搜索.pdf
• Minimax 算法（维基百科）
• Alpha-Beta 剪枝

📞 技术支持

如有技术问题，可以通过以下方式获得帮助：

• 课程讨论群
• 助教答疑时间