Tuesday, August 24, 2010

MtG AI: The Opening

In the previous post, we saw that for an AI program the major difficulties in Magic can be broken down into two areas, generating legal moves, and scoring the game state. The score might be simplified for now as life points plus mana or something, but the major difficulty remains of generating legal moves.

Ever turn, there's the chance of a player playing any one of hundreds of cards that are legal to play at that point.

To do a good job of looking ahead, we need to prune down the number of possible moves as much as possible.

The beginning of the game has a maximum of possibilities and a minimum of information.

AI programs for games such as chess deal with this problem in the same way as human players. They make several moves out of a "book" of already worked out opening moves.

Personally, I doubt the relevance of this strategy to Magic. If the AI "knew" that a deck was designed for a particular playing style, such as aggressive, control, or combo, there might be some standard opening plays. But at least in the initial stages, the decks constructed by the deckbuilding algorithm are not going to fall into clear categories.

Friday, August 20, 2010

MtG AI: Playing the Game

My take on MtG deck construction was pretty straightforward from an AI perspective, even though it was very different from the way a human player thinks about the process. But now that we have a deck, how do we play it with an AI?

While the complexities of 11,000+ cards and changing rules might lead to some initial frustration, let's review what is in our favor in trying to build an AI for the game.

Magic is a two person game. The players take turns making plays. If one player wins, the other loses. The game always has a specific state. All of those things are also true of chess, checkers, go, and many other well studied games. So we really do have a lot going for us in terms of theory and ideas.

Two person games of this type are playable by an algorithm called minmax, or alpha-beta pruning. The basic idea is to start from specific game position. Assuming this position is not itself a win for one player, the opposing player has to move. First make a list of all of the players legal moves. Now change the game state (as if they had taken that move) and re-evaluate the state. Is it a win for either player? If not, score the position in terms of relative advantage for one player or the other. Repeat the process, this time scoring eac of the replies of the player to each of the possible moves. And on. And on.

This process builds a tree of game states, as many moves into the future as you have time to evaluate, each one of which has a score. The AI will choose the play at the first level which leads to the best score for it, as far into the future as it can see, assuming that on the player's turn, the player is doing the same thing.

This is a very well understood algorithm in computer science. It depends on two things - being able to generate a list of legal moves for each player, and a way to score game states. It is in these two areas that the complexity of Magic rears its head.

Legal moves

For all the complexity of the Magic turn structure, it really is a game where players strictly take turns moving. You can see this is true because any time Alice takes an action, Bob her opponent can play an 'instant'. So each players legal move list is changing as the game runs through its different phases and turns, but it always includes "play instant from hand". The trouble is that 'instant' is not just one thing, but a whole class of things that or might not be in the hand. But hey, we're already in a lot better position than assuming that at any point in the game a player can play any one of 11,000+ cards!

This is a great reason to start with a very restricted set of cards to play with. For example, the recent computer game "Duels of the Planeswalkers" for Xbox 360 and PC has a game playing AI. This AI doesn't have to deal with 11,000 cards, only the ones allowed in the specific decks of the game itself.

The number of choices for legal move is called "fan out". Both Go and Magic have a big fan out, and that makes it difficult for a computer program to look very far into the future. In comparison, in a game such as checkers the program can analyze the tree many layers forward (actually, in the case of checkers, all the way to the end). The depth of this lookahead is what makes a game AI smart (or dumb).

A way to look deeper is to not look at all the choices at each level. The program can sort the list so that it is looking at the likeliest moves first, and also "prune away" whole sections of the tree that lead to bad results. In AI programming, these are standard ways to speed up and look farther ahead.

Game state evaluation

Each position needs to be scored in order to use our algorithm. Again, this might sound very complicated for Magic, since the "game state" includes the visible cards, the probabilities of the cards not seen, and even the rules themselves (which can change as different cards are played). However, we can start with some very basic scoring based simply on life points, perhaps with some modifiers for mana pool, tapped/untapped cards, etc. All of these are known to both players at all times.

Most of the time, we want our evaluator to be fast rather than accurate. For one thing, it is hard to be accurate. For another, this algorithmic approach relies on evaluating many, many positions to choose the best play.

Summary

Even though Magic is not a game of "perfect information" (unlike chess, where both players have all the information and the same information) we can still analyse it using a standard game algorithm of minmax, looking at legal moves and scoring them. This is all a program has to do to play the game.

Tuesday, August 17, 2010

MtG AI: Deck Construction

Magic is played with decks of cards, 60 or more, chosen from a pool of legal cards.

