One Post a Week

Do you remember when Austin Powers “lost his mojo”? I feel that way. I’m not sure what else to say about Magic and programming. I’ve written more than 90,000 words and have spent countless hours programming.

One of the reasons that I’ve lost my mojo is because recently I haven’t been programming very much. Yes, I’ve talked a lot about Forge version 2 and all that jazz but actually doing it is a different story. Eventually I’ll probably get an itch to work on Forge again and hopefully version 2 will be done someday but not anytime soon. (I’m not sure even a million dollars would inspire me but again it wouldn’t hurt either, ha.)

For the last 6 months or so Forge has been updated by numerous brave volunteers that have collaborated through the forums. (Thanks Huggybaby) I can’t thank those guys enough for volunteering their time and knowledge. I try to always give credit where credit is due and DennisBergkamp, Rob Cashwalker, Chris H. and others have done a great job.

And finally, I consider Forge to be a huge success. It has more than 2,600 cards and a decent AI. If I want to play Magic at 2am in the morning, I can. Forge also has an insane variety of cards that you would never be able to afford in real life.

I feel like I’m saying good-bye but I’m not. I’m just going to spend a little less time focusing (writing and programming) on Magic for awhile.

So for now I’m going to limit myself to only one post on Mondays :+)

p.s.
If you type in “Magic computer programming” into Google, my blog is the first webpage returned, yeah.

AI Book: Alpha-beta Summary

Last week I took my car in for an oil change and I got a chance to peruse a book that I received for Christmas: Artificial Intelligence: A Modern Approach by Russell and Norvig. It is a hefty 900 pages but each chapter can be read and understood separately, much like good code.

Like any thorough textbook it starts out with a definition of AI and divides all AI into four categories.
1. Systems that think like humans.
2. Systems that act like humans.
3. Systems that think rationally.
4. Systems that act rationally.

If you think about it, thinking rationally and acting rationally are two very different concepts. The book calmly says that it is concerned with the fourth point, "Systems that act rationally."

Now that I've covered the boring stuff, I can talk about the alpha-beta (AB) algorithm which can be used to program an AI for two player games. AB "should only be applied to positions that are quiescent, that is, unlikely to exhibit wild swings in value in the near future." Obviously in Magic there are often many wild swings that happen in the course of a normal game, so the AB algorithm might have trouble evaluating some of Magic's game states, especially when a player is trying to maximize the use of cards like Glorious Charge or Overrun which pumps up all of the player's creatures. I often maximize cards like these by choosing not to trade creatures when attacking or blocking.

Another AB deficiency is the "horizon problem" is when the AI "is facing a move by the opponent that causes serious damage and is ultimately unavoidable." My guess is that this applies more to chess than Magic.

Most AB implementations let you specify the depth or the number of moves ahead to search. The book suggests "iterative deepening search" which is a strategy that sidesteps the issue of choosing the best depth limit by trying all possible depth limits as limited by the time allowed. First dept 0 is searched, then dept 1, and then 2 and so on. Combining this search with AB can be very successful because the "effectiveness of AB depends on the ordering in which the successors are examined." So if it is possible, it would be sensible to give AB a good move to begin with so AB can remove (prune) a large number of lesser, unsuccessful moves.

Finally, I often say that it is hard to encode a Magic card so the computer can understand it. The more formal name for this problem is called "knowledge representation" which is the study of how to put knowledge into a form that a computer can use.

Next time I’ll talk about other AI algorithms that can be used for 2 player games and AB's evaluation function which looks at the game state and returns a number representing the chance that the AI will win.

Other Magic Projects

Shandalar updates – Yes, that old Duels of the Planeswalkers program is still being (unofficially) updated. People have added a ton of new cards and features such as drafting against the AI and Momir Basic. (The forum is a little hard to navigate but it has all the files that you need. Basically you just download the original version and then run the newest patch for it.)

