From: spirytus@get-freelancer.net   
      
   hello everyone :) i'm quite new to java programming and AI but somehow   
   managed to implement A* so far, but got problems with minimax with   
   alpha-beta prunning. in fact i was trying to implement connect4 game   
   but sometimes my AI player makes very stupid moves and i couldnt   
   figure out if the problem is with my minimax algorithm or simply with   
   evaluation function. i've created an abstract class that i hoped could   
   be reused in other games and i would really appreciate any comments on   
   my code. i wonder if that minimax with AB prunning is implemented   
   properly or not and if i need to change anything or problem must be   
   simply in evaluation function. i've also tried to insert conditional   
   statement (now its commented) checking if game is finished or not but   
   thought that maybe evaluation function could do the same and left it   
   out so far. anyway thank you very much for any comments as such would   
   be very much appreciated   
      
   abstract class AIMiniMax   
   {   
       int ply;   
      
       final int WHITE=1;	// white tokens value   
       final int BLACK=2;	// black tokens value   
       final int EMPTY=0;	   
       final int LIMIT=3;	// number of ply's (levels) to be checked   
      
       int[][] gameArray;	// actual array where the game goes on   
       Dimension bestMove=new Dimension();	// bestMove position to   
   continue we are looking for   
      
      
       // abstract classes to be defined in a class that extends that one   
   (must be different for every game)   
      
       // isGameFinished(...) checks if with position and checker passed   
   as parameter game would be finished and returns boolean   
       // getAvailableMoves(...) get an array of available moves that are   
   available to continue and need to be checked   
       // evaluateGameState(...) evaluates how good is the current state   
   of game for a player passed as parameter   
      
       abstract boolean isGameFinished(int checker, Dimension   
   positionToBeChecked);   
       abstract Dimension[] getAvailableMoves(Dimension   
   positionToBeChecked);   
       abstract int evaluateGameState(int playerToBeCheckedFor);   
      
       // method takes an array of int's and ANY AVAILABLE position as   
   parameter and returns the best move to continue   
      
       Dimension getBestMove(int[][] gameArray, Dimension   
   anyGamePosition)   
       {   
   	this.gameArray=gameArray;   
   	   
   	System.out.println(maximize(anyGamePosition,-100000,100000));   
   	   
   	return bestMove;   
       }   
      
       // method checks all available from current position moves and   
   choses one with the highest score   
       // alpha is the highest valued position already found by max   
   (player who tries to maximize) and initially   
       // is set to -inf (-some huge number). alpha is used b   
      
       int maximize(Dimension currentNodePosition,int alpha,int beta)   
       {   
   	int nodeScore=0;    // initial value of child node being checked is 0   
   	   
   	// setting size of an array to hold positions available to continue   
   from that point   
   	   
   	Dimension[] availableMoves=new   
   Dimension[gameArray.length*gameArray[0].length];   
   	   
   	// check if with currentNodePosition game is finished or not, either   
   way   
   	// dosent seem to work   
   	   
   	//if(isGameFinished(BLACK,currentNodePosition))   
   	//  return 100000;   
   		   
   	if(ply==LIMIT)		   
   	    return evaluateGameState(BLACK);	   
   	   
   	// get moves available to continue from currentNodePosition   
   	   
   	availableMoves=getAvailableMoves(currentNodePosition);   
   	   
   	// loop thru all available to continue nodes (child nodes) and get   
   best node of them all   
   	   
   	for(int a=0;anodeScore)   
   		{   
   		    beta=nodeScore;   
      
   		    // not sure if it is necessary, but leave it for now   
      
   		    bestMove.width=(int)availableMoves[a].getWidth();   
   		    bestMove.height=(int)availableMoves[a].getHeight();   
   		}   
   		   
   		ply--;   
   		   
   		gameArray[(int)availableMoves[a].getWidth()][(int)availableMov   
   s[a].getHeight()]=EMPTY;   
   	    }   
   	   
   	    if(alpha>beta)   
   		return alpha;   
   	}   
   	   
   	return beta;   
       }   
   }   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)