Walk Before We Run - ignore sideboard issues

WBWR - make the pool of legal cards small to test the code, add to the pool later.

I'd attack this problem with something like a genetic algorithm. A GA has a simple algorithm:

Create a population, give each member a score.
For as long as you want:
Choose high scoring members, modify them, score the new version, and add them to the population.
Take out members of the population based on some criteria (such as a low score).

Several modifications are usually allowed. Mutation changes a population member slightly. Crossover mixes two members of the population.

Lets make Magic decks our population members. Each member is just a list of card numbers, drawn from the list of legal numbers. Mutation might mean switching a number for another legal number. Crossover might mean choosing a number, N, between 1 and 60, and taking the first N cards from one member, and rest up to 60 from a second member. There are more sophisticated versions of these genetic operators that can be invented, as well.

Since we are constantly testing new decks that are similar to our high scoring members, and throwing away poor decks, the overall population is expected to gradually improve its score. If the poopulation is small, we can also expect it to converge on a single solution, a "killer deck" that is better than all the other decks tested. (Is this a killer deck in real life? No way. It is just good in the metagame that our population represents.) There are also ways to encourage the evolution of 'species' - several different decks that remain in the population for long periods.

Of course, the above description is hiding a big issue behind a "Separation of Concerns" wall. How do we score decks? Well, the best thing to do would be to have a huge round robin tournament, and the score for each deck would be its wins minus its losses. Now you can see why I thought "Self Play" was an important heuristic!

Until you get your game play AI running, you can substitute other scoring methods. Invent some way of assigning points to a deck. If a deck with a creature that requires some color, doesn't contain land of that color, then give that deck a penalty. If the same keyword appears on more cards (so the deck has a 'theme') give the deck a bonus. This kind of quick and dirty scoring is also useful in the beginning of a run of deck development. If our first set of decks is generated by just throwing 60 random numbers together, over and over, those decks are going to be really bad. It might save time to not even bother playing these decks until they reach some basic level of sanity.

I wouldn't overdo the scoring heuristics, though. One of the best things about a GA is that it can find a solution to a problem that a human would never think of. Using a lot of heuristics to score decks, instead of letting them compete head to head, is forcing the algorithm to follow your way of thinking.

So that is my approach in nutshell. Self play involving a variable population which improves over time.

MtG AI: First thoughts

Yes, the complexity of Magic is overwhelming! Where do we start?

Let's start by laying down some well tried heuristics (rules of thumb) for the development process.

Walk Before You Run - this means we might have to try to solve a simpler version of the problem first, learn some lessons, and then attack the bigger problem we really want to solve. Sure we want to play any kind of Magic game out there, but starting off by staring at 10,000+ card descriptions just leads to drooling. Think about ways to cut the problem down to size. Work with only the cards of a recent core set, for example, instead of every card ever made. How about limiting the number of colors? Eliminate enchantments or some other aspect of the game, until later. Even programming some BabyMagic game is going to be a challenge, so start easy. You won't get discouraged (so fast).

Separation of Concerns - this means not trying to solve everything at once in one ball of wax. Magic naturally falls into separate areas, such as deck construction and play. There are even areas such as the metagame and trading values that I won't try to talk to right now. You can attack deck construction separately from play, even if you want to integrate them eventually.

Self Play - the interface of your system should allow the system to play against a copy of itself, not just a human being. The computer can play thousands of games while you sleep, improving it's algorithms, databases, etc. Self play assumes that your AI is written so that learning/improvement can be scored independently of a human. A genetic algorithm is an example of that.

I'm sure we can come up with other high level heuristics like these, but for now this will do nicely.

Magic the Gathering, why no AI?

On my mind recently, the lack of good AI for MtG.

Why is this so? It seems that everyone is put off by the bewildering complexities of game mechanics that change the rules as each card is played.

I agree that Magic is more complicated than the sorts of boardgames that are the traditional targets of AI, such as chess. But if you can write game AI for an RTS (Real Time Strategy) game, you should be able to write an AI to play Magic. Given that position, I'd like to write a few posts here on what I think would work for Magic, if you were to go about building an AI for it.

SFABC Writers group

Just gotta say, this is a great group!

Monday, June 21, 2010

Review: Toy Story 3

Pixar is now, what, 11 for 11?

As a sequel, TS3 does suffer from replaying various bits of shtik that you've seen before. But the whole framing story works well, and the last scene is a bit of a tear jerker. There are also several laugh out loud moments in which I think the whole audience was laughing at once. No mean feat, that.

