bounds in alpha-beta

[Walter Ravenek]

In alpha-beta like procedures we can obtain a best result that
is greater than beta. If one starts out with a best value of
-INFINITY and passes the bound MAX(best, alpha) to recursive
calls of alpha-beta, one is supposed (if I understand correctly)
to return a best result greater than beta as function result.

In my program Arthur I have always used this approach. When
looking at the code of Crafty, I noticed that Bob Hyatt never
returns a score outside the search window.

I have performed an experiment to investigate the behaviour of
both methods. The results below pertain to the analysis of a
complete game, which contains both a complicated middlegame
and an endgame.

return best return beta

.. nodes : 2217102 2265696
.. qnodes : 2499183 2554797
.. swap-offs : 158760 156295
.. hash_probes : 2216688 2265252
.. hash_hits : 812128 884441
.. do_moves : 3427160 3480745
.. gen_moves : 1342774 1362852

== 358.50 sec 361.75 sec

All individual analyses yield exactly the same score and move.
Times for individual analyses differ 10% at most, in both
directions, but usually the difference is quite small.

I wonder whether somebody else has performed similar experiments,
and if so, whether the results are the same.

Walter Ravenek
Dept. of Chemistry
Vrije Universiteit
Amsterdam

[Robert Hyatt]

In article <ravenek-0506...@polonium.chem.vu.nl>,
Walter Ravenek <rav...@chem.vu.nl> wrote:
-->In alpha-beta like procedures we can obtain a best result that
-->is greater than beta. If one starts out with a best value of
-->-INFINITY and passes the bound MAX(best, alpha) to recursive
-->calls of alpha-beta, one is supposed (if I understand correctly)
-->to return a best result greater than beta as function result.
-->
-->In my program Arthur I have always used this approach. When
-->looking at the code of Crafty, I noticed that Bob Hyatt never
-->returns a score outside the search window.
-->
-->I have performed an experiment to investigate the behaviour of
-->both methods. The results below pertain to the analysis of a
-->complete game, which contains both a complicated middlegame
-->and an endgame.
-->
--> return best return beta
-->
-->.. nodes : 2217102 2265696
-->.. qnodes : 2499183 2554797
-->.. swap-offs : 158760 156295
-->.. hash_probes : 2216688 2265252
-->.. hash_hits : 812128 884441
-->.. do_moves : 3427160 3480745
-->.. gen_moves : 1342774 1362852
-->
-->== 358.50 sec 361.75 sec
-->
-->All individual analyses yield exactly the same score and move.
-->Times for individual analyses differ 10% at most, in both
-->directions, but usually the difference is quite small.
-->
-->I wonder whether somebody else has performed similar experiments,
-->and if so, whether the results are the same.
-->

This has been discussed before. The "fail-soft" implementation you are
using supposedly has one advantage (that I recall) over normal alpha/beta,
the fact that when it returns a value outside of the alpha/beta window, it
gives a better estimate of how far the window has to be widened to avoid a
fail high/low.

My only question is, how does your implementation actually result in fewer
nodes being searched? It would seem that since a cutoff occurs whenever
value >= beta, it would not matter whether you return beta or value? The
supposed benefit is seen on re-searches, notably at the root of the tree
where everything fails low, or one move fails high. In some tests I ran
over a year ago, I didn't see any improvement in Crafty, because often, the
value returned was nowhere near the value that the search returns once the
upper or lower bound was reset.

The primary benefit I see in Crafty, "as is" is that in some critical pieces
of code, the bound is clearly known. To avoid problems early on, I went for
the simple trans/ref implementation. It would take a lot of thought on my
part to understand how this change would affect hashing. Since this part of
the code is already a major source of errors when writing something like this
for the first time, I simply put this on my future work list.

--
Robert Hyatt Computer and Information Sciences
hy...@cis.uab.edu University of Alabama at Birmingham
(205) 934-2213 115A Campbell Hall, UAB Station
(205) 934-5473 FAX Birmingham, AL 35294-1170