I am trying to design a Tic-Tac-Toe game in Java. I must point out that I am a complete beginner in Java. So I am trying to generate all possible combinations of the game, then store it in a file. We know that there are 255168 possible combinations. Anyway here is my code:
import java.io.*;
import java.util.Random;
import java.util.Arrays;
public class generator2 {
public static void main(String[] args) {
Random r=new Random();
String s;
String store[] = new String[255168];
int count=0;
int i=0;
int a[][]=new int[3][3];
int wf;
int flag=0;
char b;
while(count<255168)
{
s="";
b='X';
flag=0;
for(int[] row : a)Arrays.fill(row, 0);
wf=0;
i=0;
while(wf==0)
{
int r1=r.nextInt(3)+0;
int r2=r.nextInt(3)+0;
if(a[r1][r2]==0)
{
i++;
if(flag==0) {a[r1][r2]=1;flag=1;}
else {a[r1][r2]=2;flag=0;}
if(a[0][0]==1 && a[0][1]==1 && a[0][2]==1 || a[1][0]==1 && a[1][1]==1 && a[1][2]==1 || a[2][0]==1 && a[2][1]==1 && a[2][2]==1 || a[0][0]==1 && a[1][0]==1 && a[2][0]==1 || a[0][1]==1 && a[1][1]==1 && a[2][1]==1 || a[0][2]==1 && a[1][2]==1 && a[2][2]==1 || a[0][0]==1 && a[1][1]==1 && a[2][2]==1 || a[0][2]==1 && a[1][1]==1 && a[2][0]==1)
{
b='W';
wf=1;
break;
}
else if(a[0][0]==2 && a[0][1]==2 && a[0][2]==2 || a[1][0]==2 && a[1][1]==2 && a[1][2]==2 || a[2][0]==2 && a[2][1]==2 && a[2][2]==2 || a[0][0]==2 && a[1][0]==2 && a[2][0]==2 || a[0][1]==2 && a[1][1]==2 && a[2][1]==2 || a[0][2]==2 && a[1][2]==2 && a[2][2]==2 || a[0][0]==2 && a[1][1]==2 && a[2][2]==2 || a[0][2]==2 && a[1][1]==2 && a[2][0]==2)
{
b='L';
wf=1;
break;
}
else if(i==9)
{
b='T';
wf=1;
break;
}
}
}
s+=b;
for(i=0;i<3;i++)
for(int j=0;j<3;j++)
s+=String.valueOf(a[i][j]);
if(repeat(s,store,count)) {store[count]=s;count++;s="";System.out.println(count);}
else {continue;}
}
// for(i=0;i<958;i++)
// {
// System.out.println(store[i]);
// }
}
public static boolean repeat(String s,String[] a,int count){
int flag=0;
for(int i=0;i<count;i++)
{
if(a[i].equals(s)) {flag=1;break;}
}
if(flag==1)return false;
else return true;
}
}
Format of stored string: First Character: W-Player1 Win.. L-Player2 Win.. T-Tie next 9 characters represent board layout: 211012012 represents
2 1 1
0 1 2
0 1 2
Note that 0 is for position still not filled by any player. As we can see Player1 wins in above game so the string is stored is W211012012.
Theoretically this method should generate all possible unique combinations(255168), but it is not. It generates 958 combinations and then the program is just stuck.
Actually I think you should be happy to know that 958 is the correct answer for the number of legal endgame states.
https://archive.ics.uci.edu/ml/machine-learning-databases/tic-tac-toe/tic-tac-toe.names
255168 is correct when you keep track of the order of each player's moves -- not just the final end state. You are computing the valid final end game states.
Take your example of W211012012. There are 108 ways to accomplish W211012012 when considering the order of each player's moves. Player 1's top right move can't be last and other 3 moves can be in any order for 3*3!. Player 2's three moves can be in any order for 3!. 108=3*3!*3!.
If instead you want to calculate all 255168 combinations when the order of the moves matters consider representing your state strings differently. Maybe [WLT](1,row,col)(2,row,col)(1,row,col)... or any other way that would encode the order of the moves.
You are simulating all possible games by having 2 players play randomly and keeping track of unique games. That's one way to do it, and a good exercise, but not particularly efficient. You could also use a searching algorithm like DFS https://en.m.wikipedia.org/wiki/Depth-first_search to explore the search space.