Applying Larger N-Tuple Networks to EinStein Wurfelt Nicht!
Open Access
- 25 November 2023
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 165-172
Abstract
EinStein würfelt nicht! (abbr. EWN) is a stochastic game with a die rolled in each ply which makes it full of uncertainty. It does not look easy to design a good game engine using traditional alpha-beta-based approaches. In this paper, an EWN game engine is formed by combining n-tuple networks, trained by features extracted from two billion random games, with Monte Carlo Tree Search. Similar work has been proposed previously, but in this work, we compare performances on versions with n = 4, 6 and 9. We discover that 4-tuple networks add no extra strength in comparison with a plain baseline. However, a larger n does bring extra benefit. The jump of performance is noticeable from n = 4 to n = 6 and is very visible from n = 6 to n = 9. The tuple’s size n increases from 4 and 6 to 9. When n = 9, the size of the feature set is much larger than before and cannot be stored plainly in the main memory. One of our main contributions is to come out with a good encoding design taking care of various symmetry or equivalence properties so that it can be used in real-time game playing. Using our scheme, the number of distinct features is reduced to 20,244,124,980, which is 21.21% less than the original 95,440,494,357 features for 9-tuple networks.Keywords
This publication has 15 references indexed in Scilit:
- An Agent for EinStein Würfelt Nicht! Using N-Tuple Networks2017
- An analysis for strength improvement of an MCTS-based program playing Chinese dark chessTheoretical Computer Science, 2016
- Temporal difference learning of N-tuple networks for the game 20482014
- Spiele, Rätsel, Zahlen2014
- Single-player Monte-Carlo tree search for SameGameKnowledge-Based Systems, 2012
- A Survey of Monte Carlo Tree Search MethodsIEEE Transactions on Computational Intelligence and AI in Games, 2012
- An MCTS Program to Play EinStein Würfelt Nicht!2012
- Adding Expert Knowledge and Exploration in Monte-Carlo Tree Search2010
- Monte-Carlo Tree Search in Poker Using Expected Reward Distributions2009
- Bandit Based Monte-Carlo Planning2006