# connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...

• November 20th, 2013, 05:14 AM
wickerman
connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
I edited this post because i didnt wrap the code and so it wasted a lot of room and it was annoying....the src code is to my nest post...ty
• November 20th, 2013, 05:16 AM
GregBrannon
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
How about we ignore all code not posted properly? Please review the "Announcement" topic at the top of the sub-forum for instructions and other useful tips for newcomers.

Also, ask a question. "My algorithm is stupid," is not helpful.
• November 20th, 2013, 05:28 AM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Thanks for your immediate response and i m sorry for ignorance....English its not my native language so i couldnt express in few words that my algorithm runs but not properly...i will read the announcement then i ll repost...thanks again!!!

--- Update ---

Please ignore some comments...its from a previous tic tac toe project

Code Java:

```/* A class describing a move in the board * Every produced child corresponds to a move * and we need to keep the moves as well as the states. */ public class Move { private int row; private int col; private int value;   public Move() { row = -1; col = -1; value = 0; }   public Move(int row, int col) { this.row = row; this.col = col; this.value = -1; }   public Move(int value) { this.row = -1; this.col = -1; this.value = value; }   public Move(int row, int col, int value) { this.row = row; this.col = col; this.value = value; }   public int getRow() { return row; }   public int getCol() { return col; }   public int getValue() { return value; }   public void setRow(int row) { this.row = row; }   public void setCol(int col) { this.col = col; }   public void setValue(int value) { this.value = value; } }     import java.util.ArrayList;   public class Board { //Variables for the Boards values public static final int X = 1; public static final int O = -1; public static final int EMPTY = 0; private static int[][] evaluationTable = {{3, 4, 5, 7, 5, 4, 3}, {4, 6, 8, 10, 8, 6, 4}, {5, 8, 11, 13, 11, 8, 5}, {5, 8, 11, 13, 11, 8, 5}, {4, 6, 8, 10, 8, 6, 4}, {3, 4, 5, 7, 5, 4, 3}};   //Immediate move that lead to this board private Move lastMove;   /* Variable containing who played last; whose turn resulted in this board * Even a new Board has lastLetterPlayed value; it denotes which player will play first */ private int lastLetterPlayed;   private int [][] gameBoard;   public Board() { lastMove = new Move(); lastLetterPlayed = O; gameBoard = new int[6][7]; for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { gameBoard[i][j] = EMPTY; } } }   public Board(Board board) { lastMove = board.lastMove; lastLetterPlayed = board.lastLetterPlayed; gameBoard = new int[6][7]; for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { gameBoard[i][j] = board.gameBoard[i][j]; } } }   public Move getLastMove() { return lastMove; }   public int getLastLetterPlayed() { return lastLetterPlayed; }   public int[][] getGameBoard() { return gameBoard; }   public void setLastMove(Move lastMove) { this.lastMove.setRow(lastMove.getRow()); this.lastMove.setCol(lastMove.getCol()); this.lastMove.setValue(lastMove.getValue()); }   public void setLastLetterPlayed(int lastLetterPlayed) { this.lastLetterPlayed = lastLetterPlayed; }   public void setGameBoard(int[][] gameBoard) { for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { this.gameBoard[i][j] = gameBoard[i][j]; } } }   //Make a move; it places a letter in the board public void makeMove(int col, int letter) { for (int i = 5; i >= 0; i--) if (gameBoard[i][col] == EMPTY) { gameBoard[i][col] = letter; lastMove = new Move(i,col,letter); lastLetterPlayed = letter; break; }     }   //Checks whether a move is valid; whether a square is empty public boolean isValidMove(int col) { if (col > 6 || col < 0 || gameBoard[0][col] != EMPTY) return false; else return true; }   /* Generates the children of the state * Any square in the board that is empty results to a child */ public ArrayList<Board> getChildren(int letter) { ArrayList<Board> children = new ArrayList<Board>(); for(int row=0; row<6; row++) { for(int col=0; col<7; col++) { if(isValidMove(col)) { Board child = new Board(this); child.makeMove(col, letter); children.add(child); } } } return children; }   /* * The heuristic we use to evaluate is * the number our almost complete tic-tac-toes (having 2 letter in a row, column or diagonal) * minus the number of the opponent's almost complete tic-tac-toes * Special case: if a complete tic-tac-toe is present it counts as ten */ public int evaluate(int letter) { int v = 1; int d = 2; int h = 3;   int twoIn = 10; int threeIn = 1000;   int val = 0;     int count=0; for (int row =0; row<6; row++) { for (int col=0; col<7; col++) { if (gameBoard[row][col] == X) { count++; } } } if (count == 1) { if (gameBoard[5][3]==X) { return 4; } else if (gameBoard[5][4]==X) { return 2; } else { return 3; } } else if (count == 0){ return 3; }     //Check for horizontal 2-in-a-row.       for (int row=0;row<6;row++) { for (int col = 0;col<4;col++) { //(xx00) if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == 0 && gameBoard[row][col+3] == 0) { val+= twoIn*h; } //(x0x0) else if (gameBoard[row][col] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col+3] == 0) { val+= twoIn*h; } //(x00x) else if (gameBoard[row][col] == letter && gameBoard[row][col+3] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col+2] == 0) { val+= twoIn*h; } //(0xx0) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == 0) { val+= 2*twoIn*h; } //(0x0x) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == 0 && gameBoard[row][col+3] == letter) { val+= twoIn*h; } //(00xx) else if (gameBoard[row][col] == 0 && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == letter) { val+= twoIn*h; } } }   //Check for vertical spaced 2-in-a-row. // 0 // x // x   for (int row=5;row>1;row--) { for (int col = 0;col<7;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col] && gameBoard[row-2][col] == 0) { val+= twoIn*v; } } } //Check for diagonal spaced 2-in-a-row (/). // 0 x x x 0 0 // 0 0 x 0 x x // x 0 0 x 0 x // x x 0 0 x 0 for (int row=5;row>2;row--) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row-2][col+2] == 0 && gameBoard[row-3][col+3] == 0) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row-2][col+2] == 0 && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == 0 && gameBoard[row-2][col+2] == letter && gameBoard[row-3][col+3] == letter) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-1][col+1] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= 2*twoIn*d; } } } //Check for diagonal spaced 3-in-a-row (\). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=0;row<3;row++) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row+2][col+2] == 0 && gameBoard[row+3][col+3] == 0) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row+1][col+1] == 0 && gameBoard[row+2][col+2] == 0 && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == 0 && gameBoard[row+2][col+2] == letter && gameBoard[row+3][col+3] == letter) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col]== letter && gameBoard[row+1][col+1] == 0 && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row+1][col+1] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= twoIn*2*d; } } } //Check for horizontal 3-in-a-row. for (int row=0;row<6;row++) { for (int col = 0;col<4;col++) { //(xx0x) if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == 0 && gameBoard[row][col] == gameBoard[row][col+3]) { val+= threeIn*h; } //(x0xx) else if (gameBoard[row][col] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col] == gameBoard[row][col+3]) { val+= threeIn*h; } //(0xxx) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+1] == gameBoard[row][col+2] && gameBoard[row][col+1] == gameBoard[row][col+3]) { val+= threeIn*h; } //(xxx0) else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col+3] == 0) { val+= threeIn*h; } } }   //Check for vertical spaced 3-in-a-row. // 0 // x // x // x for (int row=5;row>2;row--) { for (int col = 0;col<7;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col] && gameBoard[row][col] == gameBoard[row-2][col] && gameBoard[row-3][col] == 0) { val+= threeIn*v; } } } //Check for diagonal spaced 3-in-a-row (/). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=5;row>2;row--) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-3][col+3] == 0) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row-2][col+2] == 0 && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-1][col+1] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3] ) { val+= threeIn*d; } } } //Check for diagonal spaced 3-in-a-row (\). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=0;row<3;row++) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row+1][col+1] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1]== gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col]== letter && gameBoard[row+1][col+1] == 0 && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row+2][col+2] == 0 && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+3][col+3] == 0) { val+= threeIn*d; } } }   //Check for open-ended 3-in-a-row. (0xxx0) for (int row=0;row<6;row++) { for (int col = 0;col<3;col++) { //horizontal if (gameBoard[row][col]== 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == letter && gameBoard[row][col] == gameBoard[row][col+4]) { val+= 2*threeIn*h; } } } for (int row=0;row<2;row++) { for (int col = 0;col<3;col++) { //diag(\) if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3] && gameBoard[row+4][col+4] == 0) { val+= 2*threeIn*d; } } } //diag(/) for (int row=5;row>3;row--) { for (int col = 0;col<3;col++) { if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-2][col+2] == letter && gameBoard[row-3][col+3] == letter && gameBoard[row-4][col+4] == 0) { val+= 2*threeIn*d; } } } if (letter>0)return val; else return -val;   }       /* * A state is terminal if there is a tic-tac-toe * or no empty tiles are available */ public boolean isTerminal() { //check for win horizontally for (int row=0; row<6; row++) for (int col=0; col<7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col] == gameBoard[row][col+3]) return true; //check for win vertically for (int row = 0; row < 6-3; row++) for (int col = 0; col < 7; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row+1][col] && gameBoard[row][col] == gameBoard[row+2][col] && gameBoard[row][col] == gameBoard[row+3][col]) return true; //check for win diagonally (upper left to lower right) for (int row = 0; row < 6-3; row++) for (int col = 0; col < 7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) return true; //check for win diagonally (lower left to upper right) for (int row = 3; row < 6; row++) for (int col = 0; col < 7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) return true; return false; }   //Prints the board public void print() { System.out.println("*****************"); for(int row=0; row<6; row++) { System.out.print("* "); for(int col=0; col<7; col++) { switch (gameBoard[row][col]) { case X: System.out.print("X "); break; case O: System.out.print("O "); break; case EMPTY: System.out.print("- "); break; default: break; } } System.out.println("*"); } System.out.println("*****************"); } }       import java.util.ArrayList; import java.util.Random;   public class GamePlayer { //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 GamePlayer() { maxDepth = 2; playerLetter = Board.X; }   public GamePlayer(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.isTerminal()) || (depth == maxDepth)) { Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate(playerLetter)); 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 save 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.isTerminal()) || (depth == maxDepth)) { Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate(playerLetter)); 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; } }   import java.util.Scanner; public class Player{   //Variable that holds which letter this player controls private int playerLetter; Move play;   Scanner scan = new Scanner(System.in);   public Player() { playerLetter = Board.X; }   public Player(int playerLetter) { this.playerLetter = playerLetter; }   public Move play(Board board){   System.out.print("Choose a column(1 - 7): "); int col = scan.nextInt() - 1; System.out.println(); while(!board.isValidMove(col)){ System.out.println("Your move is not valid.Try again.."); System.out.print("Choose a column: "); col = scan.nextInt() - 1 ; System.out.println(); } for (int i = 5; i >= 0; i--) { if (board.getGameBoard()[i][col] == 0) { play = new Move(i,col,playerLetter); board.setLastLetterPlayed(playerLetter); board.setLastMove(play); break; } } return play;   }     }   public class Main { public static void main(String[] args) { //We create the players and the board //MaxDepth for the MiniMax algorithm is set to 2; feel free to change the values Player XPlayer = new Player(Board.X); GamePlayer OPlayer = new GamePlayer(2, Board.O); Board board = new Board();   //Put this out of comments for the O to play first //board.setLastLetterPlayed(Board.X);   board.print(); //While the game has not finished while(!board.isTerminal()) { System.out.println(); switch (board.getLastLetterPlayed()) { //If X played last, then 0 plays now case Board.X: System.out.println("O moves"); Move OMove = OPlayer.MiniMax(board); board.makeMove(OMove.getCol(), Board.O); break; //If O played last, then X plays now case Board.O: System.out.println("X moves"); Move XMove = XPlayer.play(board); board.makeMove(XMove.getCol(), Board.X); break; default: break; } board.print(); }   }   }```
• November 20th, 2013, 05:34 AM
GregBrannon
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Ahh, you wrote like a native.

Now describe how your algorithm is failing you. What is or is not happening in your program that you'd like help with?
• November 20th, 2013, 05:47 AM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Hmm...in a few words, u are trying lose from the pc Player...
From the runs i noticed that pc player rare tries to stop your connect 4 and also rare finishes the game when it has 3 in a row,winning state...
That's why i called it "stupid"..

I found the evaluation code from internet...So i dont think it's wrong...i m new to artificial intelligence so i dont really have a clue what is wrong...

I can't find a way to thank you for spending your time to help me...!!!:)
• November 20th, 2013, 05:59 AM
Norm
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Some how the code has lost its formatting. Logically nested statements within {} should be indented to make the code readable.
All the statements should NOT start in the first column.
• November 20th, 2013, 06:06 AM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
[/COLOR]Here is the code again...i hope this time without lose the formatting... :/

Code java:

```/* A class describing a move in the board * Every produced child corresponds to a move * and we need to keep the moves as well as the states. */ public class Move { private int row; private int col; private int value;   public Move() { row = -1; col = -1; value = 0; }   public Move(int row, int col) { this.row = row; this.col = col; this.value = -1; }   public Move(int value) { this.row = -1; this.col = -1; this.value = value; }   public Move(int row, int col, int value) { this.row = row; this.col = col; this.value = value; }   public int getRow() { return row; }   public int getCol() { return col; }   public int getValue() { return value; }   public void setRow(int row) { this.row = row; }   public void setCol(int col) { this.col = col; }   public void setValue(int value) { this.value = value; } }         import java.util.ArrayList;   public class Board { //Variables for the Boards values public static final int X = 1; public static final int O = -1; public static final int EMPTY = 0; private static int[][] evaluationTable = {{3, 4, 5, 7, 5, 4, 3}, {4, 6, 8, 10, 8, 6, 4}, {5, 8, 11, 13, 11, 8, 5}, {5, 8, 11, 13, 11, 8, 5}, {4, 6, 8, 10, 8, 6, 4}, {3, 4, 5, 7, 5, 4, 3}};   //Immediate move that lead to this board private Move lastMove;   /* Variable containing who played last; whose turn resulted in this board * Even a new Board has lastLetterPlayed value; it denotes which player will play first */ private int lastLetterPlayed;   private int [][] gameBoard;   public Board() { lastMove = new Move(); lastLetterPlayed = O; gameBoard = new int[6][7]; for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { gameBoard[i][j] = EMPTY; } } }   public Board(Board board) { lastMove = board.lastMove; lastLetterPlayed = board.lastLetterPlayed; gameBoard = new int[6][7]; for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { gameBoard[i][j] = board.gameBoard[i][j]; } } }   public Move getLastMove() { return lastMove; }   public int getLastLetterPlayed() { return lastLetterPlayed; }   public int[][] getGameBoard() { return gameBoard; }   public void setLastMove(Move lastMove) { this.lastMove.setRow(lastMove.getRow()); this.lastMove.setCol(lastMove.getCol()); this.lastMove.setValue(lastMove.getValue()); }   public void setLastLetterPlayed(int lastLetterPlayed) { this.lastLetterPlayed = lastLetterPlayed; }   public void setGameBoard(int[][] gameBoard) { for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { this.gameBoard[i][j] = gameBoard[i][j]; } } }   //Make a move; it places a letter in the board public void makeMove(int col, int letter) { for (int i = 5; i >= 0; i--) if (gameBoard[i][col] == EMPTY) { gameBoard[i][col] = letter; lastMove = new Move(i,col,letter); lastLetterPlayed = letter; break; }     }   //Checks whether a move is valid; whether a square is empty public boolean isValidMove(int col) { if (col > 6 || col < 0 || gameBoard[0][col] != EMPTY) return false; else return true; }   /* Generates the children of the state * Any square in the board that is empty results to a child */ public ArrayList<Board> getChildren(int letter) { ArrayList<Board> children = new ArrayList<Board>(); for(int row=0; row<6; row++) { for(int col=0; col<7; col++) { if(isValidMove(col)) { Board child = new Board(this); child.makeMove(col, letter); children.add(child); } } } return children; }   /* * The heuristic we use to evaluate is * the number our almost complete tic-tac-toes (having 2 letter in a row, column or diagonal) * minus the number of the opponent's almost complete tic-tac-toes * Special case: if a complete tic-tac-toe is present it counts as ten */ public int evaluate(int letter) { int v = 1; int d = 2; int h = 3;   int twoIn = 10; int threeIn = 1000;   int val = 0;     int count=0; for (int row =0; row<6; row++) { for (int col=0; col<7; col++) { if (gameBoard[row][col] == X) { count++; } } } if (count == 1) { if (gameBoard[5][3]==X) { return 4; } else if (gameBoard[5][4]==X) { return 2; } else { return 3; } } else if (count == 0){ return 3; }     //Check for horizontal 2-in-a-row.       for (int row=0;row<6;row++) { for (int col = 0;col<4;col++) { //(xx00) if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == 0 && gameBoard[row][col+3] == 0) { val+= twoIn*h; } //(x0x0) else if (gameBoard[row][col] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col+3] == 0) { val+= twoIn*h; } //(x00x) else if (gameBoard[row][col] == letter && gameBoard[row][col+3] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col+2] == 0) { val+= twoIn*h; } //(0xx0) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == 0) { val+= 2*twoIn*h; } //(0x0x) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == 0 && gameBoard[row][col+3] == letter) { val+= twoIn*h; } //(00xx) else if (gameBoard[row][col] == 0 && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == letter) { val+= twoIn*h; } } }   //Check for vertical spaced 2-in-a-row. // 0 // x // x   for (int row=5;row>1;row--) { for (int col = 0;col<7;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col] && gameBoard[row-2][col] == 0) { val+= twoIn*v; } } } //Check for diagonal spaced 2-in-a-row (/). // 0 x x x 0 0 // 0 0 x 0 x x // x 0 0 x 0 x // x x 0 0 x 0 for (int row=5;row>2;row--) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row-2][col+2] == 0 && gameBoard[row-3][col+3] == 0) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row-2][col+2] == 0 && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == 0 && gameBoard[row-2][col+2] == letter && gameBoard[row-3][col+3] == letter) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-1][col+1] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= 2*twoIn*d; } } } //Check for diagonal spaced 3-in-a-row (\). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=0;row<3;row++) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row+2][col+2] == 0 && gameBoard[row+3][col+3] == 0) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row+1][col+1] == 0 && gameBoard[row+2][col+2] == 0 && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == 0 && gameBoard[row+2][col+2] == letter && gameBoard[row+3][col+3] == letter) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col]== letter && gameBoard[row+1][col+1] == 0 && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row+1][col+1] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= twoIn*2*d; } } } //Check for horizontal 3-in-a-row. for (int row=0;row<6;row++) { for (int col = 0;col<4;col++) { //(xx0x) if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == 0 && gameBoard[row][col] == gameBoard[row][col+3]) { val+= threeIn*h; } //(x0xx) else if (gameBoard[row][col] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col] == gameBoard[row][col+3]) { val+= threeIn*h; } //(0xxx) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+1] == gameBoard[row][col+2] && gameBoard[row][col+1] == gameBoard[row][col+3]) { val+= threeIn*h; } //(xxx0) else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col+3] == 0) { val+= threeIn*h; } } }   //Check for vertical spaced 3-in-a-row. // 0 // x // x // x for (int row=5;row>2;row--) { for (int col = 0;col<7;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col] && gameBoard[row][col] == gameBoard[row-2][col] && gameBoard[row-3][col] == 0) { val+= threeIn*v; } } } //Check for diagonal spaced 3-in-a-row (/). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=5;row>2;row--) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-3][col+3] == 0) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row-2][col+2] == 0 && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-1][col+1] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3] ) { val+= threeIn*d; } } } //Check for diagonal spaced 3-in-a-row (\). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=0;row<3;row++) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row+1][col+1] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1]== gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col]== letter && gameBoard[row+1][col+1] == 0 && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row+2][col+2] == 0 && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+3][col+3] == 0) { val+= threeIn*d; } } }   //Check for open-ended 3-in-a-row. (0xxx0) for (int row=0;row<6;row++) { for (int col = 0;col<3;col++) { //horizontal if (gameBoard[row][col]== 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == letter && gameBoard[row][col] == gameBoard[row][col+4]) { val+= 2*threeIn*h; } } } for (int row=0;row<2;row++) { for (int col = 0;col<3;col++) { //diag(\) if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3] && gameBoard[row+4][col+4] == 0) { val+= 2*threeIn*d; } } } //diag(/) for (int row=5;row>3;row--) { for (int col = 0;col<3;col++) { if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-2][col+2] == letter && gameBoard[row-3][col+3] == letter && gameBoard[row-4][col+4] == 0) { val+= 2*threeIn*d; } } } if (letter>0)return val; else return -val;   }       /* * A state is terminal if there is a tic-tac-toe * or no empty tiles are available */ public boolean isTerminal() { //check for win horizontally for (int row=0; row<6; row++) for (int col=0; col<7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col] == gameBoard[row][col+3]) return true; //check for win vertically for (int row = 0; row < 6-3; row++) for (int col = 0; col < 7; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row+1][col] && gameBoard[row][col] == gameBoard[row+2][col] && gameBoard[row][col] == gameBoard[row+3][col]) return true; //check for win diagonally (upper left to lower right) for (int row = 0; row < 6-3; row++) for (int col = 0; col < 7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) return true; //check for win diagonally (lower left to upper right) for (int row = 3; row < 6; row++) for (int col = 0; col < 7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) return true; return false; }   //Prints the board public void print() { System.out.println("*****************"); for(int row=0; row<6; row++) { System.out.print("* "); for(int col=0; col<7; col++) { switch (gameBoard[row][col]) { case X: System.out.print("X "); break; case O: System.out.print("O "); break; case EMPTY: System.out.print("- "); break; default: break; } } System.out.println("*"); } System.out.println("*****************"); } }         import java.util.ArrayList; import java.util.Random;   public class GamePlayer { //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 GamePlayer() { maxDepth = 2; playerLetter = Board.X; }   public GamePlayer(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.isTerminal()) || (depth == maxDepth)) { Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate(playerLetter)); 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 save 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.isTerminal()) || (depth == maxDepth)) { Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate(playerLetter)); 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; } }             import java.util.Scanner; public class Player{   //Variable that holds which letter this player controls private int playerLetter; Move play;   Scanner scan = new Scanner(System.in);   public Player() { playerLetter = Board.X; }   public Player(int playerLetter) { this.playerLetter = playerLetter; }   public Move play(Board board){   System.out.print("Choose a column(1 - 7): "); int col = scan.nextInt() - 1; System.out.println(); while(!board.isValidMove(col)){ System.out.println("Your move is not valid.Try again.."); System.out.print("Choose a column: "); col = scan.nextInt() - 1 ; System.out.println(); } for (int i = 5; i >= 0; i--) { if (board.getGameBoard()[i][col] == 0) { play = new Move(i,col,playerLetter); board.setLastLetterPlayed(playerLetter); board.setLastMove(play); break; } } return play;   }     }         public class Main { public static void main(String[] args) { //We create the players and the board //MaxDepth for the MiniMax algorithm is set to 2; feel free to change the values Player XPlayer = new Player(Board.X); GamePlayer OPlayer = new GamePlayer(2, Board.O); Board board = new Board();   //Put this out of comments for the O to play first //board.setLastLetterPlayed(Board.X);   board.print(); //While the game has not finished while(!board.isTerminal()) { System.out.println(); switch (board.getLastLetterPlayed()) { //If X played last, then 0 plays now case Board.X: System.out.println("O moves"); Move OMove = OPlayer.MiniMax(board); board.makeMove(OMove.getCol(), Board.O); break; //If O played last, then X plays now case Board.O: System.out.println("X moves"); Move XMove = XPlayer.play(board); board.makeMove(XMove.getCol(), Board.X); break; default: break; } board.print(); }   }   }```
• November 20th, 2013, 06:29 AM
Norm
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Much better. Now could you give a sample of the player's input that could be put into the code to make testing faster and easier? The input can be preloaded into the Scanner's constructor:
Code :

` Scanner scan = new Scanner("1 2 3 4 5 6 7 8"); //System.in); // preload user's responses`
Then add some comments saying where the computer should have played given the user input provided above.
• November 20th, 2013, 06:44 AM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
i used to make quick tests by inserting two gamePlayers at my main method....

so main will be like that:
Code java:

```public class Main { public static void main(String[] args) { //We create the players and the board //MaxDepth for the MiniMax algorithm is set to 2; feel free to change the values   GamePlayer XPlayer = new GamePlayer(2, Board.X); GamePlayer OPlayer = new GamePlayer(2, Board.O); Board board = new Board();   //Put this out of comments for the O to play first //board.setLastLetterPlayed(Board.X);   board.print(); //While the game has not finished while(!board.isTerminal()) { System.out.println(); switch (board.getLastLetterPlayed()) { //If X played last, then 0 plays now case Board.X: System.out.println("O moves"); Move OMove = OPlayer.MiniMax(board); board.makeMove(OMove.getCol(), Board.O); break; //If O played last, then X plays now case Board.O: System.out.println("X moves"); Move XMove = XPlayer.MiniMax(board); board.makeMove(XMove.getCol(), Board.X); break; default: break; } board.print(); }   }   }```

A common win for user player its by playing columns 4 3 2 1...i supposed you ran the code by yourself, so i think my answer will help you..
• November 20th, 2013, 06:48 AM
Norm
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
If the user plays: 4 3 2 1
where the computer should have played given the user input provided above?

