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.

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!

// At this point, the Minimax engine has scored some plies
// and stored them and their scores in topLevelScoresByPly.
List<KeyValuePair<Ply, double>> plyPairList = topLevelScoresByPly.ToList();

// Sort the plies descending by their scores (best score at index 0).
plyPairList.Sort((x, y) => y.Value.CompareTo(x.Value));

// Apply the RandomnessQuotient so that the best-scored ply is not guaranteed to be chosen, but is still
// exponentially more likely than the second which is exponentially more likely than the third, etc.
int plyIndex = 0;
while ((plyIndex < (plyPairList.Count - 1)) && (0 == randGen.Next((int)RandomnessQuotient)))
{
    plyIndex++;
}
if (plyIndex > 0)
{
    Logger.log(LogLevel.INFO, "RANDOMNESS! Skipping the best (0th) ply and chosing ply index " + plyIndex +" instead.");
}

// Grab the ply that the Randomness Quotient has chosen.
theChosenPly = plyPairList[plyIndex].Key;
chosenPlyScore = plyPairList[plyIndex].Value;

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!

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:
 

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!

Hive screenshot

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!

DrawString() to fit text to a Rectangle in XNA

It seems that there are a number of implementations of fitting several lines of text (of a specific size) into a rectangle and wrapping them (we wrote one too), but I was surprised that SpriteBatch.DrawString() did not have a form which does the more simple task of just taking a string and making it grow/shrink to fill a rectangle.

Desired Effects

White wins!What I wanted to accomplish, was to take a (probably short) arbitrary string and make it as big as possible while fitting inside of a certain box on the screen. Specifically, I wanted to show who won in the Game Over screen for Hive.

So we specified a rectangle (shown in red around the text) and made the text change its size to fit in the box without wrapping, regardless of what that text might be.

The Code

I put this static method into a utility class I used a bunch:

        /// 
        /// Draws the given string as large as possible inside the boundaries Rectangle without going
        /// outside of it.  This is accomplished by scaling the string (since the SpriteFont has a specific
        /// size).
        /// 
        /// If the string is not a perfect match inside of the boundaries (which it would rarely be), then
        /// the string will be absolutely-centered inside of the boundaries.
        /// 
        /// 
        /// 
        /// 
        static public void DrawString(RelativeSpriteBatch spriteBatch, SpriteFont font, string strToDraw, Rectangle boundaries)
        {
            Vector2 size = font.MeasureString(strToDraw);

            float xScale = (boundaries.Width / size.X);
            float yScale = (boundaries.Height / size.Y);

            // Taking the smaller scaling value will result in the text always fitting in the boundaires.
            float scale = Math.Min(xScale, yScale);

            // Figure out the location to absolutely-center it in the boundaries rectangle.
            int strWidth = (int)Math.Round(size.X * scale);
            int strHeight = (int)Math.Round(size.Y * scale);
            Vector2 position = new Vector2();
            position.X = (((boundaries.Width - strWidth) / 2) + boundaries.X);
            position.Y = (((boundaries.Height - strHeight) / 2) + boundaries.Y);

            // A bunch of settings where we just want to use reasonable defaults.
            float rotation = 0.0f;
            Vector2 spriteOrigin = new Vector2(0, 0);
            float spriteLayer = 0.0f; // all the way in the front
            SpriteEffects spriteEffects = new SpriteEffects();

            // Draw the string to the sprite batch!
            spriteBatch.DrawString(font, strToDraw, position, Color.White, rotation, spriteOrigin, scale, spriteEffects, spriteLayer);
        } // end DrawString()

Usage looks something like this:

        RelativeSpriteBatch batch;
        SpriteFont font;
        // ...
        Rectangle outcomeBoundaries = new Rectangle(100,100,500,500); // 500x500 rectangle with top left at (100, 100)
        string outcomeString = "White always wins!"; // 1984 reference 😉
        MotiveUtil.DrawString(batch, font, outcomeString, outcomeBoundaries);

