# Visually debugging a Minimax AI engine

While creating the Steam version of the popular board game Hive, it became clear that normal methods of on-screen debugging weren’t going to be in-depth enough.

Alpha-beta pruning of a small Minimax game tree.

Most AI for 2-player abstract-strategy games probably uses the tried-and-true Minimax algorithm. It works just how you’d think AI would work: you look at a tree of all of the possible board positions that you could get to (and all positions you get to from there, etc.) and score them. It can get a little more complex on top of that, but the basics are really straightforward.

While the Minimax algorithm is very general-purpose, the scoring function that you use to evaluate each position is game-specific. Debugging that scoring function (called a “heuristic evaluation function” in technical lingo) can be tricky, especially since it is very hard to see an entire game-tree at once. The small tree in the first picture above is used for teaching minimax, but is unrealistically small for real games. As an example, even a very simple game like Tic-Tac-Toe would have 3 possible moves right away (it would be 9 moves, but the board is symmetrical, so there are only 3 actual different moves). Looking at this tic-tac-toe tree, you can see that even this extremely-simple game’s tree grows quite large by the third layer.

### Complexity of real Game Trees

First two plies of Tic-Tac-Toe game tree

Let’s put that in perspective compared to other games: The number of moves that can be done per level is called a “branching factor“. In the tic-tac-toe example, the branching factor at the start of the game is 3. After moving, the branching factor is 2, 5, or 5, depending on which move is made. In chess, your first move can be one of 20 possibilities: 8 pawns (each with 2 different moves) and 2 knights which have 2 possible moves each. From there, the possibilities change very quickly. Due to this variability, when discussing games we tend to focus mainly on the average branching factor. The average branching factor of tic-tac-toe is 4, for chess it’s 35, the value for Hive is currently unknown but I’d estimate it between 40 and 50.

### The need for a good visualizer

For a game such as Hive, to have the AI look 3 levels deep, you’d have (50^3) = 125,000 nodes on the third level of the tree. Even if we limit the branching factor (which we do in our AI) the number of nodes is quite large. At the time of this writing one of our AI levels limits to a branching factor of 30. So (30^3) = 27,000 nodes. Needless to say, that tree won’t fit on most computer screens, so it would be hard to debug it all at once.

Therefore, we need a different way to visualize what’s going on. When debugging a heuristic evaluation function, it’s important to know the score throughout the tree, how the score worked its way up each level, and it also helps to be able to see a detailed view of how the AI scored the nodes. Keep in mind that only the scores on the bottom level of the tree are actually used to be the final scores of the path to that node. However, when we limit the branching-factor, that involves giving a preliminary score to each node and sorting all of the sibling nodes in any given level of the tree, before traversing to their children. This way, even though many moves may be skipped in a given level of the tree, the odds are high that the most important moves are being evaluated. Due to this pre-scoring, it is helpful to have detailed scoring information on every node in the tree.

In addition to seeing the nodes in a current level, it would be helpful to have pointers to which layers of the tree are maximization or minimization steps so that you don’t have to keep as much information in your head. This way, you can examine any node in the tree and tell where it got its score from (eg: it’s children) and how its score is being used by its parent-node if it has one.

### Our solution

Minimax AI Visualizer – click to enlarge

We wanted to be able to run the AI in our game’s debug-mode, then create a log-file and view it easily. After looking around, it seemed that a very simple solution would be to dump some JSON in a format that the Javascript InfoVis Toolkit (JIT) could load, then create a tool to render a “Space Tree” which expands and collapses as needed.

→→ Check out our Minimax AI Visualizer Tool in action. ←←

I started with the SpaceTree demo from JIT and just modified it from there. Features:

• Loads data from a JSON file by default, but you can paste new JSON into a text-box to create a new tree (or use the text-box modify the existing tree).
• Colorized to easily show which steps are Maximize steps or Minimize steps
• Each node says what ply it represents to get to that node, and the final score that node ended up with.
• The mouse scroll-wheel lets you zoom in and out
• Hovering over a node brings up a detailed tool-tip bubble with the breakdown of each of the scoring-factors that were used to come up with the pre-scoring for a node – or the actual scoring, in the event that it’s a leaf-node.
• Hovering over the Root Node brings up a tool-tip bubble with detailed info on the entire run of the AI: how many nodes were evaluated, how long the AI ran, how many total prune events there were, etc..
• Each time there is a prune event (from the alpha-beta pruning), there will be one node which indicates the entire number of sibling nodes that were pruned at once.

