A Good New-Fashioned Programming Throwdown

Nick Winter -

We just concluded our most challenging developer arena yet, the one-month Criss-Cross tournament. In this post, I recap the challenge, crown the champions, showcase the winning solutions, and tease you with our next multiplayer level.

In Criss-Cross, humans and ogres compete to build paths across a chasm by bidding on bridge tiles. Unlike the all-out war of our last tournament, Greed, Criss-Cross was not based in combat. However, there was plenty of turmoil to be found in the cold efficiency with which players outbid one another. You just need that one tile–but your opponent knows it. They’ve modeled your bidding strategy, and now they’re going to outbid you by a single coin!

Each match is best-three-out-of-five, and we used Bayesian Battle to calculate player skill rankings after running an exhaustive 65,000 matches on a 32-core c3.8xlarge machine. Here are the results.

The Winners

The #1 human champion is the unstoppable mdz (Matt Winter), who only lost to himself and to the #2 ogre matthewd! In second is Nafaya, with nino48 in third.

The #1 ogre champion is the devious HighSea (Michael Polyak), who only lost to himself, to mdz, and to Nafaya. He was trailed by matthewd and the Clojure champion Driphter.

The top five players on each board won interviews at top Silicon Valley tech companies. We’ve posted the full rankings here, where you can also spectate more matches.

Matt Winter (mdz)

Behold! The top human player, mdz, is a new father from Georgia whose “quick and dirty” solution spanned 1418 lines of code. He wrote a detailed writeup of his solution and posted the code on GitHub: https://github.com/mdzw/criss-cross/

Below is a summary of his solution.

Tile Scoring

This portion is very much a mathematical undertaking. A basic outline:

  1. Determine the set of all tiles that lie on any shortest path (using heavily specialized Dijkstra)
  2. Count how many unique paths use each tile (Depth-First Search on graph structure built in step 1)
  3. Divide path count by the total number of paths.
  4. Repeat steps 1-3 from the opponent’s perspective.

The number of paths which use a tile is a great metric for its value. By buying the most-used tile, I keep my options open for the number of potential paths I can pursue.

Normalizing (Step 3) is useful because if any tile has a score of 1.0, that means that every shortest-length path goes through that tile. So if my opponent buys that tile, I will have to buy at least 2 tiles to make up for it. This is helpful when determining how much to bid.

Running Dijkstra on a completely empty board is both computationally expensive and completely unnecessary. If the following conditional that defines “early game” is met, then I run my “Quick and Dirty” (QnD) evaluator:

if((myTiles < 2 && opponentTiles < 4) || (myTiles < 5 && opponentTiles < 3))

QnD values tiles that:

  • Make progress toward a finished path (anything in the gray boxes in the example below. AKA the bow-tie of reachability)
  • Are not currently in the “shadow” of an opponent’s blocking tiles (e.g. next to 3 in a column)
  • Are adjacent to one or two of my tiles
  • Are close to being in line (horizontally for humans) with my tiles
  • Partially block an opponent path

With these attributes combined, QnD quickly/cheaply picks tiles very similar to those chosen by the more expensive Path-Based solution, especially in early turns. However, because QND does not actually search for paths, it’s possible that the opponent could have blocked me. This is mostly mitigated because I only run it very early in the game, before most blocks could develop. If a block does occur then it will hopefully be overcome in later turns when I am calculating paths.

Bid Calculation

This is pretty ad hoc and dirty, with a lot of conditionals based on specific game states. I think I had two powerful advantages:

  • Identifying the game states that were different or important in some way, and figuring out what to do in those situations
  • Recording my opponent's bidding behavior (split into buckets based on the above game states), and using that to predict what they will do when a similar game state arises in the future (across multiple rounds). This let me automatically adapt my bids to many strategies, without explicitly identifying those strategies:
    • I would save gold buying cheap tiles against opponents who bid super low early on
    • I would trade tile purchases against opponents who bid middle values
    • I would wait for opponents who bid way too high to exhaust their funds, and then clean up for cheap later (while easily outbidding them to prevent any winning tile purchases)

