Tech talk about Pokemon Go

Quick background for people who don't already know: Pokemon Go is a mobile game that launched last month on Android, and more recently on iPhones. It is billed as an "augmented reality game," in that the gameplay incorporates a requirement to walk around in the real world and visit physical locations, and some virtual objects are treated within the game as if they physically exist at those locations. It was immediately popular, and has been plagued with ongoing problems with server response and performance. In this post I will discuss these issues on a level that laymen should be able to understand.

Explain like I'm five: DDoS attack

A friend of mine asked me to literally "explain like I'm five" how a DDoS (Distributed Denial of Service) attack works, because World of Warcraft was having troubles yesterday after the launch of Warlords Of Draenor, and he was trying to tell his kid why. My answer:

When you play Warcraft, the computer that represents you is always "talking" through the internet to the computer that has everything in the WoW world. Computers have a limited attention span; they can talk to a lot of people at the same time, but not everybody in the world.

Usually they have enough attention to talk to all the people who are trying to play WoW at the same time. But sometimes bad people don't want the game to work right, so they pretend to be a million people and all try to talk to the computer at once. The world computer doesn't know who's a real person and who's not, so it gets confused and talks to all the million fake people. Then it doesn't have time to talk to you, so the game goes slow because it can't send you information about what's happening fast enough.

Sometimes people do this because they're mad at the company, and sometimes just because they think it's funny. It's against the law, but it's hard for the police to understand, so usually the company that is getting attacked has to deal with it on their own.

Adventures in junior programming, episode 4

As I've mentioned in previous posts (1, 2, 3), I've been teaching my son Ben a little Python here and there over the last few years. We're not very consistent, and in fact we haven't really done it much at all in a year or so. But that's not too terrible; it sort of reflects my own experience at Ben's age. I tinkered a little bit with BASIC once in a great while, copied some programs out of books and magazines, "hacked" some programs, forgot many things, and didn't really get deeply into program structure at all until I reached high school. So this is not an urgent task for me.

Ben and I did some work over the weekend. I have taught him a few things over the last couple of years, but we do it so sporadically that it's hard to keep the information fresh in his mind. So we started with this exercise: opened several of the programs that he has worked on in the past, then read through each one and predicted what it was going to do, and why. Doing this helped him get back into his headspace from earlier sessions, and also drilled the syntax back into his mind pretty quickly. Speaking for myself, I also find that reading my own code can help to refamiliarize myself with a language much more quickly than reading somebody else's examples.

Up until now it was clear that we'd done a lot of programs that were really brief -- single problem, single solution. Print all the powers of two up to a million. Print out a times table. Create a simple password verification program (which insults you if you fail; that's a ten year old mindset for you). These problems are interesting in their own right, but the real fun of programming is making a project with no immediate end goal, something you can tinker with over a long period.

Ben is very into gaming, just like his dad. We've been playing World of Warcraft together since he was seven. This seemed like a promising starting point, so I had him create a simple system of rules which could represent a fight between a hero and a monster. So we started out with a few basic hard coded numbers: Hero hit points, monster hit points, hero damage value, monster damage value. Then we wrote a loop so that the fight would keep going until one of the hit point values dropped below zero.

The program is pretty predictable at this point; the beauty of the concept is that we can build on the basic concept over time. So the first thing Ben wanted to do was tweak the numbers: The hero should always win, but just barely. So we did some math to figure out how to make that happen, and we saw the outcome change as the starting values got closer to numbers that "felt right."

This was a good time to introduce functions, which I don't think I've explained in detail before. We had a function for printing the current status ("The hero has X hit points! The monster has Y hit points!"); a function called "hithero" and another called "hitmonster". Initially the hit functions removed a fixed amount of damage; then we got a little more sophisticated, passed in the damage as a parameter, and also printed the action to the screen. After that we also added in weapon descriptions, so it then said "The hero hit the monster for 20 damage with his sword of epicness!"

