Hashing question

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
EricLang

Hashing question

Post by EricLang » Fri Dec 05, 2008 10:02 am

As I said in an earlier post, I am relatively new to hashing.
Now my positionhash returns complete nonsense when implementing it in
my AlphaBeta search. I call AlphaBeta with a certain depth and when it gets to zero it's ready.
Below I attached a stripped version of my AlphaBeta and my Hash.Probe.
Could anyone please check the code if the probing and storing is allright?
I have my doubts about the Hash.Probe (if Hash.Depth < aDepth).
Without the hash the engine plays allright, with the hash it just produces nonsense so there must be some severe error.

Code: Select all

function AlphaBeta&#40;Depth, Alpha, Beta&#58; Integer&#41;&#58; Integer;
begin
  HashFlag &#58;= hash_alpha;

  // Probe hash
  if Personality.UseHash then
  begin
    Value &#58;= Hash.Probe&#40;EngineBoard, Depth, Alpha, Beta&#41;;
    if Value <> PROBE_UNKNOWN then
    begin
      Result &#58;= Value;
      Exit;
    end;
  end;

   // Depth <= 0&#58; Call Quiet and return the result
  if Depth <= 0 then
  begin
    Result &#58;= Quiet&#40;Alpha, Beta&#41;;
    if Personality.UseHash then
      Hash.Store&#40;EngineBoard, Depth, Result, hash_exact&#41;;
    Exit;
  end;

  Inc&#40;CurrentPly&#41;;
  with MoveStack&#91;CurrentPly&#93; do
  begin
    // Generate moves and order them
    GenerateMoves;

    // Loop through the moves
    for i &#58;= 0 to MoveCount - 1 do
    begin
      Undo &#58;= MakeMove&#40;EngineBoard, CurrentMove&#41;;
      // Skip illegal moves
      if RunnedIntoCheck&#40;EngineBoard&#41; then
      begin
        UnmakeMove&#40;EngineBoard, CurrentMove, Undo&#41;;
        Continue;
      end;
      UnmakeMove&#40;EngineBoard, CurrentMove, Undo&#41;;

      // check beta cutoff
      if Value >= Beta then
      begin
        Result &#58;= Beta;
        if Personality.UseHash then
          Hash.Store&#40;EngineBoard, Depth, Beta, hash_beta&#41;;
        goto ExitPoint;
      end;

      if Value > Alpha then
      begin
        Alpha &#58;= Value;
        HashFlag &#58;= hash_exact;
      end;

    end; // loop through moves

    //  There are no valid moves&#58; it's mate or stalemate
    if ValidMoves = 0 then
    begin
      if PrevLevel^.GivingCheck then
        Result &#58;= -MATE + CurrentPly - 1
      else
        Result &#58;= 0;
    end
    //  We have valid moves, return alpha
    else begin
      Result &#58;= Alpha;
      if Personality.UseHash then
        Hash.Store&#40;EngineBoard, Depth, Alpha, HashFlag&#41;;
    end;
  end; // with MoveStack

  ExitPoint&#58;
  Dec&#40;CurrentPly&#41;;

end;


function THash.Probe&#40;const B&#58; TBoard; aDepth, Alpha, Beta&#58; Integer&#41;&#58; Integer;
var
  Hash&#58; THashElement;
begin
  Result &#58;= PROBE_UNKNOWN;

  // get slot
  Hash &#58;= fArray^&#91;B.HashKey mod Size&#93;;

  // check hashkey
  if Hash.hKey <> B.HashKey then
    Exit;

  // check if depth good enough
  if Hash.Depth < aDepth then
    Exit;

  // return appropriate result
  case Rec.HashFlag of
    hash_exact&#58;
      Result &#58;= Hash.Eval;
    hash_alpha&#58;
        if Hash.Eval <= Alpha then
          Result &#58;= Alpha;
    hash_beta&#58;
        if Hash.Eval >= Beta then
          Result &#58;= Beta;
  end; // case
end;


User avatar
Roman Hartmann
Posts: 295
Joined: Wed Mar 08, 2006 7:29 pm
Contact:

Re: Hashing question

Post by Roman Hartmann » Fri Dec 05, 2008 10:18 am

