# How Do I Make an AI Player in Connect Four? [duplicate]

I am trying to create me one of those connect four games. I was doing some research on it and i found it to be quite a nice little self project. So I made strides in getting the game to run. So it works like a two person game but i don't really like the idea of two players. My goal is to create a player vs computer connect four. I took it upon myself and do some reasearch as to how to get an AI vs Human game and I came across using the MinMax algorithm to accomplish my goal. I am a bit lost when it comes to implementing the MinMax algorithm. I came accross which seems to be a marvellous implementation of minmax Here. I have been struggling for the past few days to implement the minmax algorithm in my code. As i said earlier, For now my code is a two player human vs human game. How do I create an AI vs Human game?

Here is my code:

    import java.util.Arrays;
import java.util.Scanner;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class ConnectFour {
private static final char[] players = new char[] { 'X', 'O' };

private final int width, height;
private final char[][] grid;
private int lastCol = -1, lastTop = -1;

public ConnectFour(int width, int height) {
this.width = width;
this.height = height;
this.grid = new char[height][];
for (int h = 0; h < height; h++) {
Arrays.fill(this.grid[h] = new char[width], '.');
}
}

public String toString() {
return IntStream.range(0, this.width)
.mapToObj(Integer::toString)
.collect(Collectors.joining()) + "\n" +
Arrays.stream(this.grid)
.map(String::new)
.collect(Collectors.joining("\n"));
}

/**
* Prompts the user for a column, repeating until a valid
*/
public void chooseAndDrop(char symbol, Scanner input) {
do {
System.out.print("\nPlayer " + symbol + " turn: ");
int col = input.nextInt();

if (! (0 <= col && col < this.width)) {
System.out.println("Column must be between 0 and " +
(this.width - 1));
continue;
}
for (int h = this.height - 1; h >= 0; h--) {
if (this.grid[h][col] == '.') {
this.grid[this.lastTop=h][this.lastCol=col] = symbol;
return;
}
}

System.out.println("Column " + col + " is full.");
} while (true);
}

/**
* Detects whether the last chip played was a winning move.
*/
public boolean isWinningPlay() {
if (this.lastCol == -1) {
throw new IllegalStateException("No move has been made yet");
}
char sym = this.grid[this.lastTop][this.lastCol];
String streak = String.format("%c%c%c%c", sym, sym, sym, sym);
return contains(this.horizontal(), streak) ||
contains(this.vertical(), streak) ||
contains(this.slashDiagonal(), streak) ||
contains(this.backslashDiagonal(), streak);
}

/**
* The contents of the row containing the last played chip.
*/
private String horizontal() {
return new String(this.grid[this.lastTop]);
}

/**
* The contents of the column containing the last played chip.
*/
private String vertical() {
StringBuilder sb = new StringBuilder(this.height);
for (int h = 0; h < this.height; h++) {
sb.append(this.grid[h][this.lastCol]);
}
return sb.toString();
}

/**
* The contents of the "/" diagonal containing the last played chip
* (coordinates have a constant sum).
*/
private String slashDiagonal() {
StringBuilder sb = new StringBuilder(this.height);
for (int h = 0; h < this.height; h++) {
int w = this.lastCol + this.lastTop - h;
if (0 <= w && w < this.width) {
sb.append(this.grid[h][w]);
}
}
return sb.toString();
}

/**
* The contents of the "\" diagonal containing the last played chip
* (coordinates have a constant difference).
*/
private String backslashDiagonal() {
StringBuilder sb = new StringBuilder(this.height);
for (int h = 0; h < this.height; h++) {
int w = this.lastCol - this.lastTop + h;
if (0 <= w && w < this.width) {
sb.append(this.grid[h][w]);
}
}
return sb.toString();
}

private static boolean contains(String haystack, String needle) {
return haystack.indexOf(needle) >= 0;
}

public static void main(String[] args) {

int XColumnPosition;
int maxDepth = 4;
MinimaxAI OPlayer = new MinimaxAI(maxDepth, Board.O); // failed attempt to add minmax

try (Scanner input = new Scanner(System.in)) {
int height = 6, width = 8, moves = height * width;
ConnectFour board = new ConnectFour(width, height);
System.out.println("Use 0-" + (width - 1) + " to choose a column.");
System.out.println(board);

for (int player = 0; moves-- > 0; player = 1 - player) {
char symbol = players[player];
board.chooseAndDrop(symbol, input);
System.out.println(board);
if (board.isWinningPlay()) {
System.out.println("Player " + symbol + " wins!");
return;
}
}
System.out.println("Game over, no winner.");
}
}
}


