Adding some randomness to turn-based AI (2 of 2)

We just released a big update to Hive which included some great visual changes as well as a number of AI improvements. One of the interesting AI changes was the addition of a bit more randomness to the AI’s decisions, with minimal impact on the skill of the AI. This is the 2nd part in a 2-post series on the topic. If you haven’t read the first post of the series, I recommend that you at least skim it first.

Randomness on all moves

Even with a large number of random openings, it would be possible to run into similar situations down the road that would play out time and time again (Battlestar Galactica style). Since this repetition would lead to predictability but most randomness decreases the skill-level of the AI, we had to strike a balance. In order to make it so that full games diverge from each other significantly, but without weakening the AI too much, I came up with the concept of a “randomness quotient”. I don’t know if this already exists in Game AI or not, but it seems to be a good solution and that was the most appropriate name I could think of for it.

“Randomness Quotient” explained

The “randomness quotient” is a setting that will increase the randomness of the choices as its value decreases. Specifically, if the randomness quotient (which we will represent with the variable “Q”) is 7, then the engine will choose a ply other than the best move about 1/7 times (which is “1/Q” times). Of those instances where the best-scored ply is not chosen, then the second-best move will be chosen 1/Q times. Therefore, the odds of getting to the second best move and still choosing to consider the third-best scored move is ((1 / Q) / Q) which is the same as (1 / (Q ^ [move-number])). To figure out the opposite number (the odds of choosing move number N, rather than the odds that we’ll skip past it) we’d use a numerator of (Q-1). For example, the 8th best move would be chosen once in approximately ((Q-1) / (Q ^ 8)) moves. The more general equation is: ((Q-1) / (Q^N)) where Q is the randomness quotient, and N is the move number (as ranked by the heuristic evaluation method so that move 1 scores the best, move 2 scored the second best, etc.).

Even with a fairly high amount of randomness – such as a Q of 2, remember: low Q means high randomness – we would only see a move as bad as the 8th move in 1 out of every (1/(2^8))= 256 moves.

These occasional less-than-stellar moves are essentially simulating a human player occasionally losing concentration.

In case the math was a bit confusing there, we can show the effects of this algorithm visually. Each bar in the chart is the move-number where the moves are ranked from the best-scoring on the left to the worst-scoring on the right.

randomnessQuotient_2In the first chart, there is a very low randomness quotient of “2” which is NOT recommended in realistic play, but it’s still a great example to visualize how this works. You’ll notice the first move is chosen 1/2 of the time. Since the other 1/2 of the moves are also cut in half, then the second-best move (move index 1) is only chosen in 1/4 of the instances.

randomnessQuotient_7In this second chart, we have a higher randomness quotient of 7 which represents a more realistic setting. This setting doesn’t add a ton of randomness to any given move, but over the length of a normal game, this should introduce enough randomness to steer any similar games apart from each other. As you may have recognized, these charts are an example of exponential decay.

In our code, we used lower Q values to give more randomness to weaker levels of AI to “nerf” them a bit, while giving them more variation at the same time. The higher levels of AI still have a modestly high randomness quotient since we want a little randomness – currently Q is around 8 or 9 – but we may continue to tweak that from experience.

Randomness Quotient pseudocode

This is almost the exact code from our Minimax engine where we implement randomness based on the Randomness Quotient. It’s not that much code!

Conclusion

The addition of randomness to the AI engine has greatly increased the replay-value of the AI in Hive. Hopefully this concept can be useful to some other developers as well. This change was released as a free update two days ago, along with a significant batch of visual updates and about a half-dozen other AI improvements that we’ve made over the past week or so. If you have the game, check them out… if you haven’t bought Hive yet, please support us by grabbing your copy on Steam today!

As always, please let us know if you have any feedback about the changes in Hive, or if you have any questions about this post! If you’ve implemented randomness in your own AI in another interesting way, please leave a comment for the other readers – and myself – to learn from.

Thanks!

Hive Visual Upgrades!

classictiles

Today we are happy to say that we have launched a new build of Hive. This build has a number of AI tweaks that Sean mentioned in the previous post and will be talking more about in an upcoming post (edit: now posted). Another large piece of this update is an overall upgrade to the in-game look. We have received a large amount of feedback of how people would like to see the game represented, and we have listened.

First and foremost, we have upped the overall realism of the game pieces by making them to scale with the real life game pieces. The dimensions of the in game tiles should mimic the real life tiles precisely in proportions. This gives you a much more familiar look. We also have set the initial orientation of insects on the tiles to match the real world tiles to add to the familiarity.

fog

Another huge update you will notice immediately is that we have added a virtual tabletop. No longer do the pieces seem to float in space, they now rest on an unending virtual wooden table complete with shadows, giving a much more real world feel. We hope in the future to expand this even a little further and allow you to select from a variety of surfaces to play on. We may even go as far as allow custom table tops.