Hi,
after a quick look I think the problem is that your QS does (most probably) not return exact values. So the following code should be removed:
if Depth <= 0 then
begin
Result := Quiet(Alpha, Beta);
if Personality.UseHash then
Hash.Store(EngineBoard, Depth, Result, hash_exact);

Exit;
end;
Maybe there are other problems I didn't spot now.

best regards
Roman

EricLang

Re: Hashing question

Post by EricLang » Fri Dec 05, 2008 11:13 am

Hmm it seems you're right. Works better now. Strange because I thougth at depth 0 the evaluation was most exact. I must be missing something:)

(edit: thanks!)

mcostalba
Posts: 2684
Joined: Sat Jun 14, 2008 7:17 pm

Re: Hashing question

Post by mcostalba » Fri Dec 05, 2008 12:09 pm

EricLang wrote:Hmm it seems you're right. Works better now. Strange because I thougth at depth 0 the evaluation was most exact. I must be missing something:)

(edit: thanks!)
At the leaves of quiesce (or quiet as you call it) it is, but the value returned by quiesce it is not because it scans only capture moves, so cannot have a good picture of the whole thing.

If you call evaluate for each node in quiet (as is done when implementing "stand pat"), in this case the value is exact.

Marco

PK
Posts: 875
Joined: Mon Jan 15, 2007 10:23 am
Location: Warsza
Contact:

Re: Hashing question

Post by PK » Fri Dec 05, 2008 12:57 pm

ff You look at the source of CPW-engine at chessprogramming wiki, You will see another solution of Your problem - a separate procedure defining the relationship between depth 0 score and bounds. I'm not sure if hashing depth 0 scores is beneficial, though.

And I'm glad to see some Pascal code, reminds me good old days of my first program.

BTW, do You have a Winboard support module? If not, there is one available at

http://blog.maciej.szmit.info/static.ph ... _compchess

EricLang

Re: Hashing question

Post by EricLang » Fri Dec 05, 2008 2:12 pm

Haha, Delphi still lives, however I'm thinking about moving to either FreePascal or C. But C I have to learn from scratch, with its strange syntax.
But currently I stick to my Delphi7 until I get the feeling it's almost ready.

I'll have a look at that link. I played around with winboard long time ago. Interesting delphi things there :)

My chessprogram is far from finished. I started it a few years ago. Now I'm trying to make it stronger. The evaluation is far from finished. And the move-ordering has to be improved.

Then another question:
What's a good hashing function. I read about "anding" with HashSize - 1 if the hashsize is a power of two. But then the high part of the 64-bits hashkey is useless, it seems to me.

User avatar
hgm
Posts: 25820
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Hashing question

Post by hgm » Fri Dec 05, 2008 3:13 pm

It is not useless, merely not used for deriving the index in the hash table. It will be stored in the entry as signature, for testing if you have a hit.

So the point you notice is actually an advantage: because the lowest N bits are the only bits that contribute to the index, you don't have to store them in the signature. In Joker I have a 64-bit hash key, but only store the upper 32 bits as signature. The lower 32 bits (actually just the lowest 23 with 128MB hash) are used to derive the index.

This works because the Zobrist-type hash key is already homogeneously distributed over key space. So any mapping onto index is as good as any other, you won't get any more or less entry collissions because of taking only a fraction of the bits. This unlike hashing, e.g., identifiers. There it would be very bad to base the index on only the first few characters, because some combinations of characters occur very frequently, while others occur never at all. But the Zobrist key construction is already designed such that a tiny difference in the Chess position (e.g. moving a single piece) leads to a completely different hash key, where every bit is changed with 50% probability. So every piece on every square contributes to every bit of the key.

EricLang

Re: Hashing question

Post by EricLang » Fri Dec 05, 2008 3:37 pm

Ok, very clear. Thanks.

EricLang

Re: Hashing question

Post by EricLang » Fri Dec 05, 2008 4:57 pm

Hmm I see I forgot to copy the recursive AlphaBeta() before UnmakeMove() in my examplecode. Can't edit it anymore...

User avatar
hgm
Posts: 25820
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Hashing question

Post by hgm » Fri Dec 05, 2008 5:12 pm

No one seemed to miss it... :lol: :lol: :lol:

Post Reply