Detecting loops with the Beamsplitter

We recently released Khet 2.0 for PC, Mac and Linux and have been working on the Beamsplitter expansion piece (among other things).

The Beamsplitter piece lets the laser pass through and also reflects it at a 90-degree angle. This changes the concept of the laser from being a linked-list to being a directed-graph. This makes most of the code become recursive, but also leads to an interesting challenge: easily detecting infinite-loops.

We could use a heavy-handed approach of storing a record of every beamsplitter and every side that a laser comes out of, then comparing it to results of any new beamsplitter hits, to see if anything changed. However, it turns out there are some generalities that may let us do it more gracefully.
eye of horus beamsplitter diagram
In this diagram, the laser source at “A” gets reflected to “B” and also travels through to “C” while the direction “D” is not affected yet. Regardless of the rotation of the beamsplitter, if we follow this key, the following rules will always be true if a laser hits the Beamsplitter again on any of the 4 surfaces:

  • “A”: If “A” is hit (which I’m not sure is possible since I think it would require a loop to already have ended), then nothing changes. The inbound laser can be considered a “closed loop” ending.
  • “B” & “C”: If either of these spots are hit, then there will be a new exit-point at “D”. Any future hits to this same Beamsplitter will be “closed loops” regardless of where they hit.
  • “D”: Hitting here has used up the last junction and is a “closed loop”. Any future hits to this same Beamsplitter will be “closed loops” regardless of where they hit.

Also convenient is that we only need to detect loops at Beamsplitters. This will let some laser-segments overlap each other occasionally, but they will only overlap once before hitting a Beamsplitter, so there is no danger of infinite-looping as long as this logic is enforced at each Beamsplitter.

That was just a random tech rambling. Hope it was interesting! 🙂

EDIT: Incidentally, I finished writing the laser logic and the brute-force approach ended up being really simple & with no real overhead so I just went that way. Oh well, I was proud of myself while I thought it mattered. ;).

Move Over Piracy… Theft Comes to Indies!

Yesterday we launched our second game: Khet 2.0 on Steam. As is usual with a Steam launch, we get a ton of requests (a couple dozen a day, probably) emailed to us for free “Review” copies for press.

Red Handed

I often had a sense that some of these people were maybe not legit, but life is busy so who has the time to really look into it? Well, my curiosity finally got the better of me. When a handful of requests in a row all seemed suspicious, I decided to compare the “from” email address to what was on YouTube and I sent a response to the real youtuber’s address. He confirmed that he was being impersonated.
2014-10-02_1144

So what?

Part of why I didn’t look into this before is that I figured the worst that could happen is some pirate (who probably wasn’t going to buy my game) would get my game for free. Turns out though, it’s a little more nefarious. Other devs have tracked these keys down to G2A* which is basically a market for illegally reselling keys**. So now people are taking keys for free and selling them to real gamers who are willing to pay money for your game. Developer makes a game… gamer pays for game… thief gets the money (and G2A gets a cut).

Therefore, if you don’t check into people at all before sending keys you’ll probably lose a few sales (not a huge deal) but you’ll be giving money to both the sketchy G2A as well as encouraging the theft to go on which takes money from away from other devs (and many of those devs can’t afford to lose a few sales).

Developer makes a game… gamer pays for game… thief gets the money (and G2A gets a cut).

Simple fix

Fortunately, once aware of the scam, this is super-easy to fix.

      Are you a gamer? Don’t buy from G2A.
      Are you a dev? Don’t “reply” to send the keys via email… instead go to the youtube page of the person and send it in a YouTube message (or to their listed email address).
      Are you a YouTuber? Add you email address to your about page (youtube protects it from spambots) and be prepared to get some keys in your YouTube messages instead of email sometimes. Sorry for any inconvenience (I know inboxes can be a mess)!
      Do you care? Spread the word. If gamers stop accidentally buying stolen keys & devs mainly send the keys out via YouTube, the thieves will move on to easier targets than indie games.

Boom, solved. It just takes a small process fix to avoid the issue entirely. Gamers are not your enemies. YouTubers are not your enemies. You don’t have to start being tightfisted with keys or anything like that. We just gave away over 100 games via @IndieGamerChick about a week ago for #GamesMatter and that went great!

Anywho… sorry for the slightly negative post. We love gamers! We love game devs! We love YouTubers & Let’s Players (and give them full permission to monetize videos about our games)!

Now back to regularly scheduled gaming! 😀
– Sean

