|
-
May 25th, 2016, 08:39 PM
#1
Minimax algorithm
Hi, can anyone see what the problem is in my code, I am getting funny results from the output as in the minimax is not always winning or drawing.
Code:
import java.io.IOException;
import java.util.ArrayList;
public class Board implements Cloneable{
public int[][] board = new int[3][3];
//@Override
protected Object clone() throws CloneNotSupportedException {
Board copy = new Board();
int[][] temp = new int[3][3];
for(int i =0; i < 3;i++){
for(int j =0; j < 3; j++){
copy.board[i][j] = board[i][j];
}
}
return copy;
}
public Board() {
}
public int[][] getBoard(){
return board;
}
public void setBoard(int [][] array){
board = array;
}
public boolean changeBoard(Integer row, Integer col, Player player) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if ((i == row) && (j == col) && player.getOorX().equals("O") && (board[i][j] == 0)) {
board[row][col] = -1;
} else if ((i == row) && (j == col) && player.getOorX().equals("X") && (board[i][j] == 0)) {
board[row][col] = 1;
}
}
}
return true;
}
public boolean renderBoard() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == -1) {
System.out.print("|O| ");
} else if (board[i][j] == 1) {
System.out.print("|X| ");
} else {
System.out.print("| | ");
}
}
System.out.println("");
}
System.out.println("------------");
return true;
}
public Integer gameOverCheck(){
int sum = 0;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3;j++){
sum += getBoard()[i][j];
}
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3;j++){
sum += getBoard()[j][i];
}
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3;j++){
if(i == j) {
sum += getBoard()[i][j];
}
}
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
}
int x = 2;
for(int i = 0; i < 3; i++){
sum += getBoard()[i][x];
x--;
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
}
return 0;
}
public int [] compMove(Board board){
int row = 0;
int col = 0;
Board copyBoard = null;
int bestScore = -2;
copyBoard = board;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if(copyBoard.getBoard()[i][j] == 0) {
copyBoard.getBoard()[i][j] = 1;
int thisScore = -minimax(copyBoard,1)[0];
if (thisScore > bestScore) {
bestScore = thisScore;
row = i;
col = j;
}
copyBoard.getBoard()[i][j] = 0;
}
}
}
return new int[] {bestScore,row,col};
}
public int [] minimax(Board board, int player){
int row = 0;
int col = 0;
Board copyBoard = null;
int bestScore = -2;
copyBoard = board;
int winner = copyBoard.gameOverCheck();
if(winner != 0) return new int[] {winner*player,row,col};
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++) {
if (copyBoard.getBoard()[i][j] == 0) {
copyBoard.getBoard()[i][j] = player*-1;
int thisScore = -minimax(copyBoard, player * -1)[0];
if (thisScore > bestScore) {
bestScore = thisScore;
row = i;
col = j;
}
copyBoard.getBoard()[i][j] = 0;
}
}
}
return new int [] {bestScore,row,col};
}
}
Last edited by gaar321; May 25th, 2016 at 08:42 PM.
-
May 26th, 2016, 08:44 AM
#2
Re: Minimax algorithm
I am getting funny results
Can you post the results and add some comments saying what is wrong with it?
How do you execute the code for testing? I don't see a main method.
Norm
-
May 26th, 2016, 10:30 AM
#3
Re: Minimax algorithm
Sorry ignore my other code I have changed it but I still get the same results...
Code:
import java.io.IOException;
import java.util.ArrayList;
public class Board implements Cloneable{
public int[][] board = new int[3][3];
//@Override
protected Object clone() throws CloneNotSupportedException {
Board copy = new Board();
int[][] temp = new int[3][3];
for(int i =0; i < 3;i++){
for(int j =0; j < 3; j++){
copy.board[i][j] = board[i][j];
}
}
return copy;
}
public Board() {
}
public int[][] getBoard(){
return board;
}
public void setBoard(int [][] array){
board = array;
}
public boolean changeBoard(Integer row, Integer col, int player) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if ((i == row) && (j == col) && player == 1 && (board[i][j] == 0)) {
board[row][col] = 1;
} else if ((i == row) && (j == col) && player == -1 && (board[i][j] == 0)) {
board[row][col] = -1;
}
}
}
return true;
}
public boolean renderBoard() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == -1) {
System.out.print("|O| ");
} else if (board[i][j] == 1) {
System.out.print("|X| ");
} else {
System.out.print("| | ");
}
}
System.out.println("");
}
System.out.println("------------");
return true;
}
public Integer gameOverCheck(){
int sum = 0;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3;j++){
sum += getBoard()[i][j];
}
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3;j++){
sum += getBoard()[j][i];
}
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
}
for(int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (i == j) {
sum += getBoard()[i][j];
}
}
}
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
int x = 2;
for(int i = 0; i < 3; i++){
sum += getBoard()[i][x];
x--;
if(sum == 3){
return 1;
}
else if(sum == -3){
return -1;
}
else{
sum = 0;
}
}
return 0;
}
public ArrayList<int[]> getAvailablePositions(Board board) {
ArrayList<int[]>temp = new ArrayList<int[]>();
int count = 0;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if(board.getBoard()[i][j] == 0) {
int[] store = new int [2];
store[0] = i;
store[1] = j;
temp.add(store);
}
}
}
return temp;
}
int index = 0;
int [] minimax(int player,Board board) {
int winner = board.gameOverCheck();
if (winner == 1) {
return new int[] {+1,index};
} else if (winner == -1) {
return new int [] {-1,index};
}
int bestScore = 0;
if(player == 1){
bestScore = Integer.MIN_VALUE;
}
else{
bestScore = Integer.MAX_VALUE;
}
ArrayList<int[]> gameMovesAvailable = getAvailablePositions(board);
if(gameMovesAvailable.size() == 0){ //get all legal moves for current board
return new int[] {0,index};
}
if(player == 1){
for (int i = 0; i < gameMovesAvailable.size() - 1; i++) {
board.changeBoard(gameMovesAvailable.get(i)[0],gameMovesAvailable.get(i)[1],1);
int currentScore = minimax(-1,board)[0]; //call with player O
board.getBoard()[gameMovesAvailable.get(i)[0]][gameMovesAvailable.get(i)[1]] = 0;
bestScore = Math.max(currentScore,bestScore);
index = i;
System.out.println("Row: "+gameMovesAvailable.get(index)[0] +" Col: "+gameMovesAvailable.get(index)[1]);
System.out.println(index);
}
return new int[] {bestScore,index};
}
else if(player == -1){
for (int i = 0; i < gameMovesAvailable.size() - 1; i++) {
board.changeBoard(gameMovesAvailable.get(i)[0],gameMovesAvailable.get(i)[1],-1);
int currentScore = minimax(1,board)[0]; //call for player X.
board.getBoard()[gameMovesAvailable.get(i)[0]][gameMovesAvailable.get(i)[1]] = 0;
bestScore = Math.min(currentScore,bestScore);
index = i;
System.out.println("Row: "+gameMovesAvailable.get(index)[0] +" Col: "+gameMovesAvailable.get(index)[1]);
System.out.println(index);
}
return new int[] {bestScore,index};
}
return new int[] {bestScore,index};
}
}
Output from the code
Code:
Row: 0 Col: 1
0
Row: 0 Col: 1
0
Row: 0 Col: 2
1
Row: 1 Col: 0
2
Row: 1 Col: 2
3
Row: 1 Col: 1
3
Row: 1 Col: 0
0
Row: 1 Col: 0
0
Row: 1 Col: 1
1
Row: 0 Col: 2
0
Row: 0 Col: 2
0
Row: 0 Col: 2
0
Row: 1 Col: 1
1
Row: 1 Col: 0
1
Row: 0 Col: 2
0
Row: 1 Col: 0
1
Row: 1 Col: 1
2
Row: 0 Col: 1
0
Row: 1 Col: 0
0
Row: 1 Col: 0
0
Row: 1 Col: 1
1
Row: 0 Col: 1
0
Row: 0 Col: 1
0
Row: 0 Col: 1
0
Row: 1 Col: 1
1
Row: 1 Col: 0
1
Row: 0 Col: 1
0
Row: 1 Col: 0
1
Row: 1 Col: 1
2
Row: 0 Col: 2
1
Row: 1 Col: 0
2
Row: 1 Col: 0
0
Row: 0 Col: 2
0
Row: 1 Col: 0
1
Row: 0 Col: 1
0
Row: 1 Col: 0
0
Row: 0 Col: 1
0
Row: 1 Col: 0
1
Row: 0 Col: 2
1
Row: 0 Col: 2
0
Row: 0 Col: 1
0
Row: 0 Col: 1
0
Row: 0 Col: 2
1
Row: 1 Col: 0
2
Row: 1 Col: 1
3
Row: 1 Col: 2
4
Row: 2 Col: 0
5
Row: 2 Col: 1
6
Index for best move: 6
|X| | | | |
| | | | | |
| | | | | |
------------
Please enter the row:
I haven't rendered the computer output but if you see where it says Row 2 col 1 I would expect the final move to be 0,1 or 1,0 given by the algorithm from the current board state? but it isn't can you see any errors in my minimax part?
-
May 26th, 2016, 10:34 AM
#4
Re: Minimax algorithm
How do you execute the code for testing? I don't see a main method.
Row 2 col 1 I would expect the final move to be 0,1 or 1,0
How is the move shown in the print out?
can you see any errors in my minimax part?
I don't see any comments about how the code is solving the problem that I can compare the code against to see if the code is following the logic for solving the problem.
Last edited by Norm; May 26th, 2016 at 10:38 AM.
Norm
-
May 26th, 2016, 10:44 AM
#5
Re: Minimax algorithm
main method
Code:
public class Game {
Player P1 = null;
Player P2 = null;
static ArrayList<ArrayList<Integer>>board;
public Game() {
}
public void gameLoop(Board board,Player P1,Player P2){
boolean gameRun = true;
while(gameRun) {
if (P1.getTurn()) {
ArrayList<Integer> moves = new ArrayList<Integer>();
moves = P1.makeMove();
P1.setTurn(false);
P2.setTurn(true);
board.changeBoard(moves.get(0), moves.get(1), 1);
board.renderBoard();
if(board.gameOverCheck() == 1){
System.out.println("P1 Wins");
gameRun = false;
}
} else if (P2.getTurn()) {
ArrayList<Integer> moves = new ArrayList<Integer>();
//moves = P2.makeMove();
P2.setTurn(false);
P1.setTurn(true);
P2.getTurn();
//moves = P2.makeMove();
board.getBoard();
Board copy = new Board();
try {
copy = (Board)board.clone();
}
catch(CloneNotSupportedException ex){
}
int [] temp = copy.minimax(-1,copy);
System.out.println("Index for best move: "+temp[1]);
//board.changeBoard(moves.get(0), moves.get(1), -1);
board.renderBoard();
if(board.gameOverCheck() == -1){
System.out.println("P2 Wins");
gameRun = false;
}
}
}
};
public void initGame(){
Player P1 = new Player(true,false,"O");
Player P2 = new Player(false,true,"X");
Board board = new Board();
P1.setTurn(true);
gameLoop(board,P1,P2);
}
public static void main(String[] args){
Game game = new Game();
game.initGame();
}
}
Well if I was to render the final output at position 2,1 then it would draw a O in that position but I have decided not to bother printing it out yet. I am just seeing the final output of the algorithm and it seems incorrect to me.
Last edited by gaar321; May 26th, 2016 at 10:52 AM.
-
May 26th, 2016, 10:52 AM
#6
Re: Minimax algorithm
Now the program needs the Player class.
can you see any errors in my minimax part?
I don't see any comments about how the code is solving the problem that I can compare the code against to see if the code is following the logic for solving the problem.
Norm
-
May 26th, 2016, 10:55 AM
#7
Re: Minimax algorithm
Code:
public class Player {
Boolean P1 = false;
Boolean P2 = false;
Boolean Turn = false;
String OX= null;
public Player (Boolean P1,Boolean P2,String OX){
this.OX = OX;
if(P1 == true){
this.P1 = true;
}
else{
this.P2 = true;
}
}
public void setTurn(Boolean Turn){
this.Turn = Turn;
}
public boolean getTurn(){
return Turn;
}
public String getPlayer(){
if(P1){
return "P1";
}else{
return "P2";
}
}
//get player OorX
public String getOorX(){
return OX;
}
//get Player input to make a move
public ArrayList<Integer> makeMove() {
ArrayList<Integer>rowCol = new ArrayList<Integer>();
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
try {
System.out.println("Please enter the row: ");
String input = reader.readLine();
Integer output = Integer.parseInt(input);
rowCol.add(output);
System.out.println("Please enter the column");
input = reader.readLine();
output = Integer.parseInt(input);
rowCol.add(output);
}
catch(IOException ex){
}
return rowCol;
}
}
-
May 26th, 2016, 10:58 AM
#8
Re: Minimax algorithm
can you see any errors in my minimax part?
I don't see any comments about how the code is solving the problem that I can compare the code against to see if the code is following the logic for solving the problem.
I won't be able to look for logic problems because the code has no comments describing the logic.
Norm
-
May 26th, 2016, 11:02 AM
#9
Re: Minimax algorithm
Code:
int [] minimax(int player,Board board) {
int index = 0;
int winner = board.gameOverCheck();
if (winner == 1) { //if 1 e.g. X
return new int[] {+1,index}; //return +1 for a win
} else if (winner == -1) {
return new int [] {-1,index}; //return a -1 for a loss;
}
int bestScore = 0;
if(player == 1){
bestScore = Integer.MIN_VALUE;
}
else{
bestScore = Integer.MAX_VALUE;
}
ArrayList<int[]> gameMovesAvailable = getAvailablePositions(board);
if(gameMovesAvailable.size() == 0){
return new int[] {0,index}; //if no more moves are avaliable return 0 which is a draw.
}
if(player == 1){
for (int i = 0; i < gameMovesAvailable.size() - 1; i++) {
board.changeBoard(gameMovesAvailable.get(i)[0],gameMovesAvailable.get(i)[1],1); //execute possible position.
int currentScore = minimax(-1,board)[0]; //recurse down the tree
if(currentScore > bestScore) { //maximise player for move played
index = i;
System.out.println("Row: " + gameMovesAvailable.get(index)[0] + " Col: " + gameMovesAvailable.get(index)[1]);
System.out.println(index);
}
}
return new int[] {bestScore,index};
}
else if(player == -1){
for (int i = 0; i < gameMovesAvailable.size() - 1; i++) {
board.changeBoard(gameMovesAvailable.get(i)[0],gameMovesAvailable.get(i)[1],-1);
int currentScore = minimax(1,board)[0]; //recurse down the tree
if(currentScore < bestScore) { //minimise player for
index = i;
System.out.println("Row: " + gameMovesAvailable.get(index)[0] + " Col: " + gameMovesAvailable.get(index)[1]);
System.out.println(index);
}
}
return new int[] {bestScore,index};
}
return new int[] {bestScore,index};
}
-
May 26th, 2016, 11:10 AM
#10
Re: Minimax algorithm
How are you debugging the code to see if it is doing what you want? I use print statements that print out the values of variables as they are changed and as they are used?
The program requires input. For faster debugging recommend using values stored in the code. For example:
Code:
StringReader sr = new StringReader("1\n2\n"); //???? what input
BufferedReader reader = new BufferedReader(sr); //<<<moved here
//get Player input to make a move
public ArrayList<Integer> makeMove() {
ArrayList<Integer>rowCol = new ArrayList<Integer>();
// BufferedReader reader = new BufferedReader(new InputStreamReader(System.in)); //<<<<<<<<<<<< ???? Needs input
This will save a tester having to enter anything when the code executes. The input comes from the String in the StringReader's constructor.
Norm
Posting Permissions
- You may not post new threads
- You may not post replies
- You may not post attachments
- You may not edit your posts
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|
Reply With Quote