CPE 133 Final Project: Tic Tac Toe

Image from: https://www.rehabmart.com/product/giant-tictactoe2-13255.html

Tic tac toe. For this project, we decided to do a classic game of tic tac toe. It plays exactly like how you think it does but on a Basys 3 Board. The idea of how we were going to make a fully functional tic tac-toe game was to use a membrane keypad from the Arduino kit that we already had. Although the alternative option was to use the switches that were directly on the board, we were committed to the membrane. So that leaves us with just a membrane and a basic board for hardware. For the inputs, we have the membrane represent the board for inputs while the 7-segment display on the basys board is the display representation with the (from left to right) 1st one displaying who’s turn it is with 1 being player 1 and 2 being vis versa. And as for determining who is who on the board itself, we made player 1 a solid light and player 2 a flashing light on the display. When the game is over, it will either display a ‘1’ across all 4 segment displays meaning that player 1 is the winner and 2 is vis versa and the word ‘tie’ shows that there was no winner at all.

We took inspiration from both this project(https://github.com/JonathanHonrada/TicTacToe_Basys3_Verilog) and this video(https://youtu.be/Il5ZAfsUkPk).

To build this project, the supplies needed are listed below

• Basys 3 Board
• 4x4 Membrane Keypad Module 
• Vivado 
• Laptop
• Male to Male Jumper Cables

typedef enum{COL1 = 2'b00, COL2= 2'b01, COL3 =2'b10, COL4 = 2'b11} states;


module move_submit(
       input player,
       input clk,
       input reset,
       input [3:0]Y,
       output player_output,
       output [3:0]pos,
       output [3:0]X
    );
    
    logic [3:0] POS;
    logic play = 1'b0;
    logic [3:0]col;
    logic sclk;
    states PS,NS;
    
    always_ff @(posedge(clk)) begin
        PS <= NS;
    end
    
    always_comb begin
        
        case(PS)
            COL1: begin
                    col = 4'b0111;
                    NS = COL2;
            end
            COL2: begin
                    col = 4'b1011;
                    NS = COL3;
            end
            COL3: begin
                    col = 4'b1101;
                    NS = COL4;
            end
            COL4: begin 
                    col = 4'b1110;
                    NS = COL1;
            end
            default: begin
                     col = 4'b0111;
                     NS = COL2;
            end
        endcase
    
        if(player == 1'b0) begin
            play = 1'b1; //if it is currently player 1's turn, next is player 2
        end    
        else if(player == 1'b1)begin
            play = 1'b0; //if it is currently player 2's turn, next is player 1
        end
        else begin
            play = 1'b0; //defaults to player 1
        end
    end

For us, the hardest part was creating the FSM that could take in inputs from the membrane switch module. In the end we took inspiration from this file(https://github.com/JonathanHonrada/TicTacToe_Basys3_Verilog) to create our own FSM. We have your typically alwasy_ff @(posedge(clk)) to make sure that PS <= NS. However for combinational logic it is a bit different. Instead our states are the 4 different columns on the switch module. 

Image from https://lastminuteengineers.com/arduino-keypad-tutorial/ 

Looking at the image provided there are 4 rows and 4 columns on the switch module. Since we need to iterate through 4 different columns, we need 4 states of which I enumerated myself as 00, 01, 10 and 11. For the first case, 00 we read column 1. This is done by driving that column all to low or 0, and the rest to high or 1. After this is done we set the next state as 01, then 10, then 11. We repeat the same steps for each state for the corresponding columns. For example, state 01 corresponds to column 2, thus we drive column 2 to 0 and the rest to 1, or 1011. We also default to column 1 in case any hazards/glitches occur. In this module we see who's turn it last was, and set it to the next player's turn. For example if we read that player is 2'b01, or player 1 we then set it to 2'b10, or player 2.

always_ff@(posedge(sclk)) begin
        //only values that are in column 1 are, 1, 4 & 7 so we set those values to the placeholder that will be sent to the game control
        //to evaluate who occupies that space
        if((col[0] == 0) && (Y[2] == 0)) begin
            POS = 4'b0001; 
        end
        else if((col[0] == 0) && (Y[1] == 0)) begin
            POS = 4'b0100;
        end
        else if((col[0] == 0) && (Y[0] == 0)) begin
            POS = 4'b0111;
        end
        //same applies to column 2, where the only values are 2, 5, and 8
        if((col[1] == 0) && (Y[2] == 0)) begin
            POS = 4'b0010;
        end
        else if((col[1] == 0) && (Y[1] == 0)) begin
            POS = 4'b0101;
        end
        else if((col[1] == 0) && (Y[0] == 0)) begin
            POS = 4'b1000;
        end
        if((col[2] == 0) && (Y[2] == 0)) begin
            POS = 4'b0011;
        end
        //column 3 only has values 3, 6 and 9
        else if((col[2] == 0) && (Y[1] == 0)) begin
            POS = 4'b0110;
        end
        else if((col[2] == 0) && (Y[0] == 0)) begin
            POS = 4'b1001;
        end
        //added column 4 of the membrane module to prevent latches from forming
        else if((col[3] == 0) && (Y[3] == 0)) begin
            POS = 4'b1111;
        end
        else begin
            POS = 4'b1111;
        end
        
        if(reset == 1)
        //resets all rows
           POS = 4'b0000;
    end
    
    
    assign X = col;
    assign player_output = play;
    assign pos = POS;
    
    
endmodule


After we decide which column to focus on, i.e column one, we then iterate through the rows. Since the rows are inputs, we detect if that space is 0, or free. If it is, we save that position to a variable, which we will send to the game control to help save/tell which player is about to occupy that space. 

module Game_Control(
       input clk,
       input [4:0]move,
       output player,
       output [1:0]pos1,pos2,pos3,pos4,pos5,pos6,pos7,pos8,pos9
    );
    
    logic [17:0] position_reg = 18'b000000000000000000;
    logic last_play;

This module helps to read the player input and stores the position of each move. It does this by first having a 5 bit value that we call move, which stores who’s turn it is as well as the position/move that the player just made. Likewise there is an 18 bit position register. 18 bits since there are 9 possible spaces on a 3x3 grid, and each space has to store a 2 bit value so we can “remember” who occupies what space. Thus 9x2 is 18. 

    //5th bit represents player, 0 = p1 and 1 = p2. The other 4 bits represent the positions 1 through 9 respectively
    always_ff @(posedge(clk)) begin
        if((move == 5'b10001) && (position_reg[1:0] == 2'b00)) begin //reads it's player 2's turn, and save's position as player 2
            position_reg[1:0] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b10010) && (position_reg[3:2] == 2'b00)) begin
            position_reg[3:2] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b10011) && (position_reg[5:4] == 2'b00)) begin
            position_reg[5:4] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b10100) && (position_reg[7:6] == 2'b00)) begin
            position_reg[7:6] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b10101) && (position_reg[9:8] == 2'b00)) begin
            position_reg[9:8] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b10110) && (position_reg[11:10] == 2'b00)) begin
            position_reg[11:10] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b10111) && (position_reg[13:12] == 2'b00)) begin
            position_reg[13:12] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b10111) && (position_reg[13:12] == 2'b00)) begin
            position_reg[13:12] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b11000) && (position_reg[15:14] == 2'b00)) begin
            position_reg[15:14] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b11001) && (position_reg[17:16] == 2'b00)) begin
            position_reg[17:16] = 2'b01; //sets pos1 to player 2
            last_play = 1'b1;
        end
        else if((move == 5'b00001) && (position_reg[1:0] == 2'b00)) begin 
            position_reg[1:0] = 2'b01; //sets pos1 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b00010) && (position_reg[3:2] == 2'b00)) begin
            position_reg[3:2] = 2'b01; //sets pos2 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b00011) && (position_reg[5:4] == 2'b00)) begin
            position_reg[5:4] = 2'b01; //sets pos2 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b00100) && (position_reg[7:6] == 2'b00)) begin
            position_reg[7:6] = 2'b01; //sets pos3 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b00101) && (position_reg[9:8] == 2'b00)) begin
            position_reg[9:8] = 2'b01; //sets pos4 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b00110) && (position_reg[11:10] == 2'b00)) begin
            position_reg[11:10] = 2'b01; //sets pos5 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b00111) && (position_reg[13:12] == 2'b00)) begin
            position_reg[13:12] = 2'b01; //sets pos6 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b01000) && (position_reg[15:14] == 2'b00)) begin
            position_reg[15:14] = 2'b01; //sets pos7 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b01001) && (position_reg[17:16] == 2'b00)) begin
            position_reg[17:16] = 2'b01; //sets pos8 to player 1
            last_play = 1'b0;
        end
        else if((move == 5'b00000)||(move == 5'b10000)) begin
            position_reg = 18'b000000000000000000; //resets board to clear
            last_play = 1'b1;
        end
        else begin 
            position_reg <= position_reg;
        end
    end

