当前位置: 首页 > 知识库问答 >
问题:

Tic-Tac-Toe minimax算法不适用于4x4板

司马振国
2023-03-14

所以我在过去的三周里一直在做这个项目。我很早就设法让minimax函数在3x3板上工作,但是当我尝试在4x4板上使用它时,问题开始出现,即Java堆空间错误。从那时起,在Alpha-beta修剪的帮助下,我成功地从aprox中减少了minimax函数中所需的minimax调用的数量。59000到16000到11000,最后是8000次呼叫(这是假设一个插槽已填满的电路板的初始minimax呼叫)。然而,现在的问题是,该方法只在4x4游戏中运行。它只是不停地叫自己,没有错误,没有结果,什么都没有。理论上,在我看来,我的函数应该适用于任意大小的电路板,唯一的问题是内存。现在,由于我已经大大减少了我函数的内存贪婪,我希望它能工作。嗯,3x3是这样的。但是,它不适用于4x4。函数作用的简要说明:函数返回一个大小为2的数组,其中包含所有可能的下一步动作中最有利的下一步动作,以及预期从该动作中获得的分数。评分系统很简单。O赢10分,X赢10分,平局0分。这个函数当然是递归的。在它里面,你会发现某些快捷方式,可以减少对自身的调用次数。例如,如果轮到X,返回的分数为-10(这是X的最佳分数),则退出循环,即停止观察该状态下的其他潜在移动。下面是类状态的代码:

private String [] state;    //Actual content of the board
private String turn;        //Whose turn it is
private static int n;       //Size of the board

public State(int n) {
    state = new String[n*n];
    for(int i = 0; i < state.length; i++) {
        state[i] = "-";
    }
    State.n = n;
}


public int[] newminimax47(int z) {
    int bestScore = (turn == "O") ? +9 : -9;    //X is minimizer, O is maximizer
    int bestPos = -1;
    int currentScore;
    int lastAdded = z;
    if(isGameOver() != "Not Gameover") {
        bestScore= score();
    }
    else {
        int i = 0;
        for(int x:getAvailableMoves()) {
            if(turn == "X") {   //X is minimizer
                setX(x);
                currentScore = newminimax47(x)[0];
                if(i == 0) {
                    bestScore = currentScore;
                    bestPos = x;
                    if(bestScore == -10)
                        break;
                }
                else if(currentScore < bestScore) {
                    bestScore = currentScore;
                    bestPos = x;
                    if(bestScore == -10)
                        break;
                }
            }
            else if(turn == "O") {  //O is maximizer
                setO(x);
                currentScore = newminimax47(x)[0];
                if(i == 0) {
                    bestScore = currentScore;
                    bestPos = x;
                    if(bestScore == 10)
                        break;
                }

                else if(currentScore > bestScore) {
                    bestScore = currentScore;
                    bestPos = x;
                    if(bestScore == 10)
                        break;
                }
            }
            i++;
        }
    }
    revert(lastAdded);
    return new int [] {bestScore, bestPos};
}

newMiniax47()使用的补充函数:

isGameOver():

