Java 极小极大算法的井字游戏问题
Java tictactoe problems with minmax algorithm
我想为 tictactoe 实现 MinMax 算法。我有两种方法
min() 和 max() 以及评估方法,但它不起作用。例如当我打电话给
max(9);
Field[bestCol][bestRow]='O';
min(8);
Field[bestCol][bestRow]='X';
在主函数中结果是
OX-
---
---
但玩家 'X' 的最佳移动是将 'X' 放在中间。
这是我的代码,没有评估方法:
static char[][] Field = { { '-', '-', '-' },
{ '-', '-', '-' },
{ '-', '-', '-' } };
static char Player = 'O';
static char Computer = 'X';
static int Depth =9; // searchdepth
static int bestRow=0, bestCol=0; // best Move
public static int max(int depth) {
if (depth == 0) {
return evaluateMove();
}
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (Field[i][j] == '-') {
Field[i][j] = Computer;
int value = min(depth - 1);
Field[i][j] ='-';
if (value > maxValue) {
maxValue = value;
if (depth == Depth) {
bestCol=i;
bestRow=j;
}
}
}
}
}
return maxValue;
}
public static int min(int depth) {
int minValue = Integer.MAX_VALUE;
if (depth == 0) {
return evaluateMove();
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (Field[i][j] == '-') {
Field[i][j] = Player;
int value = max(depth - 1);
Field[i][j] = '-';
if (value < minValue) {
minValue = value;
bestCol=i;
bestRow=j;
}
}
}
}
return minValue;
}
此致
编辑:
感谢您的回答。对于第一点,我忘记将'*'更改为'-'这是我的评估方法:
public static int evaluateMove() {
for(int i=0; i<3; i++) {
int countX=0; int countY=0;
for(int j=0; j<3; j++) {
if(Feld[i][j]==Computer) countX++;
if(Feld[i][j]==Player) countY++;
}
if(countX==3) return 10;
if(countY==3) return -10;
}
for(int j=0; j<3; j++) { // Spalten
int countX=0; int countY=0;
for(int i=0; i<3; i++) {
if(Feld[i][j]==Computer) countX++;
if(Feld[i][j]==Player) countY++;
if(countX==3) return 10;
if(countY==3) return -10;
}
}
return 0; // Unentschieden
}
一些让我印象深刻的事情:
- 您正在用“-”初始化运动场的空方块,但在 min/max-functions 中您假设“*”是空方块
- 在 min-function 中,与 max-function 相反,您在每个级别而不是顶层设置最佳移动,因此更深的级别将覆盖顶层的最佳结果(所以我认为你还应该检查 depth==Depth)
- 我不知道你在 main 中做了什么,但也应该在每次移动后递减 "Depth",因为这定义了顶层(因此应该分配最佳移动的级别),并且根据你的问题,你在每次调用时递减 "depth" 参数
- 我猜你知道只有递归到游戏结束才能得到最佳结果(这是每一步后递减深度和深度的另一个论点)
- 您没有在 evaluateMove 函数中检查对角线
- 在 evaluateMove 的第二个双循环中,您检查了最内层循环内 countX、countY 的条件(有效,但令人恼火的是它与第一个双循环不同 => 不太适合查找错误)
编辑: 最后(击鼓...):
- 在第一步中,您 最大化 增益(对于计算机移动 ('X'))但您实际上执行了玩家移动 ('O') .对于第二步反之亦然。但是,您必须最小化第一步的收益(这意味着玩家获胜)并最大化第二步的收益。
也就是你实际做的事情:
public static void ComputeAndExecuteBestMove()
{
// since Player begins, we minimize the gain value for the first move
if ((MaxDepth-Depth) % 2 == 0)
{
max(Depth);
Field[bestCol,bestRow] = Player;
}
else
{
min(Depth);
Field[bestCol,bestRow] = Computer;
}
// next move
Depth--;
}
但是你应该做什么:
public static void ComputeAndExecuteBestMove()
{
// since Player begins, we minimize the gain value for the first move
if ((MaxDepth-Depth) % 2 == 0)
{
min(Depth);
Field[bestCol,bestRow] = Player;
}
else
{
max(Depth);
Field[bestCol,bestRow] = Computer;
}
// next move
Depth--;
}
我想为 tictactoe 实现 MinMax 算法。我有两种方法 min() 和 max() 以及评估方法,但它不起作用。例如当我打电话给
max(9);
Field[bestCol][bestRow]='O';
min(8);
Field[bestCol][bestRow]='X';
在主函数中结果是
OX-
---
---
但玩家 'X' 的最佳移动是将 'X' 放在中间。
这是我的代码,没有评估方法:
static char[][] Field = { { '-', '-', '-' },
{ '-', '-', '-' },
{ '-', '-', '-' } };
static char Player = 'O';
static char Computer = 'X';
static int Depth =9; // searchdepth
static int bestRow=0, bestCol=0; // best Move
public static int max(int depth) {
if (depth == 0) {
return evaluateMove();
}
int maxValue = Integer.MIN_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (Field[i][j] == '-') {
Field[i][j] = Computer;
int value = min(depth - 1);
Field[i][j] ='-';
if (value > maxValue) {
maxValue = value;
if (depth == Depth) {
bestCol=i;
bestRow=j;
}
}
}
}
}
return maxValue;
}
public static int min(int depth) {
int minValue = Integer.MAX_VALUE;
if (depth == 0) {
return evaluateMove();
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (Field[i][j] == '-') {
Field[i][j] = Player;
int value = max(depth - 1);
Field[i][j] = '-';
if (value < minValue) {
minValue = value;
bestCol=i;
bestRow=j;
}
}
}
}
return minValue;
}
此致
编辑:
感谢您的回答。对于第一点,我忘记将'*'更改为'-'这是我的评估方法:
public static int evaluateMove() {
for(int i=0; i<3; i++) {
int countX=0; int countY=0;
for(int j=0; j<3; j++) {
if(Feld[i][j]==Computer) countX++;
if(Feld[i][j]==Player) countY++;
}
if(countX==3) return 10;
if(countY==3) return -10;
}
for(int j=0; j<3; j++) { // Spalten
int countX=0; int countY=0;
for(int i=0; i<3; i++) {
if(Feld[i][j]==Computer) countX++;
if(Feld[i][j]==Player) countY++;
if(countX==3) return 10;
if(countY==3) return -10;
}
}
return 0; // Unentschieden
}
一些让我印象深刻的事情:
- 您正在用“-”初始化运动场的空方块,但在 min/max-functions 中您假设“*”是空方块
- 在 min-function 中,与 max-function 相反,您在每个级别而不是顶层设置最佳移动,因此更深的级别将覆盖顶层的最佳结果(所以我认为你还应该检查 depth==Depth)
- 我不知道你在 main 中做了什么,但也应该在每次移动后递减 "Depth",因为这定义了顶层(因此应该分配最佳移动的级别),并且根据你的问题,你在每次调用时递减 "depth" 参数
- 我猜你知道只有递归到游戏结束才能得到最佳结果(这是每一步后递减深度和深度的另一个论点)
- 您没有在 evaluateMove 函数中检查对角线
- 在 evaluateMove 的第二个双循环中,您检查了最内层循环内 countX、countY 的条件(有效,但令人恼火的是它与第一个双循环不同 => 不太适合查找错误)
编辑: 最后(击鼓...):
- 在第一步中,您 最大化 增益(对于计算机移动 ('X'))但您实际上执行了玩家移动 ('O') .对于第二步反之亦然。但是,您必须最小化第一步的收益(这意味着玩家获胜)并最大化第二步的收益。
也就是你实际做的事情:
public static void ComputeAndExecuteBestMove()
{
// since Player begins, we minimize the gain value for the first move
if ((MaxDepth-Depth) % 2 == 0)
{
max(Depth);
Field[bestCol,bestRow] = Player;
}
else
{
min(Depth);
Field[bestCol,bestRow] = Computer;
}
// next move
Depth--;
}
但是你应该做什么:
public static void ComputeAndExecuteBestMove()
{
// since Player begins, we minimize the gain value for the first move
if ((MaxDepth-Depth) % 2 == 0)
{
min(Depth);
Field[bestCol,bestRow] = Player;
}
else
{
max(Depth);
Field[bestCol,bestRow] = Computer;
}
// next move
Depth--;
}