*: Disclosure: I know the author of the Polygon post in real life.
**: This statement has not been evaluated by the FDA. G2A claims it is legitimate because you could have an unredeemed Steam key for some legit reason (maybe if it was a gift?) but it is a widely held belief that most keys on there are either taken from bundles (which is against the terms of service of most bundles & of Steam), soaked up from contests, or stolen in the fashion described in this article.

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!

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!

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

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

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

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

C# – KonamiCode.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Audio;
using Microsoft.Xna.Framework.Content;
using Microsoft.Xna.Framework.GamerServices;
using Microsoft.Xna.Framework.Graphics;
using Microsoft.Xna.Framework.Input;
#if WINDOWS_PHONE
using Microsoft.Xna.Framework.Input.Touch;
#endif
using Microsoft.Xna.Framework.Media;

namespace KonamiCodeXna
{

    // A delegate type that represents the code has either been entered right or wrong
    public delegate void CodeEnteredEventHandler(object sender, KonamiCodeEventArgs e);

    public class KonamiCodeEventArgs : EventArgs
    {
        /// <summary>
        /// The player index that entered the code.
        /// WARNING: This can be null (eg: on WP7, or when the code was entered using the keyboard).
        /// </summary>
        public PlayerIndex? PlayerIndex { get; private set; }

        public KonamiCodeEventArgs(PlayerIndex? playerIndex)
            :base()
        {
            this.PlayerIndex = playerIndex;
        }
    }

    /// <summary>
    /// Class for easily using the KonamiCode in XNA apps (Windows, Windows Phone, and Xbox).
    /// 
    /// Originally written for Windows Phone 7 by Charles N. Cox.
    /// Expanded to work on Xbox and Windows by Sean Colombo.
    /// </summary>
    public class KonamiCode
    {
        public event CodeEnteredEventHandler CodeEnteredRight;
        public event CodeEnteredEventHandler CodeEnteredWrong;

        // Track the progress by each PlayerIndex. If playerIndex is irrelevant, just key off of "null" instead.
        private Dictionary<PlayerIndex, int> numCorrectByPlayerIndex;
        private int numCorrectKeyboard;

        // To be able to tell when buttons are pressed/released, these vars will keep track of state from previous tick.
        private Dictionary<PlayerIndex, GamePadState> previousGamePadStateByPlayerIndex;
        private KeyboardState previousKeyState;

        public KonamiCode()
        {
            numCorrectKeyboard = 0;
            numCorrectByPlayerIndex = new Dictionary<PlayerIndex, int>();
            previousGamePadStateByPlayerIndex = new Dictionary<PlayerIndex, GamePadState>();
        }

#if WINDOWS_PHONE
        enum DirType
        {
            DirTypeUp,
            DirTypeDown,
            DirTypeLeft,
            DirTypeRight
        };

        private DirType[] correctSequence = new DirType[8] {
            DirType.DirTypeUp,
            DirType.DirTypeUp,
            DirType.DirTypeDown,
            DirType.DirTypeDown,
            DirType.DirTypeLeft,
            DirType.DirTypeRight,
            DirType.DirTypeLeft,
            DirType.DirTypeRight };

        public void checkGesture(GestureSample gs)
        {
            bool rightCode = true;
 
            switch(correctSequence[numCorrect])
            {
                case DirType.DirTypeUp:
                    if (gs.Delta.Y > 0 || (Math.Abs(gs.Delta.Y) < Math.Abs(gs.Delta.X)))
                        rightCode = false;
                    break;
                case DirType.DirTypeDown:
                    if (gs.Delta.Y < 0 || (Math.Abs(gs.Delta.Y) < Math.Abs(gs.Delta.X)))
                         rightCode = false;
                    break;
                case DirType.DirTypeRight:
                    if (gs.Delta.X < 0 || (Math.Abs(gs.Delta.Y) > Math.Abs(gs.Delta.X)))
                        rightCode = false;
                    break;
                case DirType.DirTypeLeft:
                    if (gs.Delta.X > 0 || (Math.Abs(gs.Delta.Y) > Math.Abs(gs.Delta.X)))
                        rightCode = false;
                    break;
            }

            this.RecordSuccessByPlayerIndex(rightCode, null);
        }
#else
        private Keys[] correctKeySequence = new Keys[]{ // for the keyboard
            Keys.Up,
            Keys.Up,
            Keys.Down,
            Keys.Down,
            Keys.Left,
            Keys.Right,
            Keys.Left,
            Keys.Right,
            Keys.B,
            Keys.A
        };