public String isGameOver() {
    if(n == 3) {
        //Rows 1 to 3
        if((state[0] != "-") && (state[0] == state[1]) && (state[1] == state[2]))
            return (state[0] == "X") ? "X Won" : "O Won";
        else if((state[3] != "-") && (state[3] == state[4]) && (state[4] == state[5]))
            return (state[3] == "X") ? "X Won" : "O Won";
        else if((state[6] != "-") && (state[6] == state[7]) && (state[7] == state[8]))
            return (state[6] == "X") ? "X Won" : "O Won";

        //Columns 1 to 3
        else if((state[0] != "-")&&(state[0] == state[3]) && (state[3] == state[6]))
            return (state[0] == "X") ? "X Won" : "O Won";
        else if((state[1] != "-") && (state[1] == state[4]) && (state[4] == state[7]))
            return (state[1] == "X") ? "X Won" : "O Won";
        else if((state[2] != "-") && (state[2] == state[5]) && (state[5] == state[8]))
            return (state[2] == "X") ? "X Won" : "O Won";

        //Diagonals
        else if((state[0] != "-") && (state[0]==state[4]) && (state[4] == state[8]))
            return (state[0] == "X") ? "X Won" : "O Won";
        else if((state[6] != "-") && (state[6] == state[4]) && (state[4] == state[2]))
            return (state[6] == "X") ? "X Won" : "O Won";

        //Checking if draw
        else if((state[0] != "-") && (state[1]!="-") && (state[2] != "-") && (state[3]!="-") &&
                (state[4] != "-") && (state[5] != "-") && (state[6] != "-") && (state[7] != "-") &&
                (state[8] != "-"))
            return "Draw";
        else
            return "Not Gameover";
    }
    else {
        //Rows 1 to 4
        if((state[0] != "-") && (state[0] == state[1]) && (state[1] == state[2]) && (state[2] == state[3]))
            return (state[0] == "X") ? "X Won" : "O Won";
        else if((state[4] != "-") && (state[4] == state[5]) && (state[5]==state[6]) && (state[6] == state[7]))
            return (state[4] == "X") ? "X Won" : "O Won";
        else if((state[8] != "-") && (state[8] == state[9]) && (state[9]==state[10]) && (state[10] == state[11]))
            return (state[8] == "X") ? "X Won" : "O Won";
        else if((state[12] != "-") && (state[12] == state[13]) &&(state[13] == state[14]) && (state[14] == state[15]))
            return (state[12] == "X") ? "X Won" : "O Won";

        //Columns 1 to 4
        else if((state[0] != "-") && (state[0] == state[4]) && (state[4] == state[8]) && (state[8] == state[12]))
            return (state[0] == "X") ? "X Won" : "O Won";
        else if((state[1] != "-") && (state[1] == state[5]) && (state[5] == state[9]) && (state[9] == state[13]))
            return (state[1] == "X") ? "X Won" : "O Won";
        else if((state[2] != "-") && (state[2] == state[6]) && (state[6] == state[10]) && (state[10] == state[14]))
            return (state[2] == "X") ? "X Won" : "O Won";
        else if((state[3] != "-") && (state[3] == state[7]) && (state[7] == state[11]) && (state[11] == state[15]))
            return (state[3] == "X") ? "X Won" : "O Won";

        //Diagonale
        else if((state[0] != "-") && (state[0] == state[5]) && (state[5] == state[10]) && (state[10] == state[15]))
            return (state[0] == "X") ? "X Won" : "O Won";
        else if((state[12] != "-") && (state[12] == state[9]) &&  (state[9] == state[6]) && (state[6] == state[3]))
            return (state[0] == "X") ? "X Won" : "O Won";

        //Pruefe ob Gleichstand
        else if((state[0] != "-") && (state[1] != "-") && (state[2] != "-") && (state[3]!="-") &&
                (state[4] != "-") && (state[5] != "-") && (state[6] != "-") && (state[7] != "-") &&
                (state[8] != "-") && (state[9] != "-") && (state[10] != "-") && (state[11] != "-") &&
                (state[12] != "-") && (state[13] != "-") && (state[14] != "-") && (state[15] != "-")) 
            return "Draw";
        else
            return "Not Gameover";
    }   
}

请原谅isGameover()方法的直白,它只是检查董事会的状态(即。赢,平局,游戏没有结束)

getAvailableMoves()方法:

public int[] getAvailableMoves() {
    int count = 0;
    int i = 0;
    for(int j = 0; j < state.length; j++) {
        if(state[j] == "-")
            count++;
    }
    int [] availableSlots = new int[count];
    for(int j = 0; j < state.length; j++){
        if(state[j] == "-")
            availableSlots[i++] = j;        
    }
    return availableSlots;
}

此方法仅返回一个包含所有可用下一步移动(关于当前状态)的整数数组,或者如果没有可用移动或游戏结束,则返回空数组。

得分()方法:

public int score() {
    if(isGameOver() == "X Won")
        return -10;
    else if(isGameOver() == "O Won")
        return +10;
    else 
        return 0;
}
public void setX(int i) {
    state[i] = "X";
    turn = "O";
    lastAdded = i;
}
public void setO(int i) {
    state[i] = "O";
    turn = "X";
    lastAdded = i;
}
public void revert(int i) {
    state[i] = "-";
    if(turn == "X")
        turn = "O";
    else
        turn = "X";
}

对于3x3游戏,我的主要方法如下:

public static void main(String args[]) {
    State s = new State(3);
    int [] ScoreAndRecommendedMove = new int[2];
    s.setX(8);
    ScoreAndRecommendedMove = s.newminimax47(8);
    System.out.println("Score: "+ScoreAndRecommendedMove[0]+" Position: "+ ScoreAndRecommendedMove[1]);
}

在这个游戏中,X在位置8开始游戏。本例中的方法将返回

Score: 0 Position: 4  

这意味着O最有希望的移动是在位置4,在最坏的情况下会产生0分(即平局)。