It's a fun exercise and it has Ben's enthusiasm up, so he now thinks of it as "The first program I wrote mostly by myself!" (I did give him a whole lot of guidance, actually, but I've let him steer the creative direction of the program, so he does have plenty to be proud about.)

We now have a bug and feature wish list which is surely going to grow:

• Make it so hit points can't go negative.
• Make a "death" message.
• Have multiple kinds of weapons; enable weapon switching.
• Randomize damage within a range, like 16-24.
• Allow the hero to pick a type of action, a la Pokemon, such as a direct damage attack or a debuff attack.
• At some point we should probably start discussing object-oriented programming, before we get to the point where we bring in multiple monsters.
• Item drops?
• Visiting locations?
• Ben really wants to make graphics, but that is a very advanced topic, and I'd rather he get solid with the fundamentals before touching that one.
• I'm a web programmer, and putting stuff in web pages is a great way to showcase your work to friends. So maybe that's a better direction to go than graphics.

Obviously the best part of programming, as per the title of this blog, is building castles in the air -- constructing projects which seems to take on their own reality. So I'm looking forward to some more sessions where we make this thing interesting, while keeping it accessible to a kid who will be twelve soon.

Affordable Care Act rollout blues

I keep hearing journalists speculate about what the explanation might be for the Affordable Care Act website being so unreliable in its first week. While it sounds like a good talking point, the conversations have generally been pretty dumb.

You want an explanation? It's a massive online system that got hit with nine million users during launch week. That is more than World of Warcraft has subscribers right now.

As an IT engineer and an online gamer, I would be shocked NOT to see an online system on that scale experiencing technical problems. I played WoW since launch day. It had sporadic connections for the first week or two. The same thing happened when the first couple of expansions came out. Most other MMO's and numerous other games experienced similar glitches early in their life cycles also. Who remembers the PR nightmare of the latest rollout in the SimCity series? People who pre-ordered the game, mostly couldn't play at all for a week.

Non-functioning websites during launch week are the rule, not the exception. The reason is, an individual server can handle a certain number of simultaneous connections. For a large project, you use multiple servers running in parallel, so that they can spread out the load. There are also multiple redirections to other computers on the network; for instance, the database is housed on another server, and there might also be multiple parallel databases running in some cases. In the case of a big government system accessing social security numbers, it's likely to interface with some really old legacy systems somewhere along the line.

So in the first place, the throughput of the whole system can only be as reliable as its weakest connection. In the second place, systems are designed to handle an expected average load each day. One reason WoW was so slow at first, was because an especially high number of people wanted to be the first to play. After some time, usage settles down a bit.

You can't always predict how high the early load will be on the system. And even if you do guess correctly, it's not necessarily a good idea to buy double the number of computers that you'll need on an average day; that's a lot of expensive computing power that you'll just wind up having to sell off fairly quickly.

So, don't be surprised that there are problems. Be surprised that it's working at all most of the time.

Operation HackMaster Crit Tables, episode 2

Now that I've explained what data structures are for, I can finally explain how I approached the problem of deciphering those ponderous HackMaster tables.

First of all, I discovered to my dismay that the tables were only available in the form of PDF files -- images, not text.  Just as I was about to tell my friend that I didn't want to waste time converting six pages of tiny print to very usable data, my lovely assistant Lynnea (the aforementioned fiancee who actually plays the game) stepped in and volunteered to do it.  This is one thing about her personality that I've never been able to understand, but she loves doing data entry, filling out forms, etc.  I think it's some kind of OCD thing.  But for whatever reason, she's extremely enthusiastic, diligent, and thorough about this kind of work.  And by the way, if you need this kind of work done, she's available to hire!  Ask me for a resume.  :)

With this powerful slave human resource at my disposal, I wrote up a few sample lines of text in a spreadsheet to show how I wanted them, wound her up and let her go at it.  She cranked the rest out in a surprisingly short time.  I then converted the results to standard comma-separated value format, some of which you can download from here: Hacking weapon table part 1; List of effects.  In case you're not familiar with them, .csv files are a generic text-only format which can be read in a spreadsheet program like Excel, or any standard text editor.

Working with just my sample rows, I set out to work out what the abstract properties of the data were.  The first thing to consider is the way a body part is selected.  In the hacking weapon table, you can see that if you roll a 1-100, you get hit in the "Foot, Top"; if you roll 101-104, you get hit in the heel, 105-136 is Toe, and so on.

This is like a hash table, almost, but it's not one.  If it was a hash table, you'd usually have one body part per number: 1 -> Foot Top, 2 -> Heel, and so on.  Here, we're working with a range of numbers corresponding to each lookup value.

I decided to start with a generic lookup table, where you start with objects which contain a "low" value, a "high" value, and a generic object which can get returned from the lookup. The declaration looks like this:

public class RangeLookup<T>
{
   private List ranges;

   private class Entry
   {
      protected T item;
      protected int low, high;

      public Entry( T i, int l, int h )
      {
         item = i;
         low = l;
         high = h;
      }
   }
   ...
}

In Java using the "<T>" notation means that "T" could be anything.  Even though I wasn't going to be using this lookup table more than once, I like to keep structures as all-purpose as possible.  That's partly because I might want to reuse them in the future, and partly because I want to be able to test how the component works without making it dependent on the equally complex item which will be retrieved by the lookup.

Every structure needs an interface -- a means of communicating with it that only does what you want and hides the guts of it from the rest of the program.  I created an "addEntry" function to the RangeLookup class, so that you could insert a new entry with a high, a low, and a retrieved object of type T.  Then I added a "lookup" function where you send in a number, it gives you an object.  In my implementation, the lookup function simply walks through all of the possible results and checks whether the requested number is between the high and the low.  This would be inefficient if there were going to be a lot of entries, so I might have come up with some kind of hashing structure or tree search; but since there are only about 20 or so body parts, it wasn't worth the extra effort and runs fine as is.

After verifying that this was working right, I created the following additional structures:

• Looking at the Effects table, it is a basic mapping (in my case, placed in a HashMap) from one string to another.  You put in the code "f", and the resulting effect is "fall prone and drop items".  So, I created a simple object called an "effect," containing "key" and "description."
• It's a bit more complicated than that, though.  Often the table will contain numbers, but the effects will contain only the symbol "X".  For instance, if the table says "d4" then the relevant effect is "dX", which means "reduce Dexterity by X".  Therefore I made another class called an "Outcome," which contains an Effect AND a number (which may be zero if it's not necessary).
• I made an EffectTable, which implements the HashMap of Effects.
• Almost ready to create an actual table object, I first made a class called "CritTableEntry."  This represents a cell in the table.  It contains: a low roll, a high roll, the name of a body part, and a List of effects (because each cell may result in several outcomes, not just one).
• A CritTable class to put them all together.  This class has an addEntry method and another method for retrieving the entries.

