我正在尝试使用简化的最小最大值算法制作一个无与伦比的井字游戏。代码如下所示：
private static int findBestMove(String[][] board, boolean comp) {
// comp returns true if the computer is the one looking for the best move
// findBestMove is always called by the program as findBestMove(board, true)
// since the computer is the only one that uses it
// If the board in its current state is a win for the
// player, return -1 to indicate a loss
if (playerWon(board)) return -1;
// If the board in its current state is a win for the
// computer, return 1 to indicate a win
if (compWon(board)) return 1;
// If the board in its current state is a tie
// return 0 to indicate a tie
if (tie(board)) return 0;
// Set the default possible outcome as the opposite of what
// the respective player wants
int bestPossibleOutcome = comp ? -1 : 1;
// Loop through the board looking for empty spaces
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++)
// Once an empty space is found, create a copy of the board
// with that space occupied by the respective player
if (board[i][j].equals(" ")) {
String[][] newBoard = new String[3][3];
for (int a = 0; a < 3; a++) {
System.arraycopy(board[a], 0, newBoard[a], 0, 3);
}
newBoard[i][j] = comp ? "O" : "X";
// Recursively call findBestMove() on this copy
// and see what the outcome is
int outCome = findBestMove(newBoard, !comp);
// If this is the computer's turn, and the outcome
// is higher than the value currently stored as the
// best, replace it
if (comp && outCome > bestPossibleOutcome) {
bestPossibleOutcome = outCome;
// r and c are instance variables that store the row
// and column of what the computer's next move should be
r = i;
c = j;
// If this is the player's turn, and the outcome
// is lower than the value currently stored as the
// best, replace it
} else if (!comp && outCome < bestPossibleOutcome) {
bestPossibleOutcome = outCome;
}
}
}
}
// Return the ultimate value deemed to be the best
return bestPossibleOutcome;
}
这个想法是，在我运行这个程序后，实例变量r和c应该分别包含计算机最佳移动的行和列。但是，该程序只能成功防止大约一半的时间损失，我无法判断另一半是运气，还是该程序是否真的在工作。
我知道计算机将以与每场比赛完全相同的方式响应每个场景。那很好。
如果有人想运行该程序，我在下面包含了完整的类：
import java.util.Scanner;
public class TicTacToe {
private static int r;
private static int c;
private static void printBoard(String[][] board) {
System.out.println(" 0 1 2");
System.out.println("0 " + board[0][0] + " | " + board[0][1] + " | " + board[0][2] + " ");
System.out.println(" ---+---+---");
System.out.println("1 " + board[1][0] + " | " + board[1][1] + " | " + board[1][2] + " ");
System.out.println(" ---+---+---");
System.out.println("2 " + board[2][0] + " | " + board[2][1] + " | " + board[2][2] + " ");
}
private static boolean playerWon(String[][] board) {
return playerHasThreeInCol(board) || playerHasThreeInDiag(board) || playerHasThreeInRow(board);
}
private static boolean playerHasThreeInRow(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0].equals(board[i][1]) && board[i][0].equals(board[i][2]) && board[i][0].equals("X")) return true;
}
return false;
}
private static boolean playerHasThreeInCol(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[0][i].equals(board[1][i]) && board[0][i].equals(board[2][i]) && board[0][i].equals("X")) return true;
}
return false;
}
private static boolean playerHasThreeInDiag(String[][] board) {
if (board[0][0].equals(board[1][1]) && board[0][0].equals(board[2][2]) && board[0][0].equals("X")) return true;
return board[0][2].equals(board[1][1]) && board[0][2].equals(board[2][0]) && board[0][2].equals("X");
}
private static boolean compWon(String[][] board) {
return compHasThreeInCol(board) || compHasThreeInDiag(board) || compHasThreeInRow(board);
}
private static boolean compHasThreeInRow(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[i][0].equals(board[i][1]) && board[i][0].equals(board[i][2]) && board[i][0].equals("O")) return true;
}
return false;
}
private static boolean compHasThreeInCol(String[][] board) {
for (int i = 0; i < 3; i++) {
if (board[0][i].equals(board[1][i]) && board[0][i].equals(board[2][i]) && board[0][i].equals("O")) return true;
}
return false;
}
private static boolean compHasThreeInDiag(String[][] board) {
if (board[0][0].equals(board[1][1]) && board[0][0].equals(board[2][2]) && board[0][0].equals("O")) return true;
return board[0][2].equals(board[1][1]) && board[0][2].equals(board[2][0]) && board[0][2].equals("O");
}
private static boolean tie(String[][] board) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) return false;
}
}
return true;
}
private static int findBestMove(String[][] board, boolean comp) {
if (playerWon(board)) return -1;
if (compWon(board)) return 1;
if (tie(board)) return 0;
int bestPossibleOutcome = comp ? -1 : 1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
String[][] newBoard = new String[3][3];
for (int a = 0; a < 3; a++) {
System.arraycopy(board[a], 0, newBoard[a], 0, 3);
}
newBoard[i][j] = comp ? "O" : "X";
int outCome = findBestMove(newBoard, !comp);
if (comp && outCome > bestPossibleOutcome) {
bestPossibleOutcome = outCome;
r = i;
c = j;
} else if (!comp && outCome < bestPossibleOutcome) {
bestPossibleOutcome = outCome;
}
}
}
}
return bestPossibleOutcome;
}
private static void go() {
Scanner input = new Scanner(System.in);
String[][] board = new String[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
board[i][j] = " ";
}
}
printBoard(board);
for (int i = 0;; i++) {
if (i % 2 == 0) {
while (true) {
System.out.println("Enter position: ");
String position = input.nextLine();
int row, column;
try {
row = Integer.parseInt(position.substring(0, 1));
column = Integer.parseInt(position.substring(1, 2));
} catch (Exception e) {
System.out.println("Invalid entry. ");
continue;
}
if (row < 0 || row > 2 || column < 0 || column > 2) {
System.out.println("That position is not on the board. ");
continue;
}
if (!board[row][column].equals(" ")) {
System.out.println("That space is already taken. ");
continue;
}
board[row][column] = "X";
break;
}
} else {
System.out.println("nMy move: ");
findBestMove(board, true);
board[r][c] = "O";
}
printBoard(board);
if (playerWon(board)) {
System.out.println("You win!");
break;
} else if (compWon(board)) {
System.out.println("I win!");
break;
} else if (tie(board)) {
System.out.println("Tie game");
break;
}
}
}
public static void main(String[] args) {
go();
}
}
我不是要求任何人为我重写整个事情，但如果你能指出任何明显的错误或指出我正确的方向，那将不胜感激。我也愿意接受你可能提出的任何建议或意见。
我还没有广泛测试它，但我相信我已经解决了这个问题。新代码如下所示：
private static void findBestMove(String[][] board) {
double bestMove = Double.NEGATIVE_INFINITY;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
board[i][j] = "O";
double score = minimax(board, false);
board[i][j] = " ";
if (score > bestMove) {
bestMove = score;
r = i;
c = j;
}
}
}
}
}
private static double minimax(String[][] board, boolean comp) {
if (playerWon(board)) {
return -1;
}
if (compWon(board)) {
return 1;
}
if (tie(board)) return 0;
double bestScore;
if (comp) {
bestScore = Double.NEGATIVE_INFINITY;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
board[i][j] = "O";
double score = minimax(board, false);
board[i][j] = " ";
bestScore = Math.max(score, bestScore);
}
}
}
} else {
bestScore = Double.POSITIVE_INFINITY;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j].equals(" ")) {
board[i][j] = "X";
double score = minimax(board, true);
board[i][j] = " ";
bestScore = Math.min(score, bestScore);
}
}
}
}
return bestScore;
}
我将最小最大值算法从下一个移动坐标设置器中抽象出来，我认为这可能会有所作为。否则，它非常相似。