17
« on: March 02, 2018, 03:18:55 pm »
Dominion is a hard game. In the original AlphaGo paper, games are described by two parameters: the number of decisions, d, and the typical number of legal moves, d. For chess, d~80 and b~35, whereas for dominion, d~200 and b~10.
The decisions in dominion games are also quite different. In chess, each move is played on the same board, whereas in dominion, deciding which action to play is much different from deciding which card to buy or which card to trash. The difficulty of the problem is further increased by the presence of randomness and hidden information.
Fortunately, the state space can quickly be made tractable with a few simplifying assumptions. Instead of enumerating all possible states of a deck, the mean-field approximation can be used to describe the average card in a deck. For example, the starting deck produces an average of 0.7 coins/card and 3.5 coins/turn. With this model a payload function consisting of coins, buys, attacks, gains, attacks, cards trashed, and VP gained can be maximized, which allows for an analytical solution for most decisions.
Of course, some decisions are hard. These questions are best approached through the lens of machine learning. Difficult single decisions, such as how to use a remodel, can be approached with Monte Carlo Tree Search (MCTS). Each possible option is enumerated, play continues, and the choice that led to the best outcome, on average, is selected. Parameters in the global model, such as the payload function, can be optimized through a series of bot tournaments on a particular board.
The greatest advantage that AI has in dominion is its speed of play. Being able to play multiple games a second means that an AI can check for patterns and interactions far faster than a human can. With sufficient computational power, "perfect" dominion play is possible, although in practice finite resources are always available. The trick then is to determine which simplifying assumptions can be made to construct a bot that plays "very good" dominion.