The Results

Here’s how it handles some other inputs to try to fill the rectangle as much as possible without overflowing. The red box showing the boundaries is just for demonstration, it was removed from the last picture so you could see what this is actually meant to look like.

Calculating the bounding board for Hive

THIS POST IS LONG! If you don’t care to see how the answers were calculated and just want to know the size of the 3D area into which all possible Hive games could fit, just skip to the bottom of the post for the results.

While doing secondary-research to get ready for writing AI for our Xbox version of Hive, I noticed that there wasn’t much published about the game-theory for Hive yet. That’s strange for such a popular abstract-strategy game but the game, but I guess someone has to be the first …so it’s going to be us!

This is hopefully the first post in a series which will seek to start more in-depth research on Hive by calculating some of the common measures of the complexity of Hive.

This post is going to show how we calculated the bounding-board for Hive. For a very easy comparison, chess and checkers are played on a square board that has 8 rows and 8 columns and thus has 64 spaces. Since Hive doesn’t have a static board, and instead is created by whatever undirected graph of hexagonal tiles is laid down by the players, calculating the bounding board is less straightforward.

Hive Board Size Calculation – Background

Quick background:

  • As shown in the official Hive rules, the basic game has 11 black tiles and 11 white tiles for a total of 22 tiles. Our calculations will refer to this core version of the game without modifications unless noted otherwise.
  • For the sake of calculations and nomenclature, we’ll be using the coordinate system described in our recent post about representing hexagonal boards in 2-dimensional arrays. This post will be very hard to follow if you haven’t read that.
  • Since the Hive board can be reshaped dynamically and could actually be moved end-over-end in any direction indefinitely, there is no actual physical board that you could make which could be used to contain an ongoing game. Rather, the “bounding board” we seek to calculate is the smallest area in which absolutely every legal permutation of board states could be contained. In more simple English: we could use this to make a box such that any legal game of Hive could be covered with this box. If we lift the box and another play is made, we could again cover the board with the box (even if the box is in a slightly different location).

Step 1: Building the bounding board

Now it’s time to start imagining all of the extremes. To make the examples easier to visualize, we will picture all of the white tiles on one side and all of the black tiles on the other side, with their point of contact being the queen from each side. Now we can build the board:

  1. click for fullsize version

    Because of the way our coordinate system works, if all of the tiles were layed out from (0,0) downward so that the next piece was at (0,2), then all of tiles would take up 44 rows and 1 column. This is the most extreme vertical case.
  2. If the tiles were laid out to maximize the number of columns, they would follow a zig-zag pattern from the left to the right. Since each two pieces would equal one-column, then there would be 5 columns taken up by white pieces, then the white queen and black queen would share the center column, followed by 5 more columns of black tiles. This leads to 11 columns. This can be done in 2 rows, but the next example will show that the number of rows used could also be increased.

  3. To create the most extreme diagonals, interestingly, the number of columns does not decrease at all in this coordinate system. However, when the pieces are laid out so that they are all 45-degrees off from each other, the maximum number of rows now increases to 22.

  4. If all of the extreme examples are superimposed upon each other, the minimum bounding-area becomes clear. Awesomely enough, the bounding area is a heaxagon! Patterns everywhere, man. It tickles my math-parts that the hexagon is also rotated 90-degrees from the orientation of the hexagonal tiles themselves.

Step 2: Measuring the bounding board

Since the board is not a simple square, a bit more math needs to be done in order to calculate the size of the bounding area. This will be done for the general-case of Hive in terms of the number of tiles which each color has available. This gives the bonus of making it trivial to calculate a maximum board-size for the other existing variants to Hive also.

It’s actually pretty easy to calculate the size of the bounding hexagon:

