4

I want a fast way to search how many times a certain position has appeared in a database of hundreds of thousands of games. I researched the best way to store positions in a database but all of the solutions were quite large and were stored as strings.

I thought of a different way and I was wondering if this would work or if there are some corner cases I did not consider.

Remember, the point of this storage would be to quickly search if a position had ever been reached before and not used to reconstruct entire games.

The first table would be int id, and BINARY(8) pieceExist

Starting from the top left of the board and reading to the right a1 would be set in a 64 bit number if any piece exists in that square and a 0 otherwise.

I would search this table first and retrieve a list of ids where pieces were in the same position as the board I am looking at

The next table would be int id (foreign key from the first table) Binary(16) pieceSpecification

This table specifies what piece is in each position, for every square where a piece exists you create a 4 bit number which would specify color and type of piece, which would has only 12 unique combinations. You would not need to store any information on where this piece is placed on the board as that is specified in the 64 bit number in the other table.

You would then find all ids where the pieceSpecification number you constructed has an equivalent value in the table.

You could probably off the database do a joint on the two sets of ids to see how many times your position has appeared in the database.

I reckon this approach has many benefits. Space in the database is minimized and searches would hypothetically be able to be completed in a matter of milliseconds.

Let me know if there are any problems with this or perhaps a better approach I could use.

Improve this question
5
  • It seems this theory was explored nearly 20 years ago link However I would like a modern take on this
    – Marc
    Mar 15, 2021 at 20:45
  • 1
    "for every square where a piece exists you create a 4 bit number which would specify color and type of piece" for a maximum of 128 bits.
    – A. I. Breveleri
    Mar 17, 2021 at 0:31
  • 1
    This scheme might make the DB more space-efficient, but it shouldn't significantly affect retrieval times compared to doing an exact string match query on a FEN string. Exact string match should be fast and constant time given a fixed maximum search key length.
    – bjb568
    Mar 17, 2021 at 1:13
  • 1
    @bjb568 I tested this with two tables of size 2 million The first table is ID, board structure, piece1, piece2 with a multi column index on the ladder 3. The second table is ID, varchar 64 The first table is 58% the size and searches are 1.8x faster
    – Marc
    Mar 17, 2021 at 5:55
  • By ladder 3 I mean, board structure (my 64 bit representation of the boat and if a piece exists on a square), piece1 and piece2 (which specifies what piece exists on each square where a piece exists)
    – Marc
    Mar 17, 2021 at 6:06

5 Answers 5

Reset to default
6

You can use the first 64 bits to encode which squares are occupied, and then encode what's in the occupied squares one by one, using four bits per square for up to 32 occupied squares.

The four bits allow sixteen possible piece types. There are only twelve types of pieces, but this lets us get in some additional necessary information. Here's an example encoding scheme.

0 - white pawn
1 - black pawn
2 - white knight
3 - black knight
4 - white bishop
5 - black bishop
6 - white rook that can't be castled with
7 - black rook that can't be castled with
8 - white rook that can be castled with
9 - black rook that can be castled with
A - white queen
B - black queen
C - white king if white has the move
D - black king if black has the move
E - the king that doesn't have the move
F - a pawn that has just advanced two squares

This should be enough to specify the position (piece locations, player to move, castling rights and en passant, but not fifty-move counter or move number).

Improve this answer
2

24 bytes is 24 * 8 = 32 * 6 bits, giving us 6 bits for each of the 32 units, with none to spare. 6 bits gives just enough info to specify a square, with none to spare.

Specify, in this order, the positions of wK, wQ, 2 wRs, 2 wBs, 2 wNs, 8 wPs, then likewise for Black. Code that a unit is "off the board" by giving its position as the same as its side's king. However, this encodes only one-box positions: it fails to encode positions where a side has (say) 2 Qs.

Improve this answer
2
  • we can use 5 bits for bishop.
    – TigerTV.ru
    Mar 17, 2021 at 0:04
  • 1
    @TigerTV.ru Good point. And promoted Q so long as it's on rank 1 or 8. But this scheme isn't the best anyway -- Huffmann encoding of FEN can do better. I'd have deleted this answer except that for some reason SE didn't allow me, even when my answer's vote-count was 0.
    – Rosie F
    Mar 17, 2021 at 6:05
2

You are on the right track.

With most databases, your most efficient organization would be a single user-defined table with two fields: your 64 (64 x 1) bit "square occupied" field, and your 128 (32 x 4) bit "next piece ID" field. The you instruct the database engine to sort the table and construct an index on the first field.

Don't worry about how to link the two fields or how to scan for the foreign key. Let the database engine do it; they're very good at this.

Improve this answer
3
  • This was the approach I wanted however there seems to be no 128 bit field that is possible. At the movement my 128 bit field is just 2 64 bit columns. Also though I said I only wish to search how often a position has existed I realize some of the extra FEN info may be needed for that, i.e if castling is available. Because a identical looking position can be reached but maybe one side can't castle because of a king move
    – Marc
    Mar 17, 2021 at 6:03
  • 1
    Nothing wrong with two 64-bit fields to store 128 bits, (Note that in many endgames the second of these will be zero.) - This results in three 64-bit unsigned integers.
    – A. I. Breveleri
    Mar 17, 2021 at 15:32
  • Yes, even with this problem the storage space saved per position is worth it, but perhaps I will explore some methods to condense bits if there are few pieces on the board
    – Marc
    Mar 17, 2021 at 16:58
2

If you're just wanting to know whether a position has been occurred before (or keep count of occurrences), use a Zobrist hash. I believe X-piece endgame tables use Zobrist hashing. That boils down a unique representation of a position to a 64-bit integer. Polyglot opening books also use Zobrist hashing, and have standardised Zobrist keys, which might be useful for future compatibility (looking up occurring positions in an openings book)

Scanning through your approach you're not taking into account castling possibilities, en-passant possibilities, nor who is to move. These are important, because a position where the White king can castle is different to one with the exact same piece configuration but White cannot castle.

Improve this answer
3
  • The castling conundrum is something I considered and mentioned in my comments to this and you are right, it is necessary to a position and would add a potentially 4 more bits I believe. Zorbist hash is something that came up in my research so I will look further into it now that you mentioned it, thank you for your comment
    – Marc
    Mar 17, 2021 at 21:27
  • my implementation is also useful for now nnot future opening analysis. I just save the possible next moves and the SAN origin to the opening entry. Then I can climb in whatever direction I like, no need to store a million hashes while stripping the whole game away from it
    – Artiphishle
    Jul 3, 2023 at 15:03
  • I thought tablebases were exact, so could not use Zobrist hashing due to collisions?
    – qwr
    Jul 4, 2023 at 15:35
1

The fastest way to search a database is to use the same format as the database. Searching a tree database with a FEN is slow as a conversion is needed for each move. Although a shorter position storage would be useful, it's not likely to happen soon.

Improve this answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.