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.
– Chad Arimura, CEO, Iron.io
|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.
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.
if you’re interested in expanding on David’s project, here are three suggestions he’s provided:
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.
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.
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.
David 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.