And here is the MinMAx class:

 class MinimaxAI {

//Variable that holds the maximum depth the MiniMax algorithm will reach for this player
private int maxDepth;
//Variable that holds which letter this player controls
private int playerLetter;

public int getMaxDepth() {
return maxDepth;
}

public void setMaxDepth(int maxDepth) {
this.maxDepth = maxDepth;
}

public int getPlayerLetter() {
return playerLetter;
}

public void setPlayerLetter(int playerLetter) {
this.playerLetter = playerLetter;
}

public MinimaxAI() {
maxDepth = 4;
playerLetter = Board.X;
}

public MinimaxAI(int maxDepth, int playerLetter) {
this.maxDepth = maxDepth;
this.playerLetter = playerLetter;
}

//Initiates the MiniMax algorithm
public Move MiniMax(Board board) {
//If the X plays then it wants to MAXimize the heuristics value
if (playerLetter == Board.X) {
return max(new Board(board), 0);
}
//If the O plays then it wants to MINimize the heuristics value
else {
return min(new Board(board), 0);
}
}

// The max and min functions are called interchangingly, one after another until a max depth is reached
public Move max(Board board, int depth) {
Random r = new Random();

/* If MAX is called on a state that is terminal or after a maximum depth is reached,
* then a heuristic is calculated on the state and the move returned.
*/
if((board.checkGameOver()) || (depth == maxDepth))
{
Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate());
return lastMove;
}
//The children-moves of the state are calculated
ArrayList<Board> children = new ArrayList<Board>(board.getChildren(Board.X));
Move maxMove = new Move(Integer.MIN_VALUE);
for (Board child : children) {
//And for each child min is called, on a lower depth
Move move = min(child, depth + 1);
//The child-move with the greatest value is selected and returned by max
if(move.getValue() >= maxMove.getValue()) {
if ((move.getValue() == maxMove.getValue())) {
//If the heuristic has the same value then we randomly choose one of the two moves
if (r.nextInt(2) == 0) {
maxMove.setRow(child.getLastMove().getRow());
maxMove.setCol(child.getLastMove().getCol());
maxMove.setValue(move.getValue());
}
}
else {
maxMove.setRow(child.getLastMove().getRow());
maxMove.setCol(child.getLastMove().getCol());
maxMove.setValue(move.getValue());
}
}
}
return maxMove;
}

//Min works similarly to max
public Move min(Board board, int depth) {
Random r = new Random();

if((board.checkGameOver()) || (depth == maxDepth)) {
Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate());
return lastMove;
}
ArrayList<Board> children = new ArrayList<Board>(board.getChildren(Board.O));
Move minMove = new Move(Integer.MAX_VALUE);
for (Board child : children) {
Move move = max(child, depth + 1);
if(move.getValue() <= minMove.getValue()) {
if ((move.getValue() == minMove.getValue())) {
if (r.nextInt(2) == 0) {
minMove.setRow(child.getLastMove().getRow());
minMove.setCol(child.getLastMove().getCol());
minMove.setValue(move.getValue());
}
}
else {
minMove.setRow(child.getLastMove().getRow());
minMove.setCol(child.getLastMove().getCol());
minMove.setValue(move.getValue());
}
}
}
return minMove;
}

}


## marked as duplicate by Almo, Philipp, DMGregory♦, Sean Middleditch, Vaillancourt♦Jan 4 '17 at 21:01

• What's the question exactly? – Vaillancourt Dec 19 '16 at 2:37
• Code dump question. we need more specific question. – Almo Dec 19 '16 at 3:26
• @Almo I apolgize for my lack of clarity. I would like to implement an AI vs Human oppose to Human vs Human to my game. – Thomas C Dec 19 '16 at 4:08
• The problem with Min Max is usually the "good stuff" happens deeper than you can search for in a reasonable time, so what do you do if you can't see the light at the end of the tunnel. Look for a paper on Connect 4 written by Victor Allis. That should get you to the promised land. – Mike White Dec 19 '16 at 7:15
• @ThomasC why don't you just use your normal player vs player code but on the AI's turn just do a random number. It will be a simpler start you can probably then see more to expand on. – lozzajp Dec 19 '16 at 9:25

I understand that the OP is mostly asking for the integration of his AI in his program, rather than the algorithm itself as he said using min-max already

My first intuition for a Connect-four game would be to have a game loop processing the turns.

while (gameOn)
{
// Get user or AI input
// Process the input
}


As you have 2 players, you would need to know which turn it is. You can have a variable for that.

int playerNb = 0;
while (gameOn)
{
if (playerNb == 0)
// Get user input
else
// Get AI input

// Process the input
// Change playerNb to 1 or 0
}


Then just implement your algorithm in the GetAIInput() method. A min-max algorithm may be well-suited for this problem, but I would suggest you try different approaches so you can see how the AI reacts each time. That will be a really good exercise which will help you understand the basis of AI development if you are new to this.

• Hey mate thanks for that explanation. It makes much more sense to me. – Thomas C Dec 19 '16 at 17:09
• I have a question, in your representation i see you have while(gameOn) ... What is gameOn? a Variable or a function? – Thomas C Dec 19 '16 at 18:26
• It is a variable. I suggest you read some tutorials about game loops and stuff related, it will be easier then to focus on creating the AI – realUser404 Dec 20 '16 at 9:17