Posted in Java

Artificial Intelligence with Java: Understanding the Min-Max Algorithm in AI Games


Learn the min-max algorithm in this tutorial by Nisheeth Joshi, an associate professor and a researcher at Banasthali University with a Ph.D. in Natural Language Processing.

In order to understand the min-max algorithm, you should get familiar with game playing and game trees. A game tree is made of a root node, which has child nodes. Each child node is then subdivided into multiple children. This forms the tree, and the terminal nodes are termed leaves, as shown in the following diagram:

Understanding the Min-Max Algorithm in AI Games

In game play, the main goal is to win the game; in other words, try to find the best possible solution by looking ahead in the game tree. The most important thing to note about playing a game is that you don’t actually go down to a particular node (or down a complete tree), and you don’t play the entire game. You’ll be in the root position looking for the best option available, in order to maximize your chances of winning the game.

While performing game playing, take turns similar to a game of chess or tic-tac-toe, where you take a turn and then your opponent takes a turn. This means that all children of a particular node will be your opponent’s move.

Your opponent’s objective will be to make you lose because whatever the game tree would be in your perspective. Therefore, from your perspective, on any particular move, your objective is to win the game. When looking ahead, simply search the game tree. (Note that all the necessary code files for this article can be found at https://github.com/PacktPublishing/Hands-On-Artificial-Intelligence-with-Java-for-Beginners/tree/master/Chapter03/GamePlaying.)

Consider a tree with the following types of nodes:

  • min nodes: These are your opponent’s nodes
  • max nodes: These are your nodes

In min nodes, select the minimum cost successor. Out of all of the successors that you have for a particular node, choose the minimum. In a max node, you should try to find out the maximum successor, because the nodes are your moves.

Now, don’t actually move to a particular point; you are only looking ahead, performing certain computations in the memory, and trying to find the best move possible. The terminal nodes are the winning or losing nodes, but it is often not feasible to search the terminal nodes; so, you apply heuristics to compare the non-terminal nodes. The following diagram illustrates your game tree:

Understanding the Min-Max Algorithm in AI Games

Start at the root node, A. You have two options: either the right subtree or the left subtree. If you select either of the subtrees at random, your chances of losing the game become higher. To avoid this, apply certain heuristics so that your chances of winning the game increase.

Therefore, try to model the game. Suppose you select B; your opponent will have the option to select either D or E. If your opponent selects D, you’ll have the option to select either H or I. Similarly, if your opponent chooses H, you’ll have the option to select either 10 or 11; this is the maximum that can be performed. From this point on, apply heuristics.

In the preceding diagram, the heuristic values of all of the terminal nodes can be seen. The game has not yet ended and you are only looking ahead. The heuristic values comprise the maximum depth that you can go for a look ahead. The chances of winning the game at particular points are 10%, 11%, 9%, and so on. These are the terminal values that you have.

Now, suppose your opponent selects the H node. This is a min node, and a min node will always choose a minimum out of its successors. Therefore, the min node will always choose 10, if choosing between 10 and 11. If you move ahead, you have 9 and 11; so, your opponent will select 9. Similarly, your opponent will select the rest of the nodes.

Now, it’s your move. DEF, and G are the max nodes. The max nodes will always choose the maximum value out of their successors. Therefore, you’ll choose 10, 14, 2, and 20 as your nodes. Now it’s your opponent’s move again, and your opponent will always choose the minimum among his successors. This time, he will select 10 and 2. Finally, it is your turn, and you have a max node. Choose the maximum value of the successor: 10. This is illustrated in the following diagram:

Understanding the Min-Max Algorithm in AI Games

So, this is how the gameplay works.

Implementing a min-max algorithm

In this section, you’ll learn to implement the min-max algorithm (a tic-tac-toe example). Start with NetBeans. You’ll have an ArrayList; apply randomization and take input. The following are the four classes that you’ll be working with:

import java.util.ArrayList;

import java.util.List;

import java.util.Random;

import java.util.Scanner;

 

Now, define the x and y points. In a tic-tac-toe game, there are nine tiles, and, on a one-on-one basis with the opponent, the squares are filled, as shown here:

class Point {

int x, y;

public Point(int x, int y) {
this.x = x;
this.y = y;
}

@Override
public String toString() {
return “[” + x + “, ” + y + “]”;
}
}

class PointAndScore {

int score;
Point point;

PointAndScore(int score, Point point) {
this.score = score;
this.point = point;
}
}

So, define Point and the x and y points. This will give you the x and y values onto which you have to enter the values. String will return those values. PointAndScore will provide the point value and its score at each particular square, whether it is filled in or not.

The Board class will define the entire nine tiles and take input; this will give you three states. It can be that either X has won, the person who has an X has won, or the person who has a 0 has won, and the available states, if any are Empty:

class Board {

List<Point> availablePoints;
Scanner scan = new Scanner(System.in);
int[][] board = new int[3][3];

public Board() {
}

public boolean isGameOver() {
return (hasXWon() || hasOWon() || getAvailableStates().isEmpty());
}

public boolean hasXWon() {
if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
return true;
}
for (int i = 0; i < 3; ++i) {
if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
|| (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
return true;
}
}
return false;
}

public boolean hasOWon() {
if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 2) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 2)) {
return true;
}
for (int i = 0; i < 3; ++i) {
if ((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 2)
|| (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 2)) {
return true;
}
}

