Genetic algorithm for a card game (Dominion)

Question

I have a working F# program that runs Dominion, a card game. I would like to use a genetic algorithm to determine optimal strategies for playing. However, I don't know much about AI or genetic algorithms. Can you point me towards some good literature to get started?

A strategy for playing consists of a reaction to a given hand. In each turn, a bot is dealt a hand of cards. It can choose to play action cards, or buy new cards, based on what it has been dealt. The goal is to end the game with as many victory point cards as possible.

A hardcoded approach could look something like:

def play(hand, totalDeck):
    if hand contains Smithy then use Smithy
    if hand contains enough coins for Province then buy Province
    if more than 30% of the totalDeck is Smithy, then buy coins

I was thinking of describing a strategy in terms of a vector of target portions of the total deck for each card:

[Smithy, Province, Copper, ...]
[.3, .2, .1, ...]

Then to mutate a bot, I could just change that vector around, and see if the mutated version does better. The fitness function would be the average score playing Dominion against a variety of other bots. (One bot's score is dependent on who it is playing against, but hopefully by playing many games against many bots this can even out.)

Does this make sense? Am I headed down the right path?

Answer 1

Dominion's a great game, but it will be hard to optimize using a genetic algorithm, as the inputs of any given game differ between games (card-sets used), the optimal strategy changes over the course of the game, and the optimal play for any given situation is only slowly going to appear in a genetic search (intuitively, based on my pretty-good understanding of both GAs and the game).

A better approach to Dominion, I think, would be either a straight heuristic (rule-based) approach or, very interestingly, Monte Carlo Search (see, for instance, http://cacm.acm.org/magazines/2012/3/146245-the-grand-challenge-of-computer-go/fulltext). Monto Carlo Search is appealing precisely because:

• It's easy to generate a random-but-legal sequence of moves in Dominion.
• It's at least straight-forward to judge the "value" of such a sequence (increase in VP)
• A-priori building of "best play" rules is hard (that's what makes the game so good)

It's a very good challenge -- you should blog your experiences.