Fets and Crosses: Tic-Tac-Toe built from 2458 discrete transistors

Summary

Fets & Crosses Overview + Features An implementation of the classic Tic-Tac-Toe / Noughts and Crosses game built entirely from 2458 discrete transistors. Simulation / Design While playing around with a graphical logic simulator during a 'Digital Design' lecture, I came up with a simple Tic-Tac-Toe game, featuring both a player-vs-player and player-vs-computer mode. It is capable of detecting all possible win/draw states, and features a move validator, allowing it to reject invalid inputs from the user. The 'Engine' against which a player can play was originally implemented using a parallel input/output ROM as a large lookup table: The current board state was applied to the 18-bit address applied to the ROM address input, and the engine's move read from memory. This worked well, but was very inefficient: less than 5% of all possible inputs corresponded to possible game states. In a second step I replaced this implementation with a purely combinatorial logic-gate based module, also capable of perfect play. The simulation in LOGISIM. A high-level block diagram of the system. Hardware Implementation The final circuit was much simpler than I first expected it to be: It only requires 19 Flip-Flops (18 for the current game state, and one to track the active player), and a handful of basic gates. Some quick estimates put that around 2000 transistors when built in CMOS - how hard could that be to implement? Well. In a workflow (very!) vaguely reminiscent of actual IC design, I first designed the set of basic cells I needed. This was done in KiCad, with each cell contained in a hierarchical schematic sheet. For example, here is the basic NOT gate: I should note that the specific mosfet models were chosen using the highly scientific process of "sorting by cheapest first" on lcsc.com. I then systematically constructed more complex gates from these basic cells. For example, a 2-input AND gate was built from an NAND and NOT gate: Then, I re-drew the logic circuit in KiCad, using ...