Lost Cities by Reiner Knizia – Standard Notation proposal

Just as with standard notation for Tatsu, I couldn’t find a pre-existing standard for move or board notation for Lost Cities.

If you’re not familiar with BlueLine Games, we’re best known for making digital versions of board games, and Lost Cities by Reiner Knizia is the next game we’re working on. Below is my draft at a potential notation that I think would work well.

LOST CITIES STANDARD NOTATION SPEC v1.0 – Sean Colombo 20161007

Placement Notation

In Lost Cities, there are two types of placements that a player can make on their turn. They can either place a card from their hand onto one of the five expeditions, or they can discard a card to one of the five expedition spaces. Placements shall take the format:

[CARD COLOR LETTER][CARD NUMBER OR “H” FOR HANDSHAKE]<[D FOR DISCARD]>

Where [CARD COLOR LETTER] will be a letter representing the color of the card. Typically this will be the first letter of the color in English, but there will be special cases if additional colors get added which collide with the letters from earlier expeditions. For example, the base pack has Blue represented by “B”, but there is a promo pack that will have Black cards in it, which will be represented by “k”. The letter is NOT case-sensitive, so “k” and “K” are treated the same.

Color Letter
Red R
Green G
White W
Blue B
Yellow Y
Black K

Note: No color will be assigned “D” because that is reserved for representing the “Draw Pile” in other contexts.

[CARD NUMBER OR “H” FOR HANDSHAKE] is fairly self-explanatory. This is the value on the card that is being placed. The cards have numbers 2 through 10 or a picture of a handshake. The “H” is not case-sensitive so both “h” and “H” should be accepted.

<[D FOR DISCARD]> is an optional suffix, meaning that the placement will discard the card onto the expedition color provided, rather than playing the card onto the track.

Examples:

  • R3 – Will place a Red “3” from the player’s hand onto the track for the Red expedition.
  • BHD – Will discard a Blue Handshake card onto the Blue Expedition’s discard-pile.

Draw Notation

The format is simple:
[COLOR LETTER TO DRAW FROM OR “D” FOR DRAW-PILE]
This uses the same letters for the colors that were used in Placement notation, except that “D” is reserved for the Draw-Pile.

Game Notation

Each move is numbered, and the move consists of 2 parts, separated by a Hyphen in this format:
[PLACEMENT NOTATION]-[DRAW NOTATION]

For example:

  1. R3-D
  2. BHD-D
  3. R4-B

That is a game where Player 1 plays Red 3, then draws from the draw pile. Player 2 discards a Blue Handshake card, then draws from the draw-pile. Then Player 1 plays Red 4, then draws from the Blue Discard Pile.

Conclusion

This notation seems like a good first candidate & should cover all needed cases. There are two things I don’t love about it:

  1. The “D” suffix for discard and “D” for draw-pile both exist. There is no way for them to be confused by a machine since they’re on opposite sides of a hyphen, but very new users to the notation could potentially get confused. Another option could be “X” for discard, but that might not be as intuitive as “D”. I think that an English speaker is likely to be able to look at the notation an existing game using this v1.0 draft I’ve proposed, and infer the entire standard without reading the documentation at all.
  2. It leans heavily on English language for color names and letters from “Discard” and “Draw” even though the game originates from Germany. If “Black” and “Schwartz” shared a letter that made sense to represent the color in both languages (“a” isn’t very representative of either word, but it’s the only letter they share) then I would have chosen that instead of “K”.

Compressed Version

For a quick reminder or pasting into code, here is a compressed version of the standard:
[CARD COLOR LETTER][CARD NUMBER OR “H” FOR HANDSHAKE]<[D FOR DISCARD]>-[COLOR LETTER TO DRAW FROM OR “D” FOR DRAW-PILE] (“K” for “Black” expedition)

Let me know in the comments if you have any thoughts about this notation and also feel free to link to your project if you’ve implemented this notation in a product of your own!

Proposal for “Tatsu” standard notation

