New York Botanical Garden - Beautiful!

We went to the NY Botanical Garden yesterday. It was gorgeous, except the wind chill. It was a first time experience for me, 50 years of living around NYC and had never been there before. Highly recommended, I'll probably go there again for the blossoming of the cherry trees. And again, and agian! It was easy to get to, becoming members felt like the right thing to do, to help green the city.

The Retraction of Granville Sewell

Followers of Uncommon Descent and other Intelligent Design websites may be aware that recently there was a triumphalist announcement by Dr. Dr. William Dembski of the acceptance for publication of a paper by Dr Granville Sewell, a math professor at University of Texas, El Paso. It was exactly the kind of premature "Waterloo" announcement that has backfired on Dembski in the past, and it did this time as well.
Applied Mathematics Letters had accepted the paper, but not yet published it. Dr. Sewell had a prepublication version up on his own site, to which Dembski's UD post was linked.
The paper itself was a repetition of Sewell's argument that SLOT disproves TOE. Sewell's argument is more like FOOT in MOUTH, though that hasn't prevented him from repeating it nearly word-for-word over the years, as Wesley Elsberry showed in a posting on Panda's Thumb.
Looking up the editor of AML, I took it upon myself to apprise him of the error of his ways.
 

Dr Rodin,
 
I am appalled to see a preprint, apparently from Applied Mathematical Letters, of the often repeated and often refuted nonsense of Granville Sewell on an anti-science web site.
http://www.uncommondescent.com/intelligent-design/elsevier-publishes-granville-sewells-latest-on-the-second-law/
 
Dr Sewell, whose expertise lies in partial differential equations, has writen several times on the relevance of the Second Law of Thermodynamics to the topic of evolution. Each time he makes poor arguments that do not show any understanding of the physics or chemistry involved, clearly contradicting the philosophy of your journal.
 
A concise refutation is
http://ajp.aapt.org/resource/1/ajpias/v76/i11/p1031_s1
 
The reputation of AML will be harmed by publishing this article by Sewell.
 
Yours,
David vun Kannon

Dr. Rodin's response was swift and has been published elsewhere. AML retracted publication. Science wins!

 

A big shoutout of thanks to Dr. William Dembski, whose premature ejaculations helped avoid even more severe embarrassment for AML.

Battle Royale (manga), reviewed by David vun Kannon

This is an extremely graphic manga, containing frequent scenes of violence, murder, and death. There is also a lot of nudity, 'fanservice' and explicit sex, supposedly of 9th grade students.
 
The plot is easy to summarize.  In a dystopian near-future Japan, a fascist government has created a gladatorial comabt in which a 9th grade class is abducted each year and forced to kill each other until there is only one survvivor. The students are given different weapons, ranging from Uzis to forks and boomerangs. The manga follows the 42 students of one class as they battle each other. The flavor is of a teen slasher horror movie where Freddie and Jason are your classmates.
 
Chapter arcs alternate between scenes of combat of the students trapped on the island arena and flashbacks to the normal life they led before "the Program". Several protagonist groups develop of students trying to avoid "playing the game", in some cases trying to actively destroy the Program itself. Several other major characters are students that embrace the amorality of the Program, and seek to win by killing off weaker classmates.
 
Still, even with three major good groups, two major antagonists, oodles of supporting characters, and flashbacks of everyone, the manga is padded with very repetitive philosophical conversations. The major group of protagonists does basically nothing but sit and talk until practically everyone else is killed. As in operas where characters take fifteen minutes to sing a final aria while mortally wounded, characters continue to ponder their existence and reminisce for pages and pages after their brains have been blown out.
 