        private Buttons[] correctButtonSequence = new Buttons[]{ // for gamepads
            Buttons.DPadUp,
            Buttons.DPadUp,
            Buttons.DPadDown,
            Buttons.DPadDown,
            Buttons.DPadLeft,
            Buttons.DPadRight,
            Buttons.DPadLeft,
            Buttons.DPadRight,
            Buttons.B,
            Buttons.A,
        };
        private List<Buttons> buttonsToCheck; // which buttons to check for being up/down each tick. For performance reasons, we'll only check the buttons that are part of the sequence.

        /// <summary>
        /// Should be called once each update loop when listening for the code.
        /// </summary>
        public void checkKeyboard()
        {
            bool rightCode = false;
            KeyboardState keyboardState = Keyboard.GetState();

            // Only evaluate the state if SOMETHING was pressed (we only care about the sequence, not that they're IMMEDIATELY after each other).
            if (WasAnyKeyPressed(keyboardState))
            {
                if (WasKeyPressed(correctKeySequence[numCorrectKeyboard], keyboardState))
                {
                    rightCode = true;
                }

                this.RecordSuccessByPlayerIndex(rightCode, null);
            }

            previousKeyState = keyboardState;
        }

        /// <summary>
        /// Should be called once each update loop when listening for the code, for each playerINdex
        /// that is being listened to (will track their progress separately so that their keypresses
        /// don't interfere with each other).
        /// </summary>
        /// <param name="playerIndex"></param>
        public void checkPlayerIndex(PlayerIndex playerIndex)
        {
            bool rightCode = false;

            int numCorrectSoFar = 0; // the number-correct-so-far corresponds to the index in the sequence that should be expected
            if (numCorrectByPlayerIndex.ContainsKey(playerIndex))
            {
                numCorrectSoFar = numCorrectByPlayerIndex[playerIndex];
            }

            // This is called once per tick, then re-used by the other functions below.
            GamePadState currentGamePadState = GamePad.GetState(playerIndex);

            // Only evaluate the state if SOMETHING was pressed (we only care about the sequence, not that they're IMMEDIATELY after each other).
            if (IsAnyButtonPressed(playerIndex, currentGamePadState))
            {
                if (WasButtonPressed(correctButtonSequence[numCorrectSoFar], playerIndex, currentGamePadState))
                {
                    rightCode = true;
                }

                this.RecordSuccessByPlayerIndex(rightCode, playerIndex);
            }

            previousGamePadStateByPlayerIndex[playerIndex] = currentGamePadState;
        }

        /// <summary>
        /// Returns true if any key is currently pressed down, false otherwise.
        /// 
        /// If a user presses a key and holds it down, this method will return
        /// true every time it's called while that key is held down.
        /// </summary>
        /// <returns></returns>
        //public bool IsAnyKeyDown(KeyboardState keyboardState)
        //{
        //    Keys[] keys = keyboardState.GetPressedKeys();

        //    // Some systems return an empty array when nothing is pressed, some return one item containing Keys.None
        //    bool nothingPressed = ((keys.Length == 0) || ((keys.Length == 1) && (keys[0] == Keys.None)));
        //    return (!nothingPressed);
        //}

        /// <summary>
        /// Returns true if any key was JUST pressed, false otherwise.
        /// 
        /// This means that if a key is pressed and held down, the first
        /// tick will return true and subsequent ticks will return false even while
        /// the key is still being held down.
        /// </summary>
        /// <returns></returns>
        public bool WasAnyKeyPressed(KeyboardState keyboardState)
        {
            Keys[] keys = keyboardState.GetPressedKeys();

            bool somethingNewIsPressed = false;

            // Some systems return an empty array when nothing is pressed, some return one item containing Keys.None
            bool nothingPressed = ((keys.Length == 0) || ((keys.Length == 1) && (keys[0] == Keys.None)));
            if (!nothingPressed)
            {
                IEnumerable<Keys> newlyPressed = keys.Except(previousKeyState.GetPressedKeys()); // ignore keys that were already down on the previous tick.
                somethingNewIsPressed = (newlyPressed.Count() > 0);
            }

            return somethingNewIsPressed;
        }

        private bool WasKeyPressed(Keys keyToCheck, KeyboardState keyboardState)
        {
            return (previousKeyState.IsKeyUp(keyToCheck) && keyboardState.IsKeyDown(keyToCheck));
        }

