Some opening book design questions

[hgm]

There is a trick you can use to store the moves, which is to implement a move generator that can produce moves in a repeatable sort order, and then store the move indices in the book. You don't have to store the move itself, because you can just run the move generator, get the full list of moves and then pick the nth move, where n is returned from the book.

You would still need 8 bits to store the move, as a Chess position can have more than 127 moves. And there are 8-bit encodings that do not need complete move generation, but just looking at the board. By concatenating piece type, the number of the piece of that type (according to a raster scan of the board), and the number of the move a piece of that type can have.

E.g. Pawns can have 4 moves, and you can have 8 of them, so this requires 32 codes. Knights and King have 8 moves, and you have 3, so 24 more codes. Rooks and Bishops have up to 14 (use 16), and you have four, so 64 more codes. There even would be room for some over-completeness and for under-promotions. Not exhaustive, but how much of that would you need in the opening...?

Polar coordinates also can be useful, in large variants. E.g. to make a book for Maka Dai Dai Shogi in Polyglot format would be a problem, as it has a 19x19 board, so that a square number no longer fits in a byte, and the move field of 16 bits can no longer hold from- and to-square. But you can encode as from-square (9 bits), orientation (2 bits) and location along the ray (5 bits). That even leaves some codes (with invalid square numbers) to indicate special moves, like Knight jumps, by indicating an ID number of one of the few pieces that have such moves, and the number of the move.

[jdart]

I don't think so. Fishtest is short time control.

--Jon

[Joost Buijs]

I forgot to mention:

There is a trick you can use to store the moves, which is to implement a move generator that can produce moves in a repeatable sort order, and then store the move indices in the book. You don't have to store the move itself, because you can just run the move generator, get the full list of moves and then pick the nth move, where n is returned from the book.

--Jon

If I recall Chessbase is doing something like this in it's .ctg books. In the past I wrote some software to read .ctg books, besides the move indices they encoded everything in a very unusual and complicated way, it was the weirdest format that I have ever seen.

In Nightmare I use Polyglot format for compatibility reasons. I don't use Polyglot to generate the book but made a separate utility for it which doesn't give problems when I throw a huge number of games or an occasional bad PGN on it.

Nowadays storage is so cheap and fast that the size of the book doesn't matter much. My book consists of ~3.5 million high quality computer games limited to 70 ply, the encoded size is ~100MB. The hash keys are sorted and with a binary search retrieving a move goes almost instantly.

[Ras]

You would still need 8 bits to store the move, as a Chess position can have more than 127 moves.

But not within the book where you can even get away with 7 bits.

[Dann Corbit]

I forgot to mention:

There is a trick you can use to store the moves, which is to implement a move generator that can produce moves in a repeatable sort order, and then store the move indices in the book. You don't have to store the move itself, because you can just run the move generator, get the full list of moves and then pick the nth move, where n is returned from the book.

--Jon

I first saw that trick in an Amiga chess database called Pigbase around 1997.

You can still find the source code for it (written in Modula) by searching for pigb4src.lha

[phhnguyen]

Thanks all for ideas and suggestions.

After studying I see I may have very little benefit to reuse polyglot design and/or code. Thus I have created a new project for creating Xiangqi Opening book.

At the moment an opening item is very simple with two fields: key (64 bits) and value (16 bits), takes totally 10 bytes each. The key is the hard key of a position, the value is the hit count of that position.

Learning/edit data will be added separately.

I plan to add GUI for studying / edit node values later.

I have uploaded the basic and workable code (it could create opening book from a file or a folder) with MIT license.

The board is using a clear list of 64-bit numbers for creating hash keys. I knew it is not really important but I have managed to create that list with Hamming distance of 23, just in case later.

Please join us if you could and thanks in advance.

https://github.com/nguyenpham/MRXqOpeningBook

[Uri Blass]

There is a trick you can use to store the moves, which is to implement a move generator that can produce moves in a repeatable sort order, and then store the move indices in the book. You don't have to store the move itself, because you can just run the move generator, get the full list of moves and then pick the nth move, where n is returned from the book.

You would still need 8 bits to store the move, as a Chess position can have more than 127 moves.

If we are talking about opening book I doubt if there are positions with more than 127 moves.

Can you show me one position with more than 127 legal moves from a practical game?

I think that you can safely define position with more than 127 moves for one of the sides as mate against yourself without reduction in playing strength.

I doubt if you can practically get it without promotions.

queen and 2 bishops can get at most 49 moves because only one of them can be in the centre without blocking the other pieces

[D]8/8/3Q4/1K6/4B1k1/4B3/8/8 w - - 0 1
together with 2 knights and king and 2 rooks I cannot find more than 99
moves because I believe that putting both knights in the center means that there is no queen or bishops in the center(did not prove it).

[D]R7/1k3K2/3Q4/5B2/8/2N1BN2/1q2q1b1/7R w - - 0 1

If you want pawns to have more than 28 moves you need many promotions or captures and you also need the pawns not to block too many options for the pieces so I guess without many possible moves to promote it is not possible.

I guess that if the opponent has more than 127 moves you can safely resign and if you have more than 127 moves you could safely win earlier without getting to position with more than 127 moves.

[Toadofsky]

I once authored a function which could be used to compare pawn structures of two positions to measure their similarity (by counting bits of a bitwise-AND):

https://gist.github.com/ddugovic/e1381c ... 80e6ae4eea

Theoretically this could be used to classify opening positions never seen before by measuring their similarity to known opening positions (although there is no guarantee that the moves in known positions will be good or even legal in new positions).

[noobpwnftw]

An interesting result for Xiangqi is if you do some brute force book making with perft 5 and then roll out by only cutting nodes that had a score worse than max(-75, bestscore-40/(1+exp(-abs(bestscore)/10))) (a rook=1000, bestscore is of root position) with a 20-ply search and keep at least 5 moves, it will most likely to convergent quite soon(rough growth factor of 2 for new nodes at ply=15 and some 1.7 at ply=20).

Usually any position at this stage not covered by the book are just bad and can barely have a chance of drawing.

I think if you systematically do this(i.e. brainfish?) on a scale like I did, similar result can be achieved and you get an ultimate book once and for all...

[phhnguyen]

I have just completed all main functions / blocks. All are about 60-70% of work I plan to do.

The main code (cli) is written in pure std C++ 11. The GUI is in Qt (using QML and Qt Quick). Thus all code could be compiled and run in almost all OSs. The opening book could be viewed as a tree and edited weights directly.

I still consider to develop a version for chess. Join us if you are willing to help. Thanks in advance.