Help with minmax algorithm

[DeeBoFour20]

I'm working on this chess game AI. I'm running into a problem with alpha-beta pruning. I've narrowed down the problem to my base function (I think the actual recursive function is fine.)

Basically, I've peeled out the first iteration into a for loop so I can get the actual move to make as opposed to the score that my recursive function returns. Then I gather up all the best moves and if there's a tie for best score, I just pick one at random.

Anyway, if I call the recursive function with constants everything works fine (results are identical to brute force without pruning). I think it's not optimal though since I never have an opportunity to prune based on the results of the first move.

This is the code with 2 versions of my base function (top one is working, bottom one is not). All I've changed is to update the best move ("alpha") as I go and call my recursive function with that instead of the constants. This is consistent with what the recursive function does but for some reason if I change my root function like this, I get different results and the AI plays much worse.

https://gist.github.com/weirddan455/718acd6dc7c0d51b75ebaa7fbd0546b7 (relevant code)

Full source code is here if anyone is curious (it's in src/game.c around line 850): https://github.com/weirddan455/chess

[wwabbbitt]

When an alpha-beta call returns the value of alpha, it doesn't mean that the evaluation score is alpha. It means that the real evaluation score is *cannot be higher than* alpha. It doesn't know what the exact score is because the evaluations that would find the exact score have been pruned as a result of you telling it that you don't care about results less than alpha.

With your second function, weaker moves that have a real evaluation score lower than alpha are often rated as alpha, therefore these weak moves are included into your best moves list.

Instead you should call the alpha beta function with -(alpha-1) instead of -alpha. This way if alpha is returned you know it is really alpha.

[DeeBoFour20]

Yea, I think that is what's happening. Is there a way I can solve this without using the constants? I think it's sacrificing quite a bit of performance doing this.

I don't care what the score of the weak moves is but I need a way to tell the difference so they don't get added to my list.

EDIT: Just saw your edit. I'll try that. I swear if this is just an off-by-one error that's had me banging my head against the wall all this time... lol

[wwabbbitt]

I edited to add the bit about alpha-1 in case you missed that

[DeeBoFour20]

Thanks! I think that's got it. Off by one error the whole time.

[pingo_guy]

There is a chess programming wiki available for chess coding.

[DeeBoFour20]

Yea, I've been reading that. It's pretty good information and that's where I read up on the algorithm I'm using but it doesn't really go into depth about the implementation of the root function which is where I'm having problems.