海克斯棋是一种完全信息博弈项目,而开局库作为海克斯棋博弈系统的一个重要组成部分,主要依靠人工经验和蒙特卡罗树搜索(Monte Carlo tree search,MCTS)算法进行计算生成,需要大量时间并且难以保证精度。为了解决这一问题,提出一种基于...海克斯棋是一种完全信息博弈项目,而开局库作为海克斯棋博弈系统的一个重要组成部分,主要依靠人工经验和蒙特卡罗树搜索(Monte Carlo tree search,MCTS)算法进行计算生成,需要大量时间并且难以保证精度。为了解决这一问题,提出一种基于Q学习的自博弈方法用于高效生成海克斯棋的开局库,以多线程模拟棋局为思路,使用一种改进上限置信区间(upper confidence bound apply to tree,UCT)算法来搜索优良的开局位置,引入改进ε-贪心策略用来加快Q学习算法的收敛速度。为了进一步提升算法性能,将上限置信边界(upper confidence bound,UCB)公式与Q值相结合,在实际对弈过程中,使用Q值为UCB公式提供先验经验,能够提高决策的准确性。实验结果表明,当训练达到3 000次时,棋盘各位置的Q值趋于收敛,证明了该方法在开局库制作上的可行性。此外,在博弈水平测试中,纯开局库对弈改进UCT算法的平均胜率达到62.9%;当采用Q值提供先验经验时,平均胜率进一步提高到75.9%。采用提出方法的程序在中国计算机博弈大赛中获得了一等奖,证明了该方法的有效性。展开更多
文摘海克斯棋是一种完全信息博弈项目,而开局库作为海克斯棋博弈系统的一个重要组成部分,主要依靠人工经验和蒙特卡罗树搜索(Monte Carlo tree search,MCTS)算法进行计算生成,需要大量时间并且难以保证精度。为了解决这一问题,提出一种基于Q学习的自博弈方法用于高效生成海克斯棋的开局库,以多线程模拟棋局为思路,使用一种改进上限置信区间(upper confidence bound apply to tree,UCT)算法来搜索优良的开局位置,引入改进ε-贪心策略用来加快Q学习算法的收敛速度。为了进一步提升算法性能,将上限置信边界(upper confidence bound,UCB)公式与Q值相结合,在实际对弈过程中,使用Q值为UCB公式提供先验经验,能够提高决策的准确性。实验结果表明,当训练达到3 000次时,棋盘各位置的Q值趋于收敛,证明了该方法在开局库制作上的可行性。此外,在博弈水平测试中,纯开局库对弈改进UCT算法的平均胜率达到62.9%;当采用Q值提供先验经验时,平均胜率进一步提高到75.9%。采用提出方法的程序在中国计算机博弈大赛中获得了一等奖,证明了该方法的有效性。
