Author: rasjid chan
Date: 19:19:17 04/05/04
Go up one level in this thread
On April 05, 2004 at 20:40:55, Sune Fischer wrote:
>On April 05, 2004 at 19:58:00, rasjid chan wrote:
>
>>On April 05, 2004 at 19:25:33, Sune Fischer wrote:
>>
>>If I am not wrong, this is what I am doing and my hashing SEEMS working
>>ok. The PROBLEM is I make new discoveries every now and then.
>>
>>I understand hash table may have less bugs if we follow fail-hard
>>ie NEVER FAIL OUTSIDE ALPHA OR BETA AND NEVER HASH OUTSIDE ALPHA
>>BETA. But I have used fail soft without too much thought but simply
>>because having a highest LB (> beta) or the lowest UB ( < alpha)
>>seems appealing and trendy...
>>
>>I set a test question to see if most have the same answer.
>>Assume we use fail soft and we use one TT for all nodes, hashing depth = 0
>>for QS, other things as usual, if there is anything that may be assumed.
>>
>>We are in QS and not in-check and we have a few valid moves searched and
>>let :-
>>x = highest score of all the moves searched
>>x < alpha
>>
>>We now want to hash and return from QS.
>>
>>Poser :- How do you hash this node and return.
>>
>>Thanks
>>Rasjid
>
>I don't hash qsearch, it slows me down about 15% and doesn't really trim the
>tree so it's not worth it in my case.
>
>Regardless, let's look at your question.
>
>The example I posted was a probe into the table to get information out, this is
>technically more difficult than what you want to do here which is recording
>something into the table (well depends on replacement strategy of course).
>
>I assume your code looks something like (forgetting about the standpat for
>simplicity):
>
>int qsearch(int a,int b) {
> int ao=a,s;
>
> gen_qmoves();
> while (moves) {
> make();
> s = -qsearch(-b,-a);
> unmake();
> if (s>=b) {
> Record(s,BETA_FLAG,0);
> return s;
> }
> a = max(a,s);
> }
> if (ao!=a) Record(a,EXACT_FLAG,0);
> else Record(a,ALPHA_FLAG,0);
> return a;
>}
>
>void Record(int score,int flag,int depth) {
> HASH_ENTRY *ht = &HashTable[key&0x000ffff..];
>
> ht->flag = flag; // simple replace always scheme works ok
> ht->score = score;
> ht->depth = depth;
>
>}
>
>I actually record beta, I wonder if recording the softbound is better.
>
>untested of course, hope i got most of it right.
>
>-S.
Reply
======
> Record(s,BETA_FLAG,0);
I have no problem with this. I think failing high seldom give problems
and I am not sure if failing > beta DO NOT HAVE a benefit. But to implement
a full-failsoft theoretically correct model (irrespective of whether it is
better) we must fail high > beta otherwise there is no fail low < alpha.
> if (ao!=a) Record(a,EXACT_FLAG,0);
This is EXACT so no problem.
> else Record(a,ALPHA_FLAG,0);
Here may be the problem and here you deviate from the "full fail-soft"
model as you did not collect the best of the scores < alpha.
I actually made this post because of the way I do fail-soft and I am not
sure yet I got it right and it posed problems.
My answer
=========
Let x_eval = eval() score for the node.(so cannot ignore standpat )
let best_searched_score be the best score for all moves searched.
best_searched_score <= alpha
so either :-
a) alpha = x_eval (when set after eval() )
b) x_eval < alpha (when no alpha improvement and this is your a0)
my hash is as follow:-
if (x_eval >= best_searched_score){
storehash(x_eval, EXACT, depth = 0);
return x_eval;//****** fail low
}
storehash(best_searched_score, UPPER_BOUND, depth =0);
return best_searched_score;//****** fail low
Two different way to fail low, but I like exact more than upper bound
These are the subtleties (or erroneous method) I find.
Rasjid
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.