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:
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:
- Each value is inside -1, 0, and 1
- Transpose the array
- Game result distribution
- Calculate the total sum
- Map the diagonal and anti-diagonal values
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.
The matrix transpose can be done through randomization constraints. We can use a foreach loop to have every value mapped according.
This is the same as it’s defined in the previous post. You can specify your result distribution here.
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.
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:
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.