← All Projects

Tic-Tac-Toe Box AI

Tic-Tac-Toe Box AI

Challenge: “Film a three-minute educational video of yourself explaining a STEM topic you're passionate about.” - Science Ambassador Scholarship.

Overview

In the project “Tic-Tac-Toe Box AI”, I built a mechanical computer out of boxes that through reinforcement learns to play Tic-Tac-Toe for my application to the Science Ambassador Scholarship. You can watch the video here.

Motivation: The project provides a unique and tangible way to simplify the concepts of reinforcement learning. Users of artificial intelligence need to understand how models work to effectively collaborate, troubleshoot, and trust computational programs. Reinforcement learning and other techniques within AI are often too complex and abstract to visualize, whereas physical models could provide a tactile approach to gaining insight into how these fundamental algorithms work!

Quick stats: 121 boxes, 150+ hours spent creating, 2897 lines of code, 7 new friends made!

Level up: It is incredible how quickly you can learn new skills when you jump in and start creating. I learned about laser cutting, 3D printing, human-computer interaction, engineering, web application design, serial communications, electronics, soldering, and much more. In between classes, I ran in and out of the maker space to work on the project piece by piece. Here is the process behind it!

The project consists of three parts: the mechanical computer, the game board, and a web app for logging.

The MENACE build
  • Mechanical Computer: Built out of 121 boxes representing the different board states of Tic-Tac-Toe. Every box contains differently colored beads representing the various available squares in each given scenario. Through training, the boxes tend to only contain the beads corresponding to the best moves.
  • Game Board: Integrated with an Arduino and push buttons to detect when you place an X or an O on the board. Communicates with the web app.
  • Web Application for Logging: To avoid manually tracking the bead counts in each box, I built a website to automatically keep track of and highlight each move.

From Idea to Final Product

Idea: I got inspired by the website http://dataphys.org/list/ which includes a history of data visualizations throughout time. In the age of nanotechnology, it is easy to get detached from the inner workings of devices and the algorithms that influence society. I wanted to create a physical representation of Artificial Intelligence.

History: In 1961, AI researcher Donald Michie built a mechanical computer out of matchboxes that could learn to play noughts and crosses (tic-tac-toe). It was called MENACE, for Matchbox Educable Noughts and Crosses Engine. In modern times, Matthew Scroggs built his version of MENACE with resources for anyone who wanted to engage in a similar endeavor. I wanted to take this type of project to the next level and use it for educational purposes!

The Mechanical Computer

first idea

The first idea sketch.

The game contains 304 board positions if you discard rotations and mirror flips. However, I simplified it to 121 positions by limiting each player to three moves each. I manually created 121 illustrator files with each game move that I laser-cut in acrylic.

board states

A sample from the 121 illustrator files.

I then created the illustrator files for the box towers. In total, I ended up with three towers with dimensions 2x6, 3x12, 4x18 + 1 separate box for the first move.

scaffholding

The first box scaffolding (center) and a 3D-printed box (right, in white). I quickly realized that 3D-printing every box would take forever…

The box towers consisted of the scaffolding and the individual boxes. I used precision laser cutting to cut the Duron wood pieces. The laser cutting process is quick and allows for rapid prototyping. The website makercase provides a fantastic starting point for creating drawers and open boxes. I modified this template to include a way to open each box.

lasercutting

Trying to optimize every inch of the Duron piece!

After plenty of experimentation with different sizes and box designs, I was able to laser-cut all my pieces. Then it was off to gluing all the pieces together! I used my one-hour lunch break each Monday, Wednesday, and Friday to glue 10-15 boxes at a time.

boxes

My best time for gluing one box was 52 seconds.

Spending time in the making space was incredibly fun - it is such an innovative atmosphere and I got to meet many incredible people working on their own projects.

making

Thank you to the shop assistants in the maker spaces for keeping everyone safe and providing invaluable feedback!

The Game Board