在这种情况下,最终返回到状态1的分数和位置将是

Score: 0 Position: 6

来自8号州。

注意:您看到的代码只是实际状态类的片段。这些代码片段本身应该允许您重新创建和使用newminimax47函数,而不会出现问题(至少对于3x3)。您可能发现的任何bug都不是真正的bug,它们只是没有包含在我复制的代码片段中,代码应该可以在没有它们的情况下工作。例如,setO和setX函数中最后添加的变量没有包含在这里的代码片段中,但我刚刚意识到,您不需要它来处理minimax函数,所以您可以将其注释掉。

共有2个答案

穆毅然
2023-03-14

正如用户3386109所解释的,这里的问题是计算所有内容的次数。但是,考虑到N大小的网格,有一些事情可能会对您有所帮助:

  • 如果用户的符号少于N个,则用户无法获胜,因此您可以在iGameOver函数中使用该符号作为第一次检查
  • 你要做的第一件事是阻止你的对手获胜,如果他的下一步有可能获胜
  • 通过每次移动递增计数器,跟踪每行、每列以及两条对角线中的“X”和“O”数量。如果有N-1个相同的符号,下一个将是你或你的对手获胜的一步
  • 通过这样做,您可以轻松判断哪一步是最好的,因为:
    • 如果你有一个成功的动作,你就把符号放在那里
    • 检查你的对手,如果他在同一行/列/对角线上有N-1个符号,你就把它放在那里
    • 如果你的对手在某个位置上的符号比你多,那么你可以将该位置平分(这意味着1或2,取决于谁开始比赛)
    • 如果不是这样,则将下一个符号放在行/列/对角线上,在该行/列/对角线上有更多符号
    • 如果你在某些地方有相同数量的符号,你只需把它放在对手有更多符号的地方
    • 如果你和你的对手是完全平等的,那就采取你自己的策略吧(我想随机也不错:-)

    除非您真的需要它(例如作为家庭作业),否则我不会对这个使用递归

    作为旁注:我认为让布尔函数返回一个字符串,然后将其与固定值进行比较不是一种好的做法。在我看来,isGameOver函数的真/假返回值要好得多。

秦昊穹
2023-03-14

我玩了你的代码,有很多话要说

缺陷

首先有一个bug。我认为你的代码在3x3板上不起作用。问题是您还原添加到板上的移动的位置。您在newminimax47方法的末尾执行此操作一次,即使在该方法中,您将移动添加到for循环内的电路板。这意味着调用该方法不仅会计算某些内容,还会更改电路板状态,而代码的其余部分希望它不会这样做。

因此,删除还原现在所在的位置,并尽快还原:

setX(x);                                                                                                                                                                                                                                             
currentScore = newminimax47(x)[0];                           
revert(x);       

这也意味着您不需要lastAdded变量。

播放

如果你真的和自己的算法对抗,就更容易看到发生了什么。向State类添加方法

public void dump() {                                                        
    for (int y = 0; y < n; y++) {                                           
        for (int x = 0; x < n; x++) {                                       
            System.out.print(state[y * n + x]);                             
        }                                                                   
        System.out.println();                                               
    }                                                                       
}

在你看来,主要是

public void play() {                                                        
    State s=new State(3);                                                   
    Scanner in = new Scanner (System.in);                                   
    while (s.isGameOver().equals("Not Gameover")) {                         
        int[] options = s.getAvailableMoves();                              
        s.dump();                                                           
        System.out.println ("Your options are " + Arrays.toString(options));
        int move = in.nextInt();                                            
        s.setX(move);                                                       
        int [] ScoreAndRecommendedMove=new int[2];                          
        ScoreAndRecommendedMove=s.newminimax47(0);                           
        System.out.println("Score: "+ScoreAndRecommendedMove[0]+" Position: "+ ScoreAndRecommendedMove[1]);
        s.setO(ScoreAndRecommendedMove[1]);                                 
    }                                                                       
    s.dump();                                                               
}

你可以和它对抗。在3x3板上,这对我来说很好。不幸的是,我估计在4x4上计算第一步大约需要48小时。

数据类型

你对数据类型的选择往往有点...奇怪。如果要记住单个字符,请使用char而不是String。如果要返回是/否决定,请尝试使用布尔值。程序中也有一些部分可以被执行相同操作的更少代码替换。但那不是你的问题,所以...

算法