If you want to use the same tool to visualize the progress of your own AI, all you need to do is have your code output JSON in the same format that’s used in the textarea below the graph, then paste it into that textarea and hit the “Load Tree” button.

### Outcome

Being able to more quickly track-down some of the weird decisions that the AI was making, let us drastically improve the AI in only a few days of work. The example that’s embedded in the Visualizer is from before most of the changes, but that shouldn’t matter since it’s just showing how it works. We’ve had some very good players helping us debug it, and one of the recent World Champions said that the top level of AI made him force a draw. We’re getting there!

If you want to see the AI in action, check out Hive on Steam.

If you have any questions about the Visualizer or about our AI, let me know in the comments!

# Hive is coming to Steam! Pre-order now for 30% off!

We are downright giddy to announce… Hive is coming to Steam! It’ll be the same great game as on Xbox, but will have a few extra bonuses:

• Game will track over 40 stats on Steam and you can earn 30+ Steam Achievements.
• There will be 2 new levels of AI. Since even low-end PCs are typically a lot more powerful than Xbox 360s (because those are now quite old) this gives an opportunity to have the AI make much, much better moves in the same amount of thinking-time.
• Seamlessly switch between using your mouse/keyboard or playing with a gamepad.

The first release will be on PC, but we hope to release it on both Mac and Linux soon afterward. Buying the game means you’ll get a Steam key once the game is released. This will allow you to play on any/all of the platforms once each platform is available (eg: if you buy now, you can play on PC as soon as that’s released and you do not have to re-buy it to play on Mac when the Mac version comes out).

To give a better deal to our loyal fans, we’re offering a 30% discount on pre-orders! Get it below using the Humble Widget (powered by the “Humble Bundle” team):

If you can’t see the widget above, you can click this link to pre-order Hive. Have an old computer? If you’re worried about compatibility, please check the minimum requirements on the Steam Store page (scroll down a bit or search for ‘System Requirements’).

UPDATE: You can now buy this game on Steam ‘Early Access’ which will let you play the incomplete beta immediately, and you will automatically be upgraded to the full version once it is released. Please click ‘add to card’ on the Hive page on Steam.

Like being kept in the loop? Join the mailing list to keep up with our announcements:

# Buy the Hive Pillbug expansion and get the Xbox 360 version free!

There’s been a lot of excitement around the upcoming release of the Pillbug expansion for Hive.

We have great news: if you buy the Pillbug expansion when it comes out, the package will have a code on it which will let you unlock the Pillbug in the Xbox version of Hive!

While this is a pretty big update… we have even better news coming up soon. Join the mailing list to keep up with our announcements:

# Simple single-file PHP script for combining JS / CSS assets

### Combining Assets

One of the basic tenets of making a web-page load quickly is reducing the number of HTTP requests that your page makes. One very common way of doing this, is assuring that all of your CSS files are combined into one request (ideally in the <head> tag), and all of your javscript files are combined into one request (ideally at the bottom of the <body> tag).

### The Solution

I’ve worked with several large sites which each had their own solutions, but recently I found myself needing to speed up a fairly simple site: Burndown for Trello.

To make things simple (and so that I’d never have to write this again), I made a StaticResources system which will allow me to put just one PHP script into the root directory of the site, and use a few simple calls to add files to the header or footer of the page. The script requires no setup, installation, or configuration to run correctly. However, it has some optional advanced settings (which we’ll discuss at the end).

### Usage

Usage is very simple. Just make a call to add files to the system, so that they’re included in the header or footer. Both local and external files are added with the same kind of call.

After you’ve added the files, make sure that somewhere in your code you print the HTML which will contain all of the files that were added

Here’s an example file of how you’d include a bunch of JS / CSS using this StaticResources system. It obviously won’t work if you don’t create JS/CSS files in the locations referenced, but this is very simple code to show the system in action.

### The Code

Without further delay, this is the code of static.php that you should put in the main (eg: public_html) directory of your app.