How are you debugging the code? I use println() statements to print out the values of variables as the code executes to see what the code is doing.
• November 20th, 2013, 06:59 AM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
I found the evaluation method on internet...So as i understood the the algorithm when the user plays 4 the computer should play 5 but the most times plays 7...

I m debugging the code by trying new code at parts that i thought they are wrong...Obviously without success..

I think the error has to do smth with the depth...but as i said above i m really new to artificial intelligence and i cant understand what the values of variables should be to debug it properly ... :/
• November 20th, 2013, 07:06 AM
Norm
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Quote:

when the user plays 4 the computer should play 5
If that is the best move, why does the code chose some other move? Debug the code to see why it is not choosing 5.

I don't know the game or AI, I can only make suggestions to help you see what the code is currently doing. It will be your task to find why the code does what it does and to make changes so that it will do what you want.
• November 20th, 2013, 07:31 AM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Thanks a lot...I will make some tests and if have progress i ll let u know !!!!!!!
Thanks again...!!!!!!!!!!!!!
• November 20th, 2013, 11:58 PM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Hello guys...I added some some debug lines to gamePlayer class and i changed a little my evaluation method from board class...Here is the code :
Code java:

```import java.util.ArrayList; import java.util.Random;   public class GamePlayer { //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 GamePlayer() { maxDepth = 2; playerLetter = Board.X; }   public GamePlayer(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.isTerminal()) || (depth == maxDepth)) { Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate(playerLetter)); System.out.println(lastMove.getRow() + " "+lastMove.getCol() + " "+lastMove.getValue() +" max"); 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 save 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.isTerminal()) || (depth == maxDepth)) { Move lastMove = new Move(board.getLastMove().getRow(), board.getLastMove().getCol(), board.evaluate(playerLetter)); System.out.println(lastMove.getRow() + " "+lastMove.getCol() + " "+lastMove.getValue() +" min"); 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; } }                   import java.util.ArrayList;   public class Board { //Variables for the Boards values public static final int X = 1; public static final int O = -1; public static final int EMPTY = 0; private static int[][] evaluationTable = {{3, 4, 5, 7, 5, 4, 3}, {4, 6, 8, 10, 8, 6, 4}, {5, 8, 11, 13, 11, 8, 5}, {5, 8, 11, 13, 11, 8, 5}, {4, 6, 8, 10, 8, 6, 4}, {3, 4, 5, 7, 5, 4, 3}};   //Immediate move that lead to this board private Move lastMove;   /* Variable containing who played last; whose turn resulted in this board * Even a new Board has lastLetterPlayed value; it denotes which player will play first */ private int lastLetterPlayed;   private int [][] gameBoard;   public Board() { lastMove = new Move(); lastLetterPlayed = O; gameBoard = new int[6][7]; for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { gameBoard[i][j] = EMPTY; } } }   public Board(Board board) { lastMove = board.lastMove; lastLetterPlayed = board.lastLetterPlayed; gameBoard = new int[6][7]; for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { gameBoard[i][j] = board.gameBoard[i][j]; } } }   public Move getLastMove() { return lastMove; }   public int getLastLetterPlayed() { return lastLetterPlayed; }   public int[][] getGameBoard() { return gameBoard; }   public void setLastMove(Move lastMove) { this.lastMove.setRow(lastMove.getRow()); this.lastMove.setCol(lastMove.getCol()); this.lastMove.setValue(lastMove.getValue()); }   public void setLastLetterPlayed(int lastLetterPlayed) { this.lastLetterPlayed = lastLetterPlayed; }   public void setGameBoard(int[][] gameBoard) { for(int i=0; i<6; i++) { for(int j=0; j<7; j++) { this.gameBoard[i][j] = gameBoard[i][j]; } } }   //Make a move; it places a letter in the board public void makeMove(int col, int letter) { for (int i = 5; i >= 0; i--) if (gameBoard[i][col] == EMPTY) { gameBoard[i][col] = letter; lastMove = new Move(i,col,letter); lastLetterPlayed = letter; break; }     }   //Checks whether a move is valid; whether a square is empty public boolean isValidMove(int col) { if (col > 6 || col < 0 || gameBoard[0][col] != EMPTY) return false; else return true; }   /* Generates the children of the state * Any square in the board that is empty results to a child */ public ArrayList<Board> getChildren(int letter) { ArrayList<Board> children = new ArrayList<Board>(); for(int row=5; row>=0; row--) { for(int col=0; col<7; col++) { if(isValidMove(col)) { Board child = new Board(this); child.makeMove(col, letter); children.add(child); } } } return children; }   /* * The heuristic we use to evaluate is * the number our almost complete tic-tac-toes (having 2 letter in a row, column or diagonal) * minus the number of the opponent's almost complete tic-tac-toes * Special case: if a complete tic-tac-toe is present it counts as ten */ public int evaluate(int letter) { int v = 1; int d = 2; int h = 3;   int twoIn = 10; int threeIn = 1000;   int val = 0;         //Check for horizontal 2-in-a-row.       for (int row=0;row<6;row++) { for (int col = 0;col<4;col++) { //(xx00) if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == 0 && gameBoard[row][col+3] == 0) { val+= twoIn*h; } //(x0x0) else if (gameBoard[row][col] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col+3] == 0) { val+= twoIn*h; } //(x00x) else if (gameBoard[row][col] == letter && gameBoard[row][col+3] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col+2] == 0) { val+= twoIn*h; } //(0xx0) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == 0) { val+= 2*twoIn*h; } //(0x0x) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == 0 && gameBoard[row][col+3] == letter) { val+= twoIn*h; } //(00xx) else if (gameBoard[row][col] == 0 && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == letter) { val+= twoIn*h; } } }   //Check for vertical spaced 2-in-a-row. // 0 // x // x   for (int row=5;row>1;row--) { for (int col = 0;col<7;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col] && gameBoard[row-2][col] == 0) { val+= twoIn*v; } } } //Check for diagonal spaced 2-in-a-row (/). // 0 x x x 0 0 // 0 0 x 0 x x // x 0 0 x 0 x // x x 0 0 x 0 for (int row=5;row>2;row--) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row-2][col+2] == 0 && gameBoard[row-3][col+3] == 0) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row-2][col+2] == 0 && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == 0 && gameBoard[row-2][col+2] == letter && gameBoard[row-3][col+3] == letter) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-1][col+1] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= 2*twoIn*d; } } } //Check for diagonal spaced 3-in-a-row (\). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=0;row<3;row++) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row+2][col+2] == 0 && gameBoard[row+3][col+3] == 0) { val+= twoIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row+1][col+1] == 0 && gameBoard[row+2][col+2] == 0 && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == 0 && gameBoard[row+2][col+2] == letter && gameBoard[row+3][col+3] == letter) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col]== letter && gameBoard[row+1][col+1] == 0 && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1] == gameBoard[row+3][col+3]) { val+= twoIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row+1][col+1] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= twoIn*2*d; } } } //Check for horizontal 3-in-a-row. for (int row=0;row<6;row++) { for (int col = 0;col<4;col++) { //(xx0x) if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col+2] == 0 && gameBoard[row][col] == gameBoard[row][col+3]) { val+= threeIn*h; } //(x0xx) else if (gameBoard[row][col] == letter && gameBoard[row][col+1] == 0 && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col] == gameBoard[row][col+3]) { val+= threeIn*h; } //(0xxx) else if (gameBoard[row][col] == 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+1] == gameBoard[row][col+2] && gameBoard[row][col+1] == gameBoard[row][col+3]) { val+= threeIn*h; } //(xxx0) else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col+3] == 0) { val+= threeIn*h; } } }   //Check for vertical spaced 3-in-a-row. // 0 // x // x // x for (int row=5;row>2;row--) { for (int col = 0;col<7;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col] && gameBoard[row][col] == gameBoard[row-2][col] && gameBoard[row-3][col] == 0) { val+= threeIn*v; } } } //Check for diagonal spaced 3-in-a-row (/). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=5;row>2;row--) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row-3][col+3] == 0) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row-2][col+2] == 0 && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row-1][col+1] == 0 && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-1][col+1] == gameBoard[row-2][col+2] && gameBoard[row-1][col+1] == gameBoard[row-3][col+3] ) { val+= threeIn*d; } } } //Check for diagonal spaced 3-in-a-row (\). // 0 x x x // x 0 x x // x x 0 x // x x x 0 for (int row=0;row<3;row++) { for (int col = 0;col<4;col++) { if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row+1][col+1] == gameBoard[row+2][col+2] && gameBoard[row+1][col+1]== gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col]== letter && gameBoard[row+1][col+1] == 0 && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row+2][col+2] == 0 && gameBoard[row][col] == gameBoard[row+3][col+3]) { val+= threeIn*d; } else if (gameBoard[row][col] == letter && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row+3][col+3] == 0) { val+= threeIn*d; } } }   //Check for open-ended 3-in-a-row. (0xxx0) for (int row=0;row<6;row++) { for (int col = 0;col<3;col++) { //horizontal if (gameBoard[row][col]== 0 && gameBoard[row][col+1] == letter && gameBoard[row][col+2] == letter && gameBoard[row][col+3] == letter && gameBoard[row][col] == gameBoard[row][col+4]) { val+= 2*threeIn*h; } } } for (int row=0;row<2;row++) { for (int col = 0;col<3;col++) { //diag(\) if (gameBoard[row][col] == 0 && gameBoard[row+1][col+1] == letter && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3] && gameBoard[row+4][col+4] == 0) { val+= 2*threeIn*d; } } } //diag(/) for (int row=5;row>3;row--) { for (int col = 0;col<3;col++) { if (gameBoard[row][col] == 0 && gameBoard[row-1][col+1] == letter && gameBoard[row-2][col+2] == letter && gameBoard[row-3][col+3] == letter && gameBoard[row-4][col+4] == 0) { val+= 2*threeIn*d; } } }   if( val == 0){ if(lastMove.getRow() == 5 && lastMove.getCol() == 0)val = 3; if (lastMove.getRow() == 5 && lastMove.getCol() == 1)val = 4; if (lastMove.getRow() == 5 && lastMove.getCol() == 2)val = 5; if (lastMove.getRow() == 5 && lastMove.getCol() == 3)val = 7; if (lastMove.getRow() == 5 && lastMove.getCol() == 4)val = 5; if (lastMove.getRow() == 5 && lastMove.getCol() == 5)val = 4; if (lastMove.getRow() == 5 && lastMove.getCol() == 6)val = 3; else if(lastMove.getRow() == 5 && lastMove.getCol() == -1) val = 5;   }   if (letter==X)return val; else return -val;   }       /* * A state is terminal if there is a tic-tac-toe * or no empty tiles are available */ public boolean isTerminal() { //check for win horizontally for (int row=0; row<6; row++) for (int col=0; col<7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row][col+1] && gameBoard[row][col] == gameBoard[row][col+2] && gameBoard[row][col] == gameBoard[row][col+3]) return true; //check for win vertically for (int row = 0; row < 6-3; row++) for (int col = 0; col < 7; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row+1][col] && gameBoard[row][col] == gameBoard[row+2][col] && gameBoard[row][col] == gameBoard[row+3][col]) return true; //check for win diagonally (upper left to lower right) for (int row = 0; row < 6-3; row++) for (int col = 0; col < 7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row+1][col+1] && gameBoard[row][col] == gameBoard[row+2][col+2] && gameBoard[row][col] == gameBoard[row+3][col+3]) return true; //check for win diagonally (lower left to upper right) for (int row = 3; row < 6; row++) for (int col = 0; col < 7-3; col++) if (gameBoard[row][col] != EMPTY && gameBoard[row][col] == gameBoard[row-1][col+1] && gameBoard[row][col] == gameBoard[row-2][col+2] && gameBoard[row][col] == gameBoard[row-3][col+3]) return true; return false; }   //Prints the board public void print() { System.out.println("*****************"); for(int row=0; row<6; row++) { System.out.print("* "); for(int col=0; col<7; col++) { switch (gameBoard[row][col]) { case X: System.out.print("X "); break; case O: System.out.print("O "); break; case EMPTY: System.out.print("- "); break; default: break; } } System.out.println("*"); } System.out.println("*****************"); } }```

