IronHack Deep Dive: Iron TicTacToe

By Iron | January 16, 2014 |
This past week we crowned a winner for our Iron Holiday Hack. It was a one week virtual hackathon where participants built apps that were useful, beautiful, informative, or just plain cool. 

David Jones built an awesome little project called Iron TicTacToe that hit the mark on the goals of the challenge. The application was very simple but focused on a complex algorithmic concept of game trees, a directed graph whose nodes are positions in a game and whose edges are moves.

 
 
"David was able to take a complex theory and create a very simple application. He integrated multiple API's and focused on a concept that is used in many different applications"

– Chad Arimura, CEO, Iron.io


blank
Courtesy of Wikipedia

 

About the Winning Application

So, how does a game tree work? Take a look at the image on the right and you should get a good sense. In fact, Tic-Tac-Toe is often used to teach game tree search algorithms in undergraduate computer science classes.

David took this exercise one step further and harmoniously implemented all 3 Iron products, as well as SendGrid, to build his application.

 

"My goal was to solve an interesting problem that takes advantage of parallel execution, with a large number of IronWorkers performing tasks that are small pieces of a larger puzzle. The IronCache is used to keep track of intermediate results and IronMQ are used to keep track of tasks that will be executed later."

 

So, each product was tasked with taking on a different role – similar to service oriented architecture. But let's dig into the code a little more:

 

"The parallel algorithm has 2 main parts. The first part expands the game tree. The second part passes the results from finished games (at the leaves) back up the tree towards the root. In the middle of the game tree search, some IronWorkers are busy expanding one part of the game tree while other IronWorkers are busy passing results up another part of the game tree. 

The algorithm finishes when all the results are reported back to the root, and an email is sent with the final solution."

 

More Information on the App

There's more to the project than what we can list here but you can find a lot more information about it on the HackerLeague project page.

Iron TicTacToe


 if you're interested in expanding on David's project, here are three suggestions he's provided:

  1. Taking into account the symmetries of tic-tac-toe boards, a large number of tic-tac-toe boards are actually "equivalent". By being a little smarter about how tic-tac-toe boards are represented in the IronCache, the size of the game tree (and the amount of work) could be significantly reduced.
  2. In serial game tree search, a popular optimization is Alpha-Beta pruning. It would be interesting to implement parallel Alpha-Beta pruning, to further reduce the amount of work.
  3. Tic-tac-toe is a simple game, and useful when the goal is understanding the game tree search algorithm. Once the algorithm is implemented, it would be interesting to generalize it to more complex games, such as checkers, chess, or go.

 

About the FIrst Prize Winner

blankDavid Jones is a resident of Ontario, Canada and when not hacking he’s keeping busy as a computational expert, entrepreneur, visual neuroscientist, and algorithmic artist.

 
 

 

Thank You to All

Again, thanks to all participants, New Relic, SendGrid, GitHub, and Twilio! It was truly a great hackathon and we wish everyone a Hacky New Year!!

Posted in Customer Success and tagged ,
blank

About Iron

Leave a Comment





This site uses Akismet to reduce spam. Learn how your comment data is processed.