Hello everyone, I've spent the last few days turning my alpha-beta pruned minimax functions into a single ab-pruned negamax function. The actual code has gone pretty well considering I've found multiple sources for pseudocode around the net. I am having the worst time trying to get the alpha-beta pruning to work properly. I can run the negamax without AB pruning and it returns the proper scores for the appropriate moves. When I turn on AB pruning everything blows up! One question before I post the pseudocode for my AB-pruned negamax.... do I have to change my evaluation function for use in negamax (as different from use in minimax) ??? My minimax evaluation function takes in both MIN's and MAX's positions and returns a positive score if the board favors MAX and a negative score if the board favors MIN. From what I understand I am suppose to evaluate (in negamax) according to the side that is currently playing. (Which means to me that the evaluation function returns positive values if the side that is currently playing is winning, and negative if the side currently playing is losing) ... So a board favoring MIN does not always mean negative values and a board favoring MAX does not mean positive... For negamax: a board favoring the currently playing side gets positive values, and vice versa. Here is my negamax code... please tell me if there is anything obvious I am missing: <code> negamax_ab(maxPos, minPos, isMaxTurn, depth, alpha, beta) { if( depth == 0 || testGameOver(maxPos, minPos) == true) { if(isMaxTurn == true) return scoreGame(maxPos, minPos); else return scoreGame(minPos, maxPos); } bestScore = -Infinity moveList[] = generateMoveList(maxPos, minPos); foreach(move in moveList) { modifiedMAX modifiedMIN = makeMove(move, maxPos, minPos); score = -negamax_ab(modifiedMIN, modifiedMAX, (depth-1), -beta, -alpha); if(score > bestScore) { bestScore = score; alpha = score; } if(alpha > beta) { break; } } return bestScore; } </code> I know the beta cut should be alpha >= beta... but whenever I do that the scores come out wrong. ... Like I said before, I know the negamax part of it is working because when I do it without the Alpha-Beta pruning, each node returns a proper score. I know that with AB pruning, nodes that are sub-prime will return alpha or beta limit, but it seems to be returning everything improperly. Perhaps you can see something in my code. Many many Thanks for looking!!!

It's hard to tell what the problem is without knowing more details about the rest of the code, but there are two things that look suspicious to me:

1) When you get to a leaf, you normally return scoreGame(maxPos,minPos) or -scoreGame(maxPos,minPos). It is possible that the way your scoreGame is built you are guaranteed that -scoreGame(maxPos,minPos) is always the same as scoreGame(minPos,maxPos), in which case this is not the source of the problem.

2) `score = -negamax_ab(modifiedMIN, modifiedMAX, (depth-1), -beta, -alpha);' is almost certainly an error. If your position is described by the pair (maxPos,minPos), you never need to swap those two.

Besides these two problems, there is the `alpha>beta' that should be `alpha>=beta', but you already knew about this.

I think you would benefit from describing the position in a single type, and not mess with keeping two positions around. Besides, the names MAX and MIN are pretty confusing when you use an algorithm that swaps the sign of the score every step of the way.

Thanks again Alvaro! You've had some GREAT replies to my questions in the past. I am a bit confused by the different variations of AB pruned negamax that I am seeing. I was using the Negamax pseudo code found on wikipedia but I couldn't get things to line up properly.

On your point #1, I've never seen any pseudo code that used a -scoreGame() returned at the leaf nodes. I thought the negation happened when the value is returned through the -Negamax_AB() call. When do I return +scoreGame() and when do I return -scoreGame()?

I think a big confusion point for me is how the values returned from the evaluation function differ for use in Negamax then for use in Minimax. Do I need to adjust my evaluation function at all to switch from minimax to a negamax implementation?

My evaluation function takes MAXpos and MINpos (myPos and enemyPos) and returns a single value, positive if MAX(my) is winning or a negative number if MIN(enemy) is winning. This seems very intuitive when being used in minimax, how does that evaluation change when used in negamax?


For point #2, this raises further confusion. I know I labeled the negamax function as negamax_ab(maxpos, minpos) ... but really I was more thinking negamax_ab(myPosition, enemyPosition) which is why I was swapping the MAX and MIN positions on further calls to negamax_ab(). If I don't swap the positions how will the next function call generate moves for the opposing player? wouldn't it continue to make moves for only one player?

The reason I was using two values to describe MAX and MIN's position is because they each fit perfectly into two 64bit values (1 bit per piece per square) ... so I am able to do bit math on the positions.

Thanks again!!!

Greg

Quote: Original post by alvaro
It's hard to tell what the problem is without knowing more details about the rest of the code, but there are two things that look suspicious to me:

1) When you get to a leaf, you normally return scoreGame(maxPos,minPos) or -scoreGame(maxPos,minPos). It is possible that the way your scoreGame is built you are guaranteed that -scoreGame(maxPos,minPos) is always the same as scoreGame(minPos,maxPos), in which case this is not the source of the problem.

2) `score = -negamax_ab(modifiedMIN, modifiedMAX, (depth-1), -beta, -alpha);' is almost certainly an error. If your position is described by the pair (maxPos,minPos), you never need to swap those two.

Besides these two problems, there is the `alpha>beta' that should be `alpha>=beta', but you already knew about this.

I think you would benefit from describing the position in a single type, and not mess with keeping two positions around. Besides, the names MAX and MIN are pretty confusing when you use an algorithm that swaps the sign of the score every step of the way.

Describing the position as a pair (myPos, enemyPos) is unusual, but not necessarily wrong. You typically have the side to move as part of the board description, or you pass it around in your calls to NegaMax.

The changes in sign with the score and the flipping of positions can get confusing. The only thing you need to remember is that all the numbers in NegaMax should have the convention of "positive is good for the side to move, negative is bad for the side to move". Just make sure that you follow it religiously, and your code should work fine. If it doesn't, it might be time to use a debugger, or to add a bunch of good-old debugging print statements.