return false;
}

public List<Point> getAvailableStates() {
availablePoints = new ArrayList<>();
for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
if (board[i][j] == 0) {
availablePoints.add(new Point(i, j));
}
}
}
return availablePoints;
}

public void placeAMove(Point point, int player) {
board[point.x][point.y] = player; //player = 1 for X, 2 for O
}

void takeHumanInput() {
System.out.println(“Your move: “);
int x = scan.nextInt();
int y = scan.nextInt();
Point point = new Point(x, y);
placeAMove(point, 2);
}

public void displayBoard() {
System.out.println();

for (int i = 0; i < 3; ++i) {
for (int j = 0; j < 3; ++j) {
System.out.print(board[i][j] + ” “);
}
System.out.println();

}
}

Point computersMove;

public int minimax(int depth, int turn) {
if (hasXWon()) return +1;
if (hasOWon()) return -1;

List<Point> pointsAvailable = getAvailableStates();
if (pointsAvailable.isEmpty()) return 0;

int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

for (int i = 0; i < pointsAvailable.size(); ++i) {
Point point = pointsAvailable.get(i);
if (turn == 1) {
placeAMove(point, 1);
int currentScore = minimax(depth + 1, 2);
max = Math.max(currentScore, max);

if(depth == 0)System.out.println(“Score for position “+(i+1)+” = “+currentScore);
if(currentScore >= 0){ if(depth == 0) computersMove = point;}
if(currentScore == 1){board[point.x][point.y] = 0; break;}
if(i == pointsAvailable.size()-1 && max < 0){if(depth == 0)computersMove = point;}
} else if (turn == 2) {
placeAMove(point, 2);
int currentScore = minimax(depth + 1, 1);
min = Math.min(currentScore, min);
if(min == -1){board[point.x][point.y] = 0; break;}
}
board[point.x][point.y] = 0; //Reset this point
}
return turn == 1?max:min;
}
}

If X has won, check which values are equal, such as board [0] [0] is equal to [1] [1] and [0] [0] is equal to [2] [2]. This means that the diagonals are equal, [0] [0] is equal to 1, or board 0 is equal to [1] [1]. You have all diagonals, you have any one of the horizontal lines, or you have all three squares in a vertical line. If this happens, return true; otherwise, check the other values on the board. The following part of the code will check the values and return false if they do not comply with the preceding conditions:

public boolean hasXWon() {
if ((board[0][0] == board[1][1] && board[0][0] == board[2][2] && board[0][0] == 1) || (board[0][2] == board[1][1] && board[0][2] == board[2][0] && board[0][2] == 1)) {
return true;
}
for (int i = 0; i < 3; ++i) {
if (((board[i][0] == board[i][1] && board[i][0] == board[i][2] && board[i][0] == 1)
|| (board[0][i] == board[1][i] && board[0][i] == board[2][i] && board[0][i] == 1))) {
return true;
}
}
return false;
}

Next, look whether 0 has won and do the same thing for 0. Here, check whether the value is 2. Then, if nobody has won, check the available states for the users and print them. You’ll then have placeAMove, and either player 1 will move or player 2.

Next, you have takeHumanInput. Take the human input for the x and y points, and you’ll display the board using the displayBoard method. Finally, apply a min-max algorithm. Check if X has won or if 0 has won; if not, start playing the game, and print the score positions.

Finally, in the main class, start with the one who makes the first move (either the computer or the user). If your user starts a move, you have to provide the values in x and y coordinates (in an x and y plane); otherwise, the computer will start the move, and every time, you’ll have to check whether X has won. If X has won, you’ll print Unfortunately, you lost!, and if 0 has won, print You won!. If both win, then print It’s a draw!.

Run the program to get the following output:

Understanding the Min-Max Algorithm in AI Games

The preceding output has been printed at the initial position of the port. Now, you have to select your turn. Suppose you enter 1; you’ll get the following output:

Understanding the Min-Max Algorithm in AI Games

The computer’s went first and placed the position at [0] [0]. Now, it’s your move; so, place [0] [2]. This will enter 2 in the last position on your board, as shown in the following screenshot:

Understanding the Min-Max Algorithm in AI Games

Your 2 has been placed at [0] [2]. The preceding screenshot shows your current positions. The computer has placed a mark on [1] [0]. Now, place a mark on [2] [0], as follows:

Understanding the Min-Max Algorithm in AI Games

You now have a position over [2] [0] and blocked the computer. Now, the computer has entered 1 at [1] [1]. Put a mark on [1] [2] and block the computer again:

Understanding the Min-Max Algorithm in AI Games

The computer has entered 1 at [2] [2] and won the game.

If you found this article interesting, you can explore Nisheeth Joshi’s Hands-On Artificial Intelligence with Java for Beginners to build, train, and deploy intelligent applications using Java libraries. This book will help you to not only have a solid grasp of AI concepts, but you’ll also build your own smart applications for multiple domains.

 

 

 

 

 

 

Advertisements

One thought on “Artificial Intelligence with Java: Understanding the Min-Max Algorithm in AI Games

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s