I did an assignment today for my artificial intelligence subject ... don't worry, you will not be helping me with anything, its already submitted. Anyways, I would like someone to say whether I did this correctly or not... because when I was testing it, sometimes it seemed like it was trying to lose instead of win :( Anyways, here is the algorithm specific code...

	/**
	 * Determines the best column to play, using minimax with alpha beta pruning.
	 * @param game The game board to play.
	 * @return Column to play next.
	 */
	private int minimax(ConnectNBoard game) {
		// Make sure we were initialised properly
		if (!initialized) 
			throw new Error ("Complaint: I wasn't initialized!"); 
        	// Make sure there is room to make a move.
        	if (game.isFull())
            		throw new Error ("Complaint: The board is full!");
	        // Analyse situation.
		max(game,0,0,1);
		// Return which column to play.
		return best;
	}
	
	/**
	 * Part of a recursive algorithm to determine the best move to play next.
	 * @param board Game board.
	 * @param alpha Alpha value for alpha beta pruning.
	 * @param beta Beta value for alpha beta pruning. 
	 * @param level Current level in recursive process.
	 * @return Maximum resulting value from this point onwards.
	 */
	private int max(ConnectNBoard board, int alpha, int beta, int level) {
		// Exceeded cutoff point or board is full, return board evaluation.
		if (level == _maxdepth || board.isFull())
			return boardEvaluation(board, id);
		// most promising move so far.
		int best = -1;
		// For each playable (non full) column on game board.
		for (int col=0;col<board.numCols();++col) {
			// If column is full, skip.
			if (board.isColumnFull(col))
				continue;
			// Play this column.
			board.move(col, id==1?2:1);
			// Expand.
			int move = min(board, alpha, beta, level+1);
			// reverse play this column
			board.unmove(col, id==1?2:1);
			//
			if (move > best) {
				best = move;
				alpha = move;
				this.best = col;
			}
			// Prune.
			if (beta > alpha)
				return best;
		}
		// Return most promising value.
		return best;
	}
	
	/**
	 * Part of a recursive algorithm to determine the best move to play next.
	 * @param board Game board.
	 * @param alpha Alpha value for alpha beta pruning.
	 * @param beta Beta value for alpha beta pruning. 
	 * @param level Current level in recursive process.
	 * @return Minimum resulting value from this point onwards.
	 */
	private int min(ConnectNBoard board, int alpha, int beta, int level) {
		// Exceeded cutoff point or board is full, return board evaluation.
		if (level == _maxdepth || board.isFull())
			return boardEvaluation(board, id==1?2:1);
		// most promising move so far.
		int best = -1;
		// For each playable (non full) column on game board.
		for (int col=0;col<board.numCols();++col) {
			// If column is full, skip.
			if (board.isColumnFull(col))
				continue;
			// Play this column.
			board.move(col, id);
			// Expand.
			int move = max(board, alpha, beta, level+1);
			// reverse play this column
			board.unmove(col, id);
			//
			if (move > best) {
				best = move;
				beta = move;
			}
			// Prune.
			if (beta < alpha)
				return best;
		}
		// Return most promising value.
		return best;
	}

this.id is the player number ... it is only ever 1 or 2. Any feedback?

There are several problems with your code:
* The initial values of alpha and beta at the root are not (0,0), but (-infinity, +infinity).
* Having two functions max and min that do almost the same is generally a bad idea. Whenever you make a change to one of them, you have to remember to make the symmetric change in the other one. There is a common formulation of minimax called NegaMax that uses a single function. The idea is that a positive score always means "good for the player to move".
* "if (move > best) {" looks like the right comparison for max, but not for min. This wouldn't have happened if you had been using NegaMax.
[EDIT] * Using this.best to store the best move found won't work the way you wrote it. Notice that it will be set in many places within the tree, not just the root.

If you want to get this right, start by implementing minimax first, not alpha-beta. As I said, I recommend using a single function using the NegaMax trick. It's much easier to get that to work right. You'll have a very slow searcher that does the right thing. Once you are convinced that that part is working, add alpha-beta, and check that you get the same results from a search, regardless of whether you use alpha-beta or not.

Quote: Original post by alvaro
There are several problems with your code:
* The initial values of alpha and beta at the root are not (0,0), but (-infinity, +infinity).
* Having two functions max and min that do almost the same is generally a bad idea. Whenever you make a change to one of them, you have to remember to make the symmetric change in the other one. There is a common formulation of minimax called NegaMax that uses a single function. The idea is that a positive score always means "good for the player to move".
* "if (move > best) {" looks like the right comparison for max, but not for min. This wouldn't have happened if you had been using NegaMax.
[EDIT] * Using this.best to store the best move found won't work the way you wrote it. Notice that it will be set in many places within the tree, not just the root.

If you want to get this right, start by implementing minimax first, not alpha-beta. As I said, I recommend using a single function using the NegaMax trick. It's much easier to get that to work right. You'll have a very slow searcher that does the right thing. Once you are convinced that that part is working, add alpha-beta, and check that you get the same results from a search, regardless of whether you use alpha-beta or not.

The example I was using to write this code had -infinity and +infinity, I did not know what to do for it though ...

If you look carefully you will see that this.best is only done for the top-most level.
Dammit I forgot to do that ... intended to though :( dammit dammit dammit.