Some other bidding intelligence highlights:

  • Keep track of the tie results, so we know if we’ll win a tie (save 1 gold every so often :)
  • Never bid more than opponent's remaining gold + tiebreaker
  • If there's a tile that would win you the game, bid everything on it
  • If there's a tile that would give your opponent the win, make sure you bid on something with opGold + tiebreaker (It doesn't have to be that endgame tile, just something to prevent them from winning the bid that turn)
  • This one can be tricky -- if we have detected that the opponent doesn't bid everything on the endgame, we can try to save some money while still preventing the loss.
  • If I’m low on gold or the opponent is out of gold, don’t use the opponent’s perspective (step 4 of Tile Scoring) to make bidding decisions. Basically, save gold for tiles I actually need
  • If we don’t think the opponent is interested in any tile that’s up for bidding, lower the bid (opponent's interest is based on the Path-Based tile scoring from their perspective)
  • If the opponent always bids some certain value, and that value is something low, then just outbid them
  • Always try to leave enough gold to spend 1 on each remaining needed tile – this doesn’t seem to help (if we’re that low on gold, op will probably outbid us all day), but it’s a last ditch effort

Here is a strategy that I added on the last day, and it turned out to be pretty important against other top players (looking at you, HighSea):

  • If the opponent is two tiles away from a finished path, try pretty hard to outbid them. This is important because if they become one tile away from a finished path, to stay alive you have to outbid all of their remaining gold every time a winning tile comes up. This exhausts funds pretty quickly. The specifics of “try pretty hard” are left as an exercise to the reader, but it’s based on how much gold I have left, how many tiles I need to buy, and how much gold my opponent has left.

Final Thoughts

I would say that everyone in the top 20 on both ladders had a hand in shaping my final solution, so I offer my sincerest thanks to all of my competitors. Overall, this experience has been extremely stimulating and a lot of fun. I would definitely do it again, but maybe not for the next month or two. My wife and I have been caring for a newborn this whole time, and I think I prefer to only have one reason to be up at 3am for a while :)

Read the full write-up for more on mdz's strategy.

Michael Polyak (HighSea)

Introducing the ogre champion from Canada! Michael Polyak was also the #3 human champion in our Greed tournament. This time he took the top spot with a cool 845-line solution.

Michael’s Approach

I was very excited to see another CodeCombat tournament after participating in the Greed challenge earlier and I really enjoyed it having not done any game-related development in years.

Off the bat the problem seemed like it would require a more computationally intensive solution, since I would need to traverse a 7x7 grid with an additional set of up to 7 available tiles to take into account at each turn of the game.

My first step was to implement a route calculation system based on the A* algorithm with a bias towards picking tiles that are already owned by me or are adjacent to those that I own, or tiles that could possibly block my opponent in his direction of travel.

I calculated routes for my team, and my opponent's team at each turn and fed them in to the next step of my solution, which is determining the most optimal tile to bid on.

When determining a tile to bid on, I focused on the shortest possible route that I could make, as well as taking into account my opponent's routes that I calculated previously–so that if I could bid on a tile that would be both beneficial to him and myself, I would bid on it over picking any other tile. I also made bidding on a tile that could potentially block my opponent's route be of higher priority, paying special attention to the second before last tile and trying to steal it to prevent him from completing his most optimal route.

By extension how useful a tile was to my opponent and myself determined how much gold I was willing to bid. Which brings us to the last part of my solution: calculating the least amount of gold required to bid at each turn of the game.

I used the same tile determination model from the previous step and calculated it for my opponent's team. This gave me an upper bound of gold that I would use as a limit when placing a bid for a tile. In a sense I made an assumption that my model would provide the optimal tile to bid on for either team and used that information to adjust the maximum amount of gold I should bid for a tile at each turn.

In addition, I also performed a standard deviation calculation of my opponent's previous bids to see if his bidding strategy was consistent, this information allowed me to literally one up his previous bid in the next turn's bid amount for those tiles that were not of high priority.

Keeping my bids as low as possible is what allowed me come up ahead in the later stages of the game where most routes where established and only a few tiles remained on the board for the taking.

What did HighSea think of mdz’s strategy?

I knew mdz had some element of future prediction for determining bid amount, and I suspected he was keeping that one extra piece of gold for tie-breaks!

In order to win consistently against his solution, I would have to introduce my own future prediction to the bid calculation, and I'm glad that my current solution has an element of randomness to it when deciding how much to bid on the initial tile based on the bidding of my opponent in the previous round; the intent was to confuse any pattern analysis of my bidding strategy.

The Next Arena Level

Think that a programming tournament sounds fun, but don’t want to write a thousand lines of code to compete?

Want epic battle and heroic tactics without melting your CPU?

Want to, uh, get over your fear of heights?

Then start playtesting Sky Span, our next arena level!

We aren’t starting the tournament for this one yet, as the level is subject to change. In particular, with the official launch of Sky Span, we are hoping to introduce our real-time PVP layer on top of the asynchronous combat that you know and love, as well as an entirely new hero-based game mode. You’ll equip your hero with items you’ve earned in the game to grant her special abilities and programming powers. But you can help us get the balance and abilities worked out right now, as well as getting a leg up for when the Sky Span tournament starts later this fall. Check it out!