Wednesday, November 12, 2008

AI – MTG Forge, Alpha-beta pruning

MTG Forge’s current AI is very basic. It tries to play the highest costed card and it attacks unless you have a creature that is bigger. A better AI would generate possible future game states and would then choose the best future. In other words, the AI would simulate what if it played card A and then simulate what if it played card B. This type of AI deals only with predicting future game states. Min-max and alpha-beta pruning are two types of predicting algorithms. This type of AI does not learn.

In order to effectively use predicting algorithms you have to generate many future states and you must decide how “deep” you want to test. Do you generate just one level deep for combat or do you want to generate three levels deep Main1, combat, Main2 or do you want to generate Computer Combat, Human Computer, Computer Combat?

On another issue, a better AI for MTG Forge’s draft mode would have access to a pick list and would just select the card that was highest on the list. The pick list could be a global pick list of all the cards or could be divided up into deck archetypes. The AI for sealed could be similar and use the same pick lists as the draft AI. The current draft AI randomly chooses two colors before the draft starts and then chooses creatures then spells in those colors. (It sounds brain-dead but it was pretty hard to program, lol.)

6 comments:

Forge said...

OK, more regular MTG Forge coming up. Sometimes like I discussing AI, but I am not trying to alienate my visitors. So stay tuned for some tough programmming articles ;-)

Forge said...

Maybe I'll write about state effects, which are complicated but essential, like Glorious Anthem.

juzamjedi said...

Hello,

For draft format it is hard to build deck archtypes. An alternative drafting AI would be:

- Prioritize fatty creatures
- Prioritize creature kill spells (burn, terror's, swords to plowshares, etc.)
- Give extra priority to creatures with a kill spell bonus (Shriekmaw, etc.)
- Give highest priority to mass destruction.
- Let the computer take the best cards available for first 5 selections, then limit future choices to colors already selected.

It is pretty funny one time I was able to get a deck with Shriekmaw, 2 Wrath of God, 1 Damnation, and a few other goodies. Needless to say the computer decks didn't stand a chance!

Forge said...

The drafting feature of MTG Forge is very basic. The computer doesn't really ever stand a chance against a decent drafted deck. Hopefully the computer is surprising once in awhile, like when I faced off a pretty decent land destruction deck.

Gando the Wandering Fool said...

If you lose to a land destruction deck in MTG Forge you have either not built your deck correctly or have been royally screwed by the RNG (which does happen occasionally but usually doesn't matter in the long run.)

Id say the Draft AI could use a serious overhaul. For one thing the priorities that Juzam mentioned could be quibbled with but are mainly essential. For another being able to limit the number of useless cards (counterspells/pumpers) that the AI drafts would make it alot stronger. Currently to make the AI play better one needs to limit what cards are available to it by severely editing the rarities text files.

LSK said...

Here is a suggestion for a draft AI:

Assign each card numerical value.
Assign additional weight to each of these values depending on the quantity and quality of cards you already have - for example, green cards might all rise in value if you have a green card, and if you have a good green card, all green cards will further rise in value.