The number of tiles which each color has will be called “X”. In the default Hive game, for example, there are 11 tiles of each color. eg: X = 11
For simplicity, the hexagon can be broken into three parts. Triangle A on top, rectangle B in the middle, and triangle C on the bottom.
The number of spaces (the area) of the bounding board is just the sum of these parts. Area = A + B + C
This is a hexagon, so A is just a mirror-image of C, but the size of A and C is the same A = C, so
Area = 2A + B
The way hexagons get laid out in a triangular shape makes it so that row 1 has 1 tile, row 2 has 2 tiles, etc. Therefore, the area of A is the triangle number of X. We’ll use T(X) to represent the triangle number of X. A = T(X)
B is a rectangle on the hexagonal grid, so it contains rows whose width fluctuates between being X tiles wide and X-1 tiles wide. Therefore, we can say that B is the sum of the longer rows (which appear on the top and bottom) plus the sum of the narrower rows (of which there is one-fewer because they are neither on the top of the rectangle nor on the bottom). Area = 2T(X) + B
B = (sum of pieces in the wider rows) + (sum of pieces in the narrower rows)
The wider rows are X+1 tiles wide, and the whole rectangle is X tiles high. sum of pieces in the wider rows = ((X+1 tiles) * X rows)
The narrower rows are X tiles wide and there is one less row of these because they are bounded on each side by the wider rows. sum of pieces in the narrower rows = (X tiles * (X-1) rows)
Therefore… B = ((X+1) * X) + (X * (X-1))
Substituting that back into the area equation we get… Area = 2T(X) + ( ((X+1) * X) + (X * (X-1)) )

So that gives us the maximum area of the bottom layer of the minimum bounding board of Hive. Bottom layer, you say? Yup: we haven’t accounted for that wily Beetle yet! For the unacquainted: the Beetle is a special piece in Hive which has the ability to climb on top of other tiles and trap them.

Step 2.5: Modifying the total to take height into account – a.k.a. “What about the Beetle!?”

Since Hive pieces can be stacked, the board is technically 3D: it is a hexagonal prism. Therefore we need the total volume of the board to measure the number of board-spaces.

In Game Theory, it’s most important to create an upper-bound on the number of board spaces (cells), the state-space complexity (number of valid board configurations), and game-tree complexity (all possible moves), rather than necessarily having the exact number. While the calculations shown above for the bottom-layer of the board are exact, when taking height into account we can over-estimate a little (for simplicity) to get a general case equation for the upper-bound of all variants of Hive.

Since the total number of spaces (on all levels) needs to be calculated, the equation can be modified by multiplying the maximum size of a layer by the maximum height the board can achieve. The maximum height that the tiles can achieve will be referred to as H, so the new equation is:

Max board spaces = H * (2T(X) + ( ((X+1) * X) + (X * (X-1)) ))

Step 3: Applying the equation: the actual upper-bound of the Hive board size!

As mentioned above, this is a slight over-counting which we might explain and tweak in a later post, but this will still give us an important start if we just fill in the numbers to the general-case equation above.

Plug and chug:

General equation derived above Max board spaces = H * (2T(X) + ( ((X+1) * X) + (X * (X-1)) ))
Hive without any modifications has 11 tiles of each color. X = 11
In the basic edition of Hive, the maximum height is achieved by piling all 4 Beetles (2 from each color) on top of the same non-Beetle tile. This maximum height, therefore is 5. H = 5
The general equation for Triangle numbers is T(X) = (X * ((X+1)/2)) T(11) = (11 * ((11+1)/2))
T(11) = 66
Substitute these values in Max board spaces = 5 * ((2*66) + ( ((11+1) * 11) + (11 * (11-1)) ))
The maximum possible number of board-spaces in the smallest bounding region which could contain any legal configuration of a game of Hive with no modifications: Max board spaces in Hive = 1,870

So there you have it, there are no more than 1,870 spaces in the virtual board for Hive. For comparison, chess (which is pretty complex already) has 64 spaces.

Did you have as much fun with that as I did? 😀

Please comment if you’ve looked over my reasoning and it seems solid, if you’ve found some errors to correct, or if you have any questions.
Thanks!

