Today, we’re releasing some Open Source freeware! As part of creating our next game (Reversi for PC, Mac, and Linux on Steam), we wanted to make use of some of the great AI that’s already been written for Reversi over the years.
One of the most respected Reversi AI programs is WZebra by Gunnar Andersson. WZebra hasn’t been updated since around 2005, but it was released under GPL and included a command-line tool for solving the end of a bunch of games (scrZebra) as well as some other analysis tasks. What it didn’t include, was a way to access WZebra’s AI via command-line to easily get the best move for a specific board layout. That’s exactly what BlueZebra is: BlueLine’s customization to allow command-line access to WZebra AI.
Here is a zip of the project: download BlueZebra*. Since it is based on a GPL project, it is itself released under a GPL license. To make changes, use the Visual Studio solution and recompile. We also updated the Makefile to work with modern systems (it was made when everything was 32 bit) and made the Makefile compile on OSX, not just Linux.
Run “blueZebra.exe ?” to get help info for each of the parameters, but to give you an idea of how you can pass everything in & get back a move from the AI, here is example usage:
prompt> blueZebra.exe -cli -b 1 -e 0 -line 2 -scores 0 -depth 24 26 28 -board -----X------X------XOX-----OO-----OXO------X-------------------- -turn O
“c6″ is the move that the AI returned for White to play.
*: hashes of the zip file…
I often hear the question of why there aren’t more board games on a certain platform. The short overarching answer is just that digital board games are a niche-market, so big game companies aren’t often willing to take the risk of making them.
However, I think there are some hints as to where board games will start showing up in the near future.
I’ll be working with the assumption that other than a few outliers (Monopoly, Risk, etc.) that are made by EA or some other huge publisher, most digital versions of board games will likely be made by indies.
This is a complicated one, but I think that we’re not going to see many new board games on consoles in the near future. The old-gen consoles were a mixed-bag for independent developers. Xbox 360 was really the only one that indies could easily get into. BlueLine could probably get into all of them at our current size, but it excludes any first-timers. Additionally, after Microsoft announced that they were no longer supporting XNA, the amount of games that sold on Xbox Live Indie Games (their deeply-hidden indie channel) dropped off a cliff.
What about the current generation? Sony has gone out and recruited a bunch of indies to build games for the PS4… but I doubt they’ll continue doing that much longer after launch – they’re flat-out funding games and that’s a big financial investment. Xbox is again trying to be accessible to indies with their “ID@Xbox” program (which we’ve been accepted to), but there are two major things holding back board games from Xbox One*. First: it’s expensive. Unlike other indie-friendly locations where the startup costs are around typically a couple of hundred dollars, a very lean Xbox One indie game runs upward of $5,000. Secondly, even in 2014, Xbox 360 still has about twice as many sales as Xbox One. A market with high costs and low sales isn’t great for niche games. It’ll be a while before the install-base of new consoles grows enough that a bunch of board games start popping up on there.
PC, Mac, Linux
There are a decent number of board-games coming to PC (especially on Steam) over the past year or so. I think more will continue to show up, just slowly. We released Hive and Khet 2.0 this year, and just our two-man team still hasn’t been bumped off the list of 10 Newest Releases tagged with “Board Game”. It’s entirely possible that our next game, Reversi will bump Hive off of the most-recent list, if no new board games come out in January or February.
PC, Mac, and Linux are probably the best platform for selling digital versions of board games at the moment.
Smart phones are a great form-factor for many board games, and a bunch of games came out over the year since they became popular. However, many have had a rough time with sales in recent months/years. Most digital board games are made by fairly small devs: we survive on the Steam store’s visibility and we’d have a really rough time in mobile because you need to be on the “top downloads” list to get any traction there. Board games are usually too niche for that to happen organically and it’s too expensive to buy the number of downloads needed to fake it. This “faking it” is the current modus operandi for most mobile games. They buy huge amounts of downloads (via ads in other games) and hope that it generates enough of a following to get them to the Top Downloads list where they get to see if they’ll actually get traction. That’s usually not a great strategy for board games!
Board gamers often lament the lack of titles on tablets – which seem like the most ideal medium for digital board games. However, I think that’ll happen even more slowly. Even though tablets are a fantastic device for playing games, the market is currently (unfortunately) just an afterthought. The games on there now are mostly because it’s easy to go to tablets from a mobile game. However, the market for tablets themselves are really small (around $3.6b compared to about$20b for PC). The reason market-size matters is just that it’s an indicator of how many games you can sell if you have great exposure. Tablets are a just a very small market at the moment, and aren’t expected to catch up to PC for about another 5 years.
We’ll get our games on tablets eventually… but it’s going to take a while. Hopefully not more than a year or so!
It’s really hard to monetize a straightforward board game in HTML5 at the moment. If you saw Goko (who got the license to Dominion) and thought that they would ever be able to earn enough to support their big dev team & pay back all that venture capital… you probably weren’t paying attention to the margins in this industry. Nobody has made it work correctly yet. The only board game sites that are currently surviving seem to be those that don’t make any money & don’t pay any royalties. Since most of those are hobbies, you can probably expect a handful of very basic implementations to continue to come out… just not with paid licenses.
What I’m most excited for in the future is cross-platform online play. It’s super time-consuming to get it working (in part because you literally need to create the game multiple times**) but it should be a lot of fun and make it easier to find online games with other people instead of having an already-niche community silo’ed across several devices, as is currently the case with Hive which currently has different 5 different online communities.
Do you know of any digital board games coming out in the near future? Let us know in the comments below.
*: There are actually three, but one of them is technical and it’s covered by an NDA so I can’t talk about it until it’s fixed.
**: I realize that Unity/MonoGame/etc. take a ton of work away from porting, but if you want the game experience to be really good, it should be designed once for consoles (with gamepads) then another way for PC/Mac/Linux (to allow gamepad and/or mouse/keyboard) and have another – probably significantly different – interface for touch/drag devices with unreliable screen resolutions.
About a month and a half ago, we released Khet 2.0 on Steam. After a few updates (fixes & new features) then last weeks release of the ‘Eye of Horus’ Beam Splitter expansion… we’re spending part of our time on our next game: Reversi!
It will be on Steam and we plan to support PC, Mac, and Linux at launch & we currently have no plans for any DLC.
If you’ve been following along on our @BlueLineGames twitter account, this might not be a huge surprise to you. We were tweeting a picture of our passing unit-tests in mid-summer. Yup, while we were ironing out the details of the licensing on Khet, we did about a month of work on Reversi! So we’re off to a great head-start.
As an indie-dev, releasing a game in the middle of the holiday season seems a bit quixotic, so we’re not going to rush it. In parallel, we’ll be doing upgrades to add new features to our engine – which will benefit Reversi as well as our already-released games Hive and Khet 2.0.
Some may be wondering about why we’re going with the classic “Reversi” name rather than the more modern licensed name. Honestly, we like the newer name & the community that’s been built around it. We spent months chasing after that license and we want to (and think we may) get it one day. In the meantime… Reversi!
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.
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. ;).
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.
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.
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).
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!
*: 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.
Our second major release, “Khet 2.0” is now live on Steam! Buy it once and play it for PC, Mac, and Linux.
Hit that link to the Steam page to read all about the game. Here I’ll just wax poetic about our history launching it…
Before we (Sean & Geoff) started making games together, we had another startup that we worked on together. After a while we sold that company, but even back then we talked about making video games someday. We kicked around all kinds of ideas and Khet was one of the earlier ones. I think Geoff actually introduced me to the game years before, at RIT, but my memory is a bit fuzzy on when he first told me about it.
I started reading a ton of indie game blogs in 2007 to learn more. It seemed like a really brutal industry & I didn’t want to go in blindly, take one swing for the fences and then have to go back to a day-job if it wasn’t a hit. Four years later when BlueLine couldn’t be postponed any longer, my devious plot to take gaming by storm was based around creating a number of digital versions of award-winning board games. We had two games in mind that we thought we could do great. This is a for-reals photo from December 2011 after Geoff and I just finished playing board games at an Eat N’ Park late one night (they’re awesome for tolerating that kind of thing):
With today’s launch, we finally managed to ship the second of those games that we were playing nearly 3 years ago and dreaming of converting to a digital version!
It’s been a long ride, and we even had a false-start. We got about half-way making Khet for Xbox 360’s indie store when Microsoft announced that it would stop supporting XNA (the language used to make those games) and sales immediately tanked on that whole marketplace. We had to shelf the game for several months as we switched gears to port Hive – and our entire board game engine – to run on PC, Mac, and Linux with Steam networking instead of Xbox LIVE. As you can imagine, it was a bit tricky getting the PC, Mac, Linux license from the game designer after not shipping on Xbox 360. We shipped today though… reputation restored!
That’s our very long backstory that’s probably mainly interesting to others devs or those thinking about starting some business (possibly gaming related) of their own.
If you have any questions, leave us a comment! We’re allowed to share most info. Now, go buy Khet 2.0 on Steam!
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.
In 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.
In 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!
Code that implements the Randomness Quotient in a Minimax engine after scoring plies.
// At this point, the Minimax engine has scored some plies
// and stored them and their scores in topLevelScoresByPly.
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.
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.
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.
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.
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.
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.
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.
*: “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.
While creating the Steam version of the popular board game Hive, it became clear that normal methods of on-screen debugging weren’t going to be in-depth enough.
Alpha-beta pruning of a small Minimax game tree.
Most AI for 2-player abstract-strategy games probably uses the tried-and-true Minimax algorithm. It works just how you’d think AI would work: you look at a tree of all of the possible board positions that you could get to (and all positions you get to from there, etc.) and score them. It can get a little more complex on top of that, but the basics are really straightforward.
While the Minimax algorithm is very general-purpose, the scoring function that you use to evaluate each position is game-specific. Debugging that scoring function (called a “heuristic evaluation function” in technical lingo) can be tricky, especially since it is very hard to see an entire game-tree at once. The small tree in the first picture above is used for teaching minimax, but is unrealistically small for real games. As an example, even a very simple game like Tic-Tac-Toe would have 3 possible moves right away (it would be 9 moves, but the board is symmetrical, so there are only 3 actual different moves). Looking at this tic-tac-toe tree, you can see that even this extremely-simple game’s tree grows quite large by the third layer.
Complexity of real Game Trees
First two plies of Tic-Tac-Toe game tree
Let’s put that in perspective compared to other games: The number of moves that can be done per level is called a “branching factor“. In the tic-tac-toe example, the branching factor at the start of the game is 3. After moving, the branching factor is 2, 5, or 5, depending on which move is made. In chess, your first move can be one of 20 possibilities: 8 pawns (each with 2 different moves) and 2 knights which have 2 possible moves each. From there, the possibilities change very quickly. Due to this variability, when discussing games we tend to focus mainly on the average branching factor. The average branching factor of tic-tac-toe is 4, for chess it’s 35, the value for Hive is currently unknown but I’d estimate it between 40 and 50.
The need for a good visualizer
For a game such as Hive, to have the AI look 3 levels deep, you’d have (50^3) = 125,000 nodes on the third level of the tree. Even if we limit the branching factor (which we do in our AI) the number of nodes is quite large. At the time of this writing one of our AI levels limits to a branching factor of 30. So (30^3) = 27,000 nodes. Needless to say, that tree won’t fit on most computer screens, so it would be hard to debug it all at once.
Therefore, we need a different way to visualize what’s going on. When debugging a heuristic evaluation function, it’s important to know the score throughout the tree, how the score worked its way up each level, and it also helps to be able to see a detailed view of how the AI scored the nodes. Keep in mind that only the scores on the bottom level of the tree are actually used to be the final scores of the path to that node. However, when we limit the branching-factor, that involves giving a preliminary score to each node and sorting all of the sibling nodes in any given level of the tree, before traversing to their children. This way, even though many moves may be skipped in a given level of the tree, the odds are high that the most important moves are being evaluated. Due to this pre-scoring, it is helpful to have detailed scoring information on every node in the tree.
In addition to seeing the nodes in a current level, it would be helpful to have pointers to which layers of the tree are maximization or minimization steps so that you don’t have to keep as much information in your head. This way, you can examine any node in the tree and tell where it got its score from (eg: it’s children) and how its score is being used by its parent-node if it has one.
Minimax AI Visualizer – click to enlarge
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.
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!