Min-Max help. StackOverFlowError
Having trouble with my minmax algorithm for my game. Keep getting StackOverFlowError - possible due to too much recursion?
If it is too much recusion - ie the game tree is too vast what should I do?
This is just for a Dominoes game - so I didnt think it would be that complicated :S
Any help / suggestions / insight will be greatly appreciated!!!
NB. It is the tacticExtreme method that is the recursive one
// Strategy MinMax
publicvoid tacticMinMaxAlpha(Domino player[]){
Domino probDomino =new Domino(7,7);
int score = 0;
int highestScore = 0;
// Create array of possible opponent dominoes
possiblePlays();
// Create ArrayList of possible moves from current situation
ArrayList possMoves =new ArrayList(possibleMoves(player, moveLeft, moveRight));
if(possMoves.size() == 0){
// If there are no plays do nothing!
}else{
// For each of my dominoes that are playable...
for(int i = 0; i < possMoves.size(); i++){
Domino tempDomino[] =new Domino[7];
int newLeft = moveLeft;
int newRight = moveRight;
Domino domino = (Domino)possMoves.get(i);
if (domino.x == moveLeft && domino.x != moveRight){
newLeft = domino.y;
}elseif (domino.x == moveRight){
newRight = domino.y;
}elseif (domino.y == moveLeft && domino.y != moveRight){
newLeft = domino.x;
}elseif (domino.y == moveRight){
newRight = domino.x;
}
// Mark the domino used
for(int j = 0; j < 7; j++){
tempDomino[j] =new Domino(player[j].x, player[j].y);
//if(!player[j].available) tempDomino[j].available = false;
if(domino.x == tempDomino[j].x){
if(domino.y == player[j].y){
tempDomino[j].available =false;
}
}
}
// Calculate the number of possible moves at most the opponent may have
ArrayList other =new ArrayList(possibleMoves(possible, newLeft, newRight));
if(other.size() > 0){
score = tacticExtreme(tempDomino, possible, newLeft, newRight,false);
}
if (score > highestScore){
highestScore = score;
probDomino =new Domino(domino.x, domino.y);
}elseif(score == highestScore){
if((domino.x + domino.y) > (probDomino.x + probDomino.y)){
probDomino =new Domino(domino.x, domino.y);
}
}
}
}
if((probDomino.x != 7)){
for(int i = 0; i < 7; i++){
if(probDomino.x == player[i].x){
if(probDomino.y == player[i].y){
play = i + 1;
}
}
}
}else{
play = 0;
}
}// end tacticProbability()
// Tactic tacticProbability
publicint tacticExtreme(Domino player1[], Domino player2[],int left,int right,boolean flag){
int score = 0;
boolean player1First = flag;
// Check not greater than 3 recursion calls by this method
if( DepthLimitReached() ){
depth = 0;
}else{
if(player1First){
Domino tempDomino[] =new Domino[player1.length];
ArrayList possMoves =new ArrayList(possibleMoves(player1, moveLeft, moveRight));
// For each playable domino
for(int i = 0; i < possMoves.size(); i++){
int newLeft = left;
int newRight = right;
Domino domino = (Domino)possMoves.get(i);
if (domino.x == moveLeft && domino.x != moveRight){
newLeft = domino.y;
}elseif (domino.x == moveRight){
newRight = domino.y;
}elseif (domino.y == moveLeft && domino.y != moveRight){
newLeft = domino.x;
}elseif (domino.y == moveRight){
newRight = domino.x;
}
// Mark the current domino as used to pass to the next recursion call
for(int j = 0; j < player1.length; j++){
tempDomino[j] =new Domino(player1[j].x, player1[j].y);
if(domino.x == tempDomino[j].x){
if(domino.y == player1[j].y){
tempDomino[j].available =false;
}
}
}
// Check if that was the last Domino in hand. If it wasn't then continue on search tree.
if(outOfDominoes(tempDomino)){
score = 100;// Played all the Dominoes - WIN!!!
}else{
ArrayList x =new ArrayList(player2.length);
x = possibleMoves(player2, newLeft, newRight);
ArrayList y =new ArrayList(tempDomino.length);
y = possibleMoves(tempDomino, newLeft, newRight);
if(x.size() > 0){// If player2 has a move it is their turn
score = tacticExtreme(tempDomino, player2, newLeft, newRight, !player1First);
}elseif (y.size() > 0){// If player2 has no move. Have I got a move?
score = tacticExtreme(tempDomino, player2, newLeft, newRight, player1First);
}else{// If no one can make a move then it is a draw.
score = 50;
}
}
}
}else{
Domino tempDomino[] =new Domino[player2.length];
ArrayList possMoves =new ArrayList(possibleMoves(player2, moveLeft, moveRight));
// For each playable domino
for(int i = 0; i < possMoves.size(); i++){
int newLeft = left;
int newRight = right;
Domino domino = (Domino)possMoves.get(i);
if (domino.x == moveLeft && domino.x != moveRight){
newLeft = domino.y;
}elseif (domino.x == moveRight){
newRight = domino.y;
}elseif (domino.y == moveLeft && domino.y != moveRight){
newLeft = domino.x;
}elseif (domino.y == moveRight){
newRight = domino.x;
}
// Mark the domino used
for(int j = 0; j < player2.length; j++){
tempDomino[j] =new Domino(player2[j].x, player2[j].y);
if(domino.x == tempDomino[j].x){
if(domino.y == player2[j].y){
tempDomino[j].available =false;
}
}
}
if(outOfDominoes(tempDomino)){
score = -100;
}else{
ArrayList other =new ArrayList(player1.length);
other = possibleMoves(player1, newLeft, newRight);
ArrayList myPlayable =new ArrayList(tempDomino.length);
myPlayable = possibleMoves(tempDomino, newLeft, newRight);
if(other.size() > 0){
score = tacticExtreme(player1, tempDomino, newLeft, newRight, player1First);
}elseif (myPlayable.size() > 0){
score = tacticExtreme(player1, tempDomino, newLeft, newRight, !player1First);
}else{
score = 50;
}
}
}
}
}
return score;
}// end tacticExtreme()
