problem with alpha-beta..

[pimidrez]

hi, im doing alpha beta in my search tree, and its works fine..except in some positions with alpha-beta cuting its finds positions with a good value, but if I dont do alpha-beta cuting thats sames moves are not so well valueds..
only happen in some positions..
so I dont know why could its be...maybe improve ordering moves?
I only have orderin first the killer moves and then all the others..


any idea?

[crystalclear]

Alpha-Beta is a faster way of getting the same result as a complete search.
Move ordering should affect the length of time the search takes, but not the result: examining the good moves first means that bad moves may be eliminated by cut-off more quickly. That's how I see it.

I'd say there is an error in your alpha-beta code and I suspect that it might lie in an inequality eg

Code: Select all

       while ((i < number_of_moves) && (best_so_far <=  beta) ....
       while ((i < number_of_moves) && (best_so_far <  beta) ....


Then maybe searches are stopping because one move cannot be better than another and your software goes on to think that it is actually as good, thereby incorrectly evaluating it.

Alpha beta searches return a value. The value is only precise when it is inside the range alpha to beta. Whether the limits alpha and beta are included in the values which are precise appears to me to depend on how inequalities are tested inside the Alpha beta function, eg <, <=, >, >= etc.
It is my belief that care is required with the inequalities. Get them wrong and you will either search positions unnecessarily - which is not so bad, or reach incorrect conclusions - which is worse.

I have seen this sort of thing happen myself when my engine played a KR-K endgame and the engine sacrificed the rook.
The alpha beta routine determined that a move could do no better than keeping the rook, ie it didn't see far enough ahead to spot a checkmate.
And then it went on to think that the move actually kept the rook, which it didn't.
A tweak on an inequality in the Alpha Beta routine fixed things.

I think a number of very good chess engines don't have their alpha-beta stuff perfect.
I think incorrect parameters are passed at times, causing engines to search for example at depth greater than 6 for a move that is better than an already found Mate in 3. Or people do zero window searches A-B(x,x+1) instead of A-B(x,x).

When you read technical stuff about A-B, eg university theses, some seem to say that the return value x from alpha beta searches are valid if
a<x<b and others if a<=x<=b. I don't think that some of these theses are wrong; simply that there are alternative approaches to how to test inequalities.
But I think you can't pick-and-mix, and if you crib and alpha-beta algorithm from somewhere and another idea form somewhere else, you had better be careful that inequalites are correctly tested for your program.