As computers get more and more powerful and artificial intelligence algorithms improve, few games remain where the best humans can reliably beat their electronic counterparts. In chess this barrier was passed in 2005 with the last human win against a computer, and recently humans lost to computers at go. Simpler games like tic-tac-toe have been solved for all possible positions for a while now, so even a simple computer will always win or tie the game. But that doesn’t mean that there’s nothing left to learn about these games as [Hayden] demonstrates with this tic-tac-toe game built entirely on an FPGA.
[Hayden] is making this as part of a college course on digital design, so it really starts at first principles for working with FPGAs. It’s programmed in Verilog on a Basys 3 board, which also hosts the switches used as the game’s input and handles the VGA video output as well. The build uses state machines to keep track of the moves played on each of the squares, and another state machine to keep track of whether or not the current game has been won. If so, it highlights the winning moves in red, and stops taking further inputs until it is reset. Some more logic ties everything together along with a customized VGA driver to produce the entire gaming experience.
A game like tic-tac-toe is a great way to master the fundamentals of a system like this before moving on to more complex programs, especially on an FPGA platform that might handle a lot of the things we take for granted on more traditional computing systems, such as the video output. If you’re interested in taking more of a deep dive into the world of FPGAs, we published a primer about them a few years ago that will get you started.
‘A strange game.
The only winning move is not to play.
How about a nice game of chess?’
How about a game of thermonuclear war, instead ?
That is not a topic I was expecting when I started reading “FPGA Plays Tic-Tac-Toe”!
it’s a reference to War Games (80’s movie with Matthew Broderick)
That’s a WHOPPER
I hate seeing people waste precious electronics to do trivial projects. In my country this kind of FPGA board is available only for government and military industries. What I would give to actually play with PLD or FPGA instead of just reading ebooks about it.
How is doing a school project a “waste of precious electronics” ? The board is probably cheaper than the course textbook.
Do you not understand the concept of private property? And where the hell do you live where you can’t buy a cheap fpga/cpld? Is it illegal or something?
Even Gowin is not available in your country?
Not to sound like a jerk but it sounds like the problem may be more with your country than the use of this FPGA.
OldGuy™ here. During grade school I visited a planetarium/science center which had a huge assembly of electromechanical whatnot that could play tic-tac-toe, accompanied by clicks and rattles. Kids lined up for a chance to play the machine; of course, you couldn’t win. Amazing!
Today… after seeing this article I’m beginning to understand how my grandmother felt when she saw Apollo 11 land on the moon. She was born the year that the Wright brothers made their first flight. Some STEM advances are slow but steady. Others just blow you away with their speed.
I remember from about 45 or 50 years ago the Buhl Planetarium & Observatory having a Tic-Tac-Toe machine that was based entirely on relays. It would always win or draw, but never lose. At one time I had found a schematic for a different relay-based TTT machine. Always thought it would be fun to build, never got around to it.
https://www.youtube.com/watch?v=5RcQNeO58dc
Thank you for postibg that!
Thanks for finding this video. I think I first saw the machine in ’71 or ’73. This and the Foucault Pendulum are two things that really stuck with me.
Boston MoS had a tic-tac-toe device back around 1975 or 76, not sure anymore whether it was all right there in the exhibit, or if the visible part was just the display. Curious now how they did it. Certainly a microprocessor could have done it, but wondering if it wasn’t built from simpler stuff.
I remember an undefeatable tic tac toe game made only with a few logic gates mentioned in a comment on this site. It was a circuit from a logic gate trainer from the 60s or 70s. The game was simplified by having the outputs be the first open position numbered starting with 1 for the center, then a corner, then on to the rest of the cells in a loop. The human goes first, therefore the computer makes a maximum of four plays, the first output is always 1 for the center, or if it the center is already taken, it represents a corner, the logic would calculate the three remaining outputs. The game required the player to keep track of the board on a sheet of paper.
This made me think of the tic tac toe project from the 1970s with diode logic and a cheat switch so you could win: https://worldradiohistory.com/Archive-Poptronics/Experimenters-Handbook/Electronic-Experimenters-Handbook-1976.pdf
Also Don Lancaster had a very advanced setup: http://cini.classiccmp.org/pdf/re/1971/RE1971-Dec-pg32.pdf