Java 井字游戏中的 Alpha-Beta 修剪
Java Alpha-Beta Pruning in Tic Tac Toe
我有一个使用 Minimax 算法的井字游戏。我想通过添加 alpha-beta 修剪来改进它。然而,alpha-beta 方法似乎无法有效计算移动。它只是将其棋子放在下一个可用的 space 中,无论它是否是最佳着法。我对 minimax 方法没有这个问题。我确定这是我一直忽略的简单问题,所以请原谅我。我使用 this tutorial for minimax and this alpha-beta 修剪教程。
这是 Minimax class。它包括 alpha-beta 方法:
public class Minimax {
private Token playerToken;
private EndStates endStates;
private Token opponentToken;
public Minimax(Token playerToken, EndStates endStates) {
this.playerToken = playerToken;
this.endStates = endStates;
opponentToken = makeOpponentToken();
}
public Token makeOpponentToken() {
if (playerToken == Token.O) {
return Token.X;
}
else {
return Token.O;
}
}
public Token getOpponentToken() {
return opponentToken;
}
public int evaluate(Cell[] board) {
//rows across
if (endStates.checkWinByRow(board, playerToken) || endStates.checkWinByColumn(board, playerToken) || endStates.checkWinByDiagonal(board, playerToken)) {
return 10;
}
else if (endStates.checkWinByRow(board, opponentToken) || endStates.checkWinByColumn(board, opponentToken) || endStates.checkWinByDiagonal(board, opponentToken)) {
return -10;
}
return 0;
}
public boolean hasCellsLeft(Cell[] board) {
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
return true;
}
}
return false;
}
int MAX = 1000;
int MIN = -1000;
public int alphaBeta(Cell[] board, int depth, boolean isMax, int alpha, int beta) {
int score = evaluate(board);
if (score == 10) {
return score;
}
if (score == -10) {
return score;
}
if (hasCellsLeft(board) == false) {
return 0;
}
if (isMax) {
int best = MIN;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
int val = alphaBeta(board,depth+1, !isMax, alpha, beta);
best = Math.max(best, val);
alpha = Math.max(alpha, best);
board[i].resetMarker();
}
if (best <= alpha) {
break;
}
}
return best;
}
else {
int best = MAX;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
int val = alphaBeta(board, depth+1, isMax, alpha, beta);
best = Math.min(best, val);
beta = Math.min(beta, best);
board[i].resetMarker();
}
if (beta <= alpha) {
break;
}
}
return best;
}
}
public int minimax(Cell[] board, int depth, boolean isMax) {
int score = evaluate(board);
int best;
if (score == 10) {
return score;
}
if (score == -10) {
return score;
}
if (hasCellsLeft(board) == false) {
return 0;
}
if (isMax) {
best = -1000;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
best = Math.max(best, minimax(board, depth+1, !isMax));
board[i].resetMarker();
}
}
return best;
}
else {
best = 1000;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(opponentToken);
best = Math.min(best, minimax(board, depth+1, !isMax));
board[i].resetMarker();
}
}
return best;
}
}
public int findBestMove(Cell[] board) {
int bestValue = -1000;
int bestMove = -1;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
//int moveValue = minimax(board, 0, false);
int moveValue = alphaBeta(board, 0, true, -1000, 1000);
board[i].resetMarker();
if (moveValue > bestValue) {
bestMove = i;
bestValue = moveValue;
}
}
}
return bestMove;
}
}
棋盘是一个包含 9 的数组,其中包含枚举值 Token.Empty,但可以分别替换为 Token.X 或 Token.O。
这是调用的class算法:
public class ComputerPlayer(Token token, Algorithm minimax ) {
private Token playerToken;
private Algorithm minimax;
public ComputerPlayer(Token playerToken, Algorithm minimax) {
this.playerToken = playerToken;
this.minimax = minimax;
}
public Token getPlayerToken() {
return playerToken;
}
public void makeMove(Cell[] board) {
int chosenCell;
chosenCell = minimax.findBestMove(board);
board[chosenCell].setToken(playerToken);
System.out.println("Player " + playerToken + " has chosen cell " + (chosenCell+1));
}
}
Alpha-Beta 修剪需要对未完成的游戏状态有良好的评估功能才能有效。它应该能够评估一名玩家何时 "more likely" 才能准确获胜。它将使用评估来修剪看起来没有希望的变体。
现在你的评估函数只区分游戏结束和游戏进行中,所以你不会比最小-最大做得更好。
但是,如果你做的比 min-max 还差,那么你一定在其他地方也有错误。我建议单步执行代码并尝试查看哪里出错了。
我有一个使用 Minimax 算法的井字游戏。我想通过添加 alpha-beta 修剪来改进它。然而,alpha-beta 方法似乎无法有效计算移动。它只是将其棋子放在下一个可用的 space 中,无论它是否是最佳着法。我对 minimax 方法没有这个问题。我确定这是我一直忽略的简单问题,所以请原谅我。我使用 this tutorial for minimax and this alpha-beta 修剪教程。
这是 Minimax class。它包括 alpha-beta 方法:
public class Minimax {
private Token playerToken;
private EndStates endStates;
private Token opponentToken;
public Minimax(Token playerToken, EndStates endStates) {
this.playerToken = playerToken;
this.endStates = endStates;
opponentToken = makeOpponentToken();
}
public Token makeOpponentToken() {
if (playerToken == Token.O) {
return Token.X;
}
else {
return Token.O;
}
}
public Token getOpponentToken() {
return opponentToken;
}
public int evaluate(Cell[] board) {
//rows across
if (endStates.checkWinByRow(board, playerToken) || endStates.checkWinByColumn(board, playerToken) || endStates.checkWinByDiagonal(board, playerToken)) {
return 10;
}
else if (endStates.checkWinByRow(board, opponentToken) || endStates.checkWinByColumn(board, opponentToken) || endStates.checkWinByDiagonal(board, opponentToken)) {
return -10;
}
return 0;
}
public boolean hasCellsLeft(Cell[] board) {
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
return true;
}
}
return false;
}
int MAX = 1000;
int MIN = -1000;
public int alphaBeta(Cell[] board, int depth, boolean isMax, int alpha, int beta) {
int score = evaluate(board);
if (score == 10) {
return score;
}
if (score == -10) {
return score;
}
if (hasCellsLeft(board) == false) {
return 0;
}
if (isMax) {
int best = MIN;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
int val = alphaBeta(board,depth+1, !isMax, alpha, beta);
best = Math.max(best, val);
alpha = Math.max(alpha, best);
board[i].resetMarker();
}
if (best <= alpha) {
break;
}
}
return best;
}
else {
int best = MAX;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
int val = alphaBeta(board, depth+1, isMax, alpha, beta);
best = Math.min(best, val);
beta = Math.min(beta, best);
board[i].resetMarker();
}
if (beta <= alpha) {
break;
}
}
return best;
}
}
public int minimax(Cell[] board, int depth, boolean isMax) {
int score = evaluate(board);
int best;
if (score == 10) {
return score;
}
if (score == -10) {
return score;
}
if (hasCellsLeft(board) == false) {
return 0;
}
if (isMax) {
best = -1000;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
best = Math.max(best, minimax(board, depth+1, !isMax));
board[i].resetMarker();
}
}
return best;
}
else {
best = 1000;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(opponentToken);
best = Math.min(best, minimax(board, depth+1, !isMax));
board[i].resetMarker();
}
}
return best;
}
}
public int findBestMove(Cell[] board) {
int bestValue = -1000;
int bestMove = -1;
for (int i=0; i<board.length; i++) {
if (board[i].getToken() == Token.EMPTY) {
board[i].setToken(playerToken);
//int moveValue = minimax(board, 0, false);
int moveValue = alphaBeta(board, 0, true, -1000, 1000);
board[i].resetMarker();
if (moveValue > bestValue) {
bestMove = i;
bestValue = moveValue;
}
}
}
return bestMove;
}
}
棋盘是一个包含 9 的数组,其中包含枚举值 Token.Empty,但可以分别替换为 Token.X 或 Token.O。
这是调用的class算法:
public class ComputerPlayer(Token token, Algorithm minimax ) {
private Token playerToken;
private Algorithm minimax;
public ComputerPlayer(Token playerToken, Algorithm minimax) {
this.playerToken = playerToken;
this.minimax = minimax;
}
public Token getPlayerToken() {
return playerToken;
}
public void makeMove(Cell[] board) {
int chosenCell;
chosenCell = minimax.findBestMove(board);
board[chosenCell].setToken(playerToken);
System.out.println("Player " + playerToken + " has chosen cell " + (chosenCell+1));
}
}
Alpha-Beta 修剪需要对未完成的游戏状态有良好的评估功能才能有效。它应该能够评估一名玩家何时 "more likely" 才能准确获胜。它将使用评估来修剪看起来没有希望的变体。
现在你的评估函数只区分游戏结束和游戏进行中,所以你不会比最小-最大做得更好。
但是,如果你做的比 min-max 还差,那么你一定在其他地方也有错误。我建议单步执行代码并尝试查看哪里出错了。