Playout Optimization for Monte-Carlo Search Algorithms. Application to Morpion Solitaire
Buzer, Lilian; Cazenave, Tristan (2021), Playout Optimization for Monte-Carlo Search Algorithms. Application to Morpion Solitaire, 2021 IEEE Conference on Games (CoG), IEEE - Institute of Electrical and Electronics Engineers : Piscataway, NJ, p. 01-08. 10.1109/CoG52621.2021.9618896
TypeCommunication / Conférence
Conference title2021 IEEE Conference on Games (CoG)
Book title2021 IEEE Conference on Games (CoG)
MetadataShow full item record
Laboratoire d'Informatique Gaspard-Monge [LIGM]
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)In Monte-Carlo based algorithms, we generate a lot of playouts by successively playing moves. Building the current list of possible moves for each turn of a game becomes a time-consuming task and this last task can be even more costly if a too large area of the gameboard is analyzed. We introduce the Range Query technique which speeds up playouts' generation by a factor of about 10. This rather general technique can be reused with any game where the possible moves are modified only locally around the played move. This technique uses very little memory and all the game data can remain in the L1 CPU cache which helps to improve performance. We also propose SSE2 optimization to improve the performance of list processing. The performance gain can impact any algorithm based on playouts' generation. For the experiments, we test our technique with the NMCS and NRPA algorithms on the 5D and 5T variants of the Morpion Solitaire.
Subjects / KeywordsRange Query; Monte Carlo Search; Morpion Solitaire
Showing items related by title and author.