Thursday, September 3, 2009

AI vs. AI - Temporal Difference

Initially I decided that MTG Forge version 2 would NOT be able to play itself, but then I changed my mind. I happened to read an article describing how a program named TD-Gammon learned to play backgammon by playing itself. I found this very, very interesting and you can read it for yourself here.

TD stands for “Temporal Difference” which is an algorithm that actually learns. Many times the AI for games like chess, checkers, and Magic’s Xbox game use an algorithm called “min-max” or “minimax” which looks ahead and tries to figure out the best move. The min-max algorithm doesn’t learn, it is “static”, but the temporal difference algorithm actually learns, which is amazing.

The good news is that some very smart people have put together a nice Java library that implements temporal difference and since these people are so smart they also have libraries that work with other programming languages like C, C++, and Python. The website is here. I don’t understand all of the math behind temporal difference but hopefully I should be able to use it in MTG Forge 2.0. (I currently have 0 cards working for it and my goal is a measly 10 or 20.)

This quote comes to mind and I hope it makes sense, “I see further because I stand on the shoulders of giants” which means that I plan to use other people’s code in order to improve MTG Forge’s AI.

5 comments:

Forge said...

I *try* to post something every Monday and Wednesday but I was late this week. Better late than never, :=)

telengard said...

Sounds interesting. I wonder if it would work well for such a complex game as MtG. I'm always looking for ways to improve my AI (which uses minimax w/ some extras).

~telengard

toilet_duck said...

Sounds like a great idea! I am new to this project, but am very optimistic about it! So far, my favorite feature is that the game implements the rules correctly! I just wish some more cards were available, like Psychic Venom, Pendrel Mists, Soul Barrier, etc. Is there any way we can contribute to this project?

nantuko84 said...

I also like the idea of collecting damage info about cards: what amount of damage any card previously dealt per game or per to turn to ai or its creatures, and then add weights to decisions according to this info. E.g. Grim Lavamancer, if is not killed, deals 4 damage to ai and 8 damage to it creatures if enters the game. That means that it should be destroyed asap.

Forge said...

Is there any way we can contribute to this project?

You can look through the forums, but no there isn't anything you can do to help. Probably the best thing that you can do is to spread the word about MTG Forge. Post about it and tell your friends.