Incantus – (PvP) Lets you play other people on the Internet with rules enforcement. It has approximately 6,000 cards and is written in Python. Forum, Screenshot

MagicEngine – (PvP) Lets you play other people on the Internet with rules enforcement. Blog, Download Site, Forum

Wagic – (PvC) Lets you play against the computer with rules enforcement. Designed to work on a Playstation Portable (PSP) but it can also run on Windows and Linux. I suggest using a gamepad for the numerous buttons. It has approximately 5,100 cards.
Blog – also has links to forum and downloads section

Deckbot - (PvC) Lets you play against the computer with rules enforcement. It has approximately 1,790 cards. The user interface is text based so you'll have imagine the beautiful card art. Deckbot is unique because you can setup the program to play itself with 2 different decks and it will tell you which deck won the most number of games.

"The idea is to let your computer to play your decks and give you the winner of one of them. With all the steps logged in a text file, you can review what can be improved in your decks." Download Site

(generically named) Deckbuilder and Rules viewer – lets you easily create decks for constructed, vintage, or of any other type. It also generates nice text spoilers. Forum, Download, It uses 7z compression which you can get here.

And here I describe a variety of other Magic programs also.

What is Computer Programming? (In plain English)

I thought I might address one of the most basic questions that some people might have when reading this blog: "What exactly is computer programming?" (On a side note, if you know what computer programming is, you'll probably want to read something else.)

Let me start out by throwing two metaphors at you (hopefully you'll catch one).
1. Computer programming is like writing a long novel.
2. Computer programming is like working on a very long math problem that takes up multiple pages. (Computer bugs can be viewed as small mistakes in the overall problem.)

Computer programming is the difficult task of trying to convey thousands, and even millions, of tiny details to the computer. Computer programmers use a variety of languages in order to convey the details to the computer such as C, C++, Java, Visual Basic, and C#.

(C is very popular and it actually came after a language named B if you can believe it. C++ just means "C plus 1", which is sort of a joke. Microsoft created C# which is another trendy way of saying "This is a C language but with improvements.")

Each specific programming language has pros and cons and “experts” will debate them but basically all programming languages are the same: they each let you "communicate" with the computer.

Computer programs are very, very long. Short programs consist of thousands of lines of code while programs like Word, Internet Explorer, and Firefox have millions of lines. "Bugs" in the computer program occur when something unexpected happens that the programmer didn't expect. Since most commercial computer programs have millions of lines of code, they will probably have a few bugs because of the enormous number of users. (Eventually a user will do something that the programmer didn't expect.)

Computer programs usually consist of two parts: the user interface (front end) and the "main logic" (back end). The user interface is everything that you see on the screen and can be very complicated to program. The “back end” is whatever the program is supposed to do. The “back end” for Word is moves words around and writes files to the hard drive.

And one last explanation, you’ve probably encountered the words “object” and “method”. An object is typically a noun, a good example would be a “Person” object which would hold data about a person. A method is part of an object that does a specific task like Person.getName() which would get the full name of the person. And just to make things *more* confusing the words “object” and “class” mean the same thing as well as “method” and “function”. (Hey, no one said learning this stuff was going to be fun, ha.)

If you are NOT a programmer and have read all of this well…consider yourself an honorary computer programmer (in training). Go print yourself a nice, big certification of completion in Word. :--)

p.s.
And just in case you have never seen real code, below is a simple Person class with the methods getName() and setName(). This example is written in Java.

class Person
{
  private String name;

  public String getName()
  {
    return name;
  }

  public void setName(String n)
  {
     name = n;
  }
}

New Version

(Forge lets you play Magic: The Gathering against the computer and it enforces all of the rules. Forge runs on Windows, Mac, and Linux. Forge uses Java and if you don't have Java installed you can get it from here.)

Hold onto your hat because there is a brand-spanken new version of Forge with almost 300 new cards. Overall Forge now has a super, grand total of 2,624 cards. This version is crammed stuffed with a ton of great new cards and features that you will make you forget about your girlfriend, Facebook, and your new iPhone.

Forge now has one of the most memorable cards in Magic: Stasis (1U, Enchantment, Players skip their untap steps. At the beginning of your upkeep, sacrifice Stasis unless you pay U). It is a fun card to use, not to play against. Build yourself a nice Stasis deck and have some fun. And yes the artwork is utter nonsense.

The deck builder screen now has filters which are VERY, VERY useful. Try them out.

The long list of rocking new cards includes Loxodon Gatekeeper and Kismet who always keeps your opponent’s creatures one step behind. Blue mages will dominate with Force of Will, Thwart, and Chronatog.

Loxodon Gatekeeper (and Kismet) – Artifacts, creatures, and lands your opponents control enter the battlefield tapped.

Force of Will – 3UU, Instant, You may pay 1 life and exile a blue card from your hand rather than pay Force of Will's mana cost. Counter target spell.
Thwart – 2UU, Instant, You may return three Islands you control to their owner's hand rather than pay Thwart's mana cost. Counter target spell.

Chronatog – 1U, Creature, 0: Chronatog gets +3/+3 until end of turn. You skip your next turn. Activate this ability only once each turn.

Timmy’s and people who love big, overcosted creatures will salivate at Cosmic Horror (3BBB, 7/7), Force of Nature (2GGGG, 8/8) and Krosan Cloudscraper (7GGG, 13/13). Old school players will appreciate echo and cumulative upkeep cards like Flamecore Elemental (2RR, 5/4 echo) and Illusionary Forces (3U, 4/4 flying, cumulative upkeep:U). Both timmy’s and old school players will appreciate Nicol Bolas (2UUBBRR, 7/7), Palladia-Mors (2WWRRGG, 7/7), and Vaevictis Asmadi (2BBRRGG, 7/7).

Players who love insane combos will jump at Donate (2U, Sorcery, Target player gains control of target permanent you control.) and Illusions of Grandeur (3U, Enchantment, Cumulative upkeep:2, When Illusions of Grandeur enters the battlefield, you gain 20 life. When Illusions of Grandeur leaves the battlefield, you lose 20 life.)

p.s.
Officially this version is named “01-01” because that is when it was released on the forums. For a complete list of changes check out the readme file.

Download Forge – version 01/01

Program Details (this information is also in the zip file above):

To run Forge double-click on the file "run-forge.jar".

For the card pictures, you should open the menu after the program is running. You can "Import Pictures" that you currently have on your hard drive or "Download Card LQ Pictures" which downloads "low quality" cards pictures from wizards.com. The "Download Card HQ Pictures" option is experimental and may or may not work on your computer. This downloads high quality cards pictures.

5 Ideas That Will Improve Your Code

I've been programming more and playing Magic less, so some of my posts (like this one) are only about programming. Hopefully I'm not alienating my audience. I'm not sure who exactly reads this blog but I'm guessing it is a mix of non-programmers, programmers, computer literate Magic players, as well as a few people who program and play Magic. (Hi to frwololo, nantuko84, DennisBergkamp, Rob Cashwalker , etc...)

These points are taken from the book "Code Complete" by Steve McConnell.

1. The less you know about the internal workings of another method, the fewer assumptions you make about how the method operates. The fewer the assumptions you make, there is less chance that one of them is wrong.

2. The goal for individual methods is to make them like a "black "box". You know what goes in and you know what comes out but you don't know what happens inside.

3. The more independent the subsystems are, the more you reduce the complexity. Carefully defined modules separate concerns so you can focus on one thing at one time.

4. If you have data leaks between the subsystems because of sloppily defined interfaces, you will have a flood of unnecessary complexity.

5. A blanket attempt to avoid mistakes is the biggest mistake of all. Design is a process of carefully planning small mistakes in order to avoid making big ones.

The first and second points are basic but still very important. Sometimes I forget that objects and methods shouldn't know the internal workings of each other. Writing methods like "black boxes" will improve your code.

I think that the third point is the most important. Forge has several parts: IO, user interface (gui), decks, rules implementation but I didn't design these parts to be separate which results in the fourth point.

The fifth point made me laugh because I thought that the design process tried to make everything perfect. The program should be perfectly planned and each part of the program should be perfectly defined and everything is just perfect. The truth is that program design is a very sloppy process. Mistakes are OK but you try to make small mistakes instead of big ones.

Early mistakes (on paper) are less frustrating than later mistakes which are etched in code. Early mistakes are MUCH easier to fix.

Internally Forge has two play areas. I misunderstood the rules and thought that each player had his own "in play" area (now called battlefield, yeah). The problem occurs when you steal a creature that has a "come into play" ability and Forge thinks that creature is being played and the ability triggers. This problem can be fixed by some clever coding but it all stems from my initial misunderstanding. Changing the code to create a unified "in play" area would be a nightmare. (Mostly the user interface (gui) code would have to be changed.)

Unit Testing - To Test or Not To Test

For Forge 2.0 I've embracing unit testing (JUnit) and I'm writing tests for each method. In the first version of Forge I just wrote code like a madman and only debugged my code if there was a problem. The only part of the code that I tested extensively was the code that handled paying the mana costs. The code kept braking on unusual mana costs like GGG so I wrote a whole truckload of tests in order to test the code backwards and forwards.

Even though part of me still thinks writing tests is a waste of time, it does feel good to KNOW that your code works. The tests should also help refactoring because you can change the code and then run the tests to see if the new code really works.

Unit testing also encourages programmers to write small methods that do one thing well. Small well-named methods are the backbone of any project.

Version 2 Features

This is just a short list of features for Forge 2.

1. Better AI, which also includes AI versus AI. Some AI algorithms can help the computer play better but the computer has to play many games, like a thousand or a hundred thousand. The Temporal Difference algorithm can improve if the AI can play itself.

If I can get AI versus AI working, the AI can play itself and try to find game-crashing errors. Also I’ve heard that watching the AI play itself is a good screensaver. The Wagic project has an AI versus AI mode. Wagic is designed to run on a Playstation Portable (PSP) but it can also run on Windows. It lets you play against the AI like Forge.

2. Better more strict rules interpretation. I want to make the rules engine rock solid and more flexible so it can handle Magic’s insane variety of card effects.

3. Complete code testing coverage with JUnit which will help to stamp out and isolate bugs as well as refactoring.

One “non-feature” is a better user interface. It is always in the back of my mind but I don’t plan on improving the user interface until the rules engine can handle a couple thousand cards.

4 Levels of Abstraction for Computer Programmers

Every program is divided up into different levels of abstraction and the goal of any project is to write code that mirrors the problem as closely as possible. The Forge computer program is about Magic: The Gathering, so it should reference things like players, cards, library, and creature. Some of the high level of code in Forge should almost be readable by non-programmers.

In "Code Complete" by Steve McConnell, he writes about the 4 different levels of any computer program.

Level 1 is programming in a language "higher" than assembly. Level 2 is Computer Science structures like stacks, queues, linked lists, tress, sort algorithms, search algorithms, etc... Level 3 is low-level problem-domain terms. "At this level, you have the primitives you need in order to work in terms of the problem domain. The routines might be too primitive to be used to solve the problem directly, but they provide an Erector (Lego) set that higher-level routines can use to build a solution to the problem."

Level 4 is the highest level and is defined as "high-level problem-domain terms" "This level provides the abstractive power to work with a problem on its own terms. Your code at this level should be somewhat readable by someone who's not a computer-science whiz. Code at this level won't depend much on the specific features of your programming language because you'll have built your own set of tools to work with the problem. Consequently, at this level your code depends more on the tools you've built than on the capabilities of the language you're using."

The goal is to build the other levels so that you can program on level 4, in terms of the problem itself. Forge version 1 is probably written on level 3 1/2. I tried my best to get to level 4 but I just didn't have the "big picture" in mind. My main priority was to get the code running, so I mostly programmed at level 3. Hopefully in version 2 I can get to level 4. Personally I always things of programming like building a house. First, you start with a good foundation. Then you build the wall and finally you put on the roof. If there are any problems building the house, they will affect other parts of the house as well.

If you lower level code isn’t robust, your high level code won’t be robust either.

Version 2 - A New Hope

I'm slowly making progress on Forge version 2. Right now it has 11 classes, 102 methods, 117 lines of comments and 280 lines of code. There are a high number of comments because I am trying to be very thorough for myself and for whoever else that may read and update my code in the future. (And yes, the title of this article references Star Wars Episode IV, you know the GOOD "Star Wars".)

Counting the total number of lines of code (loc) for a project gives you a rough estimation on how big and complex the project is. The loc for any project can be calculated many different ways. I wrote my own little program that only counted "real" lines of code. I defined a "real" line of code to be
1. Not a comment.
2. Not whitespace.
3. Not a bracket {}, since I put brackets on separate lines.

Basically the code for version 2 just generates all of the phases for both players. While this seems trivial it is not. Each player's turn has approximately 28 phases which are listed below.

The phase array is a two-dimensional array of Strings. Index 0 is the active player (the player who's turn it is), index 1 is the player who has priority (can cast a card or activate an ability), and index 2 is the phase name. In order to generate the computer's phases I just swap the Human and Computer players, which are just Strings.

Some of these "phases" are technically steps but it doesn't matter because the mana pool empties at the end of every phase and step. Forge version 1 and 2 have the phases "Declare Blockers" and "After Declare Blockers". A few of these phases are "artificial" and don't officially exist such as "After Declare Blockers", which is when Forge lets players play cards. On a side note, I will have to make sure that the mana pool empties according to the rules and the "artificial" phases don't cause any problems.

Magic has million tiny details and technically during the untap and cleanup phases no player gets priority. For the untap and cleanup phases maybe I should use an empty string "" for the priority player.

final String Human = "Human";
final String Computer = "Computer";

private String humanTurn[][] =
{
//active player, priority player, phase name
//
{Human, Human, Constant.PhaseName.Untap},

{Human, Human   , Constant.PhaseName.Upkeep},
{Human, Computer, Constant.PhaseName.Upkeep},

{Human, Human   , Constant.PhaseName.Draw},
{Human, Computer, Constant.PhaseName.Draw},

{Human, Human   , Constant.PhaseName.Main1},
{Human, Computer, Constant.PhaseName.Main1},

{Human, Human   , Constant.PhaseName.Begin_Combat},
{Human, Computer, Constant.PhaseName.Begin_Combat},

{Human, Human, Constant.PhaseName.Attack},

{Human, Human   , Constant.PhaseName.Attack_After},
{Human, Computer, Constant.PhaseName.Attack_After},

{Human, Computer, Constant.PhaseName.Block},

{Human, Human   , Constant.PhaseName.Block_After},
{Human, Computer, Constant.PhaseName.Block_After},

{Human, Human   , Constant.PhaseName.Combat_Damage},
{Human, Computer, Constant.PhaseName.Combat_Damage},

{Human, Human   , Constant.PhaseName.End_Combat},
{Human, Computer, Constant.PhaseName.End_Combat},

{Human, Human   , Constant.PhaseName.Main2},
{Human, Computer, Constant.PhaseName.Main2},

{Human, Human   , Constant.PhaseName.At_EOT},
{Human, Computer, Constant.PhaseName.At_EOT},

{Human, Human   , Constant.PhaseName.EOT},
{Human, Computer, Constant.PhaseName.EOT},

{Human, Human   , Constant.PhaseName.Until_EOT},
{Human, Computer, Constant.PhaseName.Until_EOT},

{Human, Human, Constant.PhaseName.Cleanup}
};