AI Evolution

[Chris H.]

I think that I can move this topic over to the Developer's Corner which in turn will make it easier for the other devs to find.

I am not sure what it would take to add a game state mechanism to forge. Having one would allow several nice features to be added to forge as Dennis stated earlier in this topic.

[alexAG76]

I think the game-state is mostly there; it's just that accesses to it need to be through methods or parameters, not global variables.

When you say "move the topic", is that something you are going to do? Or do I need to start posting there from now on?

[Chris H.]

I think the game-state is mostly there; it's just that accesses to it need to be through methods or parameters, not global variables.

When you say "move the topic", is that something you are going to do? Or do I need to start posting there from now on?

`
I was able to move the topic.

[Sloth]

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.

The boolean function canPlay() handles timing (and some other things), computerUtil.canPayCost(spellability,Player) checks for most costs (only AI usable costs).

[alexAG76]

I think the game-state is mostly there; it's just that accesses to it need to be through methods or parameters, not global variables.

This is the first and probably not the last time I'll write this: Forge's code uses static members to excess. This makes it inflexible, to say the least.

I started to write a class that would temporarily create and substitute ("push") cloned values for the static members of AllZone and then put them back ("pop"), but now I'm running into static members inside the cloned values (such as ( Phase . StormCount ) )*. It's starting to feel more and more like Quicksand.

In Forge, are there any plans to drop the "static" keyword from any significant number of non-final static members? It's a hefty rewrite, and I don't want static tomatoes thrown at me, so I'm not (yet) volunteering.

*I suppose I could adjust these secondary, static members from the same code that pushes out and pops values into AllZone. It's stifling to create code so ... ugly.

Anyway, the whole experience has led me to writing my first signature line on this site.

[alexAG76]

While I waited for a response, I decided to try a compromise: to change all but one static variable reference to static method calls. I moved the static member fields from forge.AllZone, forge.card.spellability.Cost_Payment, forge.ComputerUtil_Block2, forge.Phase, and forge.PlayerZone_ComesIntoPlay into a new FGameState class as non-static fields.

I then pointed the static method calls to get their data from an FGameState instance through a class called Unstatic. From its documentation: "Being Unstatic is rather like being undead. You're not exactly static, and you're not exactly NOT static." Unstatic.getGlobalGameState fetches the FGameState instance these classes need, creating and boot-strapping it if it doesn't already exist.

I couldn't tell if Forge had a formal unit-test suite, but I ran some of the files with public static void main(String[]) methods, plus Gui_NewGame. Duels and drafting seem to work OK.

The change is widespread: -3489 lines and +3587 lines. (I excluded blank lines from those numbers.) This means I changed about 3489 lines and added 98 new ones. I backed up all the source files to a separate directory before modifying them. I can provide patch files in various formats, such as unified context-diff.

[friarsol]

A lot of these static member variables you point out are leftovers from a codebase that is at least a few years old. A bunch of us have been trying to uproot what we can, and fix what issues we notice, but in general if something is working well enough, it usually stays well enough. You seem to be harping a lot on this static issue as if everyone of the active devs has a hand in it. This is not the case. I know for sure that AllZone, Block, Phase and ComesIntoPlay is from the old codebase. Any recent work done in those areas didn't consider the ramifications of the existing static variables, since they probably weren't changing that portion of the code.

I'm not sure how Cost_Payment got a static member variable slipped in, but please don't move that anywhere. I'll get that streamlined this week when I have an hour to look why it got written that way. I have a feeling it won't take me long to get that working the way the rest of that class does.

AllZone, Phase, and the SimultaneousEntryCounter variable in ComesIntoPlay can all probably be merged into some type of GameState class. I'm not sure what the deal is with Block, and why it uses static variables. But it's probably best if that stays where it is, and we solve the problem of "Why is this Static?" as opposed to Shoving all the "bad stuff" in a corner and then making it "unbad" that's what makes ugly code unmaintainable.

[juzamjedi]

Really cool video on Youtube about AI. It's a Google lecture that goes about 1 hour in length. I recommend anyone interested in developing AI for games to watch it.

http://www.youtube.com/watch?v=IJcuQQ1eWWI

[alexAG76]

Let me start on a positive note by stating that it's really great to hear from you, friarsol. I've never really tried to contribute significantly to an existing open source-project before, and I appreciate your patience with my awkwardness.

A lot of these static member variables you point out are leftovers from a codebase that is at least a few years old. A bunch of us have been trying to uproot what we can, and fix what issues we notice, but in general if something is working well enough, it usually stays well enough. You seem to be harping a lot on this static issue as if everyone of the active devs has a hand in it. This is not the case. I know for sure that AllZone, Block, Phase and ComesIntoPlay is from the old codebase. Any recent work done in those areas didn't consider the ramifications of the existing static variables, since they probably weren't changing that portion of the code.

I get it. I have had similar experiences "inheriting" code that is inflexible. I have personally left similar "sleeping giants" undisturbed for the sake of getting the job done. It often makes a lot of sense to go that route.

I apologize for my repetitiveness (harping). It was not my intent to accuse, but to point out something that I thought was important.

I'm not sure how Cost_Payment got a static member variable slipped in, but please don't move that anywhere. I'll get that streamlined this week when I have an hour to look why it got written that way. I have a feeling it won't take me long to get that working the way the rest of that class does.

I am working from a public "read only" branch, so there is presently no danger of "infecting" the code-base with my numerous changes. I am not certain when I next intend to incorporate the latest baseline into my environment, but I appreciate the notice. I will be able to keep an eye on that class in particular.

AllZone, Phase, and the SimultaneousEntryCounter variable in ComesIntoPlay can all probably be merged into some type of GameState class. I'm not sure what the deal is with Block, and why it uses static variables. But it's probably best if that stays where it is, and we solve the problem of "Why is this Static?" as opposed to Shoving all the "bad stuff" in a corner and then making it "unbad" that's what makes ugly code unmaintainable.

I wholeheartedly agree that removing unnecessary static variables should be a priority, but at this moment, keeping stuff where it is makes it impossible for me to create a game-state capable of being cloned. Second, I don't really know how to specifically test the removal of a static keyword. On the other hand, I do know that the transformations I have made are semantically equivalent to their previous structures. In that sense, I think they are very safe in that they are not likely to introduce new bugs.

I also have very clearly marked within FGameState where each member variable originated, so that if someone eliminates its "static cling", it can be removed from the FGameState as well.

You may be surprised how elegant my solution actually is. If you would, please consider this subset of my changes to Phase.java, focusing on PlayerSpellCount:

Code: Select all

...
     public void turnReset(){
        setStormCount(0);
-        PlayerSpellCount = 0;
+        setPlayerSpellCount(0);
...
     }
...
    public static void increaseSpellCount(SpellAbility sp){
...
       if (sp.getActivatingPlayer().isHuman()) {
-         PlayerSpellCount++;
+         incrementPlayerSpellCount();
...
       }
...
    }
...
+   protected static void incrementPlayerSpellCount() {
+      FGameState gs = Unstatic.getGlobalGameState();
+      gs.setPlayerSpellCount(1 + gs.getPlayerSpellCount());
+      
       }
...
+    static int getPlayerSpellCount() {
+       return Unstatic.getGlobalGameState().getPlayerSpellCount();
+    }
+
+    static void setPlayerSpellCount(int i) {
+       Unstatic.getGlobalGameState().setPlayerSpellCount(i);
+    }


The intent of the code is unchanged. Where it once referenced, set, or incremented a static member, it makes a method call instead. If someone comes along and says, "Hey, PlayerSpellCount shouldn't be static, let's make it an ordinary private member instead," all that person has to do is rewrite the bodies of getPlayerSpellCount, setPlayerSpellCount, and incrementPlayerSpellCount, and remove the static keywords from them. (Modifying FGameState would be a good idea, too.) Removing these keywords will make it immediately obvious to the compiler where these methods were (improperly?) used from a static context.

Speaking of static contexts, let us not forget the all-important AllZone. References to it are many. In fact, of those 3489 lines I changed, 3210 (92%) contain references to AllZone that I had carefully refactored using Eclipse.

I think it is OK for Forge to use something like AllZone, a static gateway to the game-state. Without it, we would have to pass the game-state instance around like a hot potato. No, it's not a hot potato, it's a ubiquitous titan. We would have to edit numerous method signatures to include it. I am against that. I think it is OK for the game-state to be available globally. On the other hand, I want to police its use through method-calls.

In any case, I understand your reluctance to side with my modifications. They are not really needed to fix immediate bugs or implement more cards. My changes are needed for a minimax AI, of which many are skeptical. That effort hasn't yet proved itself, but there are other benefits to having a non-static (but statically available) game-state:

...
- 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.
...

I once heard an important maxim when it comes to business and engineering: Say what you do, and do what you say. I am describing my activities here to make people aware of what I am doing, why, and what my progress is. For great justice.

[Chris H.]

Let me start on a positive note by stating that it's really great to hear from you, friarsol. I've never really tried to contribute significantly to an existing open source-project before, and I appreciate your patience with my awkwardness.

I get it. I have had similar experiences "inheriting" code that is inflexible. I have personally left similar "sleeping giants" undisturbed for the sake of getting the job done. It often makes a lot of sense to go that route.

I apologize for my repetitiveness (harping). It was not my intent to accuse, but to point out something that I thought was important.

`
Rares, the original developer burned out and released the code into the open source community about three years ago. The code that he released was far from perfect.

