Author: Vincent Diepeveen
Date: 07:06:32 03/11/04
Go up one level in this thread
On March 10, 2004 at 06:24:22, Uri Blass wrote:
>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.
Using the fail soft he uses that would be
return val;
But indeed one must return something >= beta :)
>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.