# Tic-Tac-Toe

Thread Starter

#### sailord

Joined Nov 28, 2011
4
Full Disclosure) I am a college student who is over his head in a digital electronics class. I am working on my final project in the class and am desperate for some help. The course uses MultiSim to design circuits and is at a beginner level.

I'll post the assignment in here and my take in the next post....

Assignment:

Digital Tic-Tac-Toe

If individual flip flops are used to represent the squares on the board, what type of logic is needed to detect wins and draws? How are Xs and Os represented by flip flops? How are the player turns sequenced? How are the flip flops that represent the squares changed during the game to represent Xs or Os? Your game logic should generate the following output signals based on the state of the board flip flops:
Output Signal
Meaning
XWINS
The flip flop pattern for X has been found in any row, column, or diagonal.
OWINS
The flip flop pattern for O has been found in any row, column, or diagonal.
DRAW
All board positions are filled, but neither XWINS nor OWINS is active.
XTURN
Active when it is Xs turn to place an X.
OTURN
Active when it is Os turn to place an O.
ILLEGAL
Active when either player tries to move into an occupied board position. Allow player to re-enter move.

For simplicity, X will always go first. Use 4 switches to represent the board position (0 to 8 or 1 to 9) where the next X or O will be placed. Another switch must be used to enter the board position chosen by the first 4 switches. Finally, a reset switch must be used to place all board flip flops and other logic into their initial states (to start a new game).

Thread Starter

#### sailord

Joined Nov 28, 2011
4
I am stuck on how to use only 4 switches as an input.
I have tried setting up the JK flip flops in a grid like the tic tac toe game and using individual inputs that would just require an insane amount of AND gates for each potential victory with a varying voltage to determine which player was x and o. I am also playing with the BCD counter concept and maybe creating binary code for each possible output?

Anyways, I am in over my head and am desperate for some help.

Anyone???

Thanks

#### Wendy

Joined Mar 24, 2008
22,208
Lets see, 9 inputs, which is more than 7 (mod 3, 000), or 15 (mod 4, 0000). You will need 4 bits to define which location you are talking about.

Another thing, the permutations of tic tac toe are very small. You could use a 9 bit addressable memory and define every possible combination, including best response.

Thread Starter

#### sailord

Joined Nov 28, 2011
4
Lets see, 9 inputs, which is more than 7 (mod 3, 000), or 15 (mod 4, 0000). You will need 4 bits to define which location you are talking about.

Another thing, the permutations of tic tac toe are very small. You could use a 9 bit addressable memory and define every possible combination, including best response.
So you think I should build it like a 4 bit counter? I don't understand how I would enter selections that way. How would a 9 bit addressable memory use flip flops and 4 switches to accomplish this task?

Thanks

Like I said, beginner level.

Derek

#### Wendy

Joined Mar 24, 2008
22,208
It is either that or a CPU of some sort. Or are you trying to make a play board for two players?

You can have 9 push buttons that decode to 4 logic lines, if that is easier. Simple gates used for this scheme.

#### Georacer

Joined Nov 25, 2009
5,182
From what I understand, it's a two-player game, no pseydo-AI needed.

The basic components, as I would construct them:
9 push buttons that encode to a 4-bit address.
1 bus to be driven by the 4-bit address.
1 rising edge detector for the player move.
1 toggle bit that indicates player turn.
9 2-bit information units to hold the tick mark.

The part I 'm not sure about is the winner detection. I 'm not too fond of implementing a 9-input K-map.

#### ErnieM

Joined Apr 24, 2011
8,090
It's an interesting problem. My personal inclination is to use a micro for this as a single chip could do all the functions (input buttons, selected game cells, output to direct drive LEDs) but I'm a micro controller guy with decades of experience there. Using a micro I could hand a physical unit to you complete in a day or two.

4 switches for an input is workable if not user-friendly. That can count 0 to 15 which can map to game cell 0 to 8 or 1 to 9 (your choice, I would use 1-9). I would save each Game cell in a single flip flop, 9 F/Fs for X's and another 9 for O's.

There needs to be some decoding between the switches and the F/F's not only to set the correct game cell, but to also inhibit setting a used cell. A multiplexer would work for that.

These 18 F/Fs can also drive LEDs to indicate who picked game cells.

A winner is 3 cells in a row and there are 12 combinations for either X or O, so a total of 24 3 input AND gates. A draw is all cells taken with no winner; brute force for that is to logically OR each X & O cell for 9 lines, AND then with {NOT (OR of all winners)}. That's quite a few gates.

Just some top of the head ideas here. Since this is a simulation and not a build job then it is possibly workable.

Good luck, ping back for some more poking from us.

Thread Starter

#### sailord

Joined Nov 28, 2011
4
@Ernie- is there any way to compact that design any? Also, it wouldn't really be selecting if we had two SR FF's for each block/ 1 per player... That's alot of AND gates...

Georacer- Does you concept work with 4 switches?

Bill- The circuit is required to have FF's to accomplish the task.

Thanks to all of you for the guidance.

Derek

#### ErnieM

Joined Apr 24, 2011
8,090
First compaction idea is end of game: if you count moves then 9 moves without a winner is a draw. You still need to logic OR all winning signals to make a CLEAR input to this counter.

While it is a lot of AND gates to determine a winner I don't see any other way.

Same with 2 F/Fs per cell: each cell has 3 states (empty, X pick, O pick) and 3 states need 2 bits (or 2 F/Fs)