1. Abstract
The intent of this report is to provide the reader an overview of the design of Tic-Tac-Toe Master (TTTM). Tic-Tac-Toe Master is a smart digital system that plays the game of Tic-Tac-Toe against a user. TTTM has two modes of operation: expert mo de and beginners mode. In the expert mode, it is guaranteed that the TTTM will either win or draw the game. However in beginners mode, there is no such guarantee provided.
It is assumed that the reader is aware of the rules of Tic-Tac-Toe game. No effort is made in this report to explain the rules of the game.
TTTM is designed using VHDL, simulated using VHDL simulators, and prototyped on a Xilincs 4000 series FPGA. All the design procedures, simulation procedures, and test procedures are described in detail in this report. The complete VHDL code is also app ended in the appendix of this report.
TTTM has two modes of operations: expert mode and beginners mode. In the expert mode, it is guaranteed that TTTM will either win or draw the game. However in beginner mode, no such guarantee is provided. The TTTM system powers up in the reset mo de, and if it wins three games then it switches to beginners mode. If the TTTM is in the beginners mode and it loses three games, then it will automatically switch to expert mode. Users are not allowed to select the mode.
User must press the reset button after powering up the system. Before user can start playing games with TTTM, he/she must answer three questions. There are three output signals allotted to these questions: LED_Q1, LED_Q2, and LED_Q3. When the sy stem is expecting user to respond to any of these questions, the corresponding signal will be high. For example, if the system is expecting the user to respond to question 1 then the LED_Q1 signal will be high. This signal should be connected to an LED and the text of the question should be written beside the LED. The text of the questions is as follows:
Q1: Please select a symbol. Use switch S0. 0 for red and 1 for green
Q2: Do you want to move first? Use Switch S0. 1 for yes, 0 for no
Q3: Set the time between moves. Use push buttons up and down
Once user has answered these three questions, a fourth signal, LED_Q4, will go high. This should also be connected to an LED with a text "Please press enter to begin playing game" beside it. At this point, user must press enter to start a game.
To make a move user has to wait for the signal LED_YOUR_TURN to go high, and use the switches S0 to S8. The squares of the Tic-Tac-Toe grid are numbered from 0 to 8 , and from left to right and top to bottom. If user wants to move on square 3, t hen he/she has to set the switch S3 to high and press enter push button.
Once the game is finished, the system will set LED_YOU_WON, LED_I_WON, or LED_GAME_DRAWN signal high depending upon what was the out come of the game. At this point user must press enter to play the next game or reset to start all over ag ain.
TTTM is prototyped on a Xilincs 4000 series FPGA. The IC pin assignments are shown in Figure 1. TTTM has 14 inputs and 34 outputs. The following text discusses in detail the purpose of all these input and output signals.
The input signals can be divided up into three categories: switches, push buttons and clock. There are nine switches labeled S0 to S8. Each switch is used to make a move to a particular square on the Tic-Tac-Toe grid. S0 is also used for responding to the questions described in the previous section.
The TTTM chip has four inputs which can be implemented using push buttons: PB_ENTER, PB_RESET, PB_UP, and PB_DOWN. User sets the PB_ENTER signal high for a brief period of time when he/she has finished a task e.g. finished answering a question or finis hed making a move. Since this signal has to be high just for brief period of time, it is an ideal candidate to be connected to a push button outside of the chip. PB_RESET button is used to reset the chip. PB_UP and PB_DOWN signals are used by user, when h e/she is setting the time between moves (question 3). User sets PB_UP signal high for brief period of time to increment the time between moves by one minute. Similarly user sets PB_DOWN signal high for a brief period of time to decrement a minute from the time between moves.
The TTTM chip provides 34 outputs. These outputs can be divided into three categories: informative output signals, timer outputs, and current symbol outputs. The informative output provide feedback to the user. For e xample, LED_Q1 to LED_Q4 signals let user know what system is expecting from the user. There are 8 informative output signals provided by the TTTM chip: LED_Q1 to LED_Q4, LED_I_WON, LED_YOU_WON, LED_GAME_DRAWN, and LE D_YOUR_TURN. The purpose of these signals has already been discussed in the previous text.
The second category is timer outputs. Timer outputs are two 4-bit busses. These are binary coded decimals and can be directly connected to a BCD to 7-segment LED drivers commercially available. The first timer output provides the time between moves use r selected when answering question 2. The second timer output provides how much time user has left to make the current move. Second timer output is decremented after every minute elapsed.
The third category is current symbol outputs. These are nine 2-bit buses, each bus corresponding to one square of the Tic-Tac-Toe grid. These buses have the value of "01" to turn on the red LED, "10" to turn on the green LED and "00" turn off both the LEDs. The lower bit (bit 0) of the bus can be connected to the red LED and higher bit (bit 1) can be connected to the green LED.
The TTTM chip is divided into two components: datapath and controller, as shown in Figure 2. The two components interact with each other by means of 18 signals, 13 signals are going from controller to datapath and 5 signals are going from the da tapath to the controller.
The state diagram of controller is shown in Figure 3. The controller is designed using VHDL. It has 28 states. Behaviour of the controller is developed using VHDL and it was synthesized and simulated. The simulation of the controller is included in the appendix.
The datapath component of TTTM chip is shown in Figure 4. The datapath is composed of 13 different components:
The first 7 components are standard latches, registers, and counters of different widths, and they do not require any more elaboration. The next 6 components are more complex and are discussed separately in the following text.
User Input Driver is like a filtering device. Whenever user makes a move, it goes through the UID. UID makes sure that it is user’s turn, and there is no symbol already on the square where user wants to make a move. If these conditions are true, then U ID changes the content of the 2-bit register for the square where user wants to make the move. UID takes in four inputs and provides a 2-bit output. The output is connected to the 2-bit symbol registers through a 2 to 1 mux. The inputs are switch signal < B>ss, user_type, turn, and current content of symbol register, cur_sym.
Mode master determines if there is a need to change the system mode from expert to beginner or from beginner to expert. It takes in 5 inputs: Games_Won, Games_Lost, Mode, reset, and clock. Depending upon what the curr ent mode is and how many games have been won or lost, it determines if there is a need to change the mode. It provides two outputs: New_Mode and Mode_Changed. New_Mode is the changed mode and the Mode_Changed is a pulsed signal . Whenever the mode is changed, Mode_Changed is set to high for one clock cycle.
Timer module figures out if a minute is up or not. It has two internal 32-bit registers. One is set to a particular constant value and other one is a free incrementing register. It starts at 0 and increments at every rising edge of clock. When t he two registers have the same content, the output signal minute_is_up is set to high for one clock cycle.
Timer compare module compares the time remaining for the user to make move against 0. If the time has decremented down to 0 then the output User_time_is_Up signal is set to high for one clock cycle.
Finished checker module checks to see whether a game is finished or not. There are three cases when one can assume that a game is finished: (1) user has won the game, (2) system has won the game, or (3) neither have won the game and there are no more squares available to make a move. In the first two cases the output Game_Finshed is set to high for one clock cycle and in the third case, the output Game_Drawn is set to high for one clock cycle.
This module is the brain of TTTM chip. This module makes the decision as to where to move next if it is system’s turn to move. When making a decision, this module follows 6 heuristics. These 6 heuristics are followed in order. If earlier heurist ic provides a suitable move then the module makes that move without trying the later heuristics. For example, according to heuristic number one, if the system is supposed to make the move on square three then system will not evaluate the other six heurist ics (from two to seven). The following is the brief discussion of these heuristics.
Check all possible combinations of the grid to see if the system is in winning position. That is, if the two red LEDs are on (assuming the system is red) in a row or a column or a diagonal, and the third square is empty then move on the third empty square.
Check all combinations of the grid to see if user is in winning position. If this is the case then block the user’s next move.
If the center square is available then make a move there.
The Tic-Tac-Toe grid is numbered as shown in figure 5. The square numbers 1, 3, 5, and 7 are the squares which are called the side squares. The square numbers 0, 2, 6, and are called the corner squares. Impose from side means, check every empty sid e square and see if making a move there will put the system in winning position. If this is the case then make the move to that side square.
If making a move to any of the empty corner squares puts the system in winning position then go for it.
Pick first empty corner square. Search in "S" configuration, that is, first search square 0 followed by squares 6, 2 and 8.
Pick first available side square.
Each of the datapath components, described in the previous section, is simulated separately first by forcing certain values to the inputs and inspecting the output. Once all the components are simulated properly then we connected them in dat apath as shown in Figure 4, and tested the complete datapath. Controller is also tested separately. Once both controller and datapath are simulated separately, we connected them together and built the whole system, and tested the whole system as system.
The main component we had to simulate was the decision making module. To test all the heuristics described in previous section, we came up with 18 test games. These games are listed in the appendix. Also the simulation document for these 18 games is at tached as appendix.
6. Test Procedure
To test the chip, we built a system with push buttons, LEDs and switched. The block diagram of our system is shown in Figure 6.