A Rudimentary Way to Implement Tic-Tac-Toe Using SystemVerilog Constraints

You can do lots of fun things using SystemVerilog Constraint. There are famous Einstein house puzzle, Eight queen puzzle, and many more can be solved using SystemVerilog constraints. Today I would like to talk about how to implement Tic-Tac-Toe result using SystemVerilog constraints.

I call this a rudimentary approach is because I didn’t take code reuse into consideration for this one. The way I modeled the Tic-Tac-Toe grid, requires lots of manually coding. I will post a slightly improved version for the next post.

First, I am going to model the grid of the Tic-Tac-Toe game. There are 9 spaces in total for this 3×3 grid. We can have an int array of size 9 to model the grid.
 

Image credit:Tic Tac Toe image from fte org 

For this image, we can have our array values as follow:

A[0] is empty, 0. A[1] is empty, 0. A[2] is O, -1.
A[3] is X, 1. A[4] is O, -1. A[5] is empty, 0.
A[6] is O, -1. A[7] is empty, 0. A[8] is X, 1.

Then we want to set the value for each space. X can be represented by 1, O can be represented by -1, and 0 means space is not yet filled. We can have the first constraint to make sure the value of each space is either -1, 0, or 1.

We arbitrarily use X as the firsthand player. This means at any given time, the sum of array A is either 0, after both players have played, or 1, only X has played. This will give us the second constraint that the sum of the array A is either 0 or 1.

We are going to define an enum type for different game result scenarios, X winning, X winning and a draw. In the constraint, we would like to specify the probability distribution of each scenario in the constraint.

The last constraint is about the actual definition of each game result scenario. We are going to talk about X winning and Draw here in detail. O winning is just slightly different from X winning.

  1. X winning
  2. There are a few winning cases. Either one row sum is 3, or one column sum is 3, or one diagonal sum is 3. At the same time, we want to make sure O is not winning. That is to specify any of the sum values mentioned above are not -3. We can write constraints accordingly.

  3. Draw
  4. Draw only happens after we have filled all the spaces. So we want to make sure none of array A’s value is still 0. The draw condition occurs when there is no winner, which means the sum values are neither 3 nor -3. We can also write corresponding constraints.

    The reason that this method is rudimentary is I implemented all the conditions in this constraint manually. I didn’t use any array reduction methods here. For the improved version, some array reduction methods are going to be used to make the code less cumbersome.

The code can be written accordingly in the following:

program p1;

    class c1;

        //3x3 grid
        rand int A[9];

        //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;


        //X:1 O:-1 empty:0
        constraint c1 {
            foreach(A[i])
                A[i] inside {[-1:1]};
        }


        //X first hand
        constraint c2 {
            A.sum inside{[0:1]};
        }


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


        //game result senarios
        constraint c4 {
            (result_type == X_Win) -> ((A[0]+A[1]+A[2]==3)|| (A[3]+A[4]+A[5]==3) || (A[6]+A[7]+A[8]==3) //row
            || (A[0]+A[3]+A[6]==3)||(A[1]+A[4]+A[7]==3)||(A[2]+A[5]+A[8]==3) //column
            ||(A[0]+A[4]+A[8]==3) || (A[2]+A[4]+A[6]==3)) && //diagonal
            ((A[0]+A[1]+A[2]!=-3) && (A[3]+A[4]+A[5]!=-3)&&(A[6]+A[7]+A[8]!=-3) //row
            && (A[0]+A[3]+A[6]!=-3)&&(A[1]+A[4]+A[7]!=-3)&&(A[2]+A[5]+A[8]!=-3) //column
            &&(A[0]+A[4]+A[8]!=-3) && (A[2]+A[4]+A[6]!=-3)); //diagonal


            (result_type == O_Win) -> ((A[0]+A[1]+A[2]==-3)|| (A[3]+A[4]+A[5]==-3) || (A[6]+A[7]+A[8]==-3) //row
            || (A[0]+A[3]+A[6]==-3)||(A[1]+A[4]+A[7]==-3)||(A[2]+A[5]+A[8]==-3) //column
            ||(A[0]+A[4]+A[8]==-3) || (A[2]+A[4]+A[6]==-3)) && //diagonal
            ((A[0]+A[1]+A[2]!=3) &&(A[3]+A[4]+A[5]!=3)&&(A[6]+A[7]+A[8]!=3) //row
            && (A[0]+A[3]+A[6]!=3)&&(A[1]+A[4]+A[7]!=3)&&(A[2]+A[5]+A[8]!=3) //column
            &&(A[0]+A[4]+A[8]!=3) && (A[2]+A[4]+A[6]!=3)); //diagonal

            (result_type == Draw) -> (A[0]+A[1]+A[2]!=-3) && (A[3]+A[4]+A[5]!=-3)&&(A[6]+A[7]+A[8]!=-3) //row
            && (A[0]+A[3]+A[6]!=-3)&&(A[1]+A[4]+A[7]!=-3)&&(A[2]+A[5]+A[8]!=-3) //column
            &&(A[0]+A[4]+A[8]!=-3) && (A[2]+A[4]+A[6]!=-3) &&
            (A[0]+A[1]+A[2]!=3) && (A[3]+A[4]+A[5]!=3)&&(A[6]+A[7]+A[8]!=3) //row
            && (A[0]+A[3]+A[6]!=3)&&(A[1]+A[4]+A[7]!=3)&&(A[2]+A[5]+A[8]!=3) //column
            &&(A[0]+A[4]+A[8]!=3) &&(A[2]+A[4]+A[6]!=3) //diagonal
            &&(A[0]!=0&&A[1]!=0&&A[2]!=0&&A[3]!=0&&A[4]!=0&&A[5]!=0&&A[6]!=0&&A[7]!=0&&A[8]!=0); //all spaces are filled

        }


    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("%d, %d, %d", c1_h.A[0], c1_h.A[1], c1_h.A[2]);
                $display("%d, %d, %d", c1_h.A[3], c1_h.A[4], c1_h.A[5]);
                $display("%d, %d, %d", c1_h.A[6], c1_h.A[7], c1_h.A[8]);
                $display("=============================");

            end


        end

    end


endprogram

That’s it for how I implemented a Tic-Tac-Toe game. For the next post, I am going to improve on my grid modeling and post a slightly improved version. If you have any questions, please leave your comment here. Thanks for reading.

Leave a Reply

Your email address will not be published.