好的,那么用minimax来解决这个问题有什么问题呢?假设前四个移动是X5、O8、X6O7。另一种可能是以X5、O7、X6、O8开始游戏。还有一个是X6,O7,X5,O8。最后是X6,O8,X5,O7。

游戏前四步的所有四种可能导致完全相同的游戏状态。但是minimax无法识别它们是相同的(基本上没有并行分支的内存),因此它将计算它们全部四个。如果搜索得更深,每个板状态的计算次数将迅速增加。

可能的游戏数量远远超过可能的棋盘州数量。估计游戏数量:首先有16个可能的动作,然后是15个,然后是14个,13个。。。等等粗略估计是16!,虽然minimax不必计算所有的,因为很多都会在第16步之前完成。

对游戏状态数量的估计是:棋盘上的每个方块可以是空的,也可以是X或O。所以这是3^16个棋盘。并不是所有的板都是有效的,因为板上的X数最多可以比O数多一个,但仍然接近3^16。

16个!可能的游戏比3^16个可能的棋盘状态多50万倍。这意味着我们大约计算每一块板50万次,而不是一次。

解决方法是开始记住你计算的每个游戏状态。每次调用递归函数时,首先检查您是否已经知道答案,如果已经知道,则返回旧答案。这是一种叫做记忆的技术。

回忆录

我将描述如何在使用您已经选择的数据结构时添加备忘录(尽管我不同意)。要进行备忘,您需要一个可以快速添加和快速查找的集合。列表(例如ArrayList)对我们没有任何好处。添加值很快,但在长列表中查找很慢。有一些选项,但最容易使用的是HashMap。为了使用HashMap,您需要创建一些表示您的状态的内容,并可以将其用作密钥。最直接的方法是制作一个字符串,其中包含代表您的电路板的所有X/O/-符号。

所以加上

Map<String,int[]> oldAnswers = new HashMap<String,int[]>();                                                                  

到您的State对象。

然后在你的new最小化47方法的开始创建表示State的String,并检查我们是否已经知道答案:

    String stateString = "";                                                
    for (String field : state) stateString += field;                        
    int[] oldAnswer = oldAnswers.get(stateString);                          
    if (oldAnswer != null) return oldAnswer;

最后,当您计算一个新的答案newMiniax47的结尾时,您不仅应该返回它,还应该将其存储在map中:

    int[] answer = {bestScore, bestPos};                                    
    oldAnswers.put (stateString, answer);                                   
    return answer;

有了记忆,我可以和你的代码玩4x4游戏了。第一步仍然很慢(20秒),但在那之后,一切都被计算出来了,速度非常快。如果您想进一步加快速度,可以研究alpha-beta修剪。但这一进步不会像记忆化那么大。另一种选择是使用更高效的数据类型。它不会降低算法的理论顺序,但仍然可以轻松地使其速度提高5倍。

 类似资料:
  • 我做了一个Tic-Tac-Toe游戏,使用Minimax和Alpha-Beta修剪。我想为Tic-Tac-Toe(10x10)游戏制作一个计算机AI,但它的游戏树大得离谱。 我的代码是这样的,我只需要更改两个变量就可以更改一行中所需的板大小单元格。例子: 和 我希望你明白了。 所以,我把我的计划从10x10改为3x3,效果很好。 然后我改变和,使其成为(4x4)井字游戏。 现在,我认为使用Alph

  • 我正在尝试用alpha-beta剪枝实现一个用于tic-tac-toe的minimax算法。现在我有程序在运行,但它似乎不起作用。每当我运行它时,它似乎会在所有的方块中输入垃圾。我已经实现了它,所以我的minimax函数接受一个棋盘状态,并修改该状态,以便当它完成时,棋盘状态包含下一个最佳移动。然后,我将“this”设置为与修改后的电路板相等。以下是我的minimax算法函数: 如果有人想尝试运行

  • 我在C和一般编程方面是个新手,我想知道这段代码的性能/复杂性有多好,因为它与我在SO的其他帖子中发现的不同。for循环是否使这变得不必要的复杂?

  • 首先,我是java的初学者,我正在尝试模拟TicTacToe游戏。我想使用游戏树为所有状态创建一个可能的树。树中的每个节点都将代表状态并使用此树来决定下一步要做的事情。我计划按如下方式进行, > 接口类包括表示单个移动所需的信息。 抽象/接口类包括以下方法: a、 返回一个新的状态对象,该对象表示应用该移动后游戏的状态。 B.如果当前状态代表其中一名玩家的胜利,则此游戏的获胜者ID。 c、 返回当

  • 我该怎么做? 下面是我的代码: