   is there anything wrong with my minimax AB implementation?
  hello everyone  i'm quite new to java programming and AI but somehowmanaged to implement A* so far, but got problems with minimax withalpha-beta prunning. in fact i was trying to implement connect4 gamebut sometimes my AI player makes very stupid moves and i couldntfigure out if the problem is with my minimax algorithm or simply withevaluation function. i've created an abstract class that i hoped couldbe reused in other games and i would really appreciate any comments onmy code. i wonder if that minimax with AB prunning is implementedproperly or not and if i need to change anything or problem must besimply in evaluation function. i've also tried to insert conditionalstatement (now its commented) checking if game is finished or not butthought that maybe evaluation function could do the same and left itout so far. anyway thank you very much for any comments as such wouldbe 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 tocontinue 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 passedas parameter game would be finished and returns boolean    // getAvailableMoves(...) get an array of available moves that areavailable to continue and need to be checked    // evaluateGameState(...) evaluates how good is the current stateof game for a player passed as parameter   abstract boolean isGameFinished(int checker, DimensionpositionToBeChecked);    abstract Dimension[] getAvailableMoves(DimensionpositionToBeChecked);    abstract int evaluateGameState(int playerToBeCheckedFor);   // method takes an array of int's and ANY AVAILABLE position asparameter and returns the best move to continue    Dimension getBestMove(int[][] gameArray, DimensionanyGamePosition)    {this.gameArray=gameArray;System.out.println(maximize(anyGamePosition,-100000,100000));return bestMove;    }   // method checks all available from current position moves andchoses 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 continuefrom that pointDimension[] availableMoves=newDimension[gameArray.length*gameArray[0].length];// check if with currentNodePosition game is finished or not, eitherway// dosent seem to work//if(isGameFinished(BLACK,currentNodePosition))//  return 100000;if(ply==LIMIT)   return evaluateGameState(BLACK);// get moves available to continue from currentNodePositionavailableMoves=getAvailableMoves(currentNodePosition);// loop thru all available to continue nodes (child nodes) and getbest node of them allfor(int a=0;a<availableMoves.length;a++){    if(availableMoves<A href='http://!=null)    {gameArray[(int)availableMoves[a].getWidth()][(int)availableMoves[a].getHeight()]=WHITE;// get scores for node currently being checked (availableMoves[a])and store// the one with highest value in currentScoreply++;nodeScore=minimize(availableMoves[a],alpha,beta);    if(alpha<nodeScore){    alpha=nodeScore;    bestMove.width=(int)availableMoves[a].getWidth();    bestMove.height=(int)availableMoves[a].getHeight();}ply--;gameArray[(int)availableMoves[a].getWidth()][(int)availableMoves[a].getHeight()]=EMPTY;    }   if(beta<alpha)return beta;}return alpha;    }  int minimize(Dimension currentNodePosition,int alpha,int beta)    {int nodeScore=0;Dimension[] availableMoves=newDimension[gameArray.length*gameArray[0].length];// check if with currentNodePosition game is finished or not//if(isGameFinished(WHITE,currentNodePosition))//return -100000;if(ply==LIMIT)    return evaluateGameState(WHITE);// get moves available to continue from currentNodePositionavailableMoves=getAvailableMoves(currentNodePosition);// loop thru all available to continue nodes (child nodes) and getbest node of them allfor(int a=0;a<availableMoves.length;a++){    if(availableMoves[a]!=null)    {gameArray[(int)availableMoves[a].getWidth()][(int)availableMoves[a].getHeight()]=BLACK;// get scores for node currently being checked (availableMoves[a])and store// the one with lowest value in currentScoreply++;drawToConsole();nodeScore=maximize(availableMoves[a],alpha,beta);if(beta>nodeScore){    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)availableMoves[a].getHeight()]=EMPTY;    }   if(alpha>beta)return alpha;}return beta;    }}  [edited by - Spirytus on February 15, 2004 9:23:32 PM]
  PUT IT IN A SOURCE BOX! the last bit tured into html formatting.[source ] CODE GOES HERE [/source ] without spaces    ;  A few words of advice.Keep things simple. This stuff gets confusing quickly. There''s no need to complicate more than it already is.Having established that we need to keep things simple, get rid of the abstract stuff for now (and probably for good). It''s a nice idea to reuse this for other games, but unless you want your program to play very weak, you are not going to be able to reuse it. Some search techniques work wonders in some games, but really suck in others, so you aren''t going to have much success using the exact same algorithm in different games (unless you don''t mind a very weak program).Try using the negamax version instead of two seperate min and max functions to reduce potential for errors (one function instead of two). It''s also easier to understand and spot bugs once you get used to it, and just about every programmer who uses these algorithms does it that way, so they''ll be able to offer more help. On that same note, if you were to do this in C or C++ instead of java, you could take a look at dozens of open source chess programs and see how they do it.Your code seems hard to read (maybe it''s because of the source box screwing up your comments though). Try abstracting some things away so your code is more readable and self documenting. For instance, I have no idea what you''re doing with the game array thing, so I can''t tell you if it''s wrong. See how easy this code is to read? int NegaMax(int depth){    int best = -INFINITY;    if (depth <= 0)   return Evaluate();    GenerateLegalMoves();    while (MovesLeft()) {   MakeNextMove();   val = -NegaMax(depth - 1);   UnmakeMove();   if (val > best)  best = val;    }    return best;}It doesn''t have to be completely abstracted away, but you get the idea. This code isn''t directly messing with game_array[][] or whatever. It just says what it does.If you haven''t already, read a few of these articles at this site.