As a final step, I created a "Reader" class which did the heavy lifting of reading and interpreting the CSV files and adding one row at a time into a generated table.  I don't like to reinvent the wheel, so I googled class libraries which would read CSV files and interpret them as lists.  I settled on using OpenCSV.  I could have written my own parser, but when the task is as common as reading a CSV, I tend to assume that somebody has already done all the work before me and has already been through the process of making all the mistakes and catching the bugs which come up.

Notice that none of these objects deals with input and output directly.  It's preferable to test each component of your program separately as much as possible BEFORE trying to decide what kind of user interface to make.  Your interface should be tailored to the problem space.  As it turns out, I wound up creating several different interfaces before I settled on created a web application.  I'll discuss these concerns in a later post.

When testing your data structures it's a good idea to create unit tests.  A unit test is a small, self contained application which is designed to test one thing at a time.  You need to think about every possible way that your program might break, create a unit test for each one, and make sure that it works right at the boundary conditions.

Off the top of my head, here are some boundaries of the crit tables that needed to be tested:

• Spot check several "body part" rolls with random(ish) numbers and see that the returned information matches the table.
• Spot check several "outcome" rolls in one row and see that the returned effects match the table.
• Test the boundaries of some rolls.  For instance, on the table I linked, "4301-4492" corresponds to "Arm, upper inner", and "4493-4588" corresponds to "Elbow".  Therefore I have to make sure that a roll of 4492 returns a different part from 4493.
• Test when happens when the body part roll is 0 (invalid), 1, 10000, and 10001 (invalid).
• Test what happens when the effect roll is 0, 1, 24, and 25.

Keep all your unit tests around forever.  If something breaks, that's a quick way of figuring out which part is not working.  If it's a problem with your data model rather than your user interface, the unit tests will catch it.

Next time I'll be talking about all the different ways of making an interface on the same models.

Operation HackMaster Crit Tables, episode 1

This post is about a project I recently did for fun.  Although the project itself has extremely limited application, it inspired me to do something I've been meaning to do for a long time, namely upgrade the web server for my apollowebworks.com domain to something which supports Java applications with Tomcat.  (I chose a company called Arvixe based on scanning the features they offer and reading a bunch of reviews.  Shout out to my boyz at Arvixe!)

Because I'll be touching on a wide range of topics, I'll split them up into multiple posts, and that should keep me from neglecting this blog for a little while.  So, partly to tell you what's coming and partly just so I can keep track for myself, here's a road map of the topics I plan to hit with this discussion.

• General geekery about using programming to automate complex tasks.
• Building a project from the ground up, starting by visualizing the data structures instead of just diving in blindly.
• How separating interface from implementation makes it easier to translate your program to multiple platforms.
• Good riddance to the bad old days: How the web has made program content delivery easier.
• A primer for noobs on what web servers do, and why I bought another one.

First let me explain the problem.  My fiancee, Lynnea, has gotten into paper-and-pencil roleplaying games.  She has been running a light Dungeons & Dragons campaign occasionally for me and my son Ben over the last few months. She also plays with a group of friends one night a week.  For my part, I've played RPGs a few times before but never been a strong part of that scene, so I just listen to the stories of her sessions.  Currently they're playing with a rules system called "HackMaster."

As I understand it from skimming a few chapters of the rulebook, HackMaster was written by someone who hates doing things the easy way.  When D&D was first published in 1974, it was at first an ever-expanding set of complicated rules involving tons of die-rolling for all kinds of special situations.  Or as a German exchange student my family hosted in high school put it, "D&D isn't a role-playing game, it's a roll-playing game."  Har.  Har.  Very droll, those gamers.  (Oh hey, how are things going, Max? ;)

Still, as the years went by, D&D started to reverse the trend and become more streamlined, or so I've heard.  The latest release, fourth edition rules, was clearly heavily influenced by World of Warcraft, and reduces a lot of the unnecessary choices in favor of more interesting combinations of focused options.

The HackMaster author just hates that.  Not that I would recognize the difference, but I have the impression that if anything, he's aggressively chosen to make every little action even more complicated than it would have been under old-school D&D, to the point where a party can spend thirty minutes meticulously checking a single room for traps before seeing any combat.  And the critical hit tables are an utter monstrosity.

Critical hits (or "crits") for you non-gamers, means that for every attack there is a chance (1 in 20 under D&D rules) that it will be a super-strong attack which does extra damage.  In WoW, this is handled automatically by the game; you can build up gear that will increase your crit chance, but usually there's a flat formula that says "If you crit, your strike does twice as much damage."  Rules in 4th edition D&D are pretty close to the same.

Not HackMaster.

