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;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 currentScore

		
		ply++;
		
		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=new
Dimension[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 currentNodePosition

	
	availableMoves=getAvailableMoves(currentNodePosition);
		
	// loop thru all available to continue nodes (child nodes) and get

best node of them all
	
	for(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 currentScore


		ply++;
		
		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.