We’ll all be familiar with Tic-Tac-Toe, or Noughts and Crosses, a childhood pencil-and-paper diversion which has formed the basis of many a coding exercise. It’s an easy enough task to implement in software, but how many of us have seen it done in hardware alone? That’s just what [Warren Toomey] has done using TTL chips, and his method makes for a surprisingly simple circuit.
At its heart is an 8 kB ROM that contains precomputed move sequences that are selected via an address composed of the game states for both player and machine. A series of flip-flops control and buttons to make the board, and a 555 provides a clock.
The technique of using a ROM to replace complex logic is a very powerful one that is facilitated by the low price of relatively large devices that would once have been unaffordable. We’ve seen the technique used elsewhere, including as an ALU in a TTL CPU, and even for an entire CPU in its own right.
You can see the result in operation in the video below the break, and should you wish to have a go for yourself all the relevant information can be found in a GitHub repository.
Continue reading “Tic-Tac-Toe, In TTL”
MENACE, the Matchbox Educable Noughts And Crosses Engine, is a fancy name for a machine that plays Tic-Tac-Toe. The concept is a product of Professor [Donald Mitchie]’s work in the 1960’s and was featured as an example in the “A New THEORY of AWESOMENESS and MIRACLES” talk given at this year’s UK games conference.
[James Bridle] built this fascinating example of how a computational system can learn from its successes and failures. Each box corresponds to one of 304 different board layouts. The operator uses an index sheet to locate the box that corresponds to the current state, shakes the box, then looks to see which bean has randomly fallen into a partition in the box. The color/type of bean corresponds to a space that the machine has “chosen” for that move. If MENACE won the game a bead matching the move that was played would be added to each box used. If MENACE lost, a bead would be removed from each box used. This way the machine cannot make the exact same mistakes twice, and is more likely to repeat successful solutions.
[James] notes that he couldn’t find any evidence of this machine actually being built before. It is possible that this was always a theoretical device but now we’ve seen an actual build. We consider this to be a computer because it is calculating moves based on probability of success but what do you think? If you’re thirsting for more pictures there’s plenty to see in the Flickr set he’s posted.