In HackMaster, you roll a number between 1 and 10,000 for the body part where your blow lands, and there are all kinds of "realistic" outcomes that result if you land a powerful blow on that body part.  Furthermore, rolling a 20 is just your cue to pull out a ginormous, six page tables full of teeny little numbers and two accompanying rules pages.  You then roll another number that might range from 1-24 to see just how badly your crit hurt the monster (or the monster's crit hurt you).

For instance, if you get hit on the top of the head, the crit damage can range from "8 extra damage" to "twice normal damage AND you lose some hit accuracy AND you lose some dexterity AND you fall down and drop everything you're carrying"... to "brain goo."  Do not pass go.

Each one of those individual clauses, by the way, is represented in the table by a little symbol like "dX" which you have to look up on a smaller table of effects.  I think you have to look at a sample to see what I'm talking about.

(Click for a larger image.)

Not to put too fine a point on it, this sounds like a game that I would personally hate playing.  But no accounting for taste, you know?  Even so, problems of managing huge sets of data are piles of fun to solve with a computer.  NO, that's NOT sarcasm, you non-programmers, that's fun.  Shut up.

So when the DM tentatively asked if it would be possible to write a program that could handle the die rolls and just spit out some nice, clean output, I said "Piece of cake!"  I wouldn't even accept his offer to pay for it.  Just like when I wrote a Sudoku solver, sometimes figuring out how to automate gameplay is more fun than actually playing.  (Disclaimer: I used to claim that Sudoku is a fun math problem and a crappy game.  Now I like playing it.  It's my Android Evo's fault, damn it... it's the perfect game for a handheld, and it has built in strategy advice.  Once I started improving at harder puzzles, there was no escape.)

And so it began.

To be continued...

Retrospective on my first do-it-yourself computer experience

I've always considered myself a software geek, and in the past I've had no desire to fool around with hardware beyond the occasional RAM upgrade or extra hard drive. However, so many friends have reported positive experiences with building their own computers, that I decided I really needed to try it.

I was pushed to hurry along this path when my old desktop's hard disk got corrupted and I could no longer run Windows. I was planning to pull the data off and reinstall, but I still recognized that it was time to replace the old eight year old system. Since I got a new laptop a year ago, my old computer was mostly sitting dormant, used occasionally to recover documents and sync my iPod with music that I've recorded and rated from my CD collection over the last several years.

A Facebook friend gave me some words of wisdom: You will not save money by building your own computer. Not because the parts won't be cheaper -- they will! But when you buy them individually, it's impossible to resist the siren call of "100 more watts of power couldn't hurt!" or "Gosh, this terrabyte hard drive is not nearly twice as expensive as the 500GB, how can I pass that up?" or "I'm saving money! A little more muscle in the graphics card? Why not?"

So you'll spend just as much as you would for a prefab desktop, but you will get more than you would have for your money. And then there's the "priceless" category, which is pride in creation, as well as a better understanding of what's going on under the hood of all future computers you may work with.

Another friend who used to build and test hardware for Dell pointed out that I was working at a severe disadvantage as a first timer. An experienced or professional builder will have lots of spare parts lying around to swap out and help test the machine. Nothing's on the screen, is the graphics card okay? Put in a different card and find out. Etc. I had to debug all my problems with just one set of parts, as my other PC was much too old to have any compatible bits.

Phase 1: Shopping spree

The first thing I did right was, instead of buying a motherboard, case and power supply online, I went down to the local Fry's and chatted up an extremely knowledgeable clerk. With all the dire warnings I'd heard about messing up compatibility requirements, I just didn't want to take the chance of guesswork. Before I went, I bought a short trade magazine about building a computer by PC Gamer. I read it thoroughly. They of course recommended a ridiculously overpowered and overpriced system, but later in the book they had some recommendations for working on a budget. They came up with something for under $600, but this estimate is a bit deceptive because it doesn't include an OS or any peripherals like a monitor.

Anyway, I read this thoroughly and dog-eared the page full of cheap stuff, figuring this to be a minimum benchmark for what I can buy. Then I brought the list to the Fry's guy, and I said "I am prepared to spend several hundred dollars today. Pay attention to me!" Basically I went through each item on the "cheap" list, and asked the following questions:

1. Do you have this particular part?
2. If not, what do you have that's comparable in price and performance?
3. What would I get by spending more on a better part?
4. How likely is it that I will need that extra power?
5. (In some cases) That's more expensive than the guide implies. Can I get it cheaper on New Egg?

Your mileage may vary, but this guy was extremely helpful, and didn't try argue too hard to get me to buy only at Fry's or to buy stuff that was more powerful than I needed. In fact I only wound up buying a motherboard and case that day, and I left armed with a list of precise specs that would be compatible with the mobo, and deals to look for on New Egg. (For example: "That CPU you're looking for is absolutely the best thing in that price range," he said. "In fact it's so popular that it's been out of stock for weeks. Go look for that exact thing on New Egg and see if you can find it at the price you want." And I did.) I was so happy with the experience that I made a point of coming back when I needed some odds and ends, like a keyboard and a replacement hard drive.

It happens to be the holiday season, so it seems like New Egg had even more combo details and discounts than usual, or so they told me via email every single day. You just have to know approximately what you're looking for, and then keep an eye out for discounts with other parts you're looking for. Hard disk may be paired with Windows 7. Graphics card may come along extra RAM. Stuff like that. $10-$20 savings here and there adds up, or as I warned, encourages you to buy slightly more power. :)

