Tic-tac-toe is a nearly perfect time-wasting game as it’s quick to play, easy to learn, and has a very small set of rules, which makes it ideal for implementation on a microcontroller. Michael Klements wanted to take it a step further and add a simple AI that can effectively play against a human opponent while never losing a single match. The device he came up with is a shield that fits onto an Arduino Mega and features a grid of LEDs and corresponding tactile buttons. A player can then choose from one of three different modes: easy AI, expert AI, or a human opponent. 

If an AI mode is chosen and it goes first, the first spot on the board where a piece goes is the corner, which eliminates several orders of magnitude of choices, thus speeding up the time it takes to run through the recursive minimax algorithm. The easy mode will perform a couple of random moves in the beginning to give the player a chance to win. 

You can read more about how Michael created this AI tic-tac-toe device in his well-written blog post here and see it in action below.