We first read 5 bit number stored in move, and tell what position was entered and who's turn it is. For example, if move is the 5 bit number 00001, the 5th bit tells us it’s player 1’s turn (since it is 0). We then set the value player to ‘b1, since it is player 2’s turn next. We then check the position register to make sure that the respective position, in this case 1, since 00001 in binary is 1 in decimal is empty. This is done by checking that the value is still 00. Because of this, we can make sure that no one commits any illegal moves by overwriting the current player’s position. Finally if the conditions are met we change that bit in the 18 bit register to 01, representing player 1 occupies that space. If it were player 2’s turn we would save it as 10, signifying player 2 occupies that space. 

assign pos1 = position_reg[1:0];
    assign pos2 = position_reg[3:2];
    assign pos3 = position_reg[5:4];
    assign pos4 = position_reg[7:6];
    assign pos5 = position_reg[9:8];
    assign pos6 = position_reg[11:10];
    assign pos7 = position_reg[13:12];
    assign pos8 = position_reg[15:14];
    assign pos9 = position_reg[17:16];
    assign player = last_play;
endmodule

Once the if's are resolved, we save the calculated position into the respective positions.

Image from https://geekflare.com/tic-tac-toe-python-code/ 

In Tic Tac Toe, there are 8 different win conditions. 3 in a row, 3 in a column or 3 in diagonal. 

