人工智能技术的迅速发展,使其在各种领域的应用日益广泛,尤其在棋类游戏中展现出显著优势。
连珠棋作为一种规则简单但又具有挑战的棋类游戏,长期以来一直是博弈研究的重要领域之一。
本项目首先从连珠棋的博弈本质出发,介绍了完全信息动态博弈基础概念,证明了纳什均衡存在,结合博弈树搜索算法与深度强化学习算法,提出了一种基于博弈树搜索和强化学习的混合算法,验证其在不同场景下的效果。
本人负责核心算法的设计
核心流程设计:
搜索流程:蒙特卡洛树搜索在每次搜索从根节点开始,首先判断当前节点是否为叶节点。若当前节点不是叶节点,则根据PUCT算法在其子节点中选择具有最高综合评分的动作,并将该动作应用于虚拟棋盘,进入下一步模拟。随后判断新节点是否为叶节点,若仍不是叶节点,则继续上述选择过程,直到遇到叶节点为止,跳出循环。一旦搜索路径到达叶节点,将对当前棋盘状态进行预处理,并输入至策略-价值网络中,输出当前局面的落子概率分布和价值评估价值。接着判断当前局面是否为终局:若非终局,则扩展该叶节点,将所有合法落子对应的新节点加入树中,并为每个新节点初始化其先验概率、访问次数及平均价值;若为终局,则记录当前模拟对局的胜负结果作为价值信号。最后,沿着本次搜索路径回溯,对路径中所有被访问的节点进行信息更新:根据模拟结果更新各节点的访问次数,并依据对应的胜负值修正平均价值,推动搜索树逐步收敛。
决策过程:在完成预设次数的蒙特卡洛树搜索后,算法构建出一棵搜索树,其中每个节点对应一个特定的棋盘状态,边表示从当前状态出发执行的一个合法动作,节点与边组成的路径则刻画了一条虚拟对弈轨迹。搜索过程中,每个节点都会记录其累计的访问次数与平均价值评估,用于反映该节点在模拟中的表现。 由于根节点的第一层子节点对应的是当前棋局下所有可能的下一步落子位置,因此最终的实际落子决策将基于这些子节点的访问次数进行选择。具体而言,将根节点下各子节点的访问次数进行归一化处理,得到一个概率分布。访问次数越多的子节点,其概率值越大,表明该节点代表的落子方向在搜索过程中被评估为更具优势,从而具有更高的被选为最终落子的可能性。这种以搜索频率引导决策的机制有效融合了策略先验与搜索反馈,提升了落子选择的合理性与稳定性。