Some opening book design questions

[phhnguyen]

[moderation] My sincerest apologies. By hitting a wrong button and not noticing it in time when I wanted to reply to this posting I accidentally destroyed the contents of it. I put back some of the parts I happened to quote, but some parts I could not recover. HGM

However Polyglot does not have officially enough hash key for larger board. I don't like the way it stores moves in the data either.

...

I have read already an old post about your function to generate hash key for larger board. IMO, it is better if you list those hash key as an array (similar to Polyglot) instead of using function since it is not easy to re-write exactly in other languages. It is a bit harder when other people could you different board representations. You did not show how good your hash keys too (in term of collisions).

...

Thus I have been still considering to re-write a new one or modify Polyglot. Will try to keep compatible as much as I can or at leat build some converters.

...

IMO 4 byte key is so risky. It may OK for checking collisions in a book itself but may not be safe enough for searching.

...

In my previous implementation I used 7 bytes for key and 1 byte for weight. I may change to 8 bytes for key and 2 bytes for weight for the new implementation.

[phhnguyen]

If you are meant for Xiangqi:

1. You can have a index scheme that stores only one of the mirrored positions (LR/BW/LRBW). Scores should remain the same with current moving player's perspective.
Sample probing code here:
https://github.com/noobpwnftw/chessdb/b ... update.php

You right. The LRBW is actually I missed in my previous implementation.

2. Use binary encoding of FEN would benefit you in case of hash collisions, it happens quite often in my case.
I have some code shared for my board functions with binary FEN format here:
https://github.com/noobpwnftw/chessdb/t ... il/ccboard

I don't like to use FEN since it takes too much memory and time to compare.
I think 8 byte hash key is safe enough avoiding collisions in opening book.

3. Searching is inevitable if you want to avoid repetition rule problems.

I am not sure on this point. If the opening maker / pgn extractor have checked and ruled already games based on chess rules, we may save opening positions correctly. BTW, your engine may not search opening itself if it let GUIs do that job.

4. To avoid probing the book multiple times on one position you can use a key-value store of which key(board representation) maps to scores of known moves.

Can you say more about this point? I am not sure about "multiple times on one position". In my previous one I did binary search and if a good move / position found, it is done. No more search.

5. To further reduce size you can use radix trees.

I store books as an array of sorted hash keys. It cannot have any redundant to reduce more

Borrowing your thread I also want to ask about whether a proper method exists to use book knowledge to assist search, I've tried to store book PV into TT and/or sorting PV moves at new depth with book scores, they don't seem to be effective.

As I have remembered there are already some posts about saving some extra search information into book. However, IMO, it is completely wasted. If your rival made a move out of book, your engine is out of book too. How / what clue it can extract information?

You may pre compute and store extra information for every out-of-book moves but that may be too much for a very little gain.

[phhnguyen]

6) Moves:
My previous one did not store moves in data. Only positions in form of Zobrist hash key. From a given position I generate and make all legal moves, search new positions from books so I can get which moves are still in opening and their weights. I dont understand why Polyglot, ChessBase store moves in their opening positions?

Currently, polyglot book moves are valued based on win-loss-draw ratios from games. The book move can be selected from either a "pickbest" or random percentage value. However, different positions have different complexities. For example, the Stockfish Cerebellum book was produced using long thinking times, but the results are complex positions that are difficult to solve in very fast time control.

An idea might be to consider a depth-to-solve number (DTS) for possible moves in a position rather than moves based on win-loss-draw percentages. Thus when playing very fast blitz, the engine could select a move that averages no more than 10 ply to solve, and avoid a move that requires 30 ply of thinking to solve. Perhaps select a move that minimizes the depth-to-solve for the current position, and maximizes the depth-to-solve for the opponent responses.

Thanks for the info. Do you know the purpose / benefit of the move Polyglot store for each position?

