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

Plugging these equations into Logisim (an open-source Logic Simulator), we get the following circuit:

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.

---