In most fantasy games there dragons and in a few there are two headed dragons. A two headed dragon isn’t going to go very far unless both heads work together, much like a three legged race at the park. My point is that MTG Forge has two conflicting goals. One, to program as many cards as possible. Two, to have a decent AI opponent. These two goals conflict with each other. The AI wants simple cards that are always positive. The AI can easily use a card like Giant Growth versus a situational card like Wrath of God. But as more and more cards are programmed, some of them are going to be cards that depend heavily on the particular situation. Current MTG Forge doesn’t evaluate the game situation, it just blindly plays games. So this is better than just goldfish (playing against no opponent) it doesn’t always simulate the back-and-forth action of a real game.
In a way MTG Forge has a third goal, to program the AI for each card using the least amount of code and time. Often programming the AI for a card takes as long as the card itself. Let’s use Shock for example. When should the computer play Shock?
Currently MTG Forge will use Shock if your life is under 7 (an arbitrary number) or if you have a 2/2 flyer or better. MTG Forge will never double Shock a 4/4. Each card evaluation is independent of the other cards in the computer’s hand. Having different types of AI for red-burn or green-stompy would help give the computer more personality and skill. Just having the computer play instants during combat would be an improvement.
I went through all these questions so I just want to drop my 2 cents here.
ReplyDeleteFirst of all you shouldn't aim for the number of cards at this stage. Your goal is to build an engine to support a small number of cards. You need to then implement your AI strategy (most probably a variant of minimax) with this core.
In my opinion you really have no choice but to use some form of search algorithm to accomplish the AI part. There are just two many cards in MTG and you couldn't implement AI on each one. I personally has implemented more than 800 cards in DeckBot. There are still exceptions to this rule but those are uncommon, e.g. cards involving coin tosses, peeking at another player's hand.
Now with a search algorithm, your engine needs to build in such a way that the game state can be restored at will so that searches can be continued from an earlier 'node.' Chess' game state is easy, MTG's game state is not easy. That means you couldn't pass the whole game's state between calls as stack variables. You couldn't make copy of the whole game state also because that will kill your performance. You need to really think about how to implement this 'undo' thing early on. Java has its only advantage to other languages, e.g. C++, in automatically collecting unused objects so you are in the right path.
and a game state consists of more data some people would think of. there are cards that care about damage dealt one turn, the number of turns and maaany more. also the cards with "when .. comes into play, choose ..".
ReplyDeleteFortunately, the "timestamps" that are mentioned in the CRs could be used to identify a game state; every action done alters the current timestamp, which makes restoring (a little) easier.
Lee, Not too many people in the world can say that they have programmed 800 Magic cards, lol, not even me. Version 2.0, which will probably be written in Python, will definitely include a "look ahead" function like minimax or alpha-beta pruning. I'll code everything so that it is able to be copied.
ReplyDeleteI need to be careful of performance issues, so I shouldn't just copy all the game data each time. Maybe each action, like playing a card, could be saved individually, so only a minimal amount of data will have to be copied.
All this is pretty new to me and hopefully I don't get over my head. ;)
Hehe, I've implemented about 600 magic cards in Incantus, although besides most of 10e, all the other cards are vanilla/french vanilla cards. It helps to have a program to import oracle text and automatically convert it into card code :)
ReplyDeleteLeo, I'm really interested in your minimax implementation for MtG. How did you design your board evaluation function? If you don't make a full copy of the game state, is everything reversible in the game? For Incantus, it's looking like the easiest thing to do is making copies of the game state, but i haven't tested it to see if it's fast enough (I already make lots of copies during the course of the game). But the one thing I haven't figured out is a good eval function.
As the next thing to implement in Incantus, I'm trying to decide either between a rudimentary AI, or some sort of mental poker protocol so that 2 people can play without a server and no chance of cheating.