I saw the film in 3D. I can honestly say that I did not see one case where 3D was used obtrusively, as a gimmick, an effect you were supposed to notice. Neither was the film flat. I think the filmmakers hit an effective balance. (The same cannot be said for Avatar, for example.)

Pros:
Spanish Buzz
Ken
Totoro as Miyazaki homage

Cons:
"Night and Day", the short before the main film, was not as strong as previous films. I know, I'm reaching.

Review: Legion

I saw this on the small screen of an airplane. That is about what it deserved.

The story is a combination of Terminator (imminent end of the world, the baby must die, pursued by unstoppable big guy) and "X of the Dead" (small group of strangers trapped in the house by zombies) movie.

It doesn't really work, since running away from the Terminator was the only effective strategy.

Pros:
None

Cons:
laughable CGI
you can tell an angel by their British accent

What was the early earth really like?

I've been trying to collect some facts/factoids about what the environment of the Archaean Earth might have been like, in order to organize some of my thinking about origin-of-life scenarios.

Sun:
  • 70% weaker in total(?) radiation - weaker at least in the visible by that much.
  • higher activity in UV range
  • spinning faster - like the Earth and the Moon, before they all traded rotation for distance.
  • larger magnetic field - from the faster spin.
  • bigger solar gamma and x-ray bursts - from the larger magnetic field.

Earth:
  • 6-12 hour rotation period - if you back up from current conditions of the Earth-Moon system, this is what you get for the time right after the Moon reformed after the impact of some Mars-size planetoid with the proto-Earth.
  • 3x current heat flux from the interior due to more radioactives.
  • thick atmosphere of CO2 (like Venus today) - there is a huge amount of CO2 buried today as rock formed by life.
  • no oxygen, so no ozone to stop UV from reaching the surface - an incredible 10^30 more! That is a mind boggling amount of radiation, which the ozone layer currently keeps at bay.
  • tides are 1000 times higher! (if moon is 10x closer)
  • winds are very strong, east-west bands - due to rapid rotation.
  • no large continents
  • low levels of cloud cover -no nucleating particles.
  • high level of infall of cometary organic material - inner solar system still full of debris

Moon:
  • much closer (10x closer?) - that is inside Earth's geosynchronous orbit. We have satellites that would have been further away!
  • spinning itself - not yet tidally locked
  • covering a huge piece of the sky - because of being so close
  • collisions that make moons such as ours are rare but not completely unlikely - they might happen in 5-10% of solar systems with rocky planets
  • 30 (out of 300) gas giant exoplanets discovered so far orbit in their star's 'habzone' - even if the planet is too big for life as we know it, it could have life bearing moons

Put some of these together, and you get a recipe for incredible weather. We often think of the ancient Earth as tropical volcanic islands being lapped gently by tides that swish warm and shallow waters of a lagoon containing a dilute organic soup.

Think again. Think howling winds blowing endlessly around the world, as they do between Antarctica and the southern continents. Think waves pushed by that wind and tides the size of the World Trade Center towers, rushing over flat landscapes to crash like tsunamis and run inland for miles, or entirely across the landscape to the next shoreline. Every 3 hours.

Think of the hurricanes. Clouds and rain nucleate around dust and organic chemicals floating in the sky. Not much of either would be available, so those heaving oceans just evaporate, and the amount of water in the atmosphere just keeps building up. And up. And up until it supersaturates. And then finally the rain starts to fall in huge fat drops. The storm grows, the quickly whirling planet triggers a spiral, an eye.

But there is no landfall to dissipate this hurricane. There is just the wind howling around the planet, and isolated islands being drowned by the tides. The hurricane could spin like Jupiter's Great Red Spot, around the world and then back over the same ocean that spawned it.

What are some of the Origin Of Life (OOL) implications?

High UV levels striking the ocean surface, where water and CO2 are present, can rapidly build many organic molecules. Some people fear that the UV would break big molecules apart faster than they could form. Luckily, that is not true. Long chain molecules, such as RNA, can 'quench' the high energy photon before it heats up the entire molecule, or breaks a single bond. The heat drains away into the ocean. So the high UV works in life's favor to build up lots of the chemicals of life.

Those winds? It turns out that the top layer of the ocean, a skin only a few millimeters thick, has its own dynamics. Evaporation raises the concentration of other chemicals just below the surface. And the wind whips the surface into masses of bubbles - spindrift. These bubbles trap chemicals together for long periods.

