Jun, 2011

GIB: 一个计算复杂的游戏中的不完美信息问题

HTML
PDF
TL;DR本文探讨了构建一款玩合同桥牌的计算机程序所面临的问题，包括解决完全信息变体游戏的困难和应对合同桥牌并不是完全信息游戏的方法。GIB，即本程序，包含了五种技术形式：分区搜索、将蒙特卡洛技术实际应用于现实问题、侧重于可达解集来解决蒙特卡洛方法固有的问题、将alpha-beta剪枝从总序扩展到任意分配格、使用 squeaky wheel 优化方法解决卡牌问题的问题。GIB目前被认为是大约专家水平，并且是当前世界上最强的电脑合同桥牌程序。
发现论文，激发创造
  • 不完美信息博弈中的安全和嵌套子游戏求解

    介绍了在不完全信息博弈中如何使用子游戏求解技术，这些技术可以适应对手的行动并改善游戏过程中的解，被用于 Libratus，它是第一个在无限制德州扑克中击败顶级人类的 AI。

    May, 2017

  • 有限深度求解不完全信息博弈

    该篇论文提出了一种通过让对手在深度限制处选择多个策略之一来在不完美信息游戏中进行有原则的深度限制求解的方法，证明了这种方法的有效性，并建立了一个仅使用4核CPU和16GB内存就可以击败之前的两个顶级代理的大师级德州扑克AI。

    May, 2018

  • 用于零和平衡点求解的稀疏线性规划

    该论文提出了一种新颖的方法利用线性规划解决计算均衡的问题，这种方法比以往的算法更高效，并可以用于解决大型的信息不完备博弈，特别是在极限状态下。

    Jun, 2020

  • 基于证明数的蒙特卡罗树搜索

    本文提出了一种新的游戏搜索算法，PN-MCTS，该算法将Monte-Carlo树搜索（MCTS）和证明数搜索（PNS）相结合。我们定义了三个领域，在这些领域中，在MCTS树中收集的证明和反证号所提供的额外知识可能会被使用。在不同的时间设置中测试了所有可能的组合，并与几个游戏进行了对抗。实验表明，PN-MCTS在5个游戏领域中（Gomoku除外）自信地优于MCTS，Lines of Action的胜率高达96.2%。

    Mar, 2023

  • 江郡：通过解决两人零和博弈中的不可传递性来掌握象棋

    通过分析超过10,000条人类象棋比赛记录，本文重点研究了象棋游戏中存在的传递性与非传递性元素，并引入了JiangJun算法，这是一种蒙特卡洛树搜索（MCTS）和策略空间响应神谕（PSRO）的创新组合，旨在近似纳什均衡。我们通过一个微信小程序对算法进行了经验评估，在与人类玩家的比赛中取得了99.41％的胜率，达到大师级水平。量化指标如相对人群表现和可视化结果证实了该算法在克服非传递性方面的有效性。

    Aug, 2023

  • 不完全信息博弈中的历史过滤：算法与复杂度

    我们介绍和分析了子游戏分解中过滤历史的计算方面和可处理性，揭示了深度有限搜索通过子游戏分解在不完全信息环境下进行顺序决策的时机和方式。

    Nov, 2023

  • 达芬奇密码游戏策略模拟的蒙特卡罗树搜索算法的开发与应用

    通过比较分析基于CPU和GPU的MCTS算法在分支分歧情况下的性能，我们发现CPU实现呈线性改进趋势，而GPU实现呈现出非线性的增强模式和明显的性能下降。这些发现对于优化并行计算架构上的游戏策略算法具有重要的考虑价值。

    Mar, 2024

  • 使用束搜索算法预测结果进行棋盘游戏

    引入了一种名为PROBS（Predict Results of Beam Search）的新型算法，用于具有完美信息的双人确定性游戏。与现有方法主要依赖蒙特卡洛树搜索（MCTS）进行决策过程的方法不同，我们的方法利用了一种更简单的波束搜索算法。通过对一系列棋盘游戏的算法性能进行评估，我们发现它始终在与基准对手对战时表现出增加的胜率。该研究的一个关键结果是，即使波束搜索大小远小于游戏平均回合数，PROBS算法仍然能有效运行。

    Apr, 2024

  • 期望工作搜索：结合胜率和证明大小估计

    提出了一种新的游戏求解算法Expected Work Search (EWS)，结合了蒙特卡洛树搜索中使用的胜率估计和证明数搜索中使用的证明大小估计。EWS的搜索效率源于最小化一种新颖的预期工作概念，其预测解决一个位置所需的期望计算量。在围棋和六边形游戏中，EWS的性能优于传统的求解算法。对于围棋，我们首次解决了常用的位置超级禁令规则集下的空5x5棋盘问题。对于六边形游戏，我们的算法在不到4分钟内解决了空8x8棋盘问题。实验证明，EWS不仅在有大量领域特定知识的情况下取得成功，而且在没有大量领域特定知识的情况下也能成功。

    May, 2024

  • 将组合优化引入MCTS方法：应用于棋盘游戏boop

    通过将组合优化注入蒙特卡罗树搜索，我们在抽象棋盘游戏中提出了一种新的AI方法，该方法在对强化学习算法的基线进行测试时的胜率达到96％，并在Board Game Arena平台上与人类玩家对抗时取得了良好的成绩。

    Jun, 2024