A Novel BS-UCT Algorithm With Deep Reinforcement Learning for the Game EWN
Wenzhong Xu, Zhuoxuan Li, Yiding Cao, Xinli Shi, Jinde Cao · IEEE Transactions on Games · 2025
Einstein Würfelt Nicht(EWN) is a stochastic game involving random information and uncertainty. Due to inherent randomness, many algorithms struggle to effectively solve EWN, and their level of play requires enhancement. In this article, a novel belief state-based upper confidence bound for trees (BS-UCT) algorithm is introduced for the EWN game. The algorithm addresses the challenges posed by random information in EWN by maintaining a set of belief states to estimate the impact of dice rolls, effectively improving the efficiency of Monte Carlo Tree Search under uncertainty. We also propose a self-playing method of warm-start reinforcement learning with an improved value network structure, using a pretrained model to generate high-quality data and incorporating a coordinate attention mechanism to improve feature processing. Finally, an efficient lock-free parallel search algorithm is presented, enabling rooted parallel tree search and significantly improving the search efficiency of BS-UCT during simulation. The experimental results show that the BS-UCT algorithm has an advantage over other baseline methods, with 89%, 70%, 74%, and 64% win rates for random, beta pruning, normal UCT, and quick neural network tree search (QNNTS) algorithm, respectively, highlighting its effectiveness in the processing of random information and achieving high performance in EWN.