3 rows + 3 columns + 2 diagonals = 8. The easiest solution was to use an if statement and hard code all win conditions with and if else statement.

module Win_Check(
       input clk,
       input [1:0]pos1, pos2, pos3, pos4, pos5, pos6, pos7, pos8, pos9,
       output logic[1:0]winner,
       output reset
    );
    
    logic res;
    logic win_signal;
    
    
    
    always_ff @(posedge(clk)) begin
        if(reset == 0)
            begin
            if((pos1 == 2'b01 && pos2 == 2'b01 && pos3 == 2'b01)||(pos4 == 2'b01 && pos5 == 2'b01 && pos6 == 2'b01)||
               (pos1 == 2'b01 && pos8 == 2'b01 && pos9 == 2'b01)||(pos1 == 2'b01 && pos4 == 2'b01 && pos7 == 2'b01)||
               (pos2 == 2'b01 && pos5 == 2'b01 && pos8 == 2'b01)||(pos3 == 2'b01 && pos6 == 2'b01 && pos9 == 2'b01)||
               (pos1 == 2'b01 && pos5 == 2'b01 && pos9 == 2'b01)||(pos3 == 2'b01 && pos5 == 2'b01 && pos7 == 2'b01))
                    begin
                    win_signal = 2'b01;
                    res = 0;
                    end
            else if((pos1 == 2'b10 && pos2 == 2'b10 && pos3 == 2'b10)||(pos4 == 2'b10 && pos5 == 2'b10 && pos6 == 2'b10)||
                    (pos1 == 7'b10 && pos8 == 2'b10 && pos9 == 2'b10)||(pos1 == 2'b10 && pos4 == 2'b10 && pos7 == 2'b10)||
                    (pos2 == 2'b10 && pos5 == 2'b10 && pos8 == 2'b10)||(pos3 == 2'b10 && pos6 == 2'b10 && pos9 == 2'b10)||
                    (pos1 == 2'b10 && pos5 == 2'b10 && pos9 == 2'b10)||(pos3 == 2'b10 && pos5 == 2'b10 && pos7 == 2'b10))
                    begin
                    win_signal = 2'b10;
                    res = 0;
                    end
            else if((pos1 != 2'b00) && (pos2 != 2'b00) && (pos3 != 2'b00) && (pos4 != 2'b00) && (pos5 != 2'b00) && (pos6 != 2'b00) && 
                     (pos7 != 2'b00) && (pos8 != 2'b00) && (pos9 != 2'b00) && (win_signal != 2'b10 || win_signal!= 2'b01))
                     begin
                     win_signal = 2'b11;
                     res = 0;
                     end
            else 
                     begin
                     win_signal = 2'b00;
                     res = 0;
                     end
            end
            else 
                begin
                win_signal = 2'b00;
                res = 1;
                end
    end
    
    assign reset = res;
    assign winner = win_signal;
    
endmodule

If 01 is 3 in a row, in a column or in a diagonal, then the win_signal saves 01(player 1) and sets that as an output to send to the 7 segment display to show. 

If 10 is 3 in a row, in a column or in a diagonal, then the same occurs but for player 2. 

Finally to detect a tie, we checked to make sure no spaces are empty, by making sure none of the 9 different positions are 0 (since if it is full it should all be either 01 or 10). If it makes sure all spaces are full, and the win_signal is not either 01 or 00 (player 1 or 2) then it will set the win signal to 11 which signifies a tie. 

The last case just tells us the game is still going, since there are empty spaces and the win signal is still 0. 

`timescale 1ns / 1ps


module Seven_Segment_Driver(
       input clk,
       input [1:0]pos1, pos2, pos3, pos4, pos5, pos6, pos7, pos8, pos9,
       input [1:0] win,
       input player,
       output [3:0] SEG_EN,
       output [7:0] Segments
    );
    
    logic [1:0] cnt_dig;
    logic[3:0] digit;
    logic [7:0] segment = 8'b11111111;
    logic sclk;
    logic disp_clk;
    
    clk_div my_clk(.clk(clk), .sclk(sclk));
    clk_div2 clock_for_display(.clk(clk), .disp_clk(disp_clk));
    
    always_ff @(posedge sclk)
        begin
            cnt_dig <= cnt_dig + 1;
        end
        
    assign SEG_EN = (cnt_dig == 0)? 4'b1110: 
                    (cnt_dig == 1)? 4'b1101:
                    (cnt_dig == 2)? 4'b1011: 
                    (cnt_dig == 3)? 4'b0111: 4'b1111;
                    
    always_ff @(posedge sclk) 
        begin
        segment = 8'b11111111;
            if(win == 0)
                begin
                case(cnt_dig)
                    3: begin
                        case(player)
                            0: segment <= 8'b10011111;
                            1: segment <= 8'b00100101;
                        endcase
                    end
                    
                    2:begin//middle left display
                         case (pos3)
                            0:segment[4] <= 1;
                            1:segment[4] <= 0;
                            2:segment[4] <= disp_clk;
                            default: segment[4] <= 1;
                          endcase
                          case (pos6)
                             0:segment[1] <= 1;
                             1:segment[1] <= 0;
                             2:segment[1] <= disp_clk;
                             default: segment[1] <= 1;
                          endcase
                          case (pos9)
                             0:segment[7] <= 1;
                             1:segment[7] <= 0;
                             2:segment[7] <= disp_clk;
                             default: segment[7] <= 1;
                          endcase
                       end
                       
                    1:begin // middle right display
                          case (pos2)
                             0:segment[4] <= 1;
                             1:segment[4] <= 0;
                             2:segment[4] <= disp_clk;
                             default: segment[4] <= 1;
                           endcase
                           case (pos5)
                              0:segment[1] <= 1;
                              1:segment[1] <= 0;
                              2:segment[1] <= disp_clk;
                              default: segment[1] <= 1;
                           endcase
                           case (pos8)
                              0:segment[7] <= 1;
                              1:segment[7] <= 0;
                              2:segment[7] <= disp_clk;
                              default: segment[7] <= 1;
                           endcase
                          end
                          
                    0: //right most display
                         begin 
                          case (pos1)
                             0:segment[4] <= 1;
                             1:segment[4] <= 0;
                             2:segment[4] <= disp_clk;
                             default: segment[4] <= 1;
                           endcase
                           case (pos4)
                              0:segment[1] <= 1;
                              1:segment[1] <= 0;
                              2:segment[1] <= disp_clk;
                              default: segment[1] <= 1;
                           endcase
                           case (pos7)
                              0:segment[7] <= 1;
                              1:segment[7] <= 0;
                              2:segment[7] <= disp_clk;
                              default: segment[7] <= 1;
                           endcase
                          end
                          default: segment <= 8'b11111111;
                        endcase
                      end
        
        else if(win == 1) 
            begin
            case(cnt_dig)
                1:segment <= {1'b1,disp_clk,disp_clk,5'b11111};
                2:segment <= {1'b1,disp_clk,disp_clk,5'b11111};
                3:segment <= {1'b1,disp_clk,disp_clk,5'b11111};
                0:segment <= {1'b1,disp_clk,disp_clk,5'b11111};
                default: segment <= 8'b11111111;
            endcase
            end
        else if(win == 2)
            begin
            case(cnt_dig)
                1:segment <= {disp_clk,disp_clk,1'b1,disp_clk,disp_clk,1'b1,disp_clk,1'b1};
                2:segment <= {disp_clk,disp_clk,1'b1,disp_clk,disp_clk,1'b1,disp_clk,1'b1};
                3:segment <= {disp_clk,disp_clk,1'b1,disp_clk,disp_clk,1'b1,disp_clk,1'b1};
                0:segment <= {disp_clk,disp_clk,1'b1,disp_clk,disp_clk,1'b1,disp_clk,1'b1};
                default: segment <= 8'b11111111;
          endcase
          end
       else if(win ==3)
            begin
             case(cnt_dig)
                1:segment <= 8'b01100001;
                2:segment <= 8'b11111111;
                3:segment <= 8'b11100001;
                0:segment <= 8'b10011111;
                default: segment <= 8'b11111111;
          endcase
          end
    end 
    
    assign Segments = segment;
    
    
endmodule

This module is responsible for reading the positions from the game control and displaying it onto the 7 segment display on the Basys Board. We used this file(https://github.com/JonathanHonrada/TicTacToe_Basys3_Verilog/blob/master/bc_dec.v) for the driver.

module TicTacToe_FP(
       input clk, //game's clock
       input reset, //to trigger game to reset
       input [3:0] row,
       output[3:0] SEG_EN,
       output [7:0] Segments,
       output [3:0] col
    );
    
    logic [3:0]z;
    logic p;
    logic player;
    logic [1:0]pos1,pos2,pos3,pos4,pos5,pos6,pos7,pos8,pos9;
    logic [1:0]win;
    
    move_submit submit_move(.player(player), .reset(reset), .X(col), .Y(row), .player_output(p), .a(z), .clk(clk));
    
    Game_Control tictactoe_control(.clk(clk), .move({p,z}), .pos1(pos1), .pos2(pos2), .pos3(pos3), .pos4(pos4), .pos5(pos5), 
                           .pos6(pos6), .pos7(pos7), .pos8(pos8), .pos9(pos9), .player(player));
    
    Win_Check win_check(.clk(clk), .pos1(pos1), .pos2(pos2), .pos3(pos3), .pos4(pos4), .pos5(pos5), 
                           .pos6(pos6), .pos7(pos7), .pos8(pos8), .pos9(pos9), .winner(win), .reset(reset2));
                           
    Seven_Segment_Driver seven_segment_display(.CLK(clk), .win(win), .SEG_EN(SEG_EN), .SEGMENTS(Segments), .player({!player}), 
                                               .pos1(pos1), .pos2(pos2), .pos3(pos3), .pos4(pos4), .pos5(pos5), .pos6(pos6), .pos7(pos7), 
                                               .pos8(pos8), .pos9(pos9));
    
endmodule

This module is the simplest of the 5. It just houses the inputs and outputs, as well as feeds values into the other modules.

For the hardware, we only had to connect the switch module to the basys 3 board. We connected the module through the pmod jacks using male to male jumper cables. The rows went to jack J1 to J4, and the columns were connected from pins J7 to J10. 

We did run into a small issue where the mapping didn’t quite line up on the 3x3 grid of numbers. However it did still map to a 3x3 area, and worked as demonstrated in our demo.

What is development without problems? A few problems have occurred while in development with one of the problems being the code 7 segment display. For a while, we couldn’t get the 7-segment display to change to player 2 after player 1 would make an input and it would just always be P1’s turn. This was eventually resolved so that it would function properly. However, there was one problem that could not be fixed with code. The membrane is a very finicky piece of hardware as touching even the membrane would be considered multiple inputs at the same time. Even just moving the membrane would cause inputs to occur. The only way we got it to properly function was to make sure that the pad and membrane would not move at all and that the button press on the pad itself were to be kept short and brief.