        /// <summary>
        /// Returns true if any of the buttons RELEVANT TO THE KONAMI CODE were pressed. For performance, does not
        /// check all buttons each tick, just checks the buttons that appear in the correctButtonSequence.
        /// </summary>
        /// <param name="playerIndex"></param>
        /// <param name="currentGamePadState"></param>
        /// <returns></returns>
        private bool IsAnyButtonPressed(PlayerIndex playerIndex, GamePadState currentGamePadState)
        {
            bool somethingPressed = false;

            if (buttonsToCheck == null)
            {
                // Not all users will have my (Sean's) Set<> class, so abuse a Dictionary instead.
                Dictionary<Buttons, bool> buttonSet = new Dictionary<Buttons, bool>();
                foreach (Buttons button in correctButtonSequence)
                {
                    buttonSet[button] = false; // the bool is trash basically. this is just a cheap way to implement a set.
                }
                buttonsToCheck = buttonSet.Keys.ToList();
            }

            foreach (Buttons button in buttonsToCheck)
            {
                somethingPressed = (somethingPressed || WasButtonPressed(button, playerIndex, currentGamePadState));

                if (somethingPressed)
                {
                    break;
                }
            }

            return somethingPressed;
        }

        private bool WasButtonPressed(Buttons button, PlayerIndex playerIndex, GamePadState currentGamePadState)
        {
            bool wasPressed;
            if(previousGamePadStateByPlayerIndex.ContainsKey(playerIndex)){
                wasPressed = (previousGamePadStateByPlayerIndex[playerIndex].IsButtonUp(button) && currentGamePadState.IsButtonDown(button));
            } else {
                wasPressed = currentGamePadState.IsButtonDown(button);
            }
            return wasPressed;
        }
#endif

        /// <summary>
        /// Records a successful/unsuccessful keypress by PlayerIndex. In cases where the
        /// PlayerIndex is irrelevant (often, on WP7 there is only one player), then null
        /// can be used.
        /// 
        /// NOTE: This method is typically called from other helpers such as checkGesture
        /// and checkGamePadHelper instead of being called directly.
        /// </summary>
        /// <param name="rightCode"></param>
        /// <param name="playerIndex"></param>
        public void RecordSuccessByPlayerIndex(bool rightCode, PlayerIndex? playerIndex)
        {
            if (rightCode)
            {
                // PlayerIndex is null for keyboard and non-null for game pads.
                if (playerIndex == null)
                {
                    numCorrectKeyboard++;
                    if(numCorrectKeyboard >= correctKeySequence.Length)
                    {
                        //reset the code, fire the event
                        numCorrectKeyboard = 0;
                        KonamiCodeEventArgs args = new KonamiCodeEventArgs(playerIndex);
                        CodeEnteredRight.Invoke(this, args);
                    }
                }
                else
                {
                    if (numCorrectByPlayerIndex.ContainsKey((PlayerIndex)playerIndex))
                    {
                        numCorrectByPlayerIndex[(PlayerIndex)playerIndex]++;
                    }
                    else
                    {
                        numCorrectByPlayerIndex[(PlayerIndex)playerIndex] = 1;
                    }

                    if (numCorrectByPlayerIndex[(PlayerIndex)playerIndex] >= correctButtonSequence.Length)
                    {
                        //reset the code, fire the event
                        numCorrectByPlayerIndex[(PlayerIndex)playerIndex] = 0;
                        KonamiCodeEventArgs args = new KonamiCodeEventArgs(playerIndex);
                        CodeEnteredRight.Invoke(this, args);
                    }
                }
            }
            else
            {
                //wrong type, reset the count, send event
                if (playerIndex == null)
                {
                    numCorrectKeyboard = 0;
                }
                else
                {
                    numCorrectByPlayerIndex[(PlayerIndex)playerIndex] = 0;
                }
                KonamiCodeEventArgs args = new KonamiCodeEventArgs(playerIndex);
                CodeEnteredWrong.Invoke(this, args);
            }
        }

    }
}

To Use the Class

It’s really just three things:

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

Getting it Into a Default Project

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

Game1

//**Start Code For This Sample - REPLACE YOUR GAME1 CONSTRUCTOR WITH THIS
KonamiCode konami = new KonamiCode();
Color clearColor = Color.CornflowerBlue;
 
public Game1()
{
    graphics = new GraphicsDeviceManager(this);
    Content.RootDirectory = "Content";
 
    // Frame rate is 30 fps by default for Windows Phone.
    TargetElapsedTime = TimeSpan.FromTicks(333333);
 
    konami.CodeEnteredRight += new CodeEnteredEventHandler(konami_CodeEnteredRight);
    konami.CodeEnteredWrong += new CodeEnteredEventHandler(konami_CodeEnteredWrong);
 
    TouchPanel.EnabledGestures = GestureType.Flick;
 
}
 
