Tic-Tac-Toe minimax 算法不适用于 4x4 棋盘
Tic-Tac-Toe minimax algorithm doesn't work with 4x4 board
所以我过去 3 周一直在从事这个项目。我设法让 minimax 函数在 3x3 板的早期工作，但是当我尝试将它用于 4x4 板时，问题开始出现，即 Java 堆 space 错误。从那时起，在 Alpha beta 剪枝的帮助下，我设法减少了 aprox 的 minimax 函数中所需的 minimax 调用次数。 59000 到 16000 到 11000，然后最后到 8000 次调用（这是假设一个初始 minimax 调用已经填充了一个插槽的板）。然而，现在的问题是该方法只为 4x4 游戏保留 运行。它只是不停地自称，没有错误，没有结果，什么都没有。从理论上讲，按照我的看法，我的函数应该适用于任意尺寸的电路板，唯一的问题是内存。现在，因为我已经大大减少了我的函数的内存贪婪，所以我希望它能工作。好吧，它适用于 3x3。但是，它不适用于 4x4。
函数作用的简要说明：
函数 return 是一个大小为 2 的数组，其中包含从所有可能的下一步行动中最有利的下一步行动以及预计从该行动中获得的分数。评分系统很简单。 O 赢+10，X 赢-10，平局0。该函数当然是递归的。在其中，您会发现某些快捷方式可以减少对自身的调用次数。例如，如果轮到 X 并且 returned 得分为 -10（这是 X 的最佳得分），则退出循环，即停止观察此状态的其他潜在移动。这是 class 州的代码：
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};
}
newminimax47() 使用的互补函数：
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;
}
此方法只是 return 一个包含所有可用下一步动作（关于当前状态）的 int 数组，或者 return 如果没有可用动作或游戏结束，则为空数组。
score() 方法：
public int score() {
if(isGameOver() == "X Won")
return -10;
else if(isGameOver() == "O Won")
return +10;
else
return 0;
}
setO()、setX() 和 revert()：
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号位置开始了游戏。这种情况下的方法将return
Score: 0 Position: 4
这意味着 O 最有希望的着法是在位置 4 并且在最坏的情况下会产生 0 分（即平局）。
下图旨在让您了解 newminimax47() 的工作原理。在这种情况下，我们的起始状态（棋盘）的编号为 1。注意：数字表示创建相关状态的优先级。 1在2之前创建，2在3之前创建，3在4之前创建等等。
在这种情况下，最终 return 状态 1 的分数和位置将是
Score: 0 Position: 6
来自州 8。
注意：您看到的代码只是实际状态的片段 class。这些片段本身应该允许您毫无问题地重新创建和使用 newminimax47 函数（至少对于 3x3）。您可能发现的任何错误都不是真正的错误，它们只是不包含在我在此处复制的代码片段中，代码应该可以在没有它们的情况下工作。例如，setO 和 setX 函数中的 lastAdded 变量未包含在此处的代码片段中，但我刚刚意识到您不需要它来使用 minimax 函数，因此您可以将其注释掉。
正如 user3386109 所解释的，这里的问题是你计算了多少次所有内容。考虑到 N 大小的网格，有几件事可能会对您有所帮助：
- 如果用户的符号少于 N 个，则用户无法获胜，因此您可以在 isGameOver 函数中使用它作为第一次检查
- 你要做的第一件事就是阻止你的对手获胜，如果他的下一步有可能获胜的话
- 通过每次移动递增计数器来跟踪每行和每列以及两条对角线中有多少 "X" 和 "O"。如果有 N-1 个相同的符号，则下一个将是您或您的对手的胜利。
- 通过这样做，您可以轻松判断哪一步是最佳着法，因为这样：
- 如果您有必胜棋步，请将符号放在那里
- 检查你的对手，如果他有 N-1 个符号 row/column/diagonal 你把它放在那里
- 如果你的对手在某个地方的符号比你多，你就会平局（这意味着 +1 或 +2，取决于谁开始游戏）
- 如果不是这种情况，您将下一个符号放在 row/colum/diagonal 上，那里有更多符号
- 如果你在某些地方有相同数量的符号，你就把它放在对手有更多符号的地方
- 如果你和你的对手完全相等，那就按照你自己的策略去做（我想随机也不错:-)）
除非你真的需要它（例如作为家庭作业），否则我不会为此使用递归。
顺便说一句：我认为让实际上是布尔函数的东西 return 是一个字符串，然后将其与固定值进行比较并不是一个好习惯。 isGameOver 函数的 true/false return 值对我来说看起来好多了。
我试过你的代码，有很多话要说
错误
首先有一个bug。我认为您的代码实际上不适用于 3x3 板。问题是你 revert 你添加到棋盘上的动作的位置。您在 newminimax47 方法的末尾只执行一次此操作，即使在该方法中您在 for 循环内向棋盘添加移动也是如此。这意味着调用该方法不仅会计算某些内容，还会更改棋盘状态，其余代码预计不会。
所以删除 revert 现在所在的位置，并尽快还原：
setX(x);
currentScore = newminimax47(x)[0];
revert(x);
这也意味着您不需要 lastAdded 变量。
播放
如果您真正与自己的算法对战，就会更容易看到发生了什么。向您的状态添加方法 class
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();
}
}
在你的 main 里有像
这样的东西
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。如果您想 return 一个 yes/no 决定，请尝试使用 boolean。程序的某些部分也可以用更少的代码来代替。但这不是你的问题，所以...
算法
好的，那么minimax解决这个问题有什么问题呢？
假设前四步是X5、O8、X6 O7。另一种可能性是用 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 的数量最多可以比 Os 的数量多一个，但仍然接近 3^16。
16！可能的游戏大约是 3^16 种可能的棋盘状态的 50 万倍。这意味着我们大约计算每块板 50 万次，而不是一次。
解决方案是开始记住您计算的每个游戏状态。每次调用递归函数时，首先检查您是否已经知道答案，如果是，只需 return 旧答案。这是一种叫做 memoization.
的技术
记忆
我将描述如何在使用您已经选择的数据结构时添加记忆（即使我不同意它们）。要进行记忆，您需要一个集合，您可以在该集合上进行快速添加和快速查找。列表（例如 ArrayList）对我们没有任何好处。添加值很快，但在长列表中进行查找非常慢。有一些选项，但最容易使用的选项是 HashMap。为了使用 HashMap 你需要创建代表你的状态的东西，你可以用作键。最直接的方法是制作一个 String，其中包含代表您的棋盘的所有 X/O/- 符号。
所以添加
Map<String,int[]> oldAnswers = new HashMap<String,int[]>();
你的 State 对象。
然后在您的 newminimax47 方法的开头创建表示状态的字符串并检查我们是否已经知道答案：
String stateString = "";
for (String field : state) stateString += field;
int[] oldAnswer = oldAnswers.get(stateString);
if (oldAnswer != null) return oldAnswer;
最后，当您计算 newminimax47 末尾的新答案时，您不仅应该 return 它，还应该将它存储在地图中：
int[] answer = {bestScore, bestPos};
oldAnswers.put (stateString, answer);
return answer;
有了记忆，我就可以和你的代码玩 4x4 游戏了。第一步仍然很慢（20 秒），但之后一切都经过计算并且速度非常快。如果您想进一步加快速度，可以查看 alpha beta pruning。但改进不会像记忆那么多。另一种选择是使用更高效的数据类型。它不会降低算法的理论阶数，但仍可轻松使其速度提高 5 倍。
所以我过去 3 周一直在从事这个项目。我设法让 minimax 函数在 3x3 板的早期工作，但是当我尝试将它用于 4x4 板时，问题开始出现，即 Java 堆 space 错误。从那时起，在 Alpha beta 剪枝的帮助下，我设法减少了 aprox 的 minimax 函数中所需的 minimax 调用次数。 59000 到 16000 到 11000，然后最后到 8000 次调用（这是假设一个初始 minimax 调用已经填充了一个插槽的板）。然而，现在的问题是该方法只为 4x4 游戏保留 运行。它只是不停地自称，没有错误，没有结果，什么都没有。从理论上讲，按照我的看法，我的函数应该适用于任意尺寸的电路板，唯一的问题是内存。现在，因为我已经大大减少了我的函数的内存贪婪，所以我希望它能工作。好吧，它适用于 3x3。但是，它不适用于 4x4。 函数作用的简要说明： 函数 return 是一个大小为 2 的数组，其中包含从所有可能的下一步行动中最有利的下一步行动以及预计从该行动中获得的分数。评分系统很简单。 O 赢+10，X 赢-10，平局0。该函数当然是递归的。在其中，您会发现某些快捷方式可以减少对自身的调用次数。例如，如果轮到 X 并且 returned 得分为 -10（这是 X 的最佳得分），则退出循环，即停止观察此状态的其他潜在移动。这是 class 州的代码：
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};
}
newminimax47() 使用的互补函数：
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;
}
此方法只是 return 一个包含所有可用下一步动作（关于当前状态）的 int 数组，或者 return 如果没有可用动作或游戏结束，则为空数组。
score() 方法：
public int score() {
if(isGameOver() == "X Won")
return -10;
else if(isGameOver() == "O Won")
return +10;
else
return 0;
}
setO()、setX() 和 revert()：
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号位置开始了游戏。这种情况下的方法将return
Score: 0 Position: 4
这意味着 O 最有希望的着法是在位置 4 并且在最坏的情况下会产生 0 分（即平局）。
下图旨在让您了解 newminimax47() 的工作原理。在这种情况下，我们的起始状态（棋盘）的编号为 1。注意：数字表示创建相关状态的优先级。 1在2之前创建，2在3之前创建，3在4之前创建等等。
在这种情况下，最终 return 状态 1 的分数和位置将是
Score: 0 Position: 6
来自州 8。
注意：您看到的代码只是实际状态的片段 class。这些片段本身应该允许您毫无问题地重新创建和使用 newminimax47 函数（至少对于 3x3）。您可能发现的任何错误都不是真正的错误，它们只是不包含在我在此处复制的代码片段中，代码应该可以在没有它们的情况下工作。例如，setO 和 setX 函数中的 lastAdded 变量未包含在此处的代码片段中，但我刚刚意识到您不需要它来使用 minimax 函数，因此您可以将其注释掉。
正如 user3386109 所解释的，这里的问题是你计算了多少次所有内容。考虑到 N 大小的网格，有几件事可能会对您有所帮助：
- 如果用户的符号少于 N 个，则用户无法获胜，因此您可以在 isGameOver 函数中使用它作为第一次检查
- 你要做的第一件事就是阻止你的对手获胜，如果他的下一步有可能获胜的话
- 通过每次移动递增计数器来跟踪每行和每列以及两条对角线中有多少 "X" 和 "O"。如果有 N-1 个相同的符号，则下一个将是您或您的对手的胜利。
- 通过这样做，您可以轻松判断哪一步是最佳着法，因为这样：
- 如果您有必胜棋步，请将符号放在那里
- 检查你的对手，如果他有 N-1 个符号 row/column/diagonal 你把它放在那里
- 如果你的对手在某个地方的符号比你多，你就会平局（这意味着 +1 或 +2，取决于谁开始游戏）
- 如果不是这种情况，您将下一个符号放在 row/colum/diagonal 上，那里有更多符号
- 如果你在某些地方有相同数量的符号，你就把它放在对手有更多符号的地方
- 如果你和你的对手完全相等，那就按照你自己的策略去做（我想随机也不错:-)）
除非你真的需要它（例如作为家庭作业），否则我不会为此使用递归。
顺便说一句：我认为让实际上是布尔函数的东西 return 是一个字符串，然后将其与固定值进行比较并不是一个好习惯。 isGameOver 函数的 true/false return 值对我来说看起来好多了。
我试过你的代码，有很多话要说
错误
首先有一个bug。我认为您的代码实际上不适用于 3x3 板。问题是你 revert 你添加到棋盘上的动作的位置。您在 newminimax47 方法的末尾只执行一次此操作，即使在该方法中您在 for 循环内向棋盘添加移动也是如此。这意味着调用该方法不仅会计算某些内容，还会更改棋盘状态，其余代码预计不会。
所以删除 revert 现在所在的位置，并尽快还原：
setX(x);
currentScore = newminimax47(x)[0];
revert(x);
这也意味着您不需要 lastAdded 变量。
播放
如果您真正与自己的算法对战，就会更容易看到发生了什么。向您的状态添加方法 class
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();
}
}
在你的 main 里有像
这样的东西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。如果您想 return 一个 yes/no 决定，请尝试使用 boolean。程序的某些部分也可以用更少的代码来代替。但这不是你的问题，所以...
算法
好的，那么minimax解决这个问题有什么问题呢？ 假设前四步是X5、O8、X6 O7。另一种可能性是用 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 的数量最多可以比 Os 的数量多一个，但仍然接近 3^16。
16！可能的游戏大约是 3^16 种可能的棋盘状态的 50 万倍。这意味着我们大约计算每块板 50 万次，而不是一次。
解决方案是开始记住您计算的每个游戏状态。每次调用递归函数时，首先检查您是否已经知道答案，如果是，只需 return 旧答案。这是一种叫做 memoization.
的技术记忆
我将描述如何在使用您已经选择的数据结构时添加记忆（即使我不同意它们）。要进行记忆，您需要一个集合，您可以在该集合上进行快速添加和快速查找。列表（例如 ArrayList）对我们没有任何好处。添加值很快，但在长列表中进行查找非常慢。有一些选项，但最容易使用的选项是 HashMap。为了使用 HashMap 你需要创建代表你的状态的东西，你可以用作键。最直接的方法是制作一个 String，其中包含代表您的棋盘的所有 X/O/- 符号。
所以添加
Map<String,int[]> oldAnswers = new HashMap<String,int[]>();
你的 State 对象。
然后在您的 newminimax47 方法的开头创建表示状态的字符串并检查我们是否已经知道答案：
String stateString = "";
for (String field : state) stateString += field;
int[] oldAnswer = oldAnswers.get(stateString);
if (oldAnswer != null) return oldAnswer;
最后，当您计算 newminimax47 末尾的新答案时，您不仅应该 return 它，还应该将它存储在地图中：
int[] answer = {bestScore, bestPos};
oldAnswers.put (stateString, answer);
return answer;
有了记忆，我就可以和你的代码玩 4x4 游戏了。第一步仍然很慢（20 秒），但之后一切都经过计算并且速度非常快。如果您想进一步加快速度，可以查看 alpha beta pruning。但改进不会像记忆那么多。另一种选择是使用更高效的数据类型。它不会降低算法的理论阶数，但仍可轻松使其速度提高 5 倍。