Others have contributed to the project since it became open source. A lot of the code, original or open source is kind of a proof in concept. I have watched over the last several years and the project is moving forward.

Originally, cards were hard coded. Rob came up with an idea for keywords that would allow for some simple card scripting. Other people used his keywords as a template and that part of the project advanced.

Late last year the new AF system was designed by Sol. It is built upon an idea that Rob came up with while advancing his ideas on keywords and card scripting. Most of the original keyword code has now been deleted.

The project is moving forward one milestone at a time.

Last year someone suggested that we should go back to the drawing board and in essence rewrite almost the entire code base. Ugh. Doing so would likely take so long that we would loose our user base. And the dev team would probably loose their sense of gratification as they improve upon our existing code base.

[alexAG76]

The boolean function canPlay() handles timing (and some other things), computerUtil.canPayCost(spellability,Player) checks for most costs (only AI usable costs).

Thanks, that helped quite a bit. I want to use some of the first generational (current) AI to help reduce the breadth of the game-tree. Only including spells and abilities for which the AI can already pay the costs and choose valid targets should help tremendously.

<game-tree-size-ramblings>
There is a trade-off I'm not certain about with the game-tree. My minimax implementation is unusual (but most applicable to TCGs), because it does not assume that the players alternate turns. At each depth, exactly one player has priority for all of the moves. To model complex decisions, I can do one of two things: I can create a wider tree by computing the Cartesian products (i.e., all combinations) of targets of a spell such as Fireball. Or, I can make a deeper tree, by deferring the target selection decision to one step after the decision to cast Fireball. I could even go so far as to make each targeting decision at its own depth; for example, targets 1, 2, 3 would all be at different depths. Ultimately, it boils down to this question: how can I minimize the number of nodes it computes before reaching a win/loss state? That question may be unanswerable.