### Using this script with a CDN

One drawback of serving a combined file is that your server has to read in all of the files, then print them all. This makes the call slightly slower than it has to be. One solution is to use a CDN to cache the files on your site. This way, even if it takes your server a second or so to generate the file the first time, it can be served to the next user instantly, from the CDN.

For Burndown for Trello, we use Fastly as our CDN (disclosure: my fiance works there, but we use it because it’s free for one backend and it’s crazy fast).

The code to make this work with a CDN is very simple: one extra line below the include call:

### Code minification

Another common performance trick is to use a minifier to reduce file-size. This hasn’t been added to the script yet, but may come in the future. If you have a favorite minifier, I’ve conspicuously commented in the code where it would make sense to run the minifier.

Minification takes a little while to run, so it’s highly recommended that you get a CDN if you’re using minificaiton.

Thanks,

- Sean Colombo

# Burndown for Trello gets flame decals!

Not literally… but we made the site faster! Our app that makes burndown charts for Trello has received a number of improvements in the past couple of weeks. A couple of days ago, we made the AJAX requests take about 1/7th of the time that they took previously. The enormous Trello board that we used for testing went from taking 14 seconds to load, to taking 1 to 2 seconds.

The changes that we made only took a couple of hours, so I figured I’d share a few quick tips so that you can get a Pareto-style improvement in your backend-performance too.

We started with a simple open source PHP profiler that I released a few years ago. The only catch is that our slow request was an AJAX call… so I added a small javascript function that can be used to wrap AJAX urls, so that the URL parameter for profiling gets passed to those calls to.

Then anytime that you make an ajax call, just wrap the URL in “profilable()” like this:

That will pass the RUN_PROFILER=true url params to the ajax endpoint. The other half of the equation is to make sure the profiling info comes back in the ajax request. As you will see from the a original post about the profiler, to get the profiling output as HTML, just call profiler_printResults() somewhere that is safe to output HTML. If the profiling isn’t enabled (eg: by the URL parameters), there will be no output.

Fortunately our ‘ajax’ is not using XML, but rather JSON which contains some HTML… so we just called profiler_printResults() right in our AJAX endpoint and the HTML in the result gets injected into the page along with the rest of the result.

To see the profiling in action, hit this URL:

https://BurndownForTrello.com/?RUN_PROFILER=true

The initial page is very light (all of the heavy lifting is done by asynchronous javascript), so there is only a small table on the first request. Once you “Connect to Trello” and then view one of your trello boards, there will be quite a bit of detail below your board’s info. Just remember that the “Totals” row is the sum of all items, and since many functions are nested inside of each other, there will be a lot of double-counting… the actual time for the backend request is what comes after “Total runtime” below the table of data.

It took only a couple of hours to pull in the open source PHP profiler, add the _begin/_end hooks to our code, write the javascript code to pass the variable along to the backend, and then actually use the profiling output to identify some easy-win hotspots and get an 85% reduction in runtime for that request.

I hope it has a similar return-on-investment for you!

# “Burndown for Trello” now has a Pro version

About a year ago, we started building a scrum-like burndown tool for Trello to help us manage our own projects. After a few months of work, we made it so that anyone could sign up for the free burndown charts for Trello.

Burndown for Trello – exponential user growth

We thought that a decent number of people would find it useful, but we didn’t count on it growing as fast as it did! We started getting a lot of requests for additional features. Since we were busy releasing Hive for Xbox 360, it was hard to find time to add new things. Our solution was to create a paid account, so we can spend more time on this project which it seems there is a huge demand for.

We want to do-right by our existing free users, so here are the basics:

• The free account will remain free and will have all of the features it has today.
• Anyone who signed up before the paid account was created is an “Early Adopter” and is eligible for a perpetual discount on the paid version (look for Early Adopter in the dropdown that lets you pick a plan).

At some point since the last blog-post, we added the average-velocity line which was requested by users.

There were some other changes that we made in the process of creating this paid account:
• The name is now “Burndown for Trello”. We were told by someone at Trello that ‘Trello Burndown’ might create trademark issues.
• The app is no longer just in a folder on BlueLine’s site… it’s at its own domain now: http://BurndownForTrello.com
• All requests are now sent over https, so your company’s data is always encrypted.

