芮雄星，王一莉

（南京工业大学 电子与信息工程学院，江苏 南京210009）

0 引 言

完备信息博弈和非完备信息博弈是机器博弈的两个分支，对于完备信息博弈，国内外已经取得了的很多较好的研究成果。而非完备信息博弈领域的相关研究还不十分成熟，目前为止非完备信息下很成功的人工智能博弈程序还很少。传统的基于最小最大 （minimax）搜索的算法很难适用于多人非完备信息博弈，由于每个博弈者可能使用不同的博弈策略，很难找到一个静态评价函数能够很好的应对每种博弈策略；而非完备信息的存在导致不确定博弈行为大量增加，博弈搜索空间将变得庞大［1］。而且，alpha－beta剪枝在多人博弈中效率很低，虽然在二人完备信息博弈中alpha－beta剪枝能使空间复杂度从O（bd）降为O（bd/2），但在多人博弈中，最好的情况只能使空间复杂度降为，其中n为玩家人数［2］。本文将介绍一种新的博弈 搜 索 算 法 UCT－RAVE［3－4］。 并 通 过 与 蒙 特 卡 罗 抽 样（Monte－Carlo sampling）技术［5］相结合，将其应用于多人非完备信息博弈中。通过简单的三人争上游牌类博弈实例，验证此方法的可行性和有效性；并与UCT算法比较，测试其性能。

1 UCT－RAVE介绍

UCT－RAVE是应用于树搜索的上限置信区间 （upper confidence bound applied to tree search）方法和快速动作值估计 （rapid action value estimation）方法的结合，是结合蒙特卡罗 （Monte－Carlo）搜索方法和强化学习 （reinforcement learning）方法为一体的一种博弈搜索算法，由Sylvain应用在计算机围棋上获得了巨大的成功［6］。

1.1 UCT介绍

UCT （UCB applied to TRee）是利用UCB （upper confidence bound）公式和蒙特卡罗模拟的结果来增量扩展搜索状态的一种算法。UCB是为了解决K臂赌博机问题［7］而产生的，K臂赌博机是一种假想的具有K只手柄的老虎机，可做的动作是选择并拉下其中的一只手柄，而由此所赢取的一定数量的钱就是和这个手柄 （动作）相关联的收益（reward）。……