There is another factor; broader trees take up more temporary memory, beyond the memory used by the tree itself. Because I have to evaluate the game-tree breadth first, I have to use a Queue to temporarily reference the nodes to compute next.* That queue can get very long. So, I'm leaning in the direction of (a) deferring decisions to deeper nodes over (b) combining simultaneous decisions and storing them all at the same depth.

*For a depth-first approach, I could use recursion instead of a Queue; but producing a depth-first game-tree is not a good idea for minimax.

As for the game-tree in my minimax algorithm, I have applied at least three optimizations to it that have already shown great promise: a cache of previously seen game-states*, some memoization of results of the Position Evaluation Function, and deleting certain game-state-clones from memory once they are no longer needed*. It can now completely solve Tic Tac Toe on my 8 year old laptop in less than 2 seconds. (It's a good thing I can limit how deep it computes the game-tree. If I have it look ahead all 9 moves in the unit-test, it realizes that all starting moves result in a draw if it plays against itself.)

*The perceptive reader may find these to be mutually exclusive; let's just say that my techniques are novel, and I do not yet wish to disclose them. I'm mainly against software patents, but having another publication on my resume would not hurt.
</game-tree-size-ramblings>

So, once I have the spell or ability selected, the next step is for the minimax AI to select how to pay the costs, what the targets are, etc. I know that Forge lists valid targets (for instance) inside GUI components. I believe I will have to separate the computation of the list from the display of the GUI, which may mean more changes to the code-base from where I've started. I am not exactly pleased with that idea.

Another difficulty I anticipate is getting Forge to ignore the fact that the HumanPlayer is using a GUI while it is guessing what moves the human makes in response to the AI's moves. In fact, I would like my initial implementation not to replace the AI, but rather to provide a "hint" to the user (from the Game's menu bar?) as to what move to make. This would include plenty of diagnostic output in a log file, so I could make sure the AI was working correctly.