We’ll be adding more and more to the paid account, but here are the main reasons to upgrade:

1. Support us! More paid accounts == more time for us to make new features!
2. Automatic daily updates of stats – even if you don’t visit the site in a given day, if you have a paid account we’ll pull the data from the Trello API for each board and store the stats. Until now, if you didn’t view a board in a specific day, then the next time you view that board, we just extrapolated (averaged) the data across all of the missing days.
3. All new features will be added to the paid accounts. Free users get the app as it is now (with only minor upgrades, like site redesigns, bug fixes and global changes like adding https). All of the big stuff coming up is paid-only.
4. MORE SOON! – We’ve had a ton of suggestions, and we’re hoping to add many cool features. Next up, we’re hoping to let you put your estimates in the titles of Trello cards, so you don’t have to visit Burndown for Trello to update your estimates.
5. Update: March 8th, 2013 – we just finished & rolled out integration with the “Scrum for Trello” Chrome extension. This means that you can put estimates in the titles of the cards in parentheses like this: (2) whether you have the extension or not. If you do this, Burndown for Trello will automatically pull in the estimate. This was hands-down our most requested feature up to this point.

If you want to get all of the new features as we add them, head over to Burndown for Trello and click on the upgrade button!

# Announcing our next game: Khet 2.0 for Xbox 360!

Keeping up with the exciting pace of this year so far… we have an awesome announcement to make:

BlueLine Game Studios has been given an exclusive license to bring the extremely popular Khet 2.0 board game to Xbox!

Khet 2.0 is an Egyptian-themed two-player game with real lasers. It has been growing in popularity world-wide, and has a successful iPhone/iPad version.

The game is already well into development, and we are using the same board game engine that we wrote while making Hive for Xbox. The Xbox version of Khet 2.0 is planned to have single-player (against AI), local multiplayer, pass-n-play (if you only have one controller), online multiplayer, full 3D graphics & camera-control, a global highscores list… and frickin’ lasers!

If you want to be notified when the game goes into Alpha/Beta testing or for the final release, please sign up for the BlueLine Games “Release Announcements” mailing list.

# New game: Hive for Xbox 360!

After more than 15 months of work, many nights of play-testing by our devoted Alpha team, and close to a kiddie-pool worth of Mountain Dew… it’s finally here!

Hive for Xbox 360!

When you think you’re starting to get good, add me on Xbox Live – “SeanColombo” – and I’ll gladly play a round with you!

If you have any questions, suggestions, or feedback… please leave them in the comments below!

# Konami Code in XNA – for Windows, Xbox, and Windows Phone (WP7)

The Konami Code is a fun part of gaming culture and a very common method for adding Easter Eggs to games. After more than a year of work on Hive, I started thinking how absurd it was that we don’t have any Easter Eggs yet. When I went to look for a module for the Konami Code in XNA (because: how could there NOT be one?!), I found that the only solution currently out there seemed to be Charles Cox’s Konami Code for WP7.

At the time of this writing, BlueLine doesn’t make any WP7 games though: just Xbox 360 games that we hope to release to PC soon. To avoid completely reinventing the wheel, and to make sure my solution would be backward compatible to anyone already using Charles Cox’s module for WP7, I decided to just piggyback on that code. I’ll send my code back to him too, so hopefully he can add it to the version on his site. I’ll also structure this post to be very similar to his post so it can be merged more easily.

The solution is a single class file that you can drop into any XNA project, and by adding a small snippet of code to your update routine, you can have Konami Code functionality in minutes.

## To Use the Class

It’s really just three things:

1. Instantiate a KonamiCode object.
2. Subscribe to the CodeEnteredRight event (and, if you want, the CodeEnteredWrong event)
3. Update it once, each game-tick (ie: in Update()).

## Getting it Into a Default Project

To mirror the example given in Charles’ original post, I’ll show how to use this module in an example project to have the same outcome that his original code did, but have it also work on Windows and Xbox 360 (in addition to WP7).

## Draw

If you run into any issues, please let us know.

## Games using this Konami code class

If you put this into a game, let us know when it’s out! We’ll add it to this list of XNA games that have Konami Code built in, using this class.