Update: In the comments, Hive Champion, Randy Ingersoll, helps narrow it down to 1,290 spaces in the virtual board for Hive.

Representing a board of Hexagonal pieces in a 2-dimensional array

When working on Hive and Proximity, we’re dealing with boards of hexagons. If you look at a bunch of hexagons together, you’ll notice that they don’t sit next to each other in a way that’s a straightforward analog to square pieces like you’d find in a chess board.

In the process of working on these two games, I came up with a system of mapping all the pieces to a 2-dimensional array (rows and columns).

As shown in the diagram: if you offset every other row by half of a tile, you can address every space using normal row/column coordinates. The red arrows show a path of traversing across columns in the same row and the blue arrows show a path moving down rows in the same column. In a board with square pieces such as chess, these would both just be straight paths instead of the blue lines zig-zagging. As an exercise, can you see where the next column to the right of the blue lines would be? The second column would start at (1, 0) and would go to (1,1), then back to (1,2), then (1, 3) and so-on. Not so complicated! 🙂

The math for finding the coordinates of a space in a specific direction from a starting-space is still slightly more complex than normal square boards because the calculation is different based on which row you start in. To completely remove the necessity for doing these calculations more than once, I started using helper functions to help get a piece in any direction or to get a collection of all adjacent spaces.

As you might be aware, Proximity is Open Source, so you can check out exactly how we handled things.

To make things quicker, I’ll post a peek at some of the helper functions we used in Proximity. One quick note: this code forces all pieces to have positive-integer coordinates because the board for Proximity is a predetermined size. Since Hive is a bit more dynamic, that game doesn’t have those restrictions. Fortunately, this coordinate system still works fine with negative coordinates.

Here is the helper-code for Proximity (in javascript):
[crayon lang=”js”]
/***** DIRECTIONAL HELPER FUNCTIONS *****/
this.leftOf = function( row, col ) { return new Proximity.Coords( row, col-1 ); }
this.topOf = function( row, col ) { return new Proximity.Coords( row-2, col); } // need to jump two rows in the array to work visually
this.rightOf = function( row, col ) { return new Proximity.Coords( row, col+1); }
this.bottomOf = function( row, col ) { return new Proximity.Coords( row+2, col); }
this.topLeftOf = function( row, col ) {
var coords;
if( row % 2 == 0 ){
coords = new Proximity.Coords( row-1, col-1 );
} else {
coords = new Proximity.Coords( row-1, col );
}
return coords;
}
this.topRightOf = function( row, col ) {
var coords;
if( row % 2 == 0 ){
coords = new Proximity.Coords( row-1, col );
} else {
coords = new Proximity.Coords( row-1, col+1 );
}
return coords;
}
this.bottomLeftOf = function( row, col ) {
var coords;
if( row % 2 == 0 ){
coords = new Proximity.Coords( row+1, col-1 );
} else {
coords = new Proximity.Coords( row+1, col );
}
return coords;
}
this.bottomRightOf = function( row, col ) {
var coords;
if( row % 2 == 0 ){
coords = new Proximity.Coords( row+1, col );
} else {
coords = new Proximity.Coords( row+1, col+1 );
}
return coords;
}

/**
* Returns an array of all of the coordinates surrounding the given coordinates.
*/
this.getSurroundingCoords = function( row, col ){
var allSurroundingCoords = [
self.topLeftOf(row,col),
self.topOf(row,col),
self.topRightOf(row,col),
self.bottomRightOf(row,col),
self.bottomOf(row,col),
self.bottomLeftOf(row,col),
];

// Only return coordinates which are on the board (not off the edge).
var validSurroundingCoords = [];
for(var index in allSurroundingCoords){
var coords = allSurroundingCoords[index];
if((coords.row >= 0) && (coords.col >= 0)
&& (coords.row < self.getNumRows()) && (coords.col < self.getNumCols())){ validSurroundingCoords.push( coords ); } } return validSurroundingCoords; }; [/crayon]