bounds in alpha-beta

23 views
Skip to first unread message

Walter Ravenek

unread,
Jun 5, 1996, 3:00:00 AM6/5/96
to

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

unread,
Jun 5, 1996, 3:00:00 AM6/5/96
to

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

Reply all
Reply to author
Forward
0 new messages