Tic-Tac-Toe minimax算法不适用于4x4板
Oma*_*aki 4 java algorithm loops tic-tac-toe minimax
所以我过去3周一直在研究这个项目.我设法让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的最佳分数)然后退出循环,即停止观察来自该状态的其他潜在移动.这是类State的代码:它适用于3x3.但是,它不适用于4x4.函数功能的简要说明:该函数返回一个大小为2的数组,其中包含所有可能的下一步移动中最有利的下一步移动以及预期从该移动中获得的分数.评分系统很简单.O赢得+10,X赢得-10,平局0.该功能当然是递归的.在其中,您将找到某些快捷方式,可以减少对自身所需的调用次数.例如,如果它是X的转弯并且返回的分数是-10(这是X的最佳分数)然后退出循环,即停止观察来自该状态的其他潜在移动.这是类State的代码:它适用于3x3.但是,它不适用于4x4.函数功能的简要说明:该函数返回一个大小为2的数组,其中包含所有可能的下一步移动中最有利的下一步移动以及预期从该移动中获得的分数.评分系统很简单.O赢得+10,X赢得-10,平局0.该功能当然是递归的.在其中,您将找到某些快捷方式,可以减少对自身所需的调用次数.例如,如果它是X的转弯并且返回的分数是-10(这是X的最佳分数)然后退出循环,即停止观察来自该状态的其他潜在移动.这是类State的代码:该函数返回一个大小为2的数组,其中包含所有可能的下一个移动中最有利的下一步移动以及预期从该移动中获得的分数.评分系统很简单.O赢得+10,X赢得-10,平局0.该功能当然是递归的.在其中,您将找到某些快捷方式,可以减少对自身所需的调用次数.例如,如果它是X的转弯并且返回的分数是-10(这是X的最佳分数)然后退出循环,即停止观察来自该状态的其他潜在移动.这是类State的代码:该函数返回一个大小为2的数组,其中包含所有可能的下一个移动中最有利的下一步移动以及预期从该移动中获得的分数.评分系统很简单.O赢得+10,X赢得-10,平局0.该功能当然是递归的.在其中,您将找到某些快捷方式,可以减少对自身所需的调用次数.例如,如果它是X的转弯并且返回的分数是-10(这是X的最佳分数)然后退出循环,即停止观察来自该状态的其他潜在移动.这是类State的代码:该功能当然是递归的.在其中,您将找到某些快捷方式,可以减少对自身所需的调用次数.例如,如果它是X的转弯并且返回的分数是-10(这是X的最佳分数)然后退出循环,即停止观察来自该状态的其他潜在移动.这是类State的代码:该功能当然是递归的.在其中,您将找到某些快捷方式,可以减少对自身所需的调用次数.例如,如果它是X的转弯并且返回的分数是-10(这是X的最佳分数)然后退出循环,即停止观察来自该状态的其他潜在移动.这是类State的代码:
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()方法的直率,它只是检查板的状态(即Win,Draw,Game not Over)
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;
}
此方法仅返回具有所有可用下一步移动的int数组(关于当前状态),或者如果没有可用移动或游戏结束则返回空数组.
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位移动游戏.本例中的方法将返回
Score: 0 Position: 4
意味着O最有希望的举动是在第4位,在最坏的情况下将得到0分(即平局).
下图是为了说明newminimax47()的工作原理.在这种情况下,我们的起始状态(板)被赋予数字1.注意:数字表示创建被认为状态的优先级.1创建在2之前,2创建在3之前,3创建在4之前,依此类推.
在这种情况下,得分和位置最终将返回到状态1
Score: 0 Position: 6
来自州8.
注意:您看到的代码只是实际State类的片段.这些片段本身应该允许你重新创建和使用newminimax47函数没有问题(至少3x3).您可能发现的任何错误都不是真正的错误,它们根本没有包含在我复制的代码段中,代码应该在没有它们的情况下工作.例如,setO和setX函数中的lastAdded变量不包含在这里的片段中,但我刚刚意识到你不需要它能够使用minimax函数,所以你可以只是注释掉它.
我玩了你的代码,还有很多话要说
窃听器
首先是一个bug.我不认为你的代码实际上适用于3x3板.问题是revert您添加到电路板的位置.您只需在newminimax47方法结束时执行此操作一次,即使在添加的方法中移动到for循环内的板.这意味着调用该方法不仅会计算某些内容,还会更改板状态,而其余代码则不会这样做.
因此revert,请尽快删除现在的位置并尽快恢复:
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.如果您想返回是/否决定,请尝试使用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个可能的棋盘状态的五十倍.这意味着我们大约计算每个电路板的半个月而不是一次.
解决方案是开始记住您计算的每个游戏状态.每次调用递归函数时,首先检查您是否已经知道答案,如果是,则返回旧答案.这是一种称为memoization的技术.
记忆化
我将描述如何在使用您已选择的数据结构时添加memoization(即使我不同意它们).要进行记忆,您需要一个集合,您可以在其上快速添加和快速查找.列表(例如ArrayList)对我们没有好处.添加值很快,但在长列表中进行查找非常慢.有一些选择,但最容易使用的是HashMap.为了使用HashMap你需要创建代表你的状态的东西,你可以用作一个关键.最简单的方法就是用一个String代表你的电路板的所有X/O/ - 符号.
所以加
Map<String,int[]> oldAnswers = new HashMap<String,int[]>();
对你的State对象.
然后在您的newminimax47方法开始时创建表示State的String并检查我们是否已经知道答案:
String stateString = "";
for (String field : state) stateString += field;
int[] oldAnswer = oldAnswers.get(stateString);
if (oldAnswer != null) return oldAnswer;
最后,当你计算一个新的答案时,newminimax47你不应该只返回它,而是将它存储在地图中:
int[] answer = {bestScore, bestPos};
oldAnswers.put (stateString, answer);
return answer;
随着记忆的到位,我能够对你的代码进行4x4游戏.第一步仍然很慢(20秒),但之后计算的一切都非常快.如果你想进一步加快速度,可以考虑进行alpha beta修剪.但改进不会像记忆那样接近.另一种选择是使用更有效的数据类型.它不会降低算法的理论顺序,但仍然可以轻松地使其快5倍.
| 归档时间： |
|
| 查看次数： |
1846 次 |
| 最近记录： |