Author: Uri Blass
Date: 03:24:22 03/10/04
Go up one level in this thread
On March 10, 2004 at 05:45:47, Renze Steenhuisen wrote:
>In the code below leaving line with "/* 1 */" out saves nodes, and I don't
>understand why?! If I am correct the code represents a normal implementation of
>the use of Transposition Tables.
>
>---------------------------
>
>SCORE search(alpha, beta, depth)
>{
> if( depth==0 )
> return static_eval();
>
> probe_TT_and_try_to_cutoff()
>
> if( do_null_move )
> {
> makeMove(null_move)
> null_val = -search(-beta-1, -beta)
> unmakeMove(null_move)
> if( null_val>=beta)
> {
> store_in_TT(null_val, LOWERBOUND) /* 1 */
> return null_val;
> }
> }
>
> best_val = -INFINITY
> for(all legal moves)
> {
> makeMove()
> val = -search(-beta, -alpha, depth-1);
> unmakeMove()
> best_val = MAX(best_val, val)
> if( val>=beta )
> {
> store_in_TT(val, LOWERBOUND)
> }
> }
>
> if( best_val>alpha )
> store_in_TT(best_val, EXACTBOUND)
> else
> store_in_TT(best_val, UPPERBOUND)
>
> return best_val
>}
2 comments:
1)I do not use hash tables efficiently and I store information only
when val>=beta(I found that other options were simply worse for me in the last
time that I tried(more than a year ago) and did not continue to investigate the
problem.
I plan to rewrite my alphabeta and one of the things to rewrite there is also
using the hash tables in a better way.
2)if val>=beta you should return beta and not only store the val in the hash.
I guess that you do not have
if( val>=beta )
{
store_in_TT(val, LOWERBOUND)
}
but
if( val>=beta )
{
store_in_TT(val, LOWERBOUND);
return val;
}
Note that I think that it is always a good idea to compare also with
if( val>=beta )
{
store_in_TT(beta, LOWERBOUND);
return beta;
}
The point is that you got val based on the assumption that the score is between
alpha and beta and this assumption may lead to pruning that can be avoided with
bigger bounds.
In other words the point is that you may prune some lines that you are sure that
they will give score above beta so the fact that you got score of beta+200 based
on selective search may be misleading because a line that could cause the score
to be beta+100 was pruned.
You may decide to prune moves except captures and checks in the last ply because
you are sure that they will not get the score above alpha.
Suppose that you find that captures and checks are bad then your selctive search
may return alpha-300 that will be translated to beta+300 when you go back when
practically there is a quiet move that return alpha-100 that is translated to
beta+100 when you go back.
I think that a poosible solution may be simply to increase best_val when you do
this kind of selective search but I guess that it is better to have always the
fail hard code because you may have some bug and having fail hard code can help
you to verify that at least you do not have bugs that cause fail hard to be
better than fail soft.
I use today fail hard but I believe that fail soft should be better and when I
rewrite my alphabeta I will try to have both fail soft and fail hard in the same
code.
Uri
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.