Is LMR Sound.

[Daniel Shawul]

The search2 function does contain two additional arithmetic operations though, score+1 and minExact-1. A real implementation would likely want to test if the current range is a null window. This test is (beta<=alpha+1) in the classical implementation, but would become (maxExact<minExact) in the alternative implementation

I think that loosing the meaning of upperbound and lowerbound is not a good idea. The upper bound could be smaller in a conventional null window search, and be equal when beta=alpha+1 in the standard case. So the test to update alpha and beta should be done separately wihtout assuming score>=alpha to imply score > beta. I didn't check it properly but your second code block may need to be modified like so. If that is the case, then it proves the point that it is a recipe for problems, but i am sure it is possible to make it work though it probably won't bring advantages. Knuth describes alpha-beta as the F2 procedure like this

Code: Select all

F2&#40;p, alpha, beta&#41; <= alpha if F&#40;p&#41; = alpha, 
F2&#40;p, alpha, beta&#41; = F&#40;p&#41; if alpha < F&#40;p&#41; < beta 
F2&#40;p, alpha, beta&#41; >= beta if F&#40;p&#41; >= beta. 

and the branch-and-bound algorithm with one bound i.e beta

Code: Select all

F1&#40;p, beta&#41; = F&#40;p&#41; if F&#40;p&#41; < beta, 
F1&#40;p, beta&#41; >= beta if F&#40;p&#41; >=beta 

[petero2]

The search2 function does contain two additional arithmetic operations though, score+1 and minExact-1. A real implementation would likely want to test if the current range is a null window. This test is (beta<=alpha+1) in the classical implementation, but would become (maxExact<minExact) in the alternative implementation

I think that loosing the meaning of upperbound and lowerbound is not a good idea. The upper bound could be smaller in a conventional null window search, and be equal when beta=alpha+1 in the standard case. So the test to update alpha and beta should be done separately wihtout assuming score>=alpha to imply score > beta. I didn't check it properly but your second code block may need to be modified like so. If that is the case, then it proves the point that it is a recipe for problems, but i am sure it is possible to make it work though it probably won't bring advantages.

In my chess program I always call the search function with beta >= alpha + 1. Therefore (score >= beta) => (score > alpha), so having "if (score >= beta)" inside the "if (score > alpha)" block is ok.

If we make the substitution minExact=alpha+1 and maxExact=beta-1 in the previous paragraph, it becomes:

Code: Select all

In my chess program I always call the search function with (maxExact+1) >= (minExact-1) + 1. Therefore (score >= (maxExact+1)) => (score > (minExact-1)), so having "if (score >= (maxExact+1))" inside the "if (score > (minExact-1))" block is ok.

Which can be simplified to:

Code: Select all

In my chess program I always call the search function with maxExact >= minExact-1. Therefore (score > maxExact) => (score >= minExact), so having "if (score > maxExact)" inside the "if (score >= minExact)" block is ok.

I don't think alternative representations of the "exact range" has any technical advantages. However I do think that if you took 100 smart persons with some programming experience but no knowledge of the alpha beta algorithm, and explained the idea without mentioning alpha, beta, or how to represent the "exact range", and asked them to implement it, it is not unreasonable to assume that some of them would come up with non-standard but correct implementations of the alpha beta idea. For example, someone with experience from the C++ standard template library might think that lo <= score < hi would be a good representation of the range.

[Daniel Shawul]

You are right about the code being correct, don't know why i thought score>alpha to imply score >= beta? However the default is still better because it keeps the meaning of upper and lower bound. (2,3)->(3,2) and (2,4)->(3,3) loose their meaning, definition of PV/CUT nodes, different search bound based pruning would be hard to reason about. As a matter of fact minExact=alpha+100 and maxExact=beta-100 would still work but you have to use a method reminiscent of macro substitution like you just did.

When you have to write things from _scratch_, you will probably make lots of mistakes if you don't use the default. I am saying this because i am one of those persons who used a non-standard variation with my first checkers program at first. I had a hard time understanding why my beta can be less than my alpha, and then convince myself that I should test for score>=beta-1 and then fix the fix when it shows problems etcetra... I understood things after some time passed. At the time I barely knew of alpha-beta, but i remember i kludged minimax by myself like many here. That after spending lots of time writing a program that plays checkers by static evaluation and pattern matching for tactics, fun times!