java - 卡在 958 个组合上

Question

我正在尝试用 Java 设计一个 Tic-Tac-Toe 游戏。我必须指出，我是一个完全的 Java 初学者。所以我试图生成游戏的所有可能的组合，然后将其存储在一个文件中。我们知道有 255168 种可能的组合。无论如何，这是我的代码:

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

存储字符串的格式:第一个角色:W-Player1 Win.. L-Player2 Win.. T-Tie接下来的 9 个字符代表电路板布局:211012012代表

2 1 1
0 1 2
0 1 2

请注意，0 表示尚未被任何玩家填补的位置。正如我们所看到的，玩家 1 在上面的游戏中获胜，因此存储的字符串是 W211012012。

理论上，此方法应该生成所有可能的唯一组合(255168)，但事实并非如此。它生成 958 种组合，然后程序就卡住了。

Answer 1

实际上，我认为您应该很高兴知道 958 是合法残局状态数量的正确答案。

https://archive.ics.uci.edu/ml/machine-learning-databases/tic-tac-toe/tic-tac-toe.names

当您跟踪每个玩家的移动顺序(而不仅仅是最终状态)时，255168 是正确的。您正在计算有效的最终游戏状态。

以 W211012012 为例。考虑到每个玩家的移动顺序，有 108 种方法可以实现 W211012012。玩家 1 的右上一步不能是最后一步，其他 3 步可以按任意顺序进行 3*3!。玩家 2 的三步 Action 可以按任意顺序进行 3!。 108=3*3!*3!.

如果您想在移动顺序很重要时计算所有 255168 个组合，请考虑以不同的方式表示您的状态字符串。也许[WLT](1,row,col)(2,row,col)(1,row,col)...或任何其他对移动顺序进行编码的方式。

您通过让 2 名玩家随机玩并跟踪独特的游戏来模拟所有可能的游戏。这是一种方法，也是一种很好的练习，但不是特别有效。您还可以使用 DFS https://en.m.wikipedia.org/wiki/Depth-first_search 等搜索算法探索搜索空间。