Tatsu logo
The tabletop designer of Hive, has just begun releasing his newest game, Tatsu. It’s out in the UK and getting great critical acclaim, and is currently rolling out in mainland Europe and the United States during the summer of 2016.

Since it’s such a new game, there isn’t a standardized notation for moves yet… so in this post I’m proposing the one that we used to make a Steam version of Tatsu.

If anyone has a chance to use this notation for anything, I’d appreciate feedback so that I know if there are any major problems with it.

TATSU STANDARD NOTATION SPEC v1.0 – Sean Colombo 20160131

Space Numbering

The spaces on the board are numbered such that each pair is a single space with a capacity of two pieces.

The notation for spaces is that they are each assigned a single number around the circle. The spaces start with number “1” as the space by the Black mat with the number “1” on it. The other spaces will be numbered increasing clockwise all the way to space “24” which will be to the left of space “1”.

This has the side-effect that all of the spaces near the Black mat will have a number drawn on them which match their actual Space Number, but no other spaces on the board will.

Dragon Notation

The different types of board pieces will be represented by a single letter. The letters will be “V” for Vine Dragons, “W” for Water Dragons, and “F” for Fire Dragons.

Move Notation (Ply Notation)

There are two types of moves in Tatsu: Entering the Arena from the Mat, and moving a Dragon from one Space to another.

All moves have a hyphen separating them. The notation is as follows:

  • Entrance into the Arena: [Dragon Letter]-[Number of space where it will enter]. Examples: “V-2” when Black moves a Vine Dragon into its middle space. “F-14” when White moves a Fire Dragon into its middle space.
  • Movement on the Arena: [Source space number]-[destination space number]. Examples “2-5” to move the aforementioned Vine Dragon 3 spaces clockwise, or “14-11” to move the aforementioned Fire Dragon 3 spaces counter-clockwise (anti-clockwise). Due to the rules that the outer piece must be moved if you have two Dragons on the same space, there are no ambiguities that require more information than just the source-space and destination space.

Turn Notation

When a player rolls the dice, they have anywhere from 0 to 2 moves to make. If they are able to Enter the Arena or to Move on the Arena, they must do so. However, they are not always able to move given the configuration of the board and the results of the dice. When a turn cannot be made, the move will be represented as “0-0”. Each turn will consist of two plies next to each other. For example, an entire turn by black could be:

V-2 2-5

While it is impossible to have a pass, then a move, in certain configurations the player may run out of abilities to take their second turn and a pass would show up like this:

V-2 0-0

In rare cases, a player may be completely unable to move:

0-0 0-0

Game Notation

It’s not really necessary to define this at this point, but I envision that it could be numbered pairs, like this:

  • 1. 2-5 5-7
  • 2. 14-11 11-9

Unlike many Chess notations where each pair represents both players taking their turns, in the Tatsu notation each number would represent one player taking a turn. As the game is an eternal cycle rather than a back-and-forth game, this seems appropriate.

How Hive sold more in Year 2 than Year 1 despite the “Indiepocalypse”

As a small two-person team, we were able to sell more units of Hive in it’s second year after launch than we did in the first – despite living through the “Indiepocalypse”.

This experience flies right in the face of the conventional wisdom of the game sales cycle being mainly one giant launch spike followed by a death-taper-to-zero afterwards.

Hive unit sales year-over-year

In this post, I’ll endeavor to tell you what we did to achieve this, and to share some other insights we learned along the way.

Background

BlueLine Game Studios is a small indie game studio – specializing in making digital versions of amazing board games. The studio consists of Sean Colombo (author of this post) and Geoff Brown. We’re anywhere from 1 to 2 people fulltime; usually one fulltime, one part-time. Years ago, we built a successful web startup together, then 4 years ago we finally became professional game devs with BlueLine Game Studios. After first releasing Hive on Xbox 360, we pivoted and after many more months released Hive as our first title on Steam, just over 2 years ago. Since that time, we’ve also released Khet 2.0, Reversi, and Simply Chess. All of our Steam titles run on Windows, Mac, and Linux.

Requirements

