Connect four AI using alpha beta pruning algorithm

[P Padda]

Hi

I'm trying to implement this algorithm in a game of connect four. I'm using this bit of psuedo code to do so :

MinMax (GamePosition game) {
  return MaxMove (game);
}
 
MaxMove (GamePosition game, Integer alpha, Integer beta) {
  if (GameEnded(game) || DepthLimitReached()) {
    return EvalGameState(game, MAX);
  }
  else {
    best_move < - {};
    moves <- GenerateMoves(game);
    ForEach moves {
       move <- MinMove(ApplyMove(game), alpha, beta);
       if (Value(move) > Value(best_move)) {
          best_move < - move;
          alpha <-  Value(move);
       }
 
       // Ignore remaining moves
       if (beta > alpha)
         return best_move;
    }
    return best_move;
  }
}
 
MinMove (GamePosition game) {
.
.
.
}

I'm having trouble in understanding a few parts:
1) The line

if (Value(move) > Value(best_move)) {

Does this mean that every move has to be evaluated against best_move using the "Evalgamestate" method?

2) What data-structure do you use to store every legal move within the "generatemove" method and what information from that particular state do you store?

[Ashish Schottky]

@Padda: Welcome to Ranch.

When you build any board game, its generally better to keep separate classes for organization ,search,evaluation.

I suggest you to write a clean 2-player game.
Then make the AI component by allowing it to play random. This will test for legal moves in a position and winning combinations.
in connect four, winning is simple, so make another fuction, let it return some value if any player has won, this is your maximum score, and in game like connect4, this is what we want to achieve.

Then make sure you would add in more sophisticated search algorithm like min-max. Here I would like to suggest you that you go for a better frame-work of min-max namely "nega-max".
Once you get this working, then add in alpha-beta pruning , PVS or what ever you feel like.


Answer for your 1) ::

Computer in normal min-max search will compare all the scores
say best_move has score +5 and move B will have score +7 then best_move's score will be assigned as 7 and best_move now will be move B.

However, addition of alpha-beta changes the things quickly.
By adding alpha-beta, search doesnt evaluate all nodes(moves), thus it is faster than naive min-max.

Answer for your 2) ::

It differs from programer to programer. In general and widely used basic data-structure are arrays.
Arrays is java are certainly faster than Strings.

If you think further, assuming your game is for 7x6(standard board), there are only 42 cells.
long type in java offers uptil 64 bits, here you can allot 1-bit per cell so that takes only 42 bits.
This is a complicated approach but would be very fast. However I suggest you not to take this approach on first go, make a working connect4, then optimize it.

I hope this is not home-work.

If you want me to help you, then let me know so that I can write on it.