文件名称：ＵＣＴ－ＲＡＶＥ与蒙特卡罗抽样相结合-云原生安全技术预研报告
文件大小：2.45MB
文件格式：PDF
更新时间：2024-06-28 06:35:23
不围棋 UCT
２．１ 蒙特卡罗抽样算法 蒙特卡罗方法又称为计算机随机模拟方法，是一种基 于随机数的计算方法。它通过随机抽样将非完备信息博弈 问题转换为完备信息博弈问题，同时通过大规模的抽样次 数来逼近真实的情况。该方法在一些非完备信息博弈游戏 中，例如Ａｌｂｅｒｔａ的桥牌程序，已经取得了较好的效果。 ２．２ ＵＣＴ－ＲＡＶＥ与蒙特卡罗抽样相结合 ＵＣＴ－ＲＡＶＥ算法运行过程中的两个重要因素在于节点 的动态扩展和节点值的回溯运算。在非完备信息条件下，这 两点是无法实现的。因此 ＵＣＴ－ＲＡＶＥ算法必须与可以将非 完备信息条件转换为完备信息条件的蒙特卡罗抽样算法相 结合。 ＵＣＴ－ＲＡＶＥ与蒙特卡罗抽样算法的结合体现在搜索算 法初始化过程中完备信息局面的生成。在 ＵＣＴ－ＲＡＶＥ算 法进行一次搜索时，首先使用蒙特卡罗抽样算法对非完备 信息局面进行抽样生成完备信息局面。然后 ＵＣＴ－ＲＡＶＥ算 法依据这个完备信息局面进行一次搜索和节点的扩展。下次 搜索将基于另一个蒙特卡罗抽样生成的完备信息局面，每次 搜索所生成的节点都保存于同一棵搜索树中，树中的每一个 节点的胜率将代表综合各种可能的局面下的平均表现。 图１为应用于非完备信息博弈的ＵＣＴ－ＲＡＶＥ算法伪代 码，与蒙特卡罗抽样技术的结合使得 ＵＣＴ－ＲＡＶＥ算法在 非完备信息博弈树的搜索问题中可以有效的运行并发挥自 己的优势。 ３ 实例分析 为了验证本文方法在多人非完备信息博弈中的效果，选 择了一个简单的三人争上游牌类博弈模型，争上游又称拱 猪、跑得快等，游戏主要流行于江浙一带，游戏规则决定了 玩家需要尽快把自己手中的牌尽量多的打出去，先把手中的 牌出完的玩家获得胜利。失败的玩家，根据手中所剩的牌的 数量计算，剩余的牌越多扣的分数越多，如图２所示。 用不同的算法作为玩家出牌的策略进行游戏，比较不 同算法的性能表现。为更好的做出比较，限制每次用两种 Ｃｒｅａｔｅ ｒｏｏｔ ｎｏｄｅ／／根据当前局面建立根节点 Ｗｈｉｌｅ ｓｉｍｕｌａｔｉｏｎ＜ｍａｘ ｓｉｍｕｌａｔｉｏｎ／／未达最大次数 ｎｏｄｅ←Ｍｏｎｔｅ－Ｃａｒｌｏ ｓａｍｐｌｅ／／局面确定化 Ｗｈｉｌｅ ｎｏｄｅ ｈａｓ ｃｈｉｌｄｒｅｎ／／未达叶节点 ｎｏｄｅ←Ｍａｘ ＱＵＲ ｃｈｉｌｄ／／根据ＱＵＲ选择子节点 Ｅｎｄ Ｗｈｉｌｅ Ｗｈｉｌｅ ｎｏｄｅ ｎｏｔ ｔｅｒｍｉｎａｌ／／叶节点不是最终状态 ｎｏｄｅ←Ｍｏｎｔｅ－Ｃａｒｌｏ ｓｉｍｕｌａｔｅ／／模拟博弈至结束 Ｅｎｄ Ｗｈｉｌｅ Ｗｈｉｌｅ ｎｏｄｅ ｎｏｔ ｒｏｏｔ ｎｏｄｅ／／更新路径上节点ＱＵＲ值 Ｕｐｄａｔｅ ｎｏｄｅ ＱＵＲ ｎｏｄｅ←ｎｏｄｅ’ｓ ｐａｒｅｎｔ Ｅｎｄ ｗｈｉｌｅ Ｅｎｄ ｗｈｉｌｅ Ｓｅｌｅｃｔ ｍａｘ ＱＵＲ ｃｈｉｌｄ／／选择最大ＱＵＲ值节点 图１ 应用于非完备信息博弈的ＵＣＴ－ＲＡＶＥ算法伪代码 图２ 三人争上游牌类博弈画面 算法控制３个玩家进行博弈，即只有两种类型的玩家，用 Ｔｙｐｅ Ａ和Ｔｙｐｅ Ｂ表示，同时为了消除位置对算法胜率的 影响，选择表１所示的６种不同的位置排列，并平均各种 位置排列下算法的表现。 表１ 两种类型玩家的不同位置排列 Ｐｌａｙｅｒ １ Ｐｌａｙｅｒ ２ Ｐｌａｙｅｒ ３ Ｔｙｐｅ Ａ Ｔｙｐｅ Ａ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ａ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ａ Ｔｙｐｅ Ａ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ａ Ｔｙｐｅ Ａ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ａ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ｂ Ｔｙｐｅ Ａ 选取ＵＣＴ－ＲＡＶＥ算法参数Ｃ值为０．４４，ｋ值为１００， 模拟次数取５０００，分别与 ＵＣＴ算法、随机 （Ｒａｎｄｏｍ）策 略方法进行比较，每种位置排列进行１０００次博弈，取平均 计算胜率和失败时剩余的牌的数量，结果如表２所示。 ·８３１１·