Not all game developers will be able to benefit from what we’ve learned, but a very large number will.

In this flooded market caused by the Indiepocalypse, there are many great games that don’t get nearly as famous as they should (eg: Escape Goat 2, Cannon Brawl, Duskers, Rymdkapsel). Making a great game is not sufficient for it to be successful, but it should be seen as mandatory. Fortunately, we knew when we licensed Hive that the gameplay of the board game was amazing. Our digital conversion seems to be satisfactory to the community and it is currently recommended by 95% of Steam users that review it. There are plenty of articles about how to make good games, and that’s way outside the scope of this article, so we’ll just take it as a pre-requisite.

Additionally, the gameplay should be something that has a lot of replay value (which is a large part of why boardgames are our strategy) and they need not to be “zeitgeisty”. For example, this article wouldn’t be very useful for a game about the 2016 American Presidential election, because it’s unlikely it will perform well in 2017.

What We Learned!

Each paragraph is a different lesson. Subsume their knowledge!

Our single biggest learning was that the only marketing endeavor which drove significant sales spikes was Steam visibility. Significant visibility on Steam comes from several types of events: Early Access Launch, Full Launch, DLC Launches, Mac/Linux Launches, Seasonal Sales (Summer & Holiday), and manually created 1-2 week Discounts.

Another huge lesson was that almost all revenue comes from sales-spikes, there are a decent number of ways to cause these spikes, and we must continue to cause them in order to survive. As mentioned before, this contradicts the common assumption that games are very launch-centric and shows that Steam games can be run almost as a service. It’s important to note that if we’d just given up on Hive after launch, our data would have looked like everyone else’s showing that launch was important and the harsh realities of the Indiepocalypse crushed us after that. If we’d stopped investing in Hive after it’s launch month, we’d have missed out on about 70% of the sales we’ve made so-far.

Solid games definitely don’t have to die right after launch. Here’s a chart showing all of the various spikes we were able to cause, and their affect on the running-total:
Hive units sold per day vs running total - first 2 years
None of those spikes happened automatically. Every one of them was directly caused by things that we did. Later in the article there is a section which explains the various things we did to cause spikes.

We didn’t do any paid advertising for Hive. We tried several different paid advertisement locations for another game and none of them ended up having a positive return-on-investment as far as we could tell.

I gave talks at the East Coast Game Conference in 2013 (“Turn Based AI“) and 2015 (“Cryptography for Game Developers”) and we also had a booth there in 2015. I also spoke on a couple of panels at PAX Dev 2013. This was a blast and I met a lot of really interesting people that I’ve learned a ton from. This didn’t lead to direct sales spikes, but I still think it was extremely valuable. Sharing what we’ve learned also felt really fulfilling. Hopefully we’ll be doing more conferences, talks, and panels in the future.

We almost entirely neglected press. This could be due to our background in consumer-websites, but after a very short period of posting links to the game on obvious places (facebook, twitter, etc.), we got sucked right back into bug-fixing and new features rather than contacting more press like we should have. We did get a little bit of press from indie reviewers & let’s players. The only press we got from a big outlet was IndieGamerChick re-reviewing the Steam version (she’d reviewed the Xbox 360 version earlier). None of the press that we got caused a visible spike in our sales-data, but we think that’s largely because we didn’t do very much work to get press. The various reviews & videos are all greatly appreciated and they probably lead to some new fans trickling in over-time but just didn’t cause a visible, instant spike in sales so they’re challenging to measure. Learning how to get press is an area where I think we really need to improve.

What were we able to do to cause spikes?

DLC: Meh

