Incentivizing Information Gain for MCTS in Hidden Information Multi-Action Games
Abstract
Hidden Information is a central mechanic in games like the Resistance or wargaming with fog of war, adding an extra layer of complexity for search algorithms. Monte Carlo Tree Search (MCTS) has gained much notoriety given its success in searching complex domains such as Go. Extensions to MCTS allow it to perform well in hidden information games such as Bridge, Kriegspiel (Chess), and Magic the Gathering. These MCTS extensions however fail to consider information gain, an important aspect of multi-action hidden information games as initial actions inform sequential decisions. This report proposes an information gain incentive function and a risk function to offset the risk of information gain. We implement the information gain incentive and risk functions into MCTS variants ISMCTS and PIMCTS which are then tested in the multi-action hidden information game TUBSTAP. Overall testing demonstrates promising results, but lack of consistency makes it largely inconclusive. Current implementation of the information gain incentive has flaws, and we offer a more effective approach.
Document Details
- Document Type
- Technical Report
- Publication Date
- Sep 15, 2022
- Accession Number
- AD1181184
Entities
People
- Nathan Lervold
Organizations
- Air Force Institute of Technology