Phase 2: Construction

In addition to getting friendly with a retail guy, it's always a good idea to identify a friend or coworker who has done this before and can guide you through it. If your workplace makes this likely, talk to everyone about your intent and see what kind of feedback they get. A guy who works in QA here is my new best friend. :)

Building the computer was both less complicated and more nerve wracking than I expected. I was frankly terrified of making mistakes, and I did make mistakes. I was curious about the CPU connections, and brushed it with my finger before remembering that you NEVER EVER TOUCH THE PINS. Similarly, I couldn't find a tube of thermal grease that my magazine claimed would come with either the CPU or motherboard. It wasn't until I poked the underside of the CPU cooler and came away with sticky fingers that I realized the stuff was pre-applied, and now I was afraid I'd contaminated and ruined it somehow. I forgot to put on my static wrist strap several times. I dropped the graphics card a little too hard as I was pulling it in and out so often. Luckily, the computer parts are considerably less fragile than I had feared. Not that they aren't fragile, but they can take a few knocks. (Except hard drives. The drive I bought from NewEgg made clicking noises and didn't get detected, which is why I wound up returning it and buying a replacement.)

Figuring out how many parts need power was also a challenge. I initially thought my power supply was busted because nothing happened when I simply plugged it in -- no fan action or anything. Turns out it needs to be hooked into the computer's power button or else it doesn't get an "on" signal. Also, count the number of fans and make sure they are ALL running. My case has two built in, with space to install another one. The CPU has its own fan; the graphics card has its own fan; and the power supply has an intake fan. At first I had plugged the fan into the power supply, but my QA friend pointed out that you are supposed to plug them into the motherboard so it can sense the temperature and regulate the fan speed.

The CPU needs power, and the mobo needs two cables plugged in SNUGLY (loose cables were also a hallmark of the experience). Then there are all the little things like LEDs and USB power supplies, which seem intimidating at first (lots of cables!) but the motherboard's manual is very specific about what goes where. It's not so bad. Just don't forget to find the loose parts you need, like a tiny speaker.

Miscellaneous stuff I learned

• If you haven't upgraded your system for a while you may be surprised to learn what is built in standard to motherboards these days. You used to need to plug in a sound card and a network card; now you don't. I bought a sound card, and I'm installing it because it's a cheap part that is not much worth returning. But the built in sound works fine for the most part.
• The BIOS may take a long time to appear on screen the first time you start it up. Give it a couple of minutes.
• If your graphics card has two ports, they are not necessarily interchangeable. One is for the primary monitor, and the other is for a dual setup. Make sure your monitor is plugged into the right one.
• The first sign that you are doing something right is if it beeps. Make sure the little internal speaker is set up. Don't put in RAM right away, because when it's out you will hear beeps indicating an error. At that point, you know your motherboard is probably okay.
• All you have to do with the new system is drop in a CD for the operating system of your choice and watch it go. There is no other initial prep work (I thought i would have to screw around in the BIOS more).
• Don't talk too much about your issues on Facebook, because an army of annoying drones will tell you to switch to Mac. They can STFU if they're not planning to play grown-up games or develop software. :)

Specs

