Monday, November 9, 2009

Performance of min-max

The min-max algorithm builds a tree of all the possible moves game states and then determines the optimal play. this sounds very expensive, and it is. to emphasize this look at this (I don't optimize anything like symmetric or rotated board positions, and don't terminate before the board is full):

tic-tac-toe, from my previous example, has one type of pieces per player and nine fields. the first move can therefore be one of nine possibilities. The second move has only eight fields free, and so on.
the total number of games is therefore 9*8*...*2*1 = 9! = 362880

Quarto is a "little" more complicated:
  • there are sixteen pieces with four characteristics:
    • small/tall
    • light/dark
    • hollow/massive
    • square/round
  • there are sixteen fields, arranged in a square
  • for his move, a player may take any piece and place it anywhere on the board
  • a player wins if his move creates a line of four pieces that share at least one characteristic. Lines can be in any direction, including diagonally
the first player can choose between 16 pieces and 16 positions, creating 16² possible first moves. The second player can choose one of the fifteen pieces and one of the fifteen fields, creating 15² possible second moves for every first move.
the total number of games is therefore (16!)² = 437763136697395052544000000 ~ 437*10²⁴
i had to use a dedicated mathematical program to calculate this, because regular java 64 bit longs weren't enough!

you see, creating every possible move is almost impossible for a game like quarto, and Magic doesn't even have a finite game tree. (for example, if both players have necropotence or something, both players can indefinitely long pass the turn). so how can you apply min-max to magic?
by introducing a reward function: instead of looking forward until the end of a game and saying -1, 0 or 1, you evaluate a board state and assign it some value between -1 and 1.

This is the real art: The reward function will directly influence your AI's performance. The better it evaluates the board, the more accurate the AI will behave.


nantuko84 said...

About reward function: once I thought over using genetic algorithm here to teach different desks to behave different.

Let's say we have reward(evaluation) function that comes with weights:
f = w1*f1(x1) + w2*f2(x2) + ...
where x1..x2 - game state parameters (life, cards in hand, creatures, etc.), w1..w2 - weight that configure the behaviour (it can be different, just an example).

Then we can create a number of game test cases where we know how to play (we can describe them as plain text files). After that we start AI vs AI battles and examine the results for different weights (here we use genetic algorithm): once we have 95% game cases resolved successfully, we can stop education.

What I like here is that we can use different weights for different desks or types of deck (e.g. aggressive decks take care about opponent's life whilst control decks about theirs own).

Silly Freak said...

yes, genetic algorithms are a cool idea, I hope I can have something like that sometimes.
An idea that should be easier to code (rather than assigning properties to evaluate) is "backwards-learning": at the end of a game, look at the moves that were made and rate them depending on the outcome of the match.

The AI could even play totally random in the beginning, after a few games it would automatically know "attacking is beneficial"

nantuko84 said...

"backwards-learning": sounds good
I've read about it once in the book
what I don't like is that one wrong action may be the reason of loss that will downgrade all other actions

it will be nice to create the possibility to replay the game manually and teach AI to choose actions. let's say, after every action it will ask you to rate it
dreams, dreams, ... ;)

Bruno Cardoso said...

I don't really know much about AI algorithms but maybe the most similar AI game with MTG is Chess.

In Chess the AI (among other approaches) uses a database of games to learn and choose the best play.

Of course in chess you have always the same pieces so it's easy to do this, in MTG all games have different decks and cards.

Also, you can't make AI for the cards only, you have to do an AI for each deck too because a card has a different goal in each deck context.