The tides? The endless pounding that landforms received was insurance that all kinds of useful chemicals were ground up and dissolved in the ocean, as rapidly as the volcanoes brought them to the surface.

It is also true that the endless cycling of tides and drying out is a natural form of what we call PCR - a way to duplicate organic molecules

No continents also meant that there was a much larger network of undersea cracks in the crust, where seawater and lava could meet. Today these conditions exist in fewer places, creating the 'black smokers' and 'lost cities' that support life without light. They would have been far more common in the ancient past.

Bottom line - as truly alien as our planet must have been three and a half billion years ago, it was still a setting in which life blossomed almost as soon as it was able. Some of the most important reasons are all based in the existence of the Moon as the large close companion of the Earth. Life may come up out of the depths, or at the surface, but the Moon donated the rocks and created the stirring motion of our oceans.

Saturday, January 9, 2010

Review: The Digital Plague, by Jeff Somers

I bought this book to read on the plane. It was a good value for the price.

The cover advertises it as 'nano-noir', a term I would agree with. It is science fiction with a hard boiled detective edge, and a good dose of humor.

The lead character and narrator, Avery Cates, is a successful assassin. Cates and his world were introduced in Somer's previous novel, The Electric Church. I have not read that book, but as in all sequels much of the plot and characters in that book are quickly sketched in this one.

The book is fun and fast-paced. Its problems are relatively minor, but the editor was asleep at the wheel a few times.

My big issue with the book is that it tries to put too many ideas forward at the same time, instead of limiting itself to the exploration of one idea fully. One key idea in particular is terribly motivated, and even the characters agree is inexplicable. It appears to exist only to punch up flagging adrenaline levels and created scenes that might be more cinematic if filmed.

Good entertainment value at the paperback price. I will go back and buy the first book, and the next in the series as well.

Review: Daybreakers

Daybreakers is an Australian-made vampire film that explores some traditional vampire tropes in unconventional ways by taking them to their logical limits. Set in the near future, it has science fiction and horror elements skillfully mixed. Except for Willem Dafoe, I did not recognize the cast.

The premise is ecological. In a predator prey-relationship, if the population of predators goes above the level that the prey population can support, it will crash. Not enough antelope = starving lions. The mathematics (called Lotka-Volterra dynamics) are very beautiful.

Many vampire stories assume that vampires will carefully cultivate the human population they feed on. Not Daybreakers. This movie introduces a destabilizing idea - that vampires will 'promote' many humans instead of feeding on them, for essentially loving reasons. Done with the best intentions, but in the future of Daybreakers, ten years after a vampire plague of unspoken origin, most of humanity are now the immortal undead, kings and queens of the night.

For the sake of argument, if a vampire needs 60 humans as a stable blood farm to provide a renewable resource of one pint a day, you can see how converting 90 percent of the humans to vampires is going to lead to 'instabilities'. There is just not enough blood to go around. Blood is both food and currency in this future.

The premise is inventive. The details are worked out nicely. The film is a good blend of horror and s-f. Those who are fans of traditional effects, as opposed to CGI, will be happy. My main quibble is that it solves the main problem twice, apparently for cinematic rather than in-story reasons. I enjoyed the music quite a bit.

Recommended.

Review: Sherlock Holmes

I saw Sherlock Holmes last night with my son.

Likes:
Title design
Set dressing
Irene Adler
Humor

Dislikes:
That same washed out color palette you've seen in other recent films.

For those who enjoyed Robert Downey Jr. in Ironman, Sherlock Holmes (the film) has a bit of steampunk Tony Stark to the character Sherlock Holmes. Jude Law plays Dr Watson very well in my view. Rachel McAdams plays Irene Adler, the moral, comic, romantic, and intellectual foil (and equal) to Downey's Holmes.

One of the joys of detective fiction for a reader is to see if they can solve the mystery before the main character. This is difficult in film detective stories, but this film does honor the trope by at least letting you see the clues, even if they whiz by too fast to process until the requisite flashback at the end.

Holmes and Watson as the bickering odd couple got old fast, though it was better than the fawning hero worship versions of Watson in other films.

The least likable parts of the film are the fight scenes. Holmes does have a reputation 'in canon' as a boxer and martial artist, so I am not objecting that they are out of character. Rather, they are filmed in gratuitous slo-mo intercut with sped up footage on some very cluttered sets. The result is some very muddy views of the action - who is hitting whom how.

Recommended - a well made 'reboot' (though not 'origins') genre film. Strong detective, minor steampunk notes, and no bitter aftertaste.