Case: Cooler Master HAF 912
Motherboard: MSI 870-G45
CPU: AMD Phenom II X2 555 Black Edition Callisto 3.2GHz Socket AM3 80W Dual-Core
Power supply: COOLER MASTER Silent Pro M700 RS-700-AMBA-D3 700W
Hard drive: Seagate Barracuda 7200.12 ST31000528AS 1TB (actually that's the one that died and got replaced; the new one is Toshiba or something)
Mouse: RAZER Lachesis Banshee Blue 9 Buttons 1 x Wheel USB Wired Laser Gaming Mouse
RAM: G.SKILL Ripjaws Series 4GB (2 x 2GB) 240-Pin DDR3 SDRAM DDR3 1600 (PC3 12800)
DVD: SAMSUNG CD/DVD Burner Black SATA Model
OS: Windows 7 64 bit Home Premium
Graphics: SAPPHIRE 100284L Radeon HD 5750 1GB 128-bit GDDR5 PCI Express 2.0 x16

The Gaming Experience

Sure, I've installed Eclipse and JBoss on the new box, and I'm enjoying the fact that I won't be coming close to filling up the hard drive for a long time. Compiling programs is nice when it's fast, but don't let me lie to you; the real benefit of a new system is the games.

For a moderate priced system it runs great. I've been playing World of Warcraft at "Ultra" graphics settings with hardly any drop in the full 60 FPS. Of course, WoW is not such a graphics intensive game, but with the new changes in place for Cataclysm, it looks pretty nice: the water has good distortion effects, you can see stuff in the landscape that is a good half a zone away; and the spell effects really sparkle.

With Starcraft II it's hard for people who don't play to notice the difference, since the view is set such a long distance from the action. When playing though, you can see enormous detail in the units, and the glowing effect of workers carrying minerals and gas is a nice bonus. Also, the Machinima in-game cutscenes are noticeably worse than the pre-rendered movies on a slower machine. With higher settings, they are still different but still pretty impressive.

Left 4 Dead 2 looks great and benefits enormously from running quickly.

I'm a pretty satisfied customer of the experience, and again, it's not so much the newness of the machine as the pride of ownership.

The Chess Master And The Computer

Garry Kasparov On Chess Metaphors

Thirteen years after Deep Blue beat him at chess, Garry Kasparov has written a long, thoughtful article about humanity's search for a meaning behind the event. Manages to cram in quite a lot of insights about both artificial intelligence in general, and the way the game of chess has changed among human opponents. As someone with a small fondness for chess and a large fondness for AI, I enjoyed it a lot.

There have been many unintended consequences, both positive and negative, of the rapid proliferation of powerful chess software. Kids love computers and take to them naturally, so it's no surprise that the same is true of the combination of chess and computers. With the introduction of super-powerful software it became possible for a youngster to have a top-level opponent at home instead of needing a professional trainer from an early age. Countries with little by way of chess tradition and few available coaches can now produce prodigies. I am in fact coaching one of them this year, nineteen-year-old Magnus Carlsen, from Norway, where relatively little chess is played.

The heavy use of computer analysis has pushed the game itself in new directions. The machine doesn't care about style or patterns or hundreds of years of established theory. It counts up the values of the chess pieces, analyzes a few billion moves, and counts them up again. (A computer translates each piece and each positional factor into a value in order to reduce the game to numbers it can crunch.) It is entirely free of prejudice and doctrine and this has contributed to the development of players who are almost as free of dogma as the machines with which they train. Increasingly, a move isn't good or bad because it looks that way or because it hasn't been done that way before. It's simply good if it works and bad if it doesn't. Although we still require a strong measure of intuition and logic to play well, humans today are starting to play more like computers.

More on gambling and random seeds

I always appreciate it when people write in with questions about something I've posted before. Gives me an excuse to keep this blog at least somewhat active.

Joe in Illinois writes:

Enjoyed reading your article on google regarding how to set a seed and randomness. Would different seeds contain different overall results. For example, some people would argue that a simple Jacks or Better video poker game returning 99.54% (in the long run, whatever that is) is still not purely random because the maker must still set this % ( over time), So would/could some seeds produce more winning combinations, maybe with fewer overall winning numbers in the seed. Players would not recognize one seed starting or ending. The next seed would/could have say, only 16% of winning combinations. Some people are overly concerned with this RNG, I say it's just doing its job, running constantly. But I also think that the player should hope for a positive seed, along with some luck and knowledge.

The short answer is, yes, different random seeds would lead to better or worse luck. But in the long run, with a good random algorithm, it wouldn't matter to you. Hoping for a "good" string of numbers coming from the RNG makes neither more nor less sense than hoping for good luck when you sit down at a physical card table.

Look at it this way. If you take a video recording of your session at a poker game, obviously you'll draw more good hands than bad hands sometimes. If you took different videos on successive days, and later you compared the tapes, then you could say "Oh look: on day one I had a lucky streak, and on day two I had an unlucky streak." But that's just the way random numbers actually behave: it's a rare string of randoms that don't show signs of patterns that appear meaningful but aren't.

Since the nature of a correctly designed random number generator is to simulate real random numbers, of course an RNG will create those same apparent patterns. But as long as there is no way for you to reverse engineer the algorithm or figure out what the seed actually was, hoping for a certain pattern is not much more than superstition.

Another interesting thing to note is that the nature of probability is that the larger your sample set is, the more likely it is to confirm to the expected distribution. In other words, if you only play three games in a row, it's not entirely unlikely that you could get a lucky streak and win all three games. Of course, it's slightly more likely that you would lose all three games; but still, if you believe in luck, betting a lot on a small number of hands makes some sense. The longer you play, though, the less the game's outcome will look like a sequence of wild streaks, and the more it will look like a typical bell curve distribution of some sort.

Thus, if you play 5000 hands of video poker, you are almost guaranteed to gradually lose money at the expected rate, as very lucky or very unlucky streaks will tend to cancel each other out.

Artificial intelligence in games, part 3

As I warned when I started this blog, I've allowed it to lie dormant for a while, but I feel like it's high time to pick up where I left off and finish the series about playing chess by look-ahead.

So to review the posts that led up to this one:

• It's possible, and not even very hard, to construct a tree that describes all games of tic-tac-toe.
• By doing so, you can prune off the branches that lead to a loss (and sometimes that lead to a draw) to write a program that plays a perfect game of tic-tac-toe.

Now we're going to turn our attention to chess.

Although chess is a much more complex game than tic-tac-toe, it's easy to see that you can apply the same tactics to systematically list all possible games of chess, in theory. Of course I'm not going to attempt to diagram them, but there's definitely a finite number of things you can do on each move. If you're the white player, on your first turn you have eight pawns that you can move forward one or two spaces, and then you have two knights that can move to two spots (forward two, left or right one). So the total possible moves on the first turn is (8*2)+(2*2), or 20.

Then it gets a little more complicated. Black has the same choices, but he has the same 20 choices for each of the 20 possible moves that white could make. So after each player has made one move, there are 20*20=400 possible states the board could be in. It only gets worse from there.

For instance, if white performed the traditional P-K4 opening, on the second move he has nearly all the other choices remaining (7 pawns to move one or two squares, plus two knights two ways, 18 moves) but he also has a whole lot of new choices. The king's knight may move into the spot occupied by the pawn (19). If the black king's pawn doesn't block it, the white king's pawn may advance one space (20) or, depending on what black did, capture an enemy pawn.

Also, the white king's bishop is now free to move to any of 5 spaces toward the upper left (25) and the queen can move to any of 4 spaces toward the upper right (29). So the number of possible moves keeps increasing as the board opens up, and so does the complexity of the tree. Now it looks like by the time white has moved twice, there are about (20*20*29) possible states the board could be in. (Some starters obviously make less than 29 moves possible, and there is more than one way to get to the same state; i.e., P-K4 followed by P-Q4 has the same result as P-Q4 followed by P-K4).

As we observed in the tic-tac-toe problem, you can calculate roughly how many possible games there are in two ways: by multiplying out the possibilities for all moves, or by figuring out every possible state of the board. The second method tends to be smaller because it eliminates various ways of GETTING to those states. However, in the case of chess, figuring out how many moves are possible from each state is massively complicated, so will go with the second approach.

Each side has 16 pieces. The pieces are not unique; for instance, the eight pawns are interchangeable with each other and so are the two rooks . However, to simplify the calculations we'll assume that all pieces are unique. So there are 32 pieces on the board, and 64 squares where they could be located. The first piece could be on any of the 64 squares, the second on any of the remaining 63, the third on any of the remaining 62, and so on. So as a rough guess, the number of board configurations is (64*63*62*...*35*34*33) and then the remaining 32 squares are blank. That is to say, the answer is "64 choose 32", or (64!/(32!*32!))

Side note: Cool feature of Google. Type "64 choose 32" into the search bar and it will answer the question for you. It's 1.83*10¹⁸.

Is this number an accurate portrayal of all chess boards? Not exactly. In the first place, many of the moves are not legal. This set of all possible boards includes boards where the two kings are next to each other, or in an impossible multiple check; it includes pawns on the first row, and positions where all eight pawns are on their home squares, but the king and queen are not.

On the other hand, it does not include any position where one or more pieces have been captured, nor does it include positions with two or more queens due to promotion. So there may be more games that are truly possibly, or there may be fewer, but on the order of 10¹⁸ possibilities is a fair guess.

Now, 10¹⁸ is a very large number. In point of fact, it is larger than the number of seconds since the universe began (about 4.4*10¹⁷... although it's only 189 billion if you're a creationist. Har har.) It's close to the number of grains of sand on earth, and much larger than the number of stars in the milky way.

In theory, you could have a computer run through the win/loss state of every one of those games, but not in a reasonable amount of time. If you could analyze one game a second, it would of course take longer than the universe has been around to decide on one move. Computers can do much better than that, of course. Currently the world's fastest supercomputer can perform 596 TeraFLOPs -- 596 trillion floating point operations per second. That means that if you were so incredibly optimistic that you believed that analyzing one board position could be done in a single operation (believe me, it can't), the world's fastest supercomputer would still take 40 minutes to analyze the outcome for a single move. And that level of optimism is ridiculous.

