January 1, 2013:
Well, I let Mr. Goodfellow talk me into it… Instead of simply playing with some old DTL logic from an ancient UNIVAC machine, I’m now trying to implement a tic-tac-toe game using that same ancient collection of gates.
I’m sure there’s a reference somewhere of just how one might accomplish this, but instead I’m just going to “wing it” and see what I can come up with.
I don’t really have enough in the way of circuitry to create a whole CPU (or much of an ALU, for that matter), so I guess I’m restricted to combinatorial logic for the moment. It occurs to me that implementing the whole game will require some form of sequential logic -- particularly when considering alternating moves and some form of game “strategy”. I’ll burn that bridge when I come to it! J
For now, I’m just thinking about how we can represent the game state. Obviously, the board has a total of 9 spaces arranged as follows:
At the beginning of each game, the spaces are “empty.” Players take turns, placing an “X” or an “O” in each space. The first player to get three in a row horizontally, vertically, or diagonally wins. If all spaces are filled, with neither player getting three in a row, the “Cat” gets the game and it’s considered a draw.
So, to summarize, we have 9 spaces that can each have one of three states (empty, X, or O). We could either code this using two-bits per space or by using two identical “boards” (one for each player). Since my first task is to determine if a “winning” state exists, I’ll consider the problem as two identical boards, for the moment.
Evaluating a “win” or “draw” state is pretty straightforward. There are three vertical winning states, three horizontal states, and two diagonal states. If the board is full, there’s a draw. We can build some simple combinatorial logic to check these as follows:
The Symbol “Ç ” is read Logical AND
CAT = B1 Ç B2 Ç B3 Ç B4 Ç B5 Ç B6 Ç B7 Ç B8 Ç B9
Row1 = B1 Ç B2 Ç B3
Row2 = B4 Ç B5 Ç B6
Row3 = B7 Ç B8 Ç B9
Col1 = B1 Ç B4 Ç B7
Col2 = B2 Ç B5 Ç B8
Col3 = B3 Ç B6 Ç B9
Diag1 = B1 Ç B5 Ç B9
Diag2 = B7 Ç B5 Ç B3
It’s a very nice circuit, but given the difficulty in finding 9-bit AND gates in my collection of junk, I need to revise the circuit using, say, 2-bit NAND gates.
Well, that’s given me a bit of a headache, so that’s all for tonight!
January 2, 2013:
It turns out that we don’t have to worry about testing for “the cat” (a draw) on the individual boards, since a board entirely filled with either “Xs” or “Os” is impossible within the normal rules of the game. This simplifies the second circuit considerably:
So now we have a simple, modular circuit that can be used to determine if a “win” condition exists. As it stands, with two complete “boards” representing each player, we can simply logical “OR” the eight outputs to create a single output for a “win” condition.
Now I need to come up with a few more things:
· An input circuit that allows the players to enter their moves.
· A simple display device that shows the status of the board.
· Some mechanism to detect illegal moves.
· A circuit that can play against a human.