i'm stuck with alpha-beta pruning algorithm implementation

Question

I'm trying to implement Game AI for 9Men's Morris game.

So far, i have the board represented like this:

    public class board 
    {
          public      node []gNode      = null;
          ... // so the table has 24 nodes, for 9 men morris game:
          gNode = new node[24];
          ...
          int evaluateBoard(); // evaluates the current board (tokens)
    } 

ok, now every node is represented like so:

    public class node 
    {
     node() // constructor
     {     ...       }

     // setting current node's neighbours (maximum 4 neighbours)
     void setNeighbours(int left, int right, int top, int bottom)
     {      ...      }

     short      gOccupiedByTeam = renderer.TEAM_NOTEAM; // info if this node is occupied by a token (and a wich team this token belongs to) 
     short    []gNeighbourId    = null; // info about this node neighbours (can be max. 4 in a 9Men's morris game)
     short      gInternalID     = -1;   // board's IDs (from 0..23)
     short      gTokenID        = -1;   // this node can be occupied by a token.  (from 0 .. 8) -see below the token class.
     short      gNodeScore      = -1;   // a dummy node score.
     vector3    gLocation       = null; // 3d coordinates for this node.


    }

and a token looks like this:

public class token 
{
   token(vector3 startpos, short nodeId) // Constructor.
   {     ...     }


   public   physx       gPhysX      = null;  // 3d coordinates , velocity , accel. for this Token.
   public boolean       bIsAlive    = false; // is this token alive ? (or eliminated?)
   public boolean       bFormsMill  = false; // does it form a Mill?

   public short         gNodeID     = -1; // "link" this token with a gNodeID (when placing a token on current board). See above the node class. This represents a link ID to that node.
   public short         gTokenMill1 = -1; // used when this token forms a mill (with gTokenMill1  token!)
   public short         gTokenMill2 = -1; // same.

}

and Here is my Alpha-Beta pruning algorithm implementation where I'm stuck :

public int getBestMove(board board, int depth, int alpha, int beta, boolean bIsPlayer)
{
    // if depth reached, return current's board's Evaluation (a score).
    if (depth == 0) return board.evaluateBoard(bIsPlayer);

    // is it Player's turn ? (max?)
    if (bIsPlayer)
    {
        // QUESTIONS: 
        // retrevie all possible "boards" below ! (all new possible token moves)
        // 1. here i should generate a new board with 1st possible move (for player token1) ?? ... then a second new board with 2nd possible move still for token1 ? .. and so on until no possible moves for token1?  
        //   (remembering that a token can move in 4 available spots - wich are a neighbour?) 
        // 
        // 2. the problem is that if i generate 4 new boards as per token 1 above let's say, then it will "eat" lot of memory for all 18 tokens and a function recursion depth of 5 for example, right ? 
        // 3. how do i fix point 2? 


        ArrayList<board> possible_boards = board.getAllPossibleBoards();

        // 4. ok, some possible boards were generated, loop thru them starting with the first one and calling recursively this function, is it right ?
        for(board iterator: possible_boards)
        {
            alpha = Math.max(alpha, getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer));

            if (beta < alpha)
            {

                break;
            }
        }

        // 5. how do i return best move to main calling function ? (wich token is it best move from all of these board's moves ?
        return alpha;
    }
    else
    {
        ArrayList<board> possible_boards = board.getAllPossibleBoards();

        for(board iterator: possible_boards)
        {

            beta = Math.min(beta, getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer));


            if (beta < alpha)
            {
                break;
            }


        }

        return beta;
    }


}

OK, this is my function so far. I Don't know even if I'm on the right track ??!

What's wrong in my function?
Please answer my above questions (1 to 5 in the getBestMove() function).

Thank you in advance and please escuse my language mistakes (my english it's not so good)

---

Thank you so much saeedn for your reply !!

I thought nobody will ever answer me :). I really helps me understand what's happening i think.

So, CheckWinner( bool ) will check if current player has a very good advantage (like winning or a very good move like blocking opponent,etc) at this depth so far, and if so then return a BIG score for current player. All of this because nor the player or the oponent will try to Win(a big score) every turn, right?

Otherwise if depth=0 then return a evaluation (score) of the current selected Board (int evaluateBoard()), allright.

After this, then I must generate a single board (with a single token posible move):

   while( board.generateNextPossibleBoard(nextBoard) ) // board generated and stored in "nextBoard". Also check if it is a valid board or no more boards to generate further.

Ok, having now a new generated board, recurse and if a better board (board with a better SCORE) is found then save current board to chosenBoard. If not then cutoff and return (don't check further down the tree).

Thanks again so much saeedn !!!

Answer 1

Generally your code is ok, but there are some points you should have in mind.

First of all you should check if the node (here a board) is final or not (someone won the game), then check for depth equal to zero. And if someone won in that state, you may want to return a big value (for winning max player) and a small value (for winning min player), for exmaple MAXINT and MININT respectively.

To avoid high memory consumption, do not generate all possible board. Generate one board and do a recursive call for that and then generate another one and search for that and so on. This way you just use memory for one state in each stack frame. This is crucial in searches with high branch factor!

Finally you should record the board updating score of max player (where you update alpha).

see my pseudo code for more clarification:

if ( board.checkWinner(bIsPlayer) ) return board.evaluateBoard(bIsPlayer);

// if depth reached, return current's board's Evaluation (a score).
if (depth == 0) return board.evaluateBoard(bIsPlayer);

board chosenBoard;    
if (bIsPlayer)
{
    // You should implement this method, or write your board generation code here
    // returns false if no more boards could be generated
    board nextBoard;
    while( board.generateNextPossibleBoard(nextBoard) )
    {
        int v = getBestMove(iterator, depth - 1, alpha, beta, !bIsPlayer));

        if ( v > alpha )
        {
            alpha = v;
            chosenBoard = nextBoard;  // return this chosenBoard by reference ;)
        }

        if (beta < alpha)
        {
            break;
        }
    }

    return alpha;
}
else
{
    // The same for beta except you don't need to update chosenBoard :)
}