Granted, computers have become a lot more powerful since this topic was discussed in the 1970's, but it's still fairly impractical to play a decent game of perfect chess, unless you have several supercomputers lying around doing parallel computations. Your desktop PC would take years. More realistically, thousands of years. Needless to say, no computer plays chess based on the tic-tac-toe strategy of exploring every possible move.

Next time: What's a heuristic, and how come a computer can beat the human chess champion of the world?

Artificial intelligence in games, part 2

In the previous post, we discussed the fact that tic-tac-toe is finite game, and you can even calculate all the possible states of the board: it's 19,683, with 362,880 different ways to get to the legal states.  Now we can talk about how to take advantage of this calculation to always win the game.

Let's imagine that we pit two perfect computer opponents against each other.  The first opponent, playing as "X", will want to evaluate each of the nine possible moves on a blank board.  How does it know which is best?

Well, starting in the corner, the question is: "Do I have a sure win on this path?  If so, then I will definitely make this move.  If not, then does my opponent have a sure win?  If so, then I will definitely not make this move."

But how do you know if you or the opponent has a sure win?  Simple: Imagine that you already made this move, and then try to make the best move for the opponent.

You can easily see that this is a recursive process.  It has a recursive step ("Let me try this move") and it definitely has a terminating condition.  After all, if you come to a step where (a) the board is full, (b) X has won, or (c) O has won, you don't need to look ahead to any other moves.

Here's an example of how the computer would evaluate the first possible path.

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

This game ends in a win for the X player.  So if you are the X player, you like this game.  If you  are the O player, you do not like this game.  So the computer then backs up by two moves ("waking up," in the dream analogy) and assumes that O would not go there, but would instead do this:

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

Of course, this game will also result in a win for X if you follow it to the conclusion, which is this:

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

You get the idea.  The computer will play every game to its ending, at which point it will know exactly which games guarantee a win for one player or the other.