Before I do that, though, maybe I should focus on unit-testing. That would be the smarter thing to do, but potentially less fun.

A request for comments from current developers: If it hasn't happened already, it would be most beneficial to the potential, second generational AI to broaden the first generational (current) AI's abilities to determine whether a mana-cost is payable. For example, I believe that in the latest version, it is not very good at using mana-converters like Azorius Signet, Crystal Quarry, and Mossfire Valley. If I am wrong, please correct me! And if it sounds boring or low priority, I understand.

For now, I also plan to use the first generational AI to decide attackers and blockers. I'm reserving minimax for (unit-tests, hints, and) spells and abilities at this time.

I would like to offer special thanks to anyone who read this entire post.

[ubeefx]

A game state cache for MiniMax is not so novel I think, look at Magarena.
The most difficult thing here is creating a simple enough id for the complex Magic game state.
I used this in the MiniMax AI search tree and it seriously improved evaluation time.
Of course your implementation of this cache can be very different.
A MiniMax tree where players do not have alternate moves is also something I already used.

[mtgrares]

I got Forge working quickly because I made the commonly used game variables global (public, static). This made the programming much easier but it makes for an messy architecture that cannot be easily changed. Think of changing the foundation of a building after the building was built. Forge is basically just a prototype that happens to work.

I don't think Forge will ever have a better, min-max AI because you would have to re-write the whole thing from scratch.

[alexAG76]

@ubeefx: Oh, well.

I got Forge working quickly because I made the commonly used game variables global (public, static). This made the programming much easier but it makes for an messy architecture that cannot be easily changed. Think of changing the foundation of a building after the building was built. Forge is basically just a prototype that happens to work.

Yes, that is consistent with my reading of the code. However, I think it's easier to change a digital foundation than a physical one.

I don't think Forge will ever have a better, min-max AI because you would have to re-write the whole thing from scratch.

I disagree. I'm already cloning the game-state, filling in imperfect information with dummy-cards. (I just removed the CardFactory instance from the game-state. That really does need to be static.)

I am already confident that the first-generation AI will be most helpful in reducing the breadth of the game-tree.

The most difficult part seems to be coercing all of those Input classes into providing a list of moves and then executing those moves in the theoretical game-state without updating the GUI. I have drafted an untested, but complete solution for the anonymous Input class in forge.card.abilityFactory.AbilityFactory_Counters.proliferate_resolve. In doing so, I also created a general-purpose, non-GUI-updating GuiUtilsGetChoiceSubstitute that understands the AI's need for acquiring a list of possible moves at every decision. It works by temporarily overriding the global InputControl's Input instance.

Oh, and I have to fix all those references to isHuman and isComputer to make the code more Player-agnostic.

Right now, I'm working on unit-tests for the above.

Other changes I've been making...

• To clone the game-state, I'm using a slow (but small!) implementation involving Serializable. I had to add "implements java.io.Serializable" clauses to several classes along with serialVersionUIDs.
• As a safety-measure, I changed forge.Card.hasCounters to remove keys from this.counters having values less than 1. I am not sure if this was necessary.
• All Input instances must now support a getMoves method that returns a collection of moves. Most of them throw NotImplementedError (a custom exception named after the one in Python) at this point.
• I added forge.ComputerUtil.getSpellAbility(Player,boolean) to allow this search for the human player (when in theoretical mode) and to allow for ignoring canPlayAI().
• I marked forge.Move and forge.TestMove as deprecated.
• In forge.Player, I added a method hasCounters() to mirror the same method in Card.
• I added methods isSilent and setSilent on forge.gui.input.Input to allow for theoretical inputs without changing the actual GUI.
• I updated forge.gui.input.Input_Cleanup to allow the Minimax AI to try discarding different cards (if it has to). Changed hard-coded references to HumanPlayer to call FGameState.whoHasPriorityAsPlayer().
• I temporarily set res/main.properties/cardsfolder--file to a directory with many fewer cards. This helps the unit-tests run faster. I'm writing this just in case I forget to put it back.

I don't expect a big round of applause, nor am I seeking validation from anyone. I'm just telling everyone what I'm doing. After all, Chris H. did write this:

... 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. ...

Bang.

[Hellfish]

Bang indeed. I for one am very interested in seeing what your work turns into,at the least as a patch on pastebin. Looks promising!