03_ Tic-Tac-Toe: Subsumption Architecture

FALL / 2021
For Cognitive Technologies
With Drijon Hasani, Kieran Adams, Asa Valentine
Role Designing the subsumption architecture and implementing the physical robot


Check the code to the robot︎︎︎

           Tic-Tac-Toe is a solved game; there exists an optimal strategy that forces a tie between the two players. Many complex tic-tac-toe playing AIs exist out there, from algorithms that simulate all game states to machine learning based algorithms.

However, we wanted to re-tackle this problem with an unconventional approach that w have not seen attempted before by adopting subsumption architecture, a design principle that rejects traditional AI’s top-down representations. We created a Tic-Tac-Toe playing AI using a bottom-up approach with incredibly simplistic hierarchal layers of action commands.

The algorithm does not know the rules of the game, nor know the over a quarter of a million game-states, nor rely on any complex rulebook of strategies to guide its behavior. Instead, it simply reacts to an opponent’s move by attempting to execute the same five hierarchal actions each time. Win if it can. If not, block oppo- nent if it can. If not, play center position if it can... and so on.

The robot stood undefeated throughout the presentation.

We first represented the board space as data, then provided the robot with basic position relationships (ie. corners, center, adjacent, two in a row, three in a row) and permissible actions (select and play). Lastly, we implemented the subsumption architecture I designed.

The board consists of nine LEDs and two buttons. Each LED represents a playable position. Xs are represented by fast blinking LEDs, Os by stably on LEDs. Human players use one button to change position selection, the other to play on selected position. Computer plays immediately after human. Below is a game example. Xs & Os are marked for clarity. A video of the game can be found here.