我正在为我的AI类开发一个项目，我们需要实施深度限制的minimax搜索，然后在Ultimate Tic-Tac-Toe或Tic-Tac-Toe-Ception游戏中添加alpha-beta修剪。此版本的井字游戏是3x3游戏板的3x3游戏板。当您在SmallBoard上的一个空格中游戏时，您刚玩过的动作对应于对手要玩的下一个SmallBoard。我已经能够找到常规井字游戏的结果，但由于游戏规则，它们并不完全适用。
[如果您在左上方的棋盘中央玩游戏，那么下一个玩家将在bigBoard的中央棋盘游戏。提供了这两个动作的图片。红色是第一位球员。
Here's the picture of the first two moves
我们的麻烦在于我们的alpha-beta实现。
关于我们的深度最小极大搜索
我们的minimax实现似乎正常工作。当我们尝试实现alpha-beta时，我们的AI代理正确停止了功能。
我们的minimax实现代码如下：
function evaluateMove(outerX2, outerY2, innerX2, innerY2, depth, isAI, tempBoard)
{
var currentBoard = JSON.parse( JSON.stringify( tempBoard ));
var score = 0;
var bestScore = 0;
var playerZZ;
if (isAI) {
playerZZ = 2;
}
else {
playerZZ = 1;
}
if(checkForWin(2, JSON.parse( JSON.stringify( currentBoard )), outerX2, outerY2, innerX2, innerY2))
{
//AI wins
return 10;
}
if(checkForWin(1, JSON.parse( JSON.stringify( currentBoard )), outerX2, outerY2, innerX2, innerY2))
{
//Human wins
return -10;
}
else if (depth == 2) {
return 0;
}
if (checkForBoardWin(innerX2, innerY2, 1) || checkForBoardWin(innerX2, innerY2, 2))
{
if (isAI)
{
bestScore = -100;
for (var X = 0; X < 3; X++)
{
for (var Y = 0; Y < 3; Y++)
{
for (var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[X][Y][x][y] == 0 && !(checkForBoardWin(X, Y, 1) || checkForBoardWin(X, Y, 2)))
{
//JAKE: Broken here?
currentBoard[X][Y][x][y] = 2
score = evaluateMove(X, Y, x, y, depth + 1, false, currentBoard);
//var bestScore = -100;
if (score > bestScore)
{
console.log("Line 105: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
}
}
else
{
bestScore = 100;
for (var X = 0; X < 3; X++)
{
for (var Y = 0; Y < 3; Y++)
{
for (var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[X][Y][x][y] == 0)
{
currentBoard[X][Y][x][y] = 1
score = evaluateMove(X, Y, x, y, depth + 1, false, currentBoard);
//bestScore = 100;
if (score < bestScore)
{
console.log("Line 137: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
}
}
}
else
{
bestScore = -100;
if (isAI)
{
for(var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[innerX2][innerY2][x][y] == 0)
{
//JAKE: Broken here?
currentBoard[innerX2][innerY2][x][y] = 2
score = evaluateMove(innerX2, innerY2, x, y, depth + 1, false, currentBoard);
//bestScore = -100;
if (score > bestScore)
{
console.log("Line 169: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
else
{
bestScore = 100;
for(var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[innerX2][innerY2][x][y] == 0)
{
currentBoard[innerX2][innerY2][x][y] = 1
score = evaluateMove(innerX2, innerY2, x, y, depth + 1, true, currentBoard);
bestScore = 100;
if (score < bestScore)
{
console.log("Line 195: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
}
return 0;
}
关于我们的Alpha-Beta修剪实现：
我们的移动评估函数接受一些变量，X2和Y2组成了我们现在评估的bigBoard中的移动的四维数组坐标。我们遵循this wikipedia page中的伪代码。不幸的是，我们的AI一直位于左上角，直到没有其他选择可以这样做为止，在这种情况下，它一直位于木板的左侧。在过去的几天里，我和我的团队一直在努力工作。
代码如下。
function evaluateMove(outerX2, outerY2, innerX2, innerY2, depth, isAI, tempBoard)
{
var currentBoard = JSON.parse( JSON.stringify( tempBoard ));
var score = 0;
var bestScore = 0;
var playerZZ;
if (isAI) {
playerZZ = 2;
}
else {
playerZZ = 1;
}
if(checkForWin(2, JSON.parse( JSON.stringify( currentBoard )), outerX2, outerY2, innerX2, innerY2))
{
//AI wins
return 10;
}
if(checkForWin(1, JSON.parse( JSON.stringify( currentBoard )), outerX2, outerY2, innerX2, innerY2))
{
//Human wins
return -10;
}
else if (depth == 2) {
return 0;
}
if (checkForBoardWin(innerX2, innerY2, 1) || checkForBoardWin(innerX2, innerY2, 2))
{
if (isAI)
{
bestScore = -100;
for (var X = 0; X < 3; X++)
{
for (var Y = 0; Y < 3; Y++)
{
for (var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[X][Y][x][y] == 0 && !(checkForBoardWin(X, Y, 1) || checkForBoardWin(X, Y, 2)))
{
//JAKE: Broken here?
currentBoard[X][Y][x][y] = 2
score = evaluateMove(X, Y, x, y, depth + 1, false, currentBoard);
//var bestScore = -100;
if (score > bestScore)
{
console.log("Line 105: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
}
}
else
{
bestScore = 100;
for (var X = 0; X < 3; X++)
{
for (var Y = 0; Y < 3; Y++)
{
for (var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[X][Y][x][y] == 0)
{
currentBoard[X][Y][x][y] = 1
score = evaluateMove(X, Y, x, y, depth + 1, false, currentBoard);
//bestScore = 100;
if (score < bestScore)
{
console.log("Line 137: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
}
}
}
else
{
bestScore = -100;
if (isAI)
{
for(var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[innerX2][innerY2][x][y] == 0)
{
//JAKE: Broken here?
currentBoard[innerX2][innerY2][x][y] = 2
score = evaluateMove(innerX2, innerY2, x, y, depth + 1, false, currentBoard);
//bestScore = -100;
if (score > bestScore)
{
console.log("Line 169: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
else
{
bestScore = 100;
for(var x = 0; x < 3; x++)
{
for (var y = 0; y < 3; y++)
{
if(currentBoard[innerX2][innerY2][x][y] == 0)
{
currentBoard[innerX2][innerY2][x][y] = 1
score = evaluateMove(innerX2, innerY2, x, y, depth + 1, true, currentBoard);
bestScore = 100;
if (score < bestScore)
{
console.log("Line 195: Score = ", score);
return score;
}
else
{
return bestScore;
}
}
}
}
}
}
return 0;
}
谢谢。
您曾经解决问题吗？我正面临类似的问题。 AI的alpha-beta修剪速度较慢。