From its document (http://hardy.uhasselt.be/Toga/book_format.html) it used only one move (not a move list) per key (position):

key uint64
move uint16
weight uint16
learn uint32

[D Sceviour]

Do you know the purpose / benefit of the move Polyglot store for each position?

From its document (http://hardy.uhasselt.be/Toga/book_format.html) it used only one move (not a move list) per key (position):

key uint64
move uint16
weight uint16
learn uint32

I do not use the learn entry in my polyglot probes so I do not know what is does. The weight of the move is determined when building the book, and is taken from the win-loss-draw ratio of a pgn game database. You have a choice of selecting the largest weight (flag pickbest) or selecting a random move from the move list.

I am suggesting a new idea here to create a book weight based upon depth-to-solve rather than building a book based on game win-loss-draw ratios. To my knowledge, this has never been tried before. I have an old GNU book code, so maybe I might experiment with depth-to-solve someday, or maybe I might modify a polyglot build.

[hgm]

However Polyglot does not have officially enough hash key for larger board. I don't like the way it stores moves in the data either.

I am not sure why one way storing the moves would be better than the other, as long as the moves are encoded uniquely. WinBoard just numbers the squares contiguously, and uses something like fromSquare + boardSize*toSquare + sqr(boardSize) * promotionChoice, where the third term doesn't play a role in Xiangqi. To decode it you need 'modulo boardSize' and 'integer divide by boardSize' operations, which in Xiangqi don't boil down to shifts and bitwise AND operations. But that hardly seems a problem.

I have read already an old post about your function to generate hash key for larger board. IMO, it is better if you list those hash key as an array (similar to Polyglot) instead of using function since it is not easy to re-write exactly in other languages. It is a bit harder when other people could you different board representations. You did not show how good your hash keys too (in term of collisions).

Quality of hash keys was discussed several times elsewhere, and on those occasions I did do actual tests to see how sets of keys obtained from rotating the bits of a given key would perform w.r.t. collision rate. My conclusion was that there was no difference for rotations by multiples of 8 bits (using each 'base key' 8 times), but rotating in steps of 1 (using each base key 64 times) would significantly drive up collision rate. Others have contradicted the latter, though, claiming that this was just an artifact due to the low quality of the PRNG used to generate the base keys.

I don't like the keys to be tabulated; IMO it would have been much better if Polyglot had included a PRNG to fill the key table at startup. Having to include the list is cumbersome even for Chess (2*6*64 keys plus some e.p. and castling keys). To do it for all 66 piece types supported by XBoad on boards potentially 16x16 would make an enormous list.

But if you prefer a list (which for Xiangqi would still be manageable, 2*7*90), it would be easy enough to take the Polyglot keys, apply the rotations on them that WinBoard would use for the board squares (64-89) and piece types (Elephant, Ferz, Wazir and Cannon) needed in Xiangqi but not used in orthodox Chess, and print that list. If you want a list you must generate it at some point, and you might as well use this one.

Thus I have been still considering to re-write a new one or modify Polyglot. Will try to keep compatible as much as I can or at leat build some converters.

Note that it is quite easy to convert one book format into another if the formats only differ in move encoding. While it is practically impossible to convert between book formats that differ in keys.

IMO 4 byte key is so risky. It may OK for checking collisions in a book itself but may not be safe enough for searching.

Agreed.

In my previous implementation I used 7 bytes for key and 1 byte for weight. I may change to 8 bytes for key and 2 bytes for weight for the new implementation.

A key of 7 bits would be safe enough. But it would lose all hope for compatibility and convertibility to other formats, which is probably not worth the space savings. As mentioned, Polyglot also adds 'learn info', two more 16-bit counters for number of games and number of half-points scored by the current book user. Most software using Polyglot books (including WinBoard) ignores these fields. But they act to make the entry size a multiple of 8, which is how the compiler would align an array of entry structs anyway.

[phhnguyen]

I don't like the keys to be tabulated; IMO it would have been much better if Polyglot had included a PRNG to fill the key table at startup. Having to include the list is cumbersome even for Chess (2*6*64 keys plus some e.p. and castling keys). To do it for all 66 piece types supported by XBoad on boards potentially 16x16 would make an enormous list.

But if you prefer a list (which for Xiangqi would still be manageable, 2*7*90), it would be easy enough to take the Polyglot keys, apply the rotations on them that WinBoard would use for the board squares (64-89) and piece types (Elephant, Ferz, Wazir and Cannon) needed in Xiangqi but not used in orthodox Chess, and print that list. If you want a list you must generate it at some point, and you might as well use this one.

If we use a list, it would take few more KB memory than using code. However, using a key list developers who want to use our books may get those keys straightaway in any programming languages. Rewriting your function may be harder and need some tests. Furthermore, your functions is actually from a GPL license project which someone don't like the license's restrictions.

A key of 7 bits would be safe enough. But it would lose all hope for compatibility and convertibility to other formats, which is probably not worth the space savings.

Actually it is doable for any sizes of hash key since they are used for searching, not for converting back (from a key) to a chess position. When the hash key systems are different, we cannot convert directly from one position key to other position key in other system. We need to rebuild whole opening tree anyway. We could do that since we always know the root (the starting position) then build up branches from that node. From an opening tree we could write down in any new format / new hash key system.

As mentioned, Polyglot also adds 'learn info', two more 16-bit counters for number of games and number of half-points scored by the current book user. Most software using Polyglot books (including WinBoard) ignores these fields. But they act to make the entry size a multiple of 8, which is how the compiler would align an array of entry structs anyway.

I don't like that field (learn info) either. In my previous implementation I separate learning data from opening data. Thus I could save a lot of memory (since real learnt data is usually small) and get easier to maintain data.

There are some tricks to use data when its size is not a multiple of 8. For example, if I need an entry of 9 bytes (8 bytes key, 1 byte weight) I simply write them as int8_t data[9] and then cast types when needed.

[jdart]

I have read a Hyatt's paper and implemented his method of book learning already. Is there any new method / update?

State of the art in this area is "dropout expansion," which was first popularized in checkers. See http://www.fierz.ch/strategy4.htm.

--Jon

[jdart]

Color-flipped positions *can* occur in chess, but I would be surprised if they were frequent enough to make this optimization a significant win.

--Jon

[noobpwnftw]

Crazy or not, here are some stats on binary encoded FENs from 8.85 billion stored positions in bytes:
min-keylen = 17, max-keylen = 45, avg-keylen = 35.19, avg-zkey = 7.34

After compression(as shown by avg-zkey) it is actually less than 8 bytes, yet seeking among keys are close to O(1). You can apply data specific filters during compression since you have quite a lot of similar rows in the opening positions.

Then, you can convert it to any other formats without having to iterate from a starting position or do de-duplication.

Certain positions in Xiangqi depend on whether the previous move contained a check or chase to determine the upcoming repetition is draw or lose. GUIs usually check it based on history moves, but when a move would cause reputation lose is found on the current moving side then it may be too late to avoid it without a major sacrifice. A small forward search in the book must be performed to avoid such cases.

If you store the book as "position_after_move -> score" then for each position you need to generate all moves and probe multiple times, I suggest you store the book as "position -> [move1 -> score1, move2 -> score2, ...]".

The last question, some opening variants may eventually lead to the same mid-game positions that can be reached by engine search, the book might not cover all paths towards it. Just like how WDL tablebases would benefit mid-game search.

Try out this one:
http://www.chessdb.cn/query_en/
The opening part contains 8.85 billion of unique positions with at least one move per position in ~32GB, covers almost every opening variation in Xiangqi. Each leaf is evaluated by engine no less than 20 plies and then back propagated to the root.

[hgm]

If we use a list, it would take few more KB memory than using code. However, using a key list developers who want to use our books may get those keys straightaway in any programming languages. Rewriting your function may be harder and need some tests. Furthermore, your functions is actually from a GPL license project which someone don't like the license's restrictions.

This argues indeed i favor of a list. But I could easily publish that list. Most of the probing code used in WinBoard was put in the public domain by Michel van den Bergh before I used it.

Actually it is doable for any sizes of hash key since they are used for searching, not for converting back (from a key) to a chess position. When the hash key systems are different, we cannot convert directly from one position key to other position key in other system. We need to rebuild whole opening tree anyway. We could do that since we always know the root (the starting position) then build up branches from that node. From an opening tree we could write down in any new format / new hash key system.

Yes, I know. I actually did this once, to decode the Elephant-Eye book. Perform a perft to generate positions, and write the info from the book probe together with a FEN to a file. You might miss disconnected positions, however.

I don't like that field (learn info) either. In my previous implementation I separate learning data from opening data. Thus I could save a lot of memory (since real learnt data is usually small) and get easier to maintain data.

There are some tricks to use data when its size is not a multiple of 8. For example, if I need an entry of 9 bytes (8 bytes key, 1 byte weight) I simply write them as int8_t data[9] and then cast types when needed.

This can be done, but on machine architectures that do not support unaligned memory access you would then have to compare the key byte by byte.

I am not saying Polyglot format is optimal. OTOH, its drawbacks are hardly important at todays storage and memory capacities, and compatibility with other software can be very useful.