Hey GD.net community! We're excited to have joined and be whipping up a first blog post to announce release of our Dots and Boxes game. A little background about us, gametable.org. We're a non-revenue side project game site created by a few friends honing their game development skills. We don't show any ads and don't have any intention to in the near future. Most of our games will likely be parallels of classic real world games or modernizations of simple old school computer games.

Now on to Tabletop Dots and Boxes- This is one of our favorite childhood games. When we learned that we'd all played it on pen and paper as kids, we figured it would be fun to take it digital. We kept the UI and SFX relatively simple, stealing the overall look-and-feel from our previous two games. 

Where we stretched our legs with this game is artificial intelligence. We poked around on the web and found a number of existing dots and boxes games, the best of which offered play for up to four players. We thought this was a nice touch and decided to tackle it ourselves. 4 player pass and play was easy, but creating an intelligent AI that wasn't overly paranoid and ran in a relatively small amount of time was difficult. We tried a number of classic approaches using minimax, then negamax, then negascout. All three suffered from acute paranoia. After way too much time hunting we found an extension of minimax, Hypermax, that solved the issue. To our surprise this algorithm was employed in a 90's NES game called "Spot." Spot is based on the 1990's 7-UP mascot and is 2+ player connect four style game. Playing it is on our todo list. Hypermax is so similar to minimax with ab pruning that we had a little trouble implementing at first. We kept making assumptions about how it works. When we eventually landed on a working version of the AI, the solution was stunningly simple and elegant. If you want to talk about it, shoot us a message. 

Even with Hypermax, getting the AI to hit deep evaluation depths with limited evaluation time was still a challenge. The game state search space for even a small dots and boxes board is massive. Toss 4 players into the mix instead of 2 and the evaluation overhead just goes up. The first thing we did to overcome this was move all of our AI code out to a web worker to take the load off the rendering thread. Next, we spent weeks identifying intelligent move generation, ordering, and culling rules to dramatically reduce the search space. If you give the game a go on a larger board size with 4 players you will still see it take a moment to generate an AI move when game is about 1/2 complete, but its well within tolerable levels for a player. 

We're super stoked about the AI we came up with for Dots and Boxes. Its a heavily studied problem and a number of excellent AIs exist but not many that run in real time and pose any real challenge. We believe ours does and haven't seen a better one out there yet. Give it a shot and let us know what you think.

Looking forward, we'd eventually like to add multiplayer support, but that is a ways down the line. More new games first! What classic games should we build next?

Cheers,

Gametable.org