Also, to bring the game a little further into the real world, we switched from an orthographic camera to a perspective camera to give the game a little more sense of depth.

Finally, we tweaked the game piece HUD just a bit to give the game a little more room to breathe and to show off the new tabletop below just a little bit.

carbontiles

We hope you enjoy the updates!

Adding some randomness to turn-based AI (1 of 2)

We make a habit of asking great Hive players to give us feedback on the AI for our Steam version of Hive . Now that the AI has become pretty formidable, a suggestion we started hearing a few times was that the AI wasn’t random enough. This allowed players to basically memorize outcomes and they found themselves replaying any moves that worked in the past, rather than playing to win.

As I mentioned in my ECGC 2013 talk, an important concern in “real-world”/commercial game AI – as opposed to just getting optimal results in a lab – is to make sure that your AI teaches players to get better at the game rather than how to get better at just beating your AI.

When to use Randomness

In perfect strategy games (those with no luck), a completely random move is highly unlikely to be good. Conversely, even with great AI: if the AI is imperfect, then having little-to-no-randomness makes it easy for players to memorize and exploit any weaknesses. Your first reaction might be to just assume we should make perfect AI. However, for sufficiently-complex games such as Hive and Chess, the possible outcomes are more numerous than the atoms in the universe, so we’re likely to be relegated to imperfect AI forever (or at least until we have decent quantum-computers).

Not only does complete randomness lead to weak decisions, but almost* any randomness generally leads to slightly worse decisions. If you aren’t using randomness, you always chose the best-scoring move. Due to this trade-off of efficacy vs. randomness, I would not recommend adding much randomness to your AI until it is already very good.

Randomness in Openings

Players who played dozens of games in a row against our AI quickly became cognizant of patterns and vulnerabilities in the AI’s openings. Once they discovered a way to make the AI have a weak opening they found themselves constantly replaying those openings and regardless of what happened after, the AI couldn’t recover from that bad of a start.

Since variation in openings was crucial to preventing the AI from getting in a rut, we added a fair amount of randomness.

How it was before:

Originally, we used a weighted probability to figure out which Hive tile to place. The second ply was always placing a Queen, off-center of the first piece (not inline). The third move and beyond were all calculated by our minimax engine.

How it is now:

Hive "C", "I", "L", and "Z" shaped openings.

Hive “C”, “I”, “L”, and “Z” shaped openings.

We use a weighted probability for the first and second pieces. The second piece is still quite likely to be a Queen (it’s a very solid choice) but it won’t always be a Queen. The location of the second placement is now completely random. In Randy Ingersoll’s book, Play Hive Like A Champion, he named the openings based on the shape of the tiles. Normal openings can be laid-out like a “C”, “I”, “L” or “Z” (there are also “F” and “J” openings, which are just rotated versions of the “L”). If a player chooses not to place their queen by the second move, then the opening is called an “X”. The “X” isn’t considered a very good opening, but all of the possible openings can now be done by the slightly random AI; the weightings are just tuned so that it will be pretty rare for the AI to play “X”.

In addition to the decent randomness on the second move, we also expanded it so that the third-move (which is computed using the minimax engine) has a high degree of randomness. 1/2 of the time, the best scoring move will not be chosen, and in 1/2 of the those instances, the second best scoring move won’t be chosen either. The next post will explain more about this type of randomness.

Randomness on all other moves!

This is a little more complicated/mathematical/technical so I’ve split it into another post to avoid tiring you out with this already-long post! It should be posted in the next day or two. edit: it’s posted now.

Conclusion

The addition of randomness to the AI engine has greatly increased the replay-value of the AI in Hive. Hopefully this concept can be useful to some other developers as well. This change is going to be released as a free update in the next couple of days, along with a significant batch of visual updates and about a half-dozen other AI improvements that we’ve made over the past week or so. Keep your eye out for the update on Steam! EDIT: The update has been released!

As always, please let us know if you have any feedback about the changes in Hive, or if you have any questions about this post! If you’ve implemented randomness in your own AI in another interesting way, please leave a comment for the other readers – and myself – to learn from.

Thanks!

*: “Almost” because you can get a small amount of randomness from randomly choosing between any moves that tie for the “best move”, but that’s unlikely to happen very often and will still yield nearly-identical moves in many cases – eg: moving one pawn in Chess instead of its mirror opposite.

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.

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

Tic-Tac-Toe game tree

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

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:

Join our mailing list to receive announcements
E-mail address:
 

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

PillbugThere’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:

Join our mailing list to receive announcements
(we have some big things coming up)!
E-mail address:
 

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.

The End

Hope you found the script useful. If you use it on your site, please link to it in the comments!
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

php_profiler_outputThe 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.

dat exponential growth

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.

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!