论文部分内容阅读
双人零和博弈问题是机器博弈研究的一个重要方向,其研究内容涉及知识表示、博弈树搜索算法、局面状态评估函数等。其中,如何制定高效准确的博弈树搜索算法是提高智能体在零和博弈问题中决策质量的关键技术。极大极小算法作为最常用的博弈树搜索算法,从理论上讲,当计算能力达到可以搜索整棵博弈树时,该算法能够搜索得到完备信息零和博弈的最优解。由于计算能力有限,实际应用中通常使用带有启发式评估函数的极大极小算法。启发式评估函数的存在不可避免的会产生评估误差,有学者们对于带有启发式评估误差的极大极小算法的搜索质量提出了质疑。人们研究发现对于某些类别的博弈树,更深层次的极大极小搜索反而会降低决策质量。他们将这种现象称为“博弈树病理现象”。由于大多数真实的博弈问题整体上表现为非病理性,使得对于极大极小算法研究仍集中于通过提高搜索效率来提升搜索深度的方向。但是,病态节点被认为存在于所有的博弈树中,不可避免的影响着启发式极大极小算法的搜索质量。本文通过分析博弈树病理现象以及极大极小算法产生搜索偏差的原因,提出了优化经典极大极小算法备份规则后的搜索算法,并将其命名为迭代最优极大极小(IOM)算法。通过在人为构建的模拟博弈树以及真实博弈问题中的实验,表明迭代最优极大极小算法在浅层的搜索中相较极大极小算法表现出了明显的优势。当搜索深度较高时,这两种算法的搜索结果趋于相似。该搜索算法表现出更好的健壮性,为极大极小算法在浅层搜索中搜索结果偏差较大的问题提供了解决思路。同时,本文还将迭代最优极大极小算法同误差最小化极大极小(EMM)算法进行了对比。误差最小化极大极小算法是为了降低病态节点对搜索质量的影响而提出的基于预先区分节点类型思想的搜索算法。但误差最小化极大极小算法存在启发式函数误差水平难以准确设定,算法复杂度无法降低等问题。为体现迭代最优极大极小算法在复杂度方面的优势,本文还提出了迭代最优极大极小算法的alpha-beta剪枝策略。最后,通过在真实博弈环境中的对比实验表明迭代最优极大极小算法同样具有更高的决策质量。