Recherche Monte Carlo multi-arbres pour l’exploitation des jeux décomposés

Résumé

Dans cet article nous présentons une variation de la recherche arborescente Monte Carlo (MCTS) consistant à réaliser une recherche dans plusieurs arbres dans le but d’exploiter des jeux décomposés. Cette recherche multi-arbres MCTS (MT-MCTS) consiste à construire simultanément plusieurs arbres de recherche MCTS correspondant aux différents sous-jeux et permet, comme tous les algorithmes de la famille MCTS, d’évaluer les actions en cours de jeu. Nous appliquons MT-MCTS sur des jeux décomposés dans le domaine du General Game Playing. Nous présentons des résultats encourageants montrant que cette approche est prometteuse et ouvre de nouvelles pistes de recherche dans le domaine de l’exploitation des décompositions. Des jeux composés complexes sont résolus de 2 fois (Incredible) jusqu’à 25 fois plus vite (Nonogramme).

Publication
13èmes Journées de l’Intelligence Artificielle Fondamentale, JIAF 2019, Toulouse, France, 1-3 July, 2019