The board game Hive has 3 expansion pieces. They each significantly change gameplay and took a while to make, so after we launched the game, we got into creating & releasing those as soon as we could finish them. Each launch resulted in more visibility on Steam and drove sales of the main game. Steam users all seem to hate DLC in a different way – I’m fairly convinced that there is no way to do DLC that users agree is the right way… they will always be mad – so it’s always stressful. We lucked out since we’re making a digital version of a board game that exists in stores (and has actual expansions) so we did a direct analog to that sales system. This means we had a system that at least we feel good about. Judging by the sales of the expansion pieces, I think people understood our reasoning overall, but if we got a lot of flack for this system, be aware that you’re likely going to get a lot of complaints for your DLC regardless of what you do. It’s just not something that gives players warm-fuzzies and we’re in an industry where warm-fuzzies and happiness are a large part of what we’re selling. Another caveat is that there is a bit of a limit on how many you can do, so this isn’t a good strategy for getting a bunch of spikes over the long-term. We did the 3 expansions and that seems to be the limit of where it makes sense for our game (unless Gen42 Games releases new expansions for Hive in the future).

Mac & Linux Launches

After Hive, we’ve been launching all games with Mac & Linux from the get-go, but originally we didn’t have the porting figured out. For Hive, we launched the Mac and Linux versions about four months after the full-launch of the game.

An interesting side-effect was that the game showed up in “New Releases” on Mac and Linux pages of Steam. This, coupled with a 20% off sale on the game (which matched our initial launch-week price), seemed to drive a fairly big week-long spike for the games. The launch-spike for games overall is usually much shorter, but as of summer 2014, it was taking a week for a game to get knocked off of the New Releases list on Mac. That list is probably also flooded by now (but less than for Windows), so your mileage may vary.
Hive sales on Steam - units and revenue - by platform
As you can see from the charts, not only did they cause spikes, but they ended up being an additional source of revenue equal to almost 12% of our total revenue for the 2 year period since Hive’s initial Early Access launch.

Discounts

Running sales gives you more visibility on Steam, and honestly many users have probably added your game to their wishlist and are just waiting for a sale.

Sale prices have become the norm on Steam. Due to international exchange rates and grouping of items into two-packs or Complete Packs (bundling the game with the expansions), it’s a bit tricky to calculate a perfect representation of how cheaply things sell. However, in the United States a single copy of Hive is $9.99 and a two-pack ends up being ~$7.99 per copy, and if you get a single Complete pack it can get as high as $15.99 per copy. If you take all of the copies we sold and divide by the total revenue from these games (this excludes revenue from DLC that was sold separately), it ends up at at an average of $3.62 per copy.

Since we have so many different starting-prices, perhaps a more useful way to grasp the exact impact of sales prices is to see a histogram of volume of sales at given percentages of full-price. For example, this chart is showing that we sold about twice as many units at 75%-off (25% of full price) as we did at full-price. The chart doesn’t show the total revenue, so since 100% is 4x the revenue-per-copy that 25% is, then we still made about twice as much money on full-priced copies as heavily discounted copies.
Number of Sales at each percentage-of-full-price

Side-note: There are sites like SteamDb that track the price-histories for games, so don’t do any crazy 90% off experiments early on in your game’s lifespan or users might hold off on buying your game, expecting it to go to that level again. If people expect to pay 20% off full-price at launch, then slowly get discounts over the following months then users will be motivated to buy now if they can. Hopefully they will only wait if they’re price-sensitive enough that a few months are worth a few percent to them (we’ve all been there). This ends up working out pretty well for everyone.

Updates, updates, updates!

When updates are announced in conjunction with sales, they lead to more units. We often announced an update in the middle of a sale-week and saw a second peak. This also indicates to potential buyers that you’re not just discounting an old, stale game, but are just selling a game that’s both mature and still growing. Even when we’re not doing sales, we do a quite a large amount of updates.

Bundles? Not yet!

Since this post is referring to how we sold more units in Year 2 than Year 1, many people might have assumed that the answer was one word: Bundles. In fact, we haven’t done any bundles for Hive yet. Hive is a premium niche product and we’d love to see it in an appropriate bundle (such as a Humble Digital Tabletop Bundle) some day. In the meantime, all of our growth was done just based on selling it on Steam, the Humble Store, and via the Humble Widget. Pay-what-you-want for Hive sounds pretty enticing, huh? 😉