void konami_CodeEnteredWrong(object sender, EventArgs e)
{
    clearColor = Color.Tomato;
}
 
void konami_CodeEnteredRight(object sender, EventArgs e)
{
    clearColor = Color.MediumSeaGreen;
}
//**End Code For This Sample

Update

//**Start Code For This Sample - REPLACE YOUR UPDATE LOOP WITH THIS
protected override void Update(GameTime gameTime)
{
    // Allows the game to exit
    if (GamePad.GetState(PlayerIndex.One).Buttons.Back == ButtonState.Pressed)
        this.Exit();
 
    #region Konami code updating
#if WINDOWS_PHONE
	while (TouchPanel.IsGestureAvailable)
	{
		GestureSample gs = TouchPanel.ReadGesture();
		konamiCode.checkGesture(gs);
	}
#else // WINDOWS || XBOX
	// Need to check the code for each game pad that's in-use.
	foreach (PlayerIndex playerIndex in new PlayerIndex[] { PlayerIndex.One, PlayerIndex.Two, PlayerIndex.Three, PlayerIndex.Four })
	{
		if (GamePad.GetState(playerIndex).IsConnected)
		{
			konamiCode.checkPlayerIndex(playerIndex);
		}
	}

	// Then check the code for the keyboard (if there is one, there will be just one so it's checked separately, not per-player).
	konamiCode.checkKeyboard();
#endif
	#endregion

    base.Update(gameTime);
}
//**End Code For This Sample

Draw

//**Start Code For This Sample - REPLACE YOUR DRAW METHOD WITH THIS
protected override void Draw(GameTime gameTime)
{
    GraphicsDevice.Clear(clearColor);
 
    // TODO: Add your drawing code here
 
    base.Draw(gameTime);
}
//**End Code For This Sample

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

Games using this Konami code class

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

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.

Drawing a hollow rectangle border in XNA 4.0

For some reason, there wasn’t much info on this. For the sake of making this faster for others, I’ll post code for a quick way to draw a rectangular outline in XNA 4.0. If you’re planning on doing a ton of 2D drawing, you might be better served by this tutorial on drawing polygons. I’d actually recommend defining some geometry classes if you go that far though.

The basic trick to drawing shapes is to make a single-pixel texture which is White, which you can then mix with other colors and display in solid shapes.

// At the top of your class:
Texture2D pixel;

// Somewhere in your LoadContent() method:
pixel = new Texture2D(GameBase.GraphicsDevice, 1, 1, false, SurfaceFormat.Color);
pixel.SetData(new[] { Color.White }); // so that we can draw whatever color we want on top of it

Then in your Draw() method do something like:

spriteBatch.Begin();

// Create any rectangle you want. Here we'll use the TitleSafeArea for fun.
Rectangle titleSafeRectangle = GraphicsDevice.Viewport.TitleSafeArea;

// Call our method (also defined in this blog-post)
DrawBorder(titleSafeRectangle, 5, Color.Red);

spriteBatch.End();

And the actual method that does the drawing:

        /// <summary>
        /// Will draw a border (hollow rectangle) of the given 'thicknessOfBorder' (in pixels)
        /// of the specified color.
        ///
        /// By Sean Colombo, from http://bluelinegamestudios.com/blog
        /// </summary>
        /// <param name="rectangleToDraw"></param>
        /// <param name="thicknessOfBorder"></param>
        private void DrawBorder(Rectangle rectangleToDraw, int thicknessOfBorder, Color borderColor)
        {
            // Draw top line
            spriteBatch.Draw(pixel, new Rectangle(rectangleToDraw.X, rectangleToDraw.Y, rectangleToDraw.Width, thicknessOfBorder), borderColor);
            
            // Draw left line
            spriteBatch.Draw(pixel, new Rectangle(rectangleToDraw.X, rectangleToDraw.Y, thicknessOfBorder, rectangleToDraw.Height), borderColor);

            // Draw right line
            spriteBatch.Draw(pixel, new Rectangle((rectangleToDraw.X + rectangleToDraw.Width - thicknessOfBorder),
                                            rectangleToDraw.Y,
                                            thicknessOfBorder,
                                            rectangleToDraw.Height), borderColor);
            // Draw bottom line
            spriteBatch.Draw(pixel, new Rectangle(rectangleToDraw.X,
                                            rectangleToDraw.Y + rectangleToDraw.Height - thicknessOfBorder,
                                            rectangleToDraw.Width,
                                            thicknessOfBorder), borderColor);
        }

Hope that saves someone some time! 🙂

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.