UCT算法在A3课程设计中的博弈树探索与优化

在本篇2021年春季学期数据结构课程设计A3题实验报告中，来自计算机科学与技术学院2019级31班的郑修远、贾燕鹏、陈敏杰和郭军豪团队，针对博弈问题，应用了经典的UCB(Upper Confidence Bound)算法，也称为UCT(Upper Confidence Trees)算法。UCB算法是一种在决策过程中平衡探索未知选项与利用已知优势的策略，其核心思想是通过模拟多次博弈，评估每个节点的期望收益并结合置信区间来选择最优节点。 该团队的主要任务是构建一个能够基于UCB公式确定行动策略的博弈树，其中，"Exploitation"指集中于具有高收益潜力的节点，而"Exploration"则确保对尚未充分探索的节点进行尝试，以防止潜在的更好选择被忽视。他们通过设置参数c来调整利用与探索的比例，优化有限时间内算力的使用。 报告详细描述了团队成员的分工，郑修远负责框架搭建和算法实现，贾燕鹏负责代码实现和调试，陈敏杰则参与调试和参数调整，郭军豪则负责测试、参数调整以及报告撰写。算法的核心部分包括建立3x3的模拟对手矩阵，构建蒙特卡洛树结构，每个节点包含关键信息如分数、模拟次数等。 在算法流程方面，他们利用UCB公式来确定节点的优先级，但具体流程图未在描述中提供。关于时间复杂度分析，虽然没有给出具体数值，但可以推测由于需要遍历和模拟整个博弈树，算法的时间复杂度会随着树的深度和每一步的模拟次数线性增加。 报告还提到，团队通过一系列测试和参数调整，最终在28个队伍中排名第七，获得了55分的成绩。实验结果显示，他们的蛇形AI在面对不同情况时表现良好，展现出一定的学习和适应能力。 这个项目展示了团队如何将理论的UCB算法应用到实际的博弈环境中，通过实验验证和不断优化，实现了一个能够有效利用资源和平衡探索的AI决策系统。通过这个过程，学生们不仅加深了对数据结构和算法的理解，也锻炼了解决实际问题的能力。