We put some of our other games in non-Humble Bundles a while ago. The revenue was negligible but dumping thousands of copies did a good job of beefing up the online communities so that there were always more people online.

Other Big Learnings

These weren’t directly related to sales spikes, but we learned a thing or two…

Be responsive to the community!

I read every forum post for all of our games (even Simply Chess which took me about 10 hours per day right after launch) and respond to almost all of them. Being present (so that users know you care) and doing bug-fixes and forward development based on their suggestions ensures that you have a product that’s actually going in the direction the market wants and it lets users know that you actually care about them even after you have their money.

As a caveat: I’ve never tried ignoring the community so I really don’t have a scientific comparison to say that this has been more useful than doing the opposite (being a jerk and completely ignoring your users). Anecdotally though: several of our Steam Reviews have mentioned that part of what they liked about our games is that we’re so responsive in the forums.

Full Launch > Early Access

Our Full Launch sold a lot more units than our Early Access launch which is the opposite of what I’ve been reading in a lot of places. This might be due to our lack of press – I’ve read that press view your Early Access launch as your only launch because your game is “old news” by the time it comes out. Another possibility is that this could just be because our Early Access launch was over 2 years ago and things may have changed since then. Your mileage may vary.

Keep grinding to build the online community

If your game has multiplayer, build the online community. If a player goes on and there is nobody to play against, they quickly abandon the lobby assuming “nobody is ever online” and then another person may come in 5 minutes later and think the same thing. This means that there is a specific tipping point where there is always someone to play with, which keeps both of those players online longer and when the next person comes in, they also see an active community and stay online playing. It is a really long arduous journey for an indie, but keep iterating until you pass that tipping point. We spent months of development on this before we started to see it pay off. We reworked the Online Game Menu Screen, wrote our own group-chat, etc. but it wasn’t until we released Asynchronous games (which took a lot of work) that the online community really started thriving.

Other Small Factors

  • We’re using the same engine for all of our games which subsidizes bug-fixing and new features.
  • If you have a thriving online community, it seems to raise the daily sales at full-price. Even though it’s not a ton of sales, 5 sales per day for a month (between spikes) is much better than 1 sale per day for that month. It adds up.
  • We’re fairly niche since we make turn based games. If you’re not niche, you might get better results from PR and even more viral growth from an online community.
  • Some sources of error in the data: these stats were just from Steam. This ignores the Humble Store and Humble Widget sales just for simplicity of pre-processing all of the data to make these charts. Also, we mainly used units-sold rather than total revenue. The raw revenue was pretty flat Y1 vs Y2. There are a lot of different currencies so I presented the data as percentages-of-full-price in some spots. The actual amount earned per unit is much less clean due to the variance in currency conversions.
  • Change is constant. The Indiepocalypse isn’t some big one-time shift in the industry. If you read The Ultimate History of Video Games (great book), you’ll realize that change is extremely normal in game development. The entire market has been changing every couple of years since its creation. The fact that Steam has been a solid place to market your game for many years in a row is actually a fairly impressive amount of stability. Get used to change and continually run tests to figure out what the current state of the world is.
  • I’m so bad at marketing that somehow, I’ve gone this whole post without asking you to buy Hive! Please buy our game: Hive on Steam.

Conclusion

The indie dev market is (and has likely always been) crazy. Making a good game is absolutely mandatory for success but despite what you read, it is never enough on its own.

By running your own experiments, tracking metrics, and learning from the experiences of other developers (eg: reading what I’ve written above!) you can survive despite the challenges of the day.

It’s always the Indiepocalypse. The Indiepocalypse never changes.

“Simply Chess” – now free to play on Steam!

Our fourth game, “Simply Chess” is now available on Steam!
Chess on Steam

It’s just what it sounds like: Chess! We wanted to stick to the basics, but to provide a ton of play modes: local multiplayer, pass-n-play, 100 Levels of AI powered by the Stockfish engine, online play, and async play (correspondence chess) w/Steam Notifications. We are also striving to make it widely accessible, so we’ve released on Windows, Mac, and Linux simultaneously and we support keyboard/mouse/gamepad interchangeably at any time.

