Hi Everyone,
I need help on the MiniMax algorithm for a game of Tic Tac Toe. I must say that although I am quite okay with the Java programming Language, I have always been poor when it comes to recursion. As you all know MiniMax involves tremendous recursion so there goes my problem. I understand how the algorithm is supposed to work and have seen and implemented lots of Pseudo-Codes and for some reason I still get to the same problem. weeks ago, I had the algorithm playing quite alright but the A.I was of course DUMB, in fact plain-DUMB (it plays to the first available spot it finds). The following highlights the issue I had at first.
1st Issue :
BreakDown :
I have a simple GUI displaying the GamePlay, have a class that keeps track of the GameState (positions filled with pieces and also positions set to true or false if a spot is taken vice-versa). The GameState class contains two 2D arrays one for the Pieces the other for positions represented by boolean values to determine if a spot is taken as said previously (The Pieces Class contains information on the Type of piece -"X" or "O" and the owner of the piece, p1 or p2 (human or AI) ). Also I have a class called bestmoves that stores the bestmove in a size 2 array (first slot for x position on my GUI, 2nd slot for the y position).......
Solution :
Now I figured a way around this issue, by making a constructive copy of every board (game state) that needs to be tested all the way down the Game-Tree (am assuming everyone knows what this means). Although I prefer coding in Java, The reason for doing the constructive copy is because of one the Sole Limitation of Java (the referencing). My previous problem was because I had the board destructively changed all the time, forcing the A.I to either do something stupid or my Recursion bit never finds a suitable spot to play to and gets Jammed.
2nd Issue :
Now that I found a way around it, I had to redefine my whole code to cope with this new method, now the algorithm works slightly better, but this time although the A.I is better this time, it is still stupid, as now it only looks for a way for itself to win rather than also trying to make the Human Lose (the sole purpose of the algorithm is defeated)....
Problem: I have been banging on this algorithm for weeks, and would deeply appreciate any sort of help, please if anyone out there has a better understanding of Java & Recursion please help me out as I must say I never thought I would get stuck on a piece of work this long (and am getting kinda of FRUSTRATED).....
Snippets of the new code can be seen Below.....
public BestMoves chooseMove(boolean side , Pieces[][] copiedGameState)
{
Player temp;
if( side == user1.getTurn() )
temp = user1;
else
temp = user2;
BestMoves best = new BestMoves();
BestMoves reply;
if( (board.WinOrLose( copiedGameState ) == true || board.full() == true) )
return ( ( new BestMoves( board.getPieces() , user1 , user2) ) );
else
System.out.println("::::: GRIDS ARE STILL EMPTY & NO WINNER YET FOUND :::::");
if(side == true)
best.setScore(-2);
else
best.setScore(2);
ArrayList<int[]> legal = getLegalMoves( copiedGameState );
for(int i = 0; i < legal.size(); i++)
{
int x = (legal.get(i))[0];
int y = (legal.get(i))[1];
//reply = GS.performMove( x , y , temp , copiedGameState ) ;
Pieces[][] ccg = GS.app( x , y , temp , copiedGameState );
reply = chooseMove( !side , ccg );
if( (side == true && reply.getScore() > best.getScore()) ||
(side == false && reply.getScore() < best.getScore()) )
{
System.out.println("Decision Made");
System.out.println("my best score so far = "+best.getScore());
System.out.println("my reply score so far = "+reply.getScore());
int [] m = {x,y};
best.setMove( m );
best.setScore( reply.getScore() );
}
}// END OF FOR-LOOP
return best;
}
/************************************************/
Explanation : The print statements I included are just to help me debug the issue
but like I said it seems the debugging ain't helping much
, the app() method in the GS(Gamestate class)
is to perform the move on the current board I pass to it and then return a constructive copy of the
new board with the piece newly played to it. (note: I call the board containing all the pieces played so far
--- Pieces[][] -- it is just for convenience sake as it represents all the pieces and their positions in the 2D
Array....................
I hope I have given sufficient info in helping anyone debug this problem..... I do not mind providing more
detail if asked to.
/************************************************/
Peace.