Algorithm for Performing a Position Search in a Database

[Dave_N]

I want to do a position search using Zobrist hash keys, can anyone point to a resource that describes the algorithm of finding "similar" positions?

[JuLieN]

I want to do a position search using Zobrist hash keys, can anyone point to a resource that describes the algorithm of finding "similar" positions?

Here's the simplest I can come to at 3.30 a.m. In pseudo-Pascal.

Code: Select all

type
  ChessPosition = record
    Zobrist: UInt64;
    PositionData: Integer;
  end;
  
var
  MyDataBase := array[1..MAXENTRIES] of ChessPosition;
  CurrentZobrist, AZobrist : UInt64;
  AChessPos, OldChessPos: ChessPosition;

  procedure SaveToDatabase(ChessPos: ChessPosition);
  begin
    MyDataBase[ChessPos.Zobrist mod MAXENTRIES] := ChessPos;
  end;

  function ProbeDatabase(PosZobrist: UInt64):ChessPosition;
  begin
    result := MyDataBase[PosZobrist mod MAXENTRIES];
  end;

begin
  // Save a position in the database
  AChessPos.Zobrist := CurrentZobrist;
  AChessPos.PositionData := whatever_you_want;
  SaveToDatabase(AChessPos);
  AZobrist := CurrentZobrist;

  ... some code...

  //Retrieve this position later
  OldChessPos := ProbeDataBase(AZobrist);
end.

[sje]

Here's the simplest I can come to at 3.30 a.m. In pseudo-Pascal.

Code: Select all

  MyDataBase := array[1..MAXENTRIES] of ChessPosition;

  procedure SaveToDatabase(ChessPos: ChessPosition);
  begin
    MyDataBase[ChessPos.Zobrist mod MAXENTRIES] := ChessPos;
  end;

  function ProbeDatabase(PosZobrist: UInt64):ChessPosition;
  begin
    result := MyDataBase[PosZobrist mod MAXENTRIES];
  end;

Can you guess what happens when PosZobrist is an integral multiple of MAXENTRIES?

[sje]

I want to do a position search using Zobrist hash keys, can anyone point to a resource that describes the algorithm of finding "similar" positions?

Ah, the old "fuzzy match" problem.

See: http://en.wikipedia.org/wiki/Approximat ... g_matching

[Dave_N]

Thanks - for the replies, although Wikipedia is down at the moment here for 24 hours. Perhaps there is a good technique for help of writing FuzzyHashProbe on the page...

[micron]

To get useful help, I think you need to be more explicit about what you intend to search, and what you mean by "similar".
Are you searching something like a polyglot book? That's a common format for a position database.

If "similar" means "within one move of the enquiry position", then normal and retrograde move generators would play a role in the solution.

This seems like something a GUI might want, not an engine, right? Please clarify the purpose.

Robert P.

[Dave_N]

Yes precisely, the search is for a GUI, however not for a polyglot book, I think having a setting for number of moves distance from the position solves most of the problems, and then simply scanning the database for matching hash entries, or even hashing the entire database into a table and scanning the hash for lists of indexes. For this is would be convenient to have a persistent hash table ... I looked at http://stlplus.sourceforge.net/ however I am still not sure about the implementation.

[Dave_N]

Although the Zobrist keys are supposed to be built incrementally, I think the move history isn't deducible from the Hash key, so a tree searchable hash table isn't built from the pgn move tree ..(or am I wrong?). I thought hash tables in tree form were usually self-balancing anyway.


edit: fixed typo

[Dave_N]

Pardon the triple post ...

I just realized that the hash table can be a separate entity and can simply index a tree built from the entire database and the tree can be searched for games from the same position, obviously all similar positions can be found from the tree.

[Rebel]

Zorbist is the way to go indeed, it's how the EOC database approach works.

Perhaps Protools can be of use for you.

•Menu F8 - Make and use EOC Chess Trees from REBEL or PGN databases. I was able to create a 88 million position EOC chess tree from a 2.5 million PGN database within an hour.

Source code to access an EOC database and find a position at: http://www.top-5000.nl/eoc.htm