TicTacToeAI 与 Minimax 算法
TicTacToeAI with Minimax Algorithm
我已经从 GeeksForGeeks 实现了 Tic Tac Toe 游戏的 Minimax 算法。我知道 Minimax Algorithm 是如何工作的，但我这里的代码并不按照它工作。我已经检查并检查了我可能做错的事情并且还调试了它。不过我好像找不到。
请查看算法，如果有更多的眼睛并找到我似乎找不到的不正确部分，将非常感谢。
我已经注释了代码中对极小极大算法有帮助的每一部分。我觉得会很容易赶上。
请帮帮我。
谢谢。
import java.util.Arrays;
import java.util.Scanner;
class Move {
// row index
protected int row;
// column index
protected int col;
// exp is 'Our Expression'.
protected char exp;
// oppExp is 'Opponent's Expression'
protected char oppExp;
}
class TicTacToe {
private final char[][] arr = new char[3][3];
// Move - to keep track of rowIndex and columnIndex
// from the minimax algorithm. And to keep track of
// 'X'/'O', who is our opponent for which the algorithm
// should find moves for.
private final Move moves = new Move();
TicTacToe() {
// Initialising field
for (int i = 0; i < 3; i++) {
Arrays.fill(this.arr[i], ' ');
}
}
public String[] whosePlaying(Scanner sc) {
while (true) {
System.out.print("Input command: ");
// Getting input for players vs players
String str = sc.nextLine();
if (str.startsWith("start")) {
String[] players = str.replaceAll("start", "").trim().split(" ");
if (players.length == 2) {
if ((players[0].equals("user") || players[0].equals("ai")) &&
(players[1].equals("user") || players[1].equals("ai"))) {
return players;
}
}
}
System.out.println("Bad parameters!");
}
}
public void playUser (Scanner sc, char exp) { // exp is expression('X' / 'O') for user
// x is RowIndex
// y is ColumnIndex
// To get from the user
int x, y;
System.out.print("Enter the coordinates (According to Matrix, Space separated integers): ");
while (true) {
// try - catch for input that might not be number
try {
sc = new Scanner(System.in);
x = sc.nextInt();
y = sc.nextInt();
break;
} catch (Exception e) {
System.out.println("You should enter numbers!");
playUser(sc, exp); // Ask again for coordinates
}
}
if (x > 2 || y > 2 || x < 0 || y < 0) {
System.out.println("Coordinates should be from 0 to 2!");
playUser(sc, exp); // Ask again for coordinates
} else {
// Check for availability.
if (this.arr[x][y] == ' ') {
this.arr[x][y] = exp;
displayField(); // Displaying TicTacToe field after user's turn.
} else {
System.out.println("This cell is occupied! Choose another one!");
playUser(sc, exp); // Ask again for coordinates
}
}
}
public void playComputer (char exp) {
System.out.println("Making move level \"AI\"");
// Setting our expresssion that is X / O.
moves.exp = exp;
// Finding opponents expresssion that is X / O.
if (moves.exp == 'X') moves.oppExp = 'O';
else moves.oppExp = 'X';
// Searching for the best move.
searchBestMove();
// Setting the best coordinates from the minimax algorithm
// into the field with our expresssion.
this.arr[moves.row][moves.col] = moves.exp;
displayField(); // Displaying TicTacToe field after AI's turn.
}
// Start of Minimax Algorithm - Contains all methods needed for the algorithm
private void searchBestMove() {
int bestVal = Integer.MIN_VALUE;
moves.row = -1;
moves.col = -1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
this.arr[i][j] = moves.exp;
int moveVal = minimax(0, false);
this.arr[i][j] = ' ';
if (moveVal > bestVal) {
moves.row = i;
moves.col = j;
bestVal = moveVal;
}
}
}
}
}
private int minimax(int depth, boolean isMax) {
int score = checkGetScore();
if (score == 10 || score == -10) return score;
if (!checkForSpace()) return 0;
int best;
if (isMax) {
best = Integer.MIN_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
this.arr[i][j] = moves.exp;
best = Math.max(best, minimax(depth + 1, false));
this.arr[i][j] = ' ';
}
}
}
} else {
best = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
this.arr[i][j] = moves.oppExp;
best = Math.min(best, minimax(depth + 1, true));
this.arr[i][j] = ' ';
}
}
}
}
return best;
}
// Check for the score if the AI wins in the upcoming move
// This method helps AI to assign score for each way in the game while searching.
private int checkGetScore() {
// For Rows
for (int i = 0; i < 3; i++) {
if (this.arr[i][0] == moves.exp && this.arr[i][1] == moves.exp && this.arr[i][2] == moves.exp) {
return 10;
} else if (this.arr[i][0] == moves.oppExp && this.arr[i][1] == moves.oppExp && this.arr[i][2] == moves.oppExp) {
return -10;
}
}
// For Cols
for (int i = 0; i < 3; i++) {
if (this.arr[0][i] == moves.exp && this.arr[1][i] == moves.exp && this.arr[2][i] == moves.exp) {
return 10;
} else if (this.arr[0][i] == moves.oppExp && this.arr[1][i] == moves.oppExp && this.arr[2][i] == moves.oppExp) {
return -10;
}
}
// For Diagonals
if (this.arr[0][0] == moves.exp && this.arr[1][1] == moves.exp && this.arr[2][2] == moves.exp) {
return 10;
} else if (this.arr[0][0] == moves.oppExp && this.arr[1][1] == moves.oppExp && this.arr[2][2] == moves.oppExp) {
return -10;
} else if (this.arr[0][2] == moves.exp && this.arr[1][1] == moves.exp && this.arr[2][0] == moves.exp) {
return 10;
} else if (this.arr[0][2] == moves.oppExp && this.arr[1][1] == moves.oppExp && this.arr[2][0] == moves.oppExp) {
return -10;
}
return 0;
}
// End of Minimax Algoritm
// Displays results of Win / Tie by checking Rows, Columns and Diagonals.
public boolean displayResult() {
int valR = checkRows();
int valC = checkCols();
int diag = checkDiag();
if (diag == 1 || diag == 3 || valR == 3 || valC == 3) {
System.out.println("X wins");
return true;
} else if (diag == 2 || diag == 4 || valR == 2 || valC == 2) {
System.out.println("O wins");
return true;
} else if ((diag == 0 || valC == 1 || valR == 1) && checkForSpace()) {
System.out.println("Draw");
return true;
}
return false;
}
// Prints the TicTacToe field
public void displayField () {
System.out.println("---------");
for (char[] a : this.arr) {
System.out.print("| ");
for (char b : a) {
System.out.print(b + " ");
}
System.out.println("|");
}
System.out.println("---------");
}
// Checks for the availability of space
// in the TicTacToe field.
private boolean checkForSpace() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
return false;
}
}
}
return true;
}
// Checks the Diagonals of the field
private int checkDiag() {
if (this.arr[0][0] == 'X' && this.arr[1][1] == 'X' && this.arr[2][2] == 'X') {
return 1;
} else if (this.arr[0][0] == 'O' && this.arr[1][1] == 'O' && this.arr[2][2] == 'O') {
return 2;
} else if (this.arr[0][2] == 'X' && this.arr[1][1] == 'X' && this.arr[2][0] == 'X') {
return 3;
} else if (this.arr[0][2] == 'O' && this.arr[1][1] == 'O' && this.arr[2][0] == 'O') {
return 4;
} else {
return 0;
}
}
// Checks the Rows of the field
private int checkRows () {
int cntX = 0,
cntO = 0;
for (int i = 0; i < 3; i++) {
if (this.arr[i][0] == 'X' && this.arr[i][1] == 'X' && this.arr[i][2] == 'X') {
cntX++;
} else if (this.arr[i][0] == 'O' && this.arr[i][1] == 'O' && this.arr[i][2] == 'O') {
cntO++;
}
}
if (cntX == 1) {
return 3;
} else if (cntO == 1) {
return 2;
} else {
return 1;
}
}
// Checks the Columns of the field
private int checkCols () {
int cntX = 0,
cntO = 0;
for (int i = 0; i < 3; i++) {
if (this.arr[0][i] == 'X' && this.arr[1][i] == 'X' && this.arr[2][i] == 'X') {
cntX++;
} else if (this.arr[0][i] == 'O' && this.arr[1][i] == 'O' && this.arr[2][i] == 'O') {
cntO++;
}
}
if (cntX == 1) {
return 3;
} else if (cntO == 1) {
return 2;
} else {
return 1;
}
}
}
public class MinimaxAlgorithm {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
TicTacToe tic = new TicTacToe();
// For game to start specify players
// Eg: start user ai <-- user is X and user chance comes first.
// Eg: start ai user <-- ai is X and ai chance comes first.
// Eg: start ai ai <-- ai vs ai
// Eg: user user <-- user vs user
String[] players = tic.whosePlaying(sc);
// Displays the empty field of TicTacToe
tic.displayField();
// turnX = true. X's turn
// turnX = false. O's turn
boolean turnX = true;
while (true) {
// Alternate player turns
// First chance of X, than O.
if (turnX) {
switch (players[0]) {
case "ai":
tic.playComputer('X');
break;
default:
tic.playUser(sc, 'X');
break;
}
turnX = false;
} else {
switch (players[1]) {
case "ai":
tic.playComputer('O');
break;
default:
tic.playUser(sc, 'O');
break;
}
turnX = true;
}
// displayresult() - Checks if the game is over by anyone winning or tie.
// If someone wins or ties the "check" becomes true and finishes the game.
// Checks after each move made by the players.
boolean check = tic.displayResult();
if (check) break;
}
sc.close();
}
}
蓝色箭头表示错误发生的地方。
绿色标记指定它应该如何。
控制台：
Input command: start user ai
---------
| |
| |
| |
---------
Enter the coordinates (According to Matrix, Space separated integers): 1 1
---------
| |
| X |
| |
---------
Making move level "AI"
---------
| O |
| X |
| |
---------
Enter the coordinates (According to Matrix, Space separated integers): 0 2
---------
| O X |
| X |
| |
---------
Making move level "AI"
---------
| O O X | <-- Explanation: The AI made its move on [0, 1]
| X | but it should have did on [2, 0]
| | which will block my win on right diagonal.
---------
Enter the coordinates (According to Matrix, Space separated integers): 2 0
---------
| O O X |
| X |
| X |
---------
X wins
您的函数 checkForSpace() 与其在 minimax() 中的使用不匹配。如果有 space 离开你 return false 并且如果你在 minimax() 中得到 false 你停止搜索，就好像有平局一样。您需要反转 checkForSpace() 中的布尔值或删除 minimax().
中的逻辑非
您应该适当地将 checkForSpace() 和 return 的其他函数重命名为布尔值。来自可读代码的艺术（Dustin Boswell 和 Trevor Foucher）：
When picking a name for a boolean variable or a function that returns a boolean, be sure it’s clear what true and false really mean.
Here’s a dangerous example:
bool read_password = true;
Depending on how you read it (no pun intended), there are two very different interpretations:
We need to read the password
The password has already been read
In this case, it’s best to avoid the word "read," and name it need_password or user_is_authenticated instead.
In general, adding words like is, has, can, or should can make booleans more clear.
For example, a function named SpaceLeft() sounds like it might return a number. If it were meant to return a boolean, a better name would be HasSpaceLeft().
Finally, it’s best to avoid negated terms in a name. For example, instead of:
bool disable_ssl = false;
it would be easier to read (and more compact) to say:
bool use_ssl = true;
我已经从 GeeksForGeeks 实现了 Tic Tac Toe 游戏的 Minimax 算法。我知道 Minimax Algorithm 是如何工作的，但我这里的代码并不按照它工作。我已经检查并检查了我可能做错的事情并且还调试了它。不过我好像找不到。
请查看算法，如果有更多的眼睛并找到我似乎找不到的不正确部分，将非常感谢。
我已经注释了代码中对极小极大算法有帮助的每一部分。我觉得会很容易赶上。
请帮帮我。
谢谢。
import java.util.Arrays;
import java.util.Scanner;
class Move {
// row index
protected int row;
// column index
protected int col;
// exp is 'Our Expression'.
protected char exp;
// oppExp is 'Opponent's Expression'
protected char oppExp;
}
class TicTacToe {
private final char[][] arr = new char[3][3];
// Move - to keep track of rowIndex and columnIndex
// from the minimax algorithm. And to keep track of
// 'X'/'O', who is our opponent for which the algorithm
// should find moves for.
private final Move moves = new Move();
TicTacToe() {
// Initialising field
for (int i = 0; i < 3; i++) {
Arrays.fill(this.arr[i], ' ');
}
}
public String[] whosePlaying(Scanner sc) {
while (true) {
System.out.print("Input command: ");
// Getting input for players vs players
String str = sc.nextLine();
if (str.startsWith("start")) {
String[] players = str.replaceAll("start", "").trim().split(" ");
if (players.length == 2) {
if ((players[0].equals("user") || players[0].equals("ai")) &&
(players[1].equals("user") || players[1].equals("ai"))) {
return players;
}
}
}
System.out.println("Bad parameters!");
}
}
public void playUser (Scanner sc, char exp) { // exp is expression('X' / 'O') for user
// x is RowIndex
// y is ColumnIndex
// To get from the user
int x, y;
System.out.print("Enter the coordinates (According to Matrix, Space separated integers): ");
while (true) {
// try - catch for input that might not be number
try {
sc = new Scanner(System.in);
x = sc.nextInt();
y = sc.nextInt();
break;
} catch (Exception e) {
System.out.println("You should enter numbers!");
playUser(sc, exp); // Ask again for coordinates
}
}
if (x > 2 || y > 2 || x < 0 || y < 0) {
System.out.println("Coordinates should be from 0 to 2!");
playUser(sc, exp); // Ask again for coordinates
} else {
// Check for availability.
if (this.arr[x][y] == ' ') {
this.arr[x][y] = exp;
displayField(); // Displaying TicTacToe field after user's turn.
} else {
System.out.println("This cell is occupied! Choose another one!");
playUser(sc, exp); // Ask again for coordinates
}
}
}
public void playComputer (char exp) {
System.out.println("Making move level \"AI\"");
// Setting our expresssion that is X / O.
moves.exp = exp;
// Finding opponents expresssion that is X / O.
if (moves.exp == 'X') moves.oppExp = 'O';
else moves.oppExp = 'X';
// Searching for the best move.
searchBestMove();
// Setting the best coordinates from the minimax algorithm
// into the field with our expresssion.
this.arr[moves.row][moves.col] = moves.exp;
displayField(); // Displaying TicTacToe field after AI's turn.
}
// Start of Minimax Algorithm - Contains all methods needed for the algorithm
private void searchBestMove() {
int bestVal = Integer.MIN_VALUE;
moves.row = -1;
moves.col = -1;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
this.arr[i][j] = moves.exp;
int moveVal = minimax(0, false);
this.arr[i][j] = ' ';
if (moveVal > bestVal) {
moves.row = i;
moves.col = j;
bestVal = moveVal;
}
}
}
}
}
private int minimax(int depth, boolean isMax) {
int score = checkGetScore();
if (score == 10 || score == -10) return score;
if (!checkForSpace()) return 0;
int best;
if (isMax) {
best = Integer.MIN_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
this.arr[i][j] = moves.exp;
best = Math.max(best, minimax(depth + 1, false));
this.arr[i][j] = ' ';
}
}
}
} else {
best = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
this.arr[i][j] = moves.oppExp;
best = Math.min(best, minimax(depth + 1, true));
this.arr[i][j] = ' ';
}
}
}
}
return best;
}
// Check for the score if the AI wins in the upcoming move
// This method helps AI to assign score for each way in the game while searching.
private int checkGetScore() {
// For Rows
for (int i = 0; i < 3; i++) {
if (this.arr[i][0] == moves.exp && this.arr[i][1] == moves.exp && this.arr[i][2] == moves.exp) {
return 10;
} else if (this.arr[i][0] == moves.oppExp && this.arr[i][1] == moves.oppExp && this.arr[i][2] == moves.oppExp) {
return -10;
}
}
// For Cols
for (int i = 0; i < 3; i++) {
if (this.arr[0][i] == moves.exp && this.arr[1][i] == moves.exp && this.arr[2][i] == moves.exp) {
return 10;
} else if (this.arr[0][i] == moves.oppExp && this.arr[1][i] == moves.oppExp && this.arr[2][i] == moves.oppExp) {
return -10;
}
}
// For Diagonals
if (this.arr[0][0] == moves.exp && this.arr[1][1] == moves.exp && this.arr[2][2] == moves.exp) {
return 10;
} else if (this.arr[0][0] == moves.oppExp && this.arr[1][1] == moves.oppExp && this.arr[2][2] == moves.oppExp) {
return -10;
} else if (this.arr[0][2] == moves.exp && this.arr[1][1] == moves.exp && this.arr[2][0] == moves.exp) {
return 10;
} else if (this.arr[0][2] == moves.oppExp && this.arr[1][1] == moves.oppExp && this.arr[2][0] == moves.oppExp) {
return -10;
}
return 0;
}
// End of Minimax Algoritm
// Displays results of Win / Tie by checking Rows, Columns and Diagonals.
public boolean displayResult() {
int valR = checkRows();
int valC = checkCols();
int diag = checkDiag();
if (diag == 1 || diag == 3 || valR == 3 || valC == 3) {
System.out.println("X wins");
return true;
} else if (diag == 2 || diag == 4 || valR == 2 || valC == 2) {
System.out.println("O wins");
return true;
} else if ((diag == 0 || valC == 1 || valR == 1) && checkForSpace()) {
System.out.println("Draw");
return true;
}
return false;
}
// Prints the TicTacToe field
public void displayField () {
System.out.println("---------");
for (char[] a : this.arr) {
System.out.print("| ");
for (char b : a) {
System.out.print(b + " ");
}
System.out.println("|");
}
System.out.println("---------");
}
// Checks for the availability of space
// in the TicTacToe field.
private boolean checkForSpace() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (this.arr[i][j] == ' ') {
return false;
}
}
}
return true;
}
// Checks the Diagonals of the field
private int checkDiag() {
if (this.arr[0][0] == 'X' && this.arr[1][1] == 'X' && this.arr[2][2] == 'X') {
return 1;
} else if (this.arr[0][0] == 'O' && this.arr[1][1] == 'O' && this.arr[2][2] == 'O') {
return 2;
} else if (this.arr[0][2] == 'X' && this.arr[1][1] == 'X' && this.arr[2][0] == 'X') {
return 3;
} else if (this.arr[0][2] == 'O' && this.arr[1][1] == 'O' && this.arr[2][0] == 'O') {
return 4;
} else {
return 0;
}
}
// Checks the Rows of the field
private int checkRows () {
int cntX = 0,
cntO = 0;
for (int i = 0; i < 3; i++) {
if (this.arr[i][0] == 'X' && this.arr[i][1] == 'X' && this.arr[i][2] == 'X') {
cntX++;
} else if (this.arr[i][0] == 'O' && this.arr[i][1] == 'O' && this.arr[i][2] == 'O') {
cntO++;
}
}
if (cntX == 1) {
return 3;
} else if (cntO == 1) {
return 2;
} else {
return 1;
}
}
// Checks the Columns of the field
private int checkCols () {
int cntX = 0,
cntO = 0;
for (int i = 0; i < 3; i++) {
if (this.arr[0][i] == 'X' && this.arr[1][i] == 'X' && this.arr[2][i] == 'X') {
cntX++;
} else if (this.arr[0][i] == 'O' && this.arr[1][i] == 'O' && this.arr[2][i] == 'O') {
cntO++;
}
}
if (cntX == 1) {
return 3;
} else if (cntO == 1) {
return 2;
} else {
return 1;
}
}
}
public class MinimaxAlgorithm {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
TicTacToe tic = new TicTacToe();
// For game to start specify players
// Eg: start user ai <-- user is X and user chance comes first.
// Eg: start ai user <-- ai is X and ai chance comes first.
// Eg: start ai ai <-- ai vs ai
// Eg: user user <-- user vs user
String[] players = tic.whosePlaying(sc);
// Displays the empty field of TicTacToe
tic.displayField();
// turnX = true. X's turn
// turnX = false. O's turn
boolean turnX = true;
while (true) {
// Alternate player turns
// First chance of X, than O.
if (turnX) {
switch (players[0]) {
case "ai":
tic.playComputer('X');
break;
default:
tic.playUser(sc, 'X');
break;
}
turnX = false;
} else {
switch (players[1]) {
case "ai":
tic.playComputer('O');
break;
default:
tic.playUser(sc, 'O');
break;
}
turnX = true;
}
// displayresult() - Checks if the game is over by anyone winning or tie.
// If someone wins or ties the "check" becomes true and finishes the game.
// Checks after each move made by the players.
boolean check = tic.displayResult();
if (check) break;
}
sc.close();
}
}
蓝色箭头表示错误发生的地方。
绿色标记指定它应该如何。
控制台：
Input command: start user ai
---------
| |
| |
| |
---------
Enter the coordinates (According to Matrix, Space separated integers): 1 1
---------
| |
| X |
| |
---------
Making move level "AI"
---------
| O |
| X |
| |
---------
Enter the coordinates (According to Matrix, Space separated integers): 0 2
---------
| O X |
| X |
| |
---------
Making move level "AI"
---------
| O O X | <-- Explanation: The AI made its move on [0, 1]
| X | but it should have did on [2, 0]
| | which will block my win on right diagonal.
---------
Enter the coordinates (According to Matrix, Space separated integers): 2 0
---------
| O O X |
| X |
| X |
---------
X wins
您的函数 checkForSpace() 与其在 minimax() 中的使用不匹配。如果有 space 离开你 return false 并且如果你在 minimax() 中得到 false 你停止搜索，就好像有平局一样。您需要反转 checkForSpace() 中的布尔值或删除 minimax().
您应该适当地将 checkForSpace() 和 return 的其他函数重命名为布尔值。来自可读代码的艺术（Dustin Boswell 和 Trevor Foucher）：
When picking a name for a boolean variable or a function that returns a boolean, be sure it’s clear what
trueandfalsereally mean.Here’s a dangerous example:
bool read_password = true;Depending on how you read it (no pun intended), there are two very different interpretations:
We need to read the password
The password has already been read
In this case, it’s best to avoid the word "read," and name it
need_passwordoruser_is_authenticatedinstead.In general, adding words like
is,has,can, orshouldcan make booleans more clear.For example, a function named
SpaceLeft()sounds like it might return a number. If it were meant to return a boolean, a better name would beHasSpaceLeft().Finally, it’s best to avoid negated terms in a name. For example, instead of:
bool disable_ssl = false;it would be easier to read (and more compact) to say:
bool use_ssl = true;