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 with. 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 the hand contains Smithy then use Smithy

    if the 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 whom 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 is a deck-building card game. While numerous studies have been done on games such as Chess and Go, little emphasis is placed on modern games such as Dominion. Games such as Dominion allows for complex strategies and multiple playstyles, which may serve as a useful testbed for various machine learning approaches. The presence of circularities, where one type of deck has an advantage over another in a circular manner, also means that there is no easily the obtainable optimal solution for this problem.

It is 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 (http://cacm.acm.org/magazines/2012/3/146245-the-grand-challenge-of-computer-go/fulltext).

If you wish to learn about Genetic Algorithm or Genetic Programming then visit this Artificial Intelligence Course.