And blown out they have been, in lyrical, explicit detail. The art is exceptionally graphic, going to pornographic at times, in the level of detail lavished on violence and harm to the body. At the same time, the sex scenes continue to dance around the idiosyncratic rules of Japan on the display of the genitals. (You'll also see a strong resemblance between one of the main characters and the style of the great Osamu Tezuka.) But the art is really focused on a fetish for bullets leaving gun barrels, brains, blood, and eyeballs not right in their sockets. Most characters display an excess of bodily fluids in the form of tears, mucus, blood, semen, and the ubiquitous "sweat drop".
 
Most characters are one dimensional, and wind up as cannon fodder to the two most evil and sociopathic of the students. The fate of some other students is study in paranoia. The male Big Bad has a pile of unfair advantages (genius, can learn any physical skill if he sees it once, etc.) on top of being a sociopath and drawing an Uzi. He is, of course, supernaturally hard to kill, and is drawn with a cape that hovers around his body no matter what fantastic martial arts moves he is pulling.
 
After lavishing over 100 chapters of attention to violence, the manga ends on a note of "love and hope and faith in human nature can conquer all" which even the characters realize is unrealistic. I am reminded of the moral ending tacked onto "Golden Lotus", the great erotic novel of China.
 
In the language of tvtropes.com (a great site), Battle Royale is high octane nightmare fuel from beginning to end. If you liked 1984, Lord of the Flies or A Clockwork Orange, you'll find the descent into paranoia, animalism, and ultraviolence familiar. It is up to each reader to decide if the author and illustrator are indulging themselves or using a legitimate device to explore the human condition. I vote for indulgence.

TRON: Legacy, reviewed by David vun Kannon

I saw the original TRON in 1982, motivated mostly by a desire to see computer graphics on the big screen. The story was secondary, and the plot device that actually transported the action from the real world to the virtual world was less believable than the twister from the Wizard of Oz. I didn't care, I still wanted to see computer graphics on the big screen. This was because I was a computer science grad with an interest in computer graphics.
 
I went to see TRON: Legacy motivated by pretty much the same thing.
 
TRON: Legacy chose to cast many of the same stars as the original TRON into reprises of their roles. Jeff Bridges is Kevin FLynn and Clu, a program that has taken over The Grid, the virtual world of TRON. Bruce Boxleitner is Allen Bradley, Flynn's friend, and the voice of Tron. Other characters are new. Michael Sheen is fun as flamboyant bar owner, Zuse. (The name is homage to Konrad Zuse, creator of one of the earliest electrical computers.)
 
Since I mentioned the Wizard of Oz, I should say that the plot of TRON: Legacy uses the same trope - how to get back home from an alternate world? But that plot is subsidiary to a series of set piece scenes the display the wonders of CG. I did not see the movie in 3D, though you can. Here, the movie is caught on the horns of a dilemma. It really really wants to go back and show light cycles and solar sailers, the state-of-the-art of 1982 computer graphics that fanboys demand. It also wants to show of its own cutting edge chops, so the clean room perfection of The Grid is rendered in 3D, blurred with smoke and the haze of digital memory.
 
This doesn't evoke the "sense of wonder" that the producers were aiming at. In the post-Avatar world, computer graphics has crossed over the 'uncanny valley' that caught Final Fantasy: The Spirits Within (the first full CG feature film). The original TRON did not aspire to having its digital world be mistaken for the real. It couldn't, with that technology, so it didn't try. TRON: Legacy does try, and comes up short as a result. The homages are so close that the modern CG of smoke, explosions, and flame seems inappropriate. Only the work on Jeff Bridges, letting him play a much younger face as Clu, is so good you don't know how they did it.
 
TRON: Legacy ends happily, and set up for a sequel. Nobody important dies on-screen. That's too bad, since it is just another way life is sapped from the plot.
 
Bottom line - limited appeal to anyone outside its core audience.
 
PS - the trailers!
 
Cowboys and Aliens - this looks fun. Daniel Craig and Harrison Ford together, woot. From the trailer, it would seem that Craig is a bad guy, was abducted by aliens, escaped or was released, and now must join forces with Sherriff Ford who wants to hang him, in order to save a western town from flying saucers. Or something.
 
Green Lanten - nice visuals, but might suffer as do all superhero origin stories.
 
Born to be Wild - baby orangutans and baby elephants! OMG can you get any cuter! Based on the First Looks segment shown in the theater before the movie, the 'making of' feature on the DVD for this film will be awesomely funny.
 
Real Steel - giant robo fight movie. Very "Transformers" feel to the robots. I'm hoping for a Rock-em-Sock-em Robots tie in, becuase that is all this movie is.

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.

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.

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.