Forge allows you to play against the computer. The computer AI isn't spectacular but it tries to provide a decent challenge. The AI plays the most expensive card it can because generally the more expensive the card, the better the effect. Then the AI asks each card, "Should I play you now?", SpellAbility.canPlayAI() which returns true or false. If the card says, "Yes" (true), the AI plays that card.Each card has a few lines of code in the method canPlayAI(). Shock's canPlayAI() might theoretically only allow the computer to play it if you have a 2/2 flyer or 3/2 creature. Shock might ignore "regular" 2/2 creatures. Likewise the computer will only play Wrath of God if it has less than 7 life or if it would destroy more of your creatures than its own.
The downside is that the AI doesn't make plans or long term decisions. Each card is evaluated separately, which is why the computer will never use two Shocks to kill your 4/4 creature. Generally the AI makes decent decisions but sometimes it still looks like a moron, especially when the computer kills himself with a card because that card causes damage to himself, like Char. (I think the computer won't do that with Char but I've had it happen with similar cards.)
The attacking and blocking code is very general and just attacks or blocks using very broad rules like: attack if you have the biggest attacker or block 50% of the time unless you would die. The computer does not take into account activated abilities of creatures like Royal Assassin, so the computer makes less that ideal decisions. Also since the computer doesn't play instants during combat, you will never be afraid of cards like Giant Growth.
Even though Forge's AI is simple, I'm glad to say that it can use cards like Counterspell. While the computer still isn't "smart", it at least can be very annoying with a blue control deck. And sometimes even the dumb computer can still make a few surprising plays.
I don't really know how to program AI. I wanted Forge get to up and running so I just created my own AI, which wasn't great but it worked "good enough". Maybe in the future Forge can use the min-max or alpha-beta algorithm and be a more worthy opponent.
For the AI, you might want to check a recent technique: the Upper Confidence bounds applied to Trees (UCT). The algorithm is quite game-agnostic; you basically let it play many games (even when its opponent is thinking!) so that it can explore the tree of possibilities and make up its mind about how relevant each possible choice is. A theoretical argument balances the needs for exploration (studying unexplored moves) and exploitation (checking whether a promising move is really good or not).
ReplyDeleteIn principle, the algorithm is quite simple to implement. It can benefit from using some heuristics: you can provide it with some a priori ordering of the possible moves, from best to worse.
The UCT algorithm has been applied to great success to computer Go. It's definitely a very interesting and refreshing approach to computer AI!
I just Googled UTC and it seems very interesting. It has been applied to chess which is an "adversarial search" like Magic.
ReplyDeleteThis is a great blog entry about UTC: here.
(While it is hard to create a computerized Go player, since it doesn't have an opponent, I don't find Go very interesting.)
I found a random technical paper entitled "Monte Carlo Search Applied to Card Selection in Magic: The Gathering" here.
While min-max and its variants have been studied to death, I'm glad that you mentioned UCT because it looks very new and interesting.
ReplyDeleteOops, I thought Go was a solitaire game. Wikipedia showed me the error of my ways.
ReplyDeleteUCT is interesting but for games like Chess min-max and is variants are king. I presuming Magic is more similar to chess than to Go but who really knows.
ReplyDelete