A Slightly Better Way to Implement Tic-Tac-Toe Using SystemVerilog Constraints

In the previous post, I talked about a rudimentary way that I think of to implement Tic-Tac-Toe in SystemVerilog. As promised, I am going to write about how to improve on the grid modeling and achieve a slightly more efficient solution.

For this solution, we are going to look at the grid in a more intuitive way. Instead of a one-dimensional array, we are going to model this as a two-dimensional array which is closer to the original 3X3 grid. So the new array is grid[3][3]. For the same image, we can model our array in the following:

Image credit:Tic Tac Toe image from fte org 

grid[0][0] is empty, 0. grid[0][1] is empty, 0. grid[0][2] is O, -1.
grid[1][0] is X, 1. grid[1][1] is O, -1. grid[1][2] is empty, 0.
grid[2][0] is O, -1. grid[2][1] is empty, 0. grid[2][2] is X, 1.

The reason I don’t really like working with 2D arrays is that it’s all good when we are working on the rows, but it can be a headache if we are doing something in the sense of column. For calculation performed on the rows, we can use those helpful array reduction methods. We need to transpose the array in order to do the same thing on the columns. This gives us a helper 3×3 transgrid. We need to add constraints to do the transpose. The constraints are listed below:

  1. Each value is inside -1, 0, and 1
  2. This is the same as it’s defined in the previous post. X as 1, O as -1, and empty as 0. If you have any questions, please refer to the previous post.

  3. Transpose the array
  4. The matrix transpose can be done through randomization constraints. We can use a foreach loop to have every value mapped according.

  5. Game result distribution
  6. This is the same as it’s defined in the previous post. You can specify your result distribution here.

  7. Calculate the total sum
  8. This can be done in two steps. First, we have a one-dimensional array to calculate the row sum. Then we can calculate the row sum array’s sum value. An additional one-dimensional array is needed here. One thing is different from the previous post is that I don’t specify which player has the first hand. So the total sum can be within the range from -1 to 1, -1 just means O plays first.

  9. Map the diagonal and anti-diagonal values
  10. Two additional arrays are needed to store the diagonal and anti-diagonal values in the grid. We can use foreach loops to do the value mapping.

One thing worth mentioning here is I specifically define the arrays in type int, it’s because I would like to use array reduction methods and I don’t want to bother myself later to do more static castings in order to get the correct sum values.

So the code can be written accordingly as below:

program p1;


    class c1;
        rand int grid [3][3];
        rand int trans_grid [3][3];


        rand int grid_row_sum[3];


        rand int diagonal [3];
        rand int anti_diagonal [3];


        //define enum type for game results
        typedef enum bit [1:0] {X_Win, O_Win, Draw} result_type_t;

        rand result_type_t result_type;


        constraint c1 {
            foreach(grid[i,j])
                grid[i][j] inside {[-1:1]};
        }


        //transpose matrix
        constraint c2 {
            foreach(grid[i,j])
                grid[i][j] == trans_grid[j][i];
           
        }


        //game result distribution
        constraint c3 {
            result_type dist {X_Win:=4, O_Win:=4, Draw := 2};
        }


        //calculate row sum
        constraint c4 {
            foreach(grid_row_sum[i])
                grid_row_sum[i] == grid[i].sum();
        }


        //calculate the total sum
        constraint c5 {
            grid_row_sum.sum() inside {[-1:1]};
        }


        //map the diagonal values
        constraint c6 {
            foreach(diagonal[i])
                diagonal[i] == grid[i][i];
        }

        //map the anti-diagonal values
        constraint c7 {
            foreach(anti_diagonal[i])
                anti_diagonal[i] == grid[i][2-i];
        }


        //game results
        constraint c8 {
            (result_type == X_Win) -> ((grid[0].sum()==3) || (grid[1].sum()==3) || (grid[2].sum()==3)// row
            || (trans_grid[0].sum()==3) || (trans_grid[1].sum()==3)|| (trans_grid[2].sum()==3) // column
            || (diagonal.sum()==3) || (anti_diagonal.sum()==3)) //diagonal
            && ((grid[0].sum()!=-3) || (grid[1].sum()!=-3) || (grid[2].sum()!=-3)// row
            || (trans_grid[0].sum()!=-3) || (trans_grid[1].sum()!=-3)|| (trans_grid[2].sum()!=-3) // column
            || (diagonal.sum()!=-3) || (anti_diagonal.sum()!=-3));

            (result_type == O_Win) -> ((grid[0].sum()==-3) || (grid[1].sum()==-3) || (grid[2].sum()==-3)// row
            || (trans_grid[0].sum()==-3) || (trans_grid[1].sum()==-3)|| (trans_grid[2].sum()==-3) // column
            || (diagonal.sum()==-3) || (anti_diagonal.sum()==-3)) //diagonal
            && ((grid[0].sum()!=3) || (grid[1].sum()!=3) || (grid[2].sum()!=3)// row
            || (trans_grid[0].sum()!=3) || (trans_grid[1].sum()!=3)|| (trans_grid[2].sum()!=3) // column
            || (diagonal.sum()!=3) || (anti_diagonal.sum()!=3));

            (result_type == Draw) -> ((grid[0].sum()!=-3) && (grid[1].sum()!=-3) && (grid[2].sum()!=-3)// row
             &&(trans_grid[0].sum()!=-3) && (trans_grid[1].sum()!=-3) && (trans_grid[2].sum()!=-3) // column
             &&(diagonal.sum()!=-3)  && (anti_diagonal.sum()!=-3))
             && ((grid[0].sum()!=3) && (grid[1].sum()!=3) &&  (grid[2].sum()!=3)// row
            &&  (trans_grid[0].sum()!=3) && (trans_grid[1].sum()!=3)&&  (trans_grid[2].sum()!=3) // column
            && (diagonal.sum()!=3) && (anti_diagonal.sum()!=3))
            &&((grid[0][0]!=0)&&(grid[0][1]!=0)&&(grid[0][2]!=0)&&(grid[1][0]!=0)&&(grid[1][1]!=0)&&
                (grid[1][2]!=0)&&(grid[2][0]!=0)&&(grid[2][1]!=0)&&(grid[2][2]!=0));

        }



    endclass

    c1 c1_h;

    initial begin

        c1_h = new();

        repeat(10) begin
            if(c1_h.randomize()) begin

                $display("=============================");
                $display("This is %s", c1_h.result_type.name());
                $display("%p", c1_h.grid[0]);
                $display("%p", c1_h.grid[1]);
                $display("%p", c1_h.grid[2]);
                $display("=============================");

            end


        end

    end




endprogram

I think the main takeaway here is that if you want to perform some column operations on a 2d array, transpose the array can be your best friend. That’s all for my slightly improved version of my original solution. Thank you for reading. If you find something better, please let me know. I will probably revisit this question in a year or so. Hopefully, I can find something better and more clever at that time.

Leave a Reply

Your email address will not be published.