Now the pruning begins.  The X-playing intelligence will try to reach one of the game states that guarantees a win for X.  If it cannot, it will at least avoid reaching any game state that guarantees a win for O.

Writing an unbeatable tic-tac-toe opponent in this way is actually pretty straightforward.  You can write it to pick the first "good" move, where "good" means "First try to pick a move that guarantees a win; then try to pick a move that doesn't guarantee a loss."  If you do this, you'll find that your tic-tac-toe game will always play in the same way.  For instance, in the first move, the upper left corner is as good a move as any (the O play can never force a win).  So your program may well always start in the upper left.  This program will not appear to be intelligent.  But it will never lose.

If you want your program to be more interesting, throw in a randomizer.  If there are multiple moves that guarantee a win, then pick one at random.  Otherwise, if there are multiple moves that don't guarantee a loss, pick one of those.  Then you'll have a program that never loses, and also it will make moves that appear unpredictable.

Even though tic-tac-toe is an unwinnable game with two perfect players, some moves are better than others.  Against novice opponents, there are tricks you can use to moderately increase the likelihood that your opponent will make a mistake and lose.  This program doesn't know that.  It doesn't evaluate different positions as tactically stronger.  It just knows whether or not one player is guaranteed to win.

By the way, needless to say, this tic-tac-toe program does not have sufficient reasoning capacity to prevent it from launching a global thermonuclear war.  ;)  The computer doesn't have abstract thoughts; it's just following instructions.  Completely deterministic instructions for winning if it can.

Next time: Chess as a deterministic game.

Artificial intelligence in games, part 1

"Chess is not a game. Chess is a well-defined form of computation. You may not be able to work out the answers, but in theory there must be a solution."

- John von Neumann

I'd like to talk about some basic concepts of Artificial Intelligence, by talking about games. In a few posts I'm going to tell you how to play a perfect game of chess. Not just a good strategy, but a perfect strategy. With this strategy, you will always beat a non-perfect opponent. If no win is possible, you will most likely be able to end the game in a draw.

Unfortunately, once I've explained this strategy, you will realize that you can't actually use it. So before I talk about that, I'm going to try something less ambitious. I'll tell you how to teach your computer to play a perfect game of tic-tac-toe, also known as "noughts and crosses" in England.

Here's some quick background for those who don't know how to play. Tic-tac-toe is played on a three-by-three grid. Two players mark their squares, one with the letter "X", the other with the letter "O". Traditionally the X player goes first, and may place a mark on any open square. The players continue to alternate marks until one of two conditions is met. A player can win by placing three of his or her marks in a row -- either horizontally, vertically, or on a diagonal. Much more commonly if the players are experienced, the board will fill up, no player will get three in a row, and the game ends in a draw.

Complexity of tic-tac-toe

How many possible games of tic-tac-toe are there? One way to do it might be to count all possible sequences of moves. The first player has nine possible moves to make. The second player can only go in an unoccupied square, so that's eight moves left. The first player can then go in any of seven remaining squares. And so on, so the number of possible games is at most 9*8*7*6*5*4*3*2*1.

This is a common mathematical operation called a factorial. "9 factorial" is abbreviated as "9!" Factorials are very big. Some algorithms have a running time of O(n!), which can be extremely dangerous -- but I'll get back to that in another post. Luckily, in this case n is only 9, and 9! is a fairly manageable number: It's 362,880.

That seems like a big number to people who are good at thinking in the abstract but bad at storing large amounts of information. However, computers are the opposite, and 362,880 is a very small, manageable number of objects to explore.

It is also an upper bound. We know that there are no MORE than 362,880 possible games of tic-tac-toe, but most of the games resemble each other. Another trick we could apply is to calculate possible states of the board without thinking of moves. Each square can be in one of three states. Either it is empty, or it has an X, or it has an O. Thus, the total number of possible states of the board (legal or not) is 3^9, which is 19,683. So actually, there are no more than this many different ways to set up the board.

In fact, there are even fewer possible states, because many of them aren't legal. For instance, the board could contain all X's, but that's not the state of a real game, because the "O" player never got to move. So there are actually far less than 19,683 states, but all we need is a rough order of magnitude estimate to see how big a problem we have ahead of us.

Calculating all possible games of tic-tac-toe

If you go first in a game of tic-tac-toe, there are nine moves that you can make. The possibilities break down like this:

|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
|
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |

|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|    |   |         |   |         |   |
| ---+---+---   ---+---+---   ---+---+---
|  X |   |         | X |         |   | X 

Actually, these nine positions do not really represent unique games. Really, there are three unique moves that you can make: Go in the center, go in a corner, and go on an edge. The rest of the moves simply lead to rotated or mirrored versions of the same games. Some algorithms might take advantage of this similarity and reduce the search space, but for our purposes, it still doesn't take too long to treat all combinations as unique.

Now, if you go in the upper left corner, there are eight moves that the "O" player could make. Here are a few.

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

Again, these do not represent unique games. For all practical purposes, the first move and the third move are the same game. But it's easier to program (though slower to run) if you don't bother trying to analyze the games.

In the next post, I'll explain how we can use this system for categorizing every possible game to write an unbeatable opponent.