I experimented with different designs but concluded that push buttons were the most robust option. The board is laser cut out of Duron, while the pieces are made out of birch plywood. I drilled holes in each square and glued on pushbuttons that I soldered to an Arduino board.

board

The making of the game board.

wires

Lot's of wires and practice for soldering!

The Web Application

Because I wanted to collect statistics from the learning process but now have to manually keep track of the bead counts, I programmed a web app that would automatically do this for me. I connected it to the game board and built a complete digital representation of the box towers (yes, that meant once again manually typing all the 121 board states…). As a bonus, I could highlight the current box making it easier to find on the real mechanical computer. In total, I ended up writing 2897 lines of code from scratch, trying at the same time to apply the concepts of functional decomposition from my programming course!

web app

The web app logs each game and contains a digital twin of the mechanical computer.

web app in action

An animation of the web app in action.

Conclusion

boxes

In conclusion, this project has been an incredible journey. I am more excited than ever to share my passion for technology in a new and engaging way. I have also learned the power of creating something from scratch with my own hands. My next ambition is to use this as an educational tool at local high schools or around campus to make AI and reinforcement learning more accessible!

Thank you so much for reading!

boxes

Acknowledgements

I want to express my gratitude to Olivia Tomassetti, who gave creative feedback and ideas during the build progress and taught me how to solder. I would also like to thank my brother for finding the best box gluing strategy and my friends for encouraging me throughout the process. Moreover, I would like to thank all the inspiring people in the maker space who I loved getting to know. Finally, I would like to thank the Science Ambassador Scholarship for inspiring me to create this project, from which I have learned so much.

References

Floridi, L., & Sanders, J. W. (2004). On the Morality of Artificial Agents. Minds and Machines, 14(3), 349–379. https://doi.org/10.1023/B:MIND.0000035461.63578.9d

Gardner, M. (1962). Mathematical Games: How to build a game-learning machine and then teach it to play and win. Scientific American. Available at https://www.scientificamerican.com/article/mathematical-games-1962-03/

Hausknecht, M., & Stone, P. (2017). Deep Recurrent Q-Learning for Partially Observable MDPs (arXiv:1507.06527). arXiv. http://arxiv.org/abs/1507.06527

Kaelbling, L. P., Littman, M. L., & Moore, A. W. (1996). Reinforcement Learning: A Survey. Journal of Artificial Intelligence Research, 4, 237–285. https://doi.org/10.1613/jair.301

List of Physical Visualizations and Related Artifacts. (n.d.). Retrieved October 18 , 2023, from http://dataphys.org/list/

Michie, D. (1963). Experiments on the Mechanization of Game-Learning Part I. Characterization of the Model and its parameters. The Computer Journal, 6(3), 232–236. https://doi.org/10.1093/comjnl/6.3.232

Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., & Riedmiller, M. (2013). Playing Atari with Deep Reinforcement Learning.

mscroggs.co.uk Blog: Building MENACEs for other games. (n.d.). Retrieved September 7, 2023, from https://www.mscroggs.co.uk/blog/52

Professor Donald Michie. (2007, July 9). The Telegraph. https://www.telegraph.co.uk/news/obituaries/1556846/Professor-Donald-Michie.html

Scroggs, M. (n.d.-a). Build your own MENACE. Retrieved September 7, 2023, from https://mscroggs.co.uk/blog/94

Scroggs, M. (n.d.-b). MENACE. Retrieved September 7, 2023, from https://mscroggs.co.uk/blog/19

Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., van den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., & Hassabis, D. (2016). Mastering the game of Go with deep neural networks and tree search. Nature, 529(7587), Article 7587. https://doi.org/10.1038/nature16961

The Royal Institution (Director). (2020, February 10). Christmas Lectures 2019: How to Bend the Rules - Hannah Fry. https://www.youtube.com/watch?v=TtisQ9yZ2zo

van Hasselt, H., Guez, A., & Silver, D. (2015). Deep Reinforcement Learning with Double Q-learning (arXiv:1509.06461). arXiv. http://arxiv.org/abs/1509.06461