AI Evolution

[SoulStorm]

The main thing would obviously be to have a real Game State, since this would allow for cool things such as:

- Min Max AI.
- Saving/loading anytime during a match.
- Saving/viewing replays of a match.
- A generic test "suite" with a lot of test cases, which can be run in a matter of seconds before releasing a new build.
- AI vs AI matches should be easier to implement.

Dennis, could you give a simple definition of "real game state" and explain how Forge's implementation differs from a real game state. I did some online research to find an answer, however, though the phrase is thrown around a lot, no one ever seems to explain what the phrase means.

I also did some research on Min Max AI using Wikipedia. Here's a link for others who may be interested: http://en.wikipedia.org/wiki/Minimax

I had 3 semesters of calculus in college and a semester of university physics (the class for physics majors- Wow was that class hard!) so I believe I get the basic idea of a Minimax AI, though I'm not exactly a math whiz.

If I understand correctly, a minimax algorithm assigns a value to each game state (I'm assuming that for forge this would be the state of the game each time a player or the AI performs an action) using a function. It also sounds like branch prediction (I read Maximum PC) could be used.

Now this is where things get fuzzy for me. As I understand the current implementation of Forge, the AI is broken up into components (AbilityFactories) which govern AI behavior, but each component is only concerned with what it can legally affect and is blind to anything else. A minimax algorithm would require a branching AI that examines the entire game state. Is this correct, and if so, is this what is meant by a real game state?

[Chris H.]

Now this is where things get fuzzy for me. As I understand the current implementation of Forge, the AI is broken up into components (AbilityFactories) which govern AI behavior, but each component is only concerned with what it can legally affect and is blind to anything else. A minimax algorithm would require a branching AI that examines the entire game state. Is this correct, and if so, is this what is meant by a real game state?

`
Things tend to get fuzzy for me too at times, so don't feel bad.

The AbilityFactories are an improved form of the old style keyword type code. Initially, cards where coded separately. This allows us to focus on just the one card and this can simplify the coding process.

And yet, the abilities that a card can have can be commonplace. Take Shivan Dragon for example. It's ability to pump up it's power is shared by a number of other cards. A pump keyword was created to handle Shivan Dragon, Soltari Crusader and similar cards.

The new AbilityFactory_Pump AB$Pump replaces the old abPump keyword. They both do the same thing but the AbilityFactory is an improvement. The AbilityFactories contain some of the AI code. But there is also AI code spread out in different areas of the code base.

My knowledge of MinMax systems is very limited. Following the various branches that can appear and then evaluating which of the many possibilities is better than others can be a real challenge.

Give the computer a Lightening Bolt. Should it go for the opponent or a creature? If it goes for a creature, which one? Should the spell be used now or later? Targeting a Royal Assassin might be a good choice if the AI is playing a creature based deck. The weights that we assign to the evaluations can and should change depending on the circumstance.

There is another java based game that has a MinMax type system. I have read the author's messages and I can somewhat understand the decision that he made. The author suggests that his card pool will be small as this limits the evaluations that the code has to support.

[mtgrares]

Now this is where things get fuzzy for me. As I understand the current implementation of Forge, the AI is broken up into components (AbilityFactories) which govern AI behavior, but each component is only concerned with what it can legally affect and is blind to anything else.

Yes, this sounds right.

Each Card object holds 1 or more SpellAbility objects. The AI plays a SpellAbility if SpellAbility.canPlayAI() returns true, so each card has a little bit of AI code hardcoded into the card. Elvish Piper 's activated ability canPlayAI() would return true if the AI has a creature in hand and would get the most expensive creature. Wrath of God canPlayAI() returns true if the AI has 2 less creatures than you, the opponent.

A minimax algorithm would require a branching AI that examines the entire game state. Is this correct, and if so, is this what is meant by a real game state?

If I understand your question it is, "What is the game state?". Game state is just a fancy way of saying "all of the information about the game at a particular point in time". Obviously Magic's game state can be quite complicated with end of turn effects and other things. The game state for Chess is almost trivial in comparison.

Min-max is hard because you have to be able to undo everything. And it is a big possibility that you will corrupt the game state, so you have to have check everything for errors.

Forge cannot undo anything but if it could, Forge could use min-max.

[mtgrares]

After re-reading your question, "real game state". I think Dennis just means that Forge does not have one location that holds everything. I presume "real game state" just means "a better implementation of Magic's rules". Forge only implements the easy rules and doesn't touch the very complicated stuff.

[mtgrares]

I had 3 semesters of calculus in college and a semester of university physics (the class for physics majors- Wow was that class hard!)

Yeah I took Calculus 1 - 3 and Physics 1 with Calculus. Of course I changed majors from Computer Science to Information Science and then didn't need those classes, go figure. (I did take Physics 2 with Calculus but I didn't pass, which is why I changed majors.)

So I believe I get the basic idea of a Minimax AI, though I'm not exactly a math whiz.

Coding min-max, and computer algorithms in general, tends to be hard because they have to be 100% right. If I was going to use min-max in a program, I would copy the code from somebody else. I found the source code for min-max from the book Algorithms in a Nutshell, "Download Example Code" is on lower left. Here is a link to all of the algorithms in the book coded in Java. 10 MB zipped is quite a lot of source code, . The guy even includes debug versions of min-max so you can see what is going on.

Source Code - min-max and its optimized cousin alpha-beta, implemented in Java.

[SoulStorm]

The cool thing about AI vs AI is that it could test for errors that occur during the game. The AI could play itself for days and find a bunch errors.

I would also imagine that a sufficiently sophisticated AI could learn how to play a deck better by adding value to moves that lead to wins and subtracting value from moves that lead to losses. Isn't that similar to what the really sophisticated chess programs do?

And since there are a huge number of possible errors because of card interactions, users should be able to send errors over the Internet. Once an error happens, like a card not working, the user clicks a button which sends the game information directly to the developers. Obviously we would get a few false positives but it would really help to improve the quality of the software. You can only fix something IF you know a problem exists.

This would be very cool. Such a framework could possibly also allow people to upload decks that the AI could then rank so that players would always have new decks to play against that are an appropriate challenge.

Currently Forge is sort of a bug factory. I don't mean this badly and the problem stems from my original hacked, duct-taped, ad hoc architecture which worked but not well. The architecture should eloquently solve the problem.

As much of a Frankenstein's Monster Forge is, it's still the best game I've ever played. There isn't a game yet that does MTG better than Forge. Believe me, I've looked. Clearly a lot of programmers agree or they wouldn't be putting the energy into Forge that they have.

Yeah I took Calculus 1 - 3 and Physics 1 with Calculus. Of course I changed majors from Computer Science to Information Science and then didn't need those classes, go figure. (I did take Physics 2 with Calculus but I didn't pass, which is why I changed majors.)

LOL, I started physics 2, but I quickly discovered that I was doomed so I dropped the class. The burnout I accumulated from taking Physics I and Mandarin 3 at the same time during the previous semester may have had something to do with it.

Coding min-max, and computer algorithms in general, tends to be hard because they have to be 100% right. If I was going to use min-max in a program, I would copy the code from somebody else.

I imagine it would still take considerable expertise to integrate that code into another program.

[mtgrares]

I would also imagine that a sufficiently sophisticated AI could learn how to play a deck better by adding value to moves that lead to wins and subtracting value from moves that lead to losses. Isn't that similar to what the really sophisticated chess programs do?

Yes, at the lowest level the evaluation function for min-max returns a number (integer) representing the strength of the board game and obviously the higher the number the better for the AI. Tuning the evaluation function can be very difficult and in chess you typically let your chess engine play against itself or against another better chess engine.

As much of a Frankenstein's Monster Forge is, it's still that best game I've ever played. There isn't a game yet that does MTG better than Forge. Believe me, I've looked. Clearly a lot of programmers agree or they wouldn't be putting the energy into Forge that they have.

Thanks, I'm sort of a perfectionist and even though I love Forge, I see all of the warts also. I really enjoy using Forge and I have had a some great games.

[alexAG76]

I think that the Game-State is the collection of instances and fields that identify the game between decisions. As mentioned by someone previously, it is analagous to what one would find in the save-file if one were to save in the middle of a game. (Besides the current state, MtG would require a little bit of history to go with the Game-State, especially for the "Storm" keyword.)

For a predictive AI, the game would need to be able to duplicate the Game-State many times to be able to evaluate the outcomes of each decision. For instance, if the AI were to consider casting Lightning Bolt, it would produce a new, theoretical Game-State for each legal target. Each Game-State then has its own set of possible decisions, which mandate more, cloned Game-States. Although resource-intensive, this could make the AI smart enough to do unusual things without custom code. For example, it might use a Lightning Bolt on its own, tiny creature that were afflicted with Wanderlust, because it would be able to predict its life total being higher in the long run.

The trouble is, the software is creating "umpteen million*" copies of the Game-State in order to evaluate the (equally) myriad possibilities. This is a resource problem in terms of RAM.

I think the first step is separating the instances and fields of the Game-State from those needed by the UI. Model-View-Controller comes to mind. Although the Model is usually a relational database, in this case, it is just a set of in-memory instances.

One solution to the resource-problem is to use deltas of the Game-State. In other words, the AI would only create a copy of an instance just before it needed to change it in its theoretical musings. This can be accomplished by replacing hard references with weak references between instances inside the Game-State. So, instead of players, cards, tokens, and zones referring to each other by an ordinary field, they instead use numeric identifiers. For each Game-State, there is a Map (dictionary) that maps the identifiers to the real instances. When code needs to dereference one of these identifiers to get the real instance, it consults the Map. When the AI needs to make a copy of the game state, it starts by making only a copy of the Map. Then, when it needs to theoretically change a player, card, token, or zone, it first creates a copy of that object, updates the map with the new instance, and then changes the copy. This reduces the amount of unnecessarily duplicated memory, and preserves the actual, non-theoretical Game-State that the human player sees.

*A quote from Janine Melnitz in The Real Ghostbusters, exact episode unknown.

[alexAG76]

There is another java based game that has a MinMax type system. I have read the author's messages and I can somewhat understand the decision that he made. The author suggests that his card pool will be small as this limits the evaluations that the code has to support.

I find this to only be true in the following cases:

• The AI is allowed to fetch any card from the card pool by means of cards such as Glittering Wish and Ring of Ma'rûf (A.K.A. Ring of Ma'ruf *). If the decisions for these cards are not restricted to exiled cards and the AI's sideboard, then the game tree broadens by the size of the entire card pool. For a complete implementation of MtG to date, that would be more than 11,000 nodes: one for each unique card ("by English name") ever printed. (I must admit, evaluating a game tree of that magnitude does sound oddly exciting to me.)
  
• The AI is considering probabilities involving imperfect information (http://en.wikipedia.org/wiki/Imperfect_information) about the contents of other players' decks and hands. Such an AI would be fearsome indeed!
• Although it is theoretically unnecessary, the authors may desire that some specific cards have code to assist the AI. Some cards may also require custom tuning of the Position Evaluation Function. In those cases, reducing the card-pool reduces the amount of such coding. This could reduce the size of the game tree.

*for the ASCII-inclined (which includes the board's feature of hovering over card-names for card-descriptions)

Other than that, the size of the card-pool is nigh irrelevant to the number of evaluations. Rather, this number depends on the size of the game tree (http://en.wikipedia.org/wiki/Game_tree), which is a (monotonically increasing) function of the size of the Game-State*. In other words, to limit the number of evaluations, one must make the Game-State smaller. To do that, one does not use a smaller card-pool; instead, one might play massively exiling cards like Apocalypse and Decree of Annihilation.

*The number of evaluations is at least exponentially proportional to the size of the Game-State, on the order of O(n to the nth power), where n is at least the sum of the number of tokens in play, permanents, cards in the AI's hand, and cards in all graveyards. This order is further exponentiated by the depth of the game tree that the AI is permitted to predict, which is probably user-configurable. (I personally prefer having the option of limiting the AI's actual (clock) time in its predictions. This provides for a predictably smooth play-experience, and it allows the AI to automatically improve as hardware improves.)

If the AI could prune the game tree based on the fact that there are two or more identical permanents, cards in hand, or cards in a graveyard, that would reduce the number of evaluations. (The pruning would occur based on what possible decisions the duplicate cards themselves would generate, not on the decisions provided by other cards, such as a single Fireball or Comet Storm in hand.) However, the number of identical cards has little to do with the size of the card pool (except for very, very small card pools*); rather, it has to do with how many duplicated cards each player has in her or his deck.

*A card pool of around 14 cards would nigh require each player to play the same decks in an ordinary, constructed format.

Inference 1: One could reduce the size of the game tree by using the above optimization and by allowing more than four copies of each card.

Inference 2: The above optimization is much less useful in singleton (highlander) formats. It would only work on basic lands, tokens, and perhaps some Clone -type cards.

In any case, a smaller card-pool means less coding.

[Sloth]

I agree that such an AI is possible, but even commercial games shy away from such implementations. It would take month of programming until you can actually see the first fruits of your effort (with the great risk of having nothing in the end). A hobby programmer like me wants to have presentable results/progress at least after a few days (mostly in the next 30 minutes). The sense of achievement is what we are doing this for.

[alexAG76]

I agree that such an AI is possible, but even commercial games shy away from such implementations. It would take month of programming until you can actually see the first fruits of your effort (with the great risk of having nothing in the end) ...

Having been in it, I can't say I have the same respect for the commercial software industry. In my experience, management prefers to take the safer route over any risky innovation. This stifles my creativity and talent.

... A hobby programmer like me wants to have presentable results/progress at least after a few days (mostly in the next 30 minutes) ...

Perhaps I'm more patient, or perhaps I'm just plain nuts.

To the point: "Challenge accepted!"* This afternoon, I have drafted a Minimax API in Java with easy-to-understand interfaces where it relies on anything game-specific. I'm unit testing it against Tic Tac Toe at the moment. (And failing; it keeps wanting to make the first move in a corner, instead of in the middle. Maybe I should first try a simpler game, such as "Rock, Paper, Scissors, Spock".)

*Neal Patrick Harris as Barney Stinson, How I Met Your Mother, myriad episodes

I'll tune down my boasting. Honestly, my approach may suck, and it may require more than a labor-month to tune it for MtG. But I'm strangely motivated ...

[friarsol]

To the point: "Challenge accepted!"* This afternoon, I have drafted a Minimax API in Java with easy-to-understand interfaces where it relies on anything game-specific. I'm unit testing it against Tic Tac Toe at the moment. (And failing; it keeps wanting to make the first move in a corner, instead of in the middle. Maybe I should first try a simpler game, such as "Rock, Paper, Scissors, Spock".)

http://ostermiller.org/tictactoeexpert.html
Playing in the corner as a first move is not a worse strategy than playing in the middle. "If player 1 moves in the corner for the first move, player 2 must take the center. If player 1 is playing against a novice, player 1 can be ruthless and always play in the corner first. That leaves a lot of board for novice to choose from and player 1 will win more often."

[Chris H.]

I took several intro programming classes at college back in the late 70's or/through the early 80-s. This included an honor class in PASCAL. There were a few reference books on game theory available for my project.

But back in those days there really wasn't much on the market by way of PC much less PC games with any real AI to speak of. The school had a mainframe with a couple of really early computer games included as part of the OS. This was a long, long time ago.

Rares did all of the original coding for forge and he used sort of a hinting system which is spread out into different places in the code base. Sloth has spent some time improving Rares original AI code.

alexAG76, if you would like to check out the code and see what you can do, then by all means take a shot at it. Like Sloth said, it will take time and effort. No one will hold it against you if at some point you decide that it would take far too much work to get it implemented and bug-fixed.

On the other hand, if you succeed, you will be thanked repeated by the devs and the user base.

[alexAG76]

OK, my minimax implementation is viable. It's even a little cruel!

In one of my test cases, we start with the following board, with X having priority:

Code: Select all

O|X|.
-+-+-
O|X|.
-+-+-
.|.|.


I was trying to force the algorithm to immediately go for the win instead of blocking, but it ignored me. Why? Because it assigned equal values to these moves:

Code: Select all

o|x|.
-+-+-
o|x|.
-+-+-
.|X|.


and

Code: Select all

o|x|
-+-+-
o|x|
-+-+-
X| |


As you can see, either move is a win condition for X. It would probably be smarter to go for the faster kill, though, especially in a game of imperfect information.

Here are the interfaces a game must implement to work with my API at present. Comments are requested.

I am licensing the code below with the Apache 2.0 license.

Code: Select all

/**
 * Represents the entire state of a game between moves.
 */
public interface GameState {
   /**
    * Create a copy of this GameState from the perspective of the given
    * player. 
    *
    * If the game has hidden (or "imperfect") information, the clone
    * must not contain anything the player does not already know for certain.
    * For trading card games, we recommend replacing all hidden cards with
    * cards that cannot be played; this preserves the stack sizes, and is
    * helpful for strategies that involve reducing the size of an opponent's
    * deck.
    *
    * @param p  the person whose perspective to use
    * @return a new GameState instance, without hidden information
    */
   public GameState cloneFor(Player p);
   
   /**
    * @see Move
    * @return a list of Move instances for the player who has priority; this
    * may be trimmed down to eliminate idiocy, but keep in mind that in
    * bizarre situations, a move that is normally idiotic may save the day.
    */
   public List<Move> getPossibleMoves();
   
   /**
    * @return the player who has priority; i.e., the player who enacts all
    * the moves in getPossibleMoves.
    * @see #getPossibleMoves
    */
   public Player whoHasPriority();
}


/**
 * This allows for modifications to the GameState to be policed by a separate
 * class.
 */
public interface Controller {
   /**
    * Change the game-state by invoking a specific move.
    * @param move  the move to make
    * @param gs  the game-state to change
    */
   public void invoke(Move move, GameState gs);
}


/**
 * This contains AI-specific code to evaluate a game-state for a specific player
 * or team of players.
 */
public interface GameStateEvaluator {
   /**
    * Produce a numeric value indicating the relative strength of the team's
    * position; higher numbers mean the team's position is better.
    *
    * @param team  the team for whom we are rooting; pom-poms are optional.
    * @param gs  the game state to examine
    *
    * @return Long.MAX_VALUE if the game-state already represents a win for
    * the team, Long.MIN_VALUE if the state already represents a loss, 0 if
    * the game is in perfect balance between the team and its enemies, or
    * another number indicating the team's relative strength.
    */
   public long evaluatePositionFor(Team team, GameState gs);
}


/**
 * This represents a player on a team.
 *
 * If your game does not support team-play, then your class may implement both
 * Player and Team.
 */
public interface Player {
   /**
    * @return the Team of which this player is a member.
    */
   Team getTeam();
}


/**
 * This simply represents something that a Controller can invoke upon a
 * GameState.
 */
public interface Move {
}


/**
 * This represents a player or group of players who are trying to achieve the
 * same goal in the game.
 */
public interface Team {
}


[alexAG76]

First, a PSA: I'm having a hard time figuring out where Forge decides to allow the human player to do something and when it doesn't. Any tips would be appreciated.

Now for the promised TL;DR (too long; didn't read) version of the previous post:

My API needs to be able to get a list of all possible moves from the game-state whichever player has priority. After looking at Forge's code, that's not straightforward. It would have to treat both players as AIs in some respects. For instance, it would need (something like) Player.canPlayLand() for either player to see if it can add {Play Plains} to the list of moves.

On the up side, it looks like the game-state is composed of the Player instances and an AllZone instance. The AI will need to be able to clone them cleanly, and global access to each would need to be evaluated.


And now for more musings...

I've discovered another way to save RAM. I noticed that minimax is only really interested in the evaluation of leaf nodes, the ones at the bottom of the [inverted, computer-science] tree. So, once a node has had all of its children computed, the cloned game-state at that node is no longer required. It can be deleted! Just don't delete the game-state at the root node, which is the current, actual game-state.