So from tests i noticed that the evaluation works fine but the problem is that the minimax algorithm doesnt choose the move with the biggest/lowest value...and i can't figure out why....
Hint: the Minimax algorithm its for sure right because our professor gave it to us... :/
• November 21st, 2013, 06:52 AM
Norm
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Quote:

the minimax algorithm doesnt choose the move with the biggest/lowest value.
Why? Can you debug the code to see why it doesn't choose the right value?
• November 21st, 2013, 07:11 AM
wickerman
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
Mmm...I can't do that...Could you please explain me this loop "for (Board child : children){}"and if you need more details
(ArrayList<Board> children = new ArrayList<Board>(board.getChildren(Board.X));

I can't understand this loop and the program checks the same moves again and again and i don't know why.....So that makes the debug really painful because of the huge amount of the output :/
• November 21st, 2013, 07:49 AM
Norm
Re: connect 4 with minimax algorithm...Please help me..my algorithm is "stupid" and i dont konw why...
That's an enhanced for loop. See the tutorial: The for Statement (The Java™ Tutorials > Learning the Java Language > Language Basics)

Quote:

makes the debug really painful because of the huge amount of the output :/
If you can have the code recognize when it is near the problem, control the print outs with a boolean variable.
Set the variable true when near the problem and false when not.
Code :

```if(nearProblem) System.out.println("the debug stuff");```