We launched it just less than a week ago and were immediately surprised by the amount of traffic it got. In one day, it had doubled the number of downloads that our previous best-selling game has gotten in 1.5 years!

With this army of 10’s of thousands of testers, the community was able to find a ton of bugs and feature-improvements so we’ve been pushing a bunch of updates nonstop! Steam handles the upgrade-process so new versions only require downloading about as many bytes as you download when you hit a website… so we’re releasing quite often.

The way this game works: all features are totally free! After you’ve played a couple of games, you’ll get a 7 second cross-promotion before each new match. The cross-promotions are just ads for one of the other three digital tabletop games that BlueLine has released on Steam. If you’d rather not see the cross-promotions or want to send us a couple of bucks as a thank-you for the game: you can upgrade to Premium for $4.99 and you won’t see the cross promotion again.

Also, as a special thanks to our loyal fans… if you own all three of our other games, we will be updating the game so that you don’t see ads (basically: you get Premium for free).

We just want to say thank you to everyone who’s been playing & who has given us feedback on the game! It’s been a wild week and we’re expecting to cross the 100,000 downloads mark today!

Introducing “BlueZebra” a GPL command-line Reversi AI

blueZebra
Today, we’re releasing some Open Source freeware! As part of creating our next game (Reversi for PC, Mac, and Linux on Steam), we wanted to make use of some of the great AI that’s already been written for Reversi over the years.

One of the most respected Reversi AI programs is WZebra by Gunnar Andersson. WZebra hasn’t been updated since around 2005, but it was released under GPL and included a command-line tool for solving the end of a bunch of games (scrZebra) as well as some other analysis tasks. What it didn’t include, was a way to access WZebra’s AI via command-line to easily get the best move for a specific board layout. That’s exactly what BlueZebra is: BlueLine’s customization to allow command-line access to WZebra AI.

Here is a zip of the project: download BlueZebra*. Since it is based on a GPL project, it is itself released under a GPL license. To make changes, use the Visual Studio solution and recompile. We also updated the Makefile to work with modern systems (it was made when everything was 32 bit) and made the Makefile compile on OSX, not just Linux.

Run “blueZebra.exe ?” to get help info for each of the parameters, but to give you an idea of how you can pass everything in & get back a move from the AI, here is example usage:

prompt> blueZebra.exe -cli -b 1 -e 0 -line 2 -scores 0 -depth 24 26 28 -board -----X------X------XOX-----OO-----OXO------X-------------------- -turn O
c6

“c6” is the move that the AI returned for White to play.

*: hashes of the zip file…
md5: af7733545b7bb21aed9399c5f3f08f6d
sha1: 30b7d0379f318c6974460d066944a11fcc3215fe

Our next game: Reversi!

Reversi
About a month and a half ago, we released Khet 2.0 on Steam. After a few updates (fixes & new features) then last weeks release of the ‘Eye of Horus’ Beam Splitter expansion… we’re spending part of our time on our next game: Reversi!

It will be on Steam and we plan to support PC, Mac, and Linux at launch & we currently have no plans for any DLC.

If you’ve been following along on our @BlueLineGames twitter account, this might not be a huge surprise to you. We were tweeting a picture of our passing unit-tests in mid-summer. Yup, while we were ironing out the details of the licensing on Khet, we did about a month of work on Reversi! So we’re off to a great head-start.

As an indie-dev, releasing a game in the middle of the holiday season seems a bit quixotic, so we’re not going to rush it. In parallel, we’ll be doing upgrades to add new features to our engine – which will benefit Reversi as well as our already-released games Hive and Khet 2.0.

Some may be wondering about why we’re going with the classic “Reversi” name rather than the more modern licensed name. Honestly, we like the newer name & the community that’s been built around it. We spent months chasing after that license and we want to (and think we may) get it one day. In the meantime… Reversi! 🙂

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:
 

Announcing our next game: Khet 2.0 for Xbox 360!

Khet 2.0
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.