Opening book implementation questions

[pedrojdm2021]

Hello, it's me again. I am nearly reaching the end to finish my engine for the chess application that i am working on.

but there is a missing feature: variation. i did a research and i found that opening books helps with this. and also they do help in other things.

i have found that people download a large .pgn files with thousands of games and then they build a book from there.

i have looked at other engines and i found that they store their "book.txt" into a file with a game per line. (a2a4 g8h6 ... )
these games per line are the raw games from a .pgn file? i mean, the complete moves list from a game? or there are some "cleanup" that is usually done to consider it an "opening book" ?

my other question is on the "lookup" for the opening book:
the lookup is for example i have a sequence of moves that corresponds from more than one game in my "book", then i choose randomly the move from one of the "next" moves in the corresponding games, right? or i am wrong?

i am a little lost on it since i can't find a very clear explaination on this, any help will be great,
greetings. Pedro

[smatovic]

I suggest to dig a little bit into PolyGlot .bin books:

https://www.chessprogramming.org/Opening_Book

You can create a PolyGlot book from .pgn games, positions are hashed, there are free implementations/code out there, for example:

https://web.archive.org/web/20190201143 ... ormat.html

Multiple move choices from a book can be scored, so you can pick by score, add some score based variation, or pick randomly.

--
Srdja

[Ras]

i have looked at other engines and i found that they store their "book.txt" into a file with a game per line. (a2a4 g8h6 ... )

I have such a book format, and it's hand curated. However, this is only the input for the opening book compiler I wrote to transform this into a position based format so that transpositions work, as huge .c file that gets compiled right into the engine executable. It's around 112kB of binary data. The lookup works via hashing the board position using a CRC-40 checksum, and the positions are sorted by hash in the opening book. I have an auxiliary array with 256 entry positions via right-shifting the hash so that I don't have to go through all of the book each time.

The advantage is that there's no need to configure anything - the disadvantage is that book updates require a recompilation. However, the user has always the option to switch off the engine internal book and let the GUI use its own book.

[JohnWoe]

PolyGlot book uses 64b hash/16bit move/... So 128bit per entry. Learn/score is useless. I would prefer tighter 96b format... For bigger boards 16bit per move isn't even enough. The book is sorted so it can be read fast w/ binary search algo. 1B entries is just 30 steps...
I use PolyGlot in Mayhem simply so I can use existing books.
Some engines use (e4(e5(Nf3))) but then there's no transpositions.
There's no reason to waste time for opening moves 1.e4 / 1. e4 c5 ...

[pedrojdm2021]

i have looked at other engines and i found that they store their "book.txt" into a file with a game per line. (a2a4 g8h6 ... )

I have such a book format, and it's hand curated. However, this is only the input for the opening book compiler I wrote to transform this into a position based format so that transpositions work, as huge .c file that gets compiled right into the engine executable. It's around 112kB of binary data. The lookup works via hashing the board position using a CRC-40 checksum, and the positions are sorted by hash in the opening book. I have an auxiliary array with 256 entry positions via right-shifting the hash so that I don't have to go through all of the book each time.

The advantage is that there's no need to configure anything - the disadvantage is that book updates require a recompilation. However, the user has always the option to switch off the engine internal book and let the GUI use its own book.

Hello, i did some research and i ended up with this:

I downloaded a big ammount of games from here: https://www.pgnmentor.com/files.html

and i generated a pretty big opening book that looks like this:

Code: Select all

e2e4 c7c5 g1f3 d7d6 d2d4 c5d4 f3d4 g8f6 b1c3 a7a6 c1g5 e7e6 
d2d4 g8f6 g1f3 e7e6 c2c4 b7b6 g2g3 f8b4 c1d2 b4d2 d1d2 c8a6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 c2c4 g7g6 b1c3 f8g7 e2e4 d7d6 g1f3 e8g8 f1e2 e7e5 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 g1f3 g7g6 c2c4 f8g7 b1c3 d7d6 e2e4 e8g8 f1e2 e7e5 
e2e4 e7e6 d2d4 d7d5 b1c3 f8b4 e4e5 g8e7 a2a3 b4c3 b2c3 c7c5 
d2d4 g8f6 c2c4 c7c5 d4d5 b7b5 c4b5 a7a6 b5a6 g7g6 b1c3 c8a6 
e2e4 c7c5 g1f3 d7d6 d2d4 c5d4 f3d4 g8f6 b1c3 a7a6 c1e3 e7e5 
g1f3 g8f6 c2c4 c7c5 b1c3 b8c6 g2g3 g7g6 f1g2 f8g7 e1g1 e8g8 
e2e4 c7c5 g1f3 b8c6 b1c3 e7e5 f1c4 f8e7 d2d3 g8f6 e1g1 d7d6 
e2e4 e7e6 d2d4 d7d5 b1c3 g8f6 e4e5 f6d7 f2f4 c7c5 g1f3 d8b6 
d2d4 d7d5 g1f3 g8f6 c2c4 c7c6 b1c3 a7a6 d1b3 e7e6 c1g5 d5c4 
d2d4 g8f6 c2c4 e7e6 g1f3 d7d5 b1c3 c7c6 c1g5 b8d7 e2e3 f8e7 
g1f3 g8f6 c2c4 c7c5 b1c3 b8c6 d2d4 c5d4 f3d4 e7e6 g2g3 d8b6 
e2e4 c7c5 g1f3 b8c6 d2d4 c5d4 f3d4 g8f6 b1c3 e7e5 d4b5 d7d6 
e2e4 c7c5 g1f3 e7e6 b1c3 b8c6 d2d4 c5d4 f3d4 d8c7 g2g3 a7a6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
e2e4 c7c5 g1f3 b8c6 f1b5 g8f6 b5c6 d7c6 d2d3 f6d7 c1f4 g7g6 
e2e4 c7c5 g1f3 e7e6 d2d4 c5d4 f3d4 b8c6 b1c3 d8c7 f2f4 c6d4 
e2e4 e7e5 f1c4 g8f6 d2d3 c7c6 g1f3 f8e7 e1g1 d7d6 a2a3 e8g8 
g1f3 c7c5 c2c4 b8c6 d2d4 c5d4 f3d4 g8f6 b1c3 e7e6 c1g5 h7h6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 c2c4 g7g6 b1c3 f8g7 e2e4 d7d6 g1f3 e8g8 f1e2 e7e5 
e2e4 e7e6 d2d4 d7d5 b1c3 d5e4 c3e4 b8d7 f1d3 g8f6 e4f6 d7f6 
....

When the applications starts, i load it and stores it into a hashtable that takes as argument the hash key from the board and it returns the list of "book moves" that are in that position (hash key)

the "book moves" are stored by the sequence of the game, if after "e2e4 c7c5 " comes a "g1f3" for the hash key that results of "e2e4 c7c5" moves it will be added "g1f3" to the list of that position, and so on.. i think you get the idea how i am doing this. Is this the "correct" implementation, right?

if that list is empty, the book simply return 0, in that way i can validate to return the book move or ask to the AI to search an move.

the other thing is that i need variation for all possible openings that a human can do in the starting position, so maybe i'have to tweak values to make opening book possible for all 20 initial moves... from a2a4 to g1h3

other than that, it is working pretty nice, the only "problem" is to generate a decent opening book

[Ras]

Is this the "correct" implementation, right?

That's nearly how I'm doing it - but I'd also add a cross-check for legality. Means, when assembling the list of available book moves for a given board hash, I also check whether each book move is in the list of legal moves on the board. That will be required latest once you have an en passant capture in the book because whether this is legal depends on how you reached the position. Other than that, I have auto-promotion to queen in the book code if a pawn reaches the last rank.

I'd also add a legality check when assembling the hash list to deal with possible mistakes in the text book list, along with a useful error message which line is wrong.

the other thing is that i need variation for all possible openings that a human can do in the starting position, so maybe i'have to tweak values to make opening book possible for all 20 initial moves... from a2a4 to g1h3

Yes, I have that, too. That in turn requires a passive book knowledge marker such as appending a "?" to book moves that the engine shall not play actively. The implemenation is to execute the line when generating the hash table, but not adding this move to the list of moves in a position.

[pedrojdm2021]

Is this the "correct" implementation, right?

That's nearly how I'm doing it - but I'd also add a cross-check for legality. Means, when assembling the list of available book moves for a given board hash, I also check whether each book move is in the list of legal moves on the board. That will be required latest once you have an en passant capture in the book because whether this is legal depends on how you reached the position. Other than that, I have auto-promotion to queen in the book code if a pawn reaches the last rank.

I'd also add a legality check when assembling the hash list to deal with possible mistakes in the text book list, along with a useful error message which line is wrong.

the other thing is that i need variation for all possible openings that a human can do in the starting position, so maybe i'have to tweak values to make opening book possible for all 20 initial moves... from a2a4 to g1h3

Yes, I have that, too. That in turn requires a passive book knowledge marker such as appending a "?" to book moves that the engine shall not play actively. The implemenation is to execute the line when generating the hash table, but not adding this move to the list of moves in a position.

I'd also add a legality check when assembling the hash list to deal with possible mistakes in the text book list, along with a useful error message which line is wrong.

the legality check, i do it at the moment of creating the hashtable, i play each of these "games" and at the same time adding the moves to the hashTable, the legality is covered inside the MakeMove function

Yes, I have that, too. That in turn requires a passive book knowledge marker such as appending a "?" to book moves that the engine shall not play actively. The implemenation is to execute the line when generating the hash table, but not adding this move to the list of moves in a position.

well i do not put the book inside the engine module, i have it on my own gui module, but i did not unterstood very good your implementaton on it, i think i'll just create some entries on the opening book to cover these situations

[phhnguyen]

i have looked at other engines and i found that they store their "book.txt" into a file with a game per line. (a2a4 g8h6 ... )

I have such a book format, and it's hand curated. However, this is only the input for the opening book compiler I wrote to transform this into a position based format so that transpositions work, as huge .c file that gets compiled right into the engine executable. It's around 112kB of binary data. The lookup works via hashing the board position using a CRC-40 checksum, and the positions are sorted by hash in the opening book. I have an auxiliary array with 256 entry positions via right-shifting the hash so that I don't have to go through all of the book each time.

The advantage is that there's no need to configure anything - the disadvantage is that book updates require a recompilation. However, the user has always the option to switch off the engine internal book and let the GUI use its own book.

Hello, i did some research and i ended up with this:

I downloaded a big ammount of games from here: https://www.pgnmentor.com/files.html

and i generated a pretty big opening book that looks like this:

Code: Select all

e2e4 c7c5 g1f3 d7d6 d2d4 c5d4 f3d4 g8f6 b1c3 a7a6 c1g5 e7e6 
d2d4 g8f6 g1f3 e7e6 c2c4 b7b6 g2g3 f8b4 c1d2 b4d2 d1d2 c8a6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 c2c4 g7g6 b1c3 f8g7 e2e4 d7d6 g1f3 e8g8 f1e2 e7e5 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 g1f3 g7g6 c2c4 f8g7 b1c3 d7d6 e2e4 e8g8 f1e2 e7e5 
e2e4 e7e6 d2d4 d7d5 b1c3 f8b4 e4e5 g8e7 a2a3 b4c3 b2c3 c7c5 
d2d4 g8f6 c2c4 c7c5 d4d5 b7b5 c4b5 a7a6 b5a6 g7g6 b1c3 c8a6 
e2e4 c7c5 g1f3 d7d6 d2d4 c5d4 f3d4 g8f6 b1c3 a7a6 c1e3 e7e5 
g1f3 g8f6 c2c4 c7c5 b1c3 b8c6 g2g3 g7g6 f1g2 f8g7 e1g1 e8g8 
e2e4 c7c5 g1f3 b8c6 b1c3 e7e5 f1c4 f8e7 d2d3 g8f6 e1g1 d7d6 
e2e4 e7e6 d2d4 d7d5 b1c3 g8f6 e4e5 f6d7 f2f4 c7c5 g1f3 d8b6 
d2d4 d7d5 g1f3 g8f6 c2c4 c7c6 b1c3 a7a6 d1b3 e7e6 c1g5 d5c4 
d2d4 g8f6 c2c4 e7e6 g1f3 d7d5 b1c3 c7c6 c1g5 b8d7 e2e3 f8e7 
g1f3 g8f6 c2c4 c7c5 b1c3 b8c6 d2d4 c5d4 f3d4 e7e6 g2g3 d8b6 
e2e4 c7c5 g1f3 b8c6 d2d4 c5d4 f3d4 g8f6 b1c3 e7e5 d4b5 d7d6 
e2e4 c7c5 g1f3 e7e6 b1c3 b8c6 d2d4 c5d4 f3d4 d8c7 g2g3 a7a6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
e2e4 c7c5 g1f3 b8c6 f1b5 g8f6 b5c6 d7c6 d2d3 f6d7 c1f4 g7g6 
e2e4 c7c5 g1f3 e7e6 d2d4 c5d4 f3d4 b8c6 b1c3 d8c7 f2f4 c6d4 
e2e4 e7e5 f1c4 g8f6 d2d3 c7c6 g1f3 f8e7 e1g1 d7d6 a2a3 e8g8 
g1f3 c7c5 c2c4 b8c6 d2d4 c5d4 f3d4 g8f6 b1c3 e7e6 c1g5 h7h6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 c2c4 g7g6 b1c3 f8g7 e2e4 d7d6 g1f3 e8g8 f1e2 e7e5 
e2e4 e7e6 d2d4 d7d5 b1c3 d5e4 c3e4 b8d7 f1d3 g8f6 e4f6 d7f6 
....

When the applications starts, i load it and stores it into a hashtable that takes as argument the hash key from the board and it returns the list of "book moves" that are in that position (hash key)

the "book moves" are stored by the sequence of the game, if after "e2e4 c7c5 " comes a "g1f3" for the hash key that results of "e2e4 c7c5" moves it will be added "g1f3" to the list of that position, and so on.. i think you get the idea how i am doing this. Is this the "correct" implementation, right?

If it works for you as you want, it is definitely a correct implementation!

However, I have seen some un-optimized issues:
1) you have to work with text, text files then convert them to binary. Look like in that process, you have to generate, make moves so many times. It is not good for an engine when playing.
2) all moves don't have any weight: you don't know which move is better than the other one.
3) store some extra information into your hash table, I guess it has to grow up on size with very limited benefit.

You may consider:
1) avoid converting text-binary just by storing directly what you need in binary format. In that case, you need a "fixed" hash Zobrist table or use a fixed seed when generating randoms for that. Now you can read/write directly hash numbers and don't need any code to convert/generate moves.

2) Each move should come with a number as a score/weight. You can generate them when working with games: a draw game will give each move score 1, otherwise, give 2 for each move if they are from the winning side.

3) Don't touch your hash table. Instead, store your opening book data in an independent structure and search when needed.

I think you have some good knowledge about opening book and it is quite closed to Polyglot book idea. Thus it is better if you study and support the Polyglot book instead of investing more time in something behind that.

[pedrojdm2021]

i have looked at other engines and i found that they store their "book.txt" into a file with a game per line. (a2a4 g8h6 ... )

I have such a book format, and it's hand curated. However, this is only the input for the opening book compiler I wrote to transform this into a position based format so that transpositions work, as huge .c file that gets compiled right into the engine executable. It's around 112kB of binary data. The lookup works via hashing the board position using a CRC-40 checksum, and the positions are sorted by hash in the opening book. I have an auxiliary array with 256 entry positions via right-shifting the hash so that I don't have to go through all of the book each time.

The advantage is that there's no need to configure anything - the disadvantage is that book updates require a recompilation. However, the user has always the option to switch off the engine internal book and let the GUI use its own book.

Hello, i did some research and i ended up with this:

I downloaded a big ammount of games from here: https://www.pgnmentor.com/files.html

and i generated a pretty big opening book that looks like this:

Code: Select all

e2e4 c7c5 g1f3 d7d6 d2d4 c5d4 f3d4 g8f6 b1c3 a7a6 c1g5 e7e6 
d2d4 g8f6 g1f3 e7e6 c2c4 b7b6 g2g3 f8b4 c1d2 b4d2 d1d2 c8a6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 c2c4 g7g6 b1c3 f8g7 e2e4 d7d6 g1f3 e8g8 f1e2 e7e5 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 g1f3 g7g6 c2c4 f8g7 b1c3 d7d6 e2e4 e8g8 f1e2 e7e5 
e2e4 e7e6 d2d4 d7d5 b1c3 f8b4 e4e5 g8e7 a2a3 b4c3 b2c3 c7c5 
d2d4 g8f6 c2c4 c7c5 d4d5 b7b5 c4b5 a7a6 b5a6 g7g6 b1c3 c8a6 
e2e4 c7c5 g1f3 d7d6 d2d4 c5d4 f3d4 g8f6 b1c3 a7a6 c1e3 e7e5 
g1f3 g8f6 c2c4 c7c5 b1c3 b8c6 g2g3 g7g6 f1g2 f8g7 e1g1 e8g8 
e2e4 c7c5 g1f3 b8c6 b1c3 e7e5 f1c4 f8e7 d2d3 g8f6 e1g1 d7d6 
e2e4 e7e6 d2d4 d7d5 b1c3 g8f6 e4e5 f6d7 f2f4 c7c5 g1f3 d8b6 
d2d4 d7d5 g1f3 g8f6 c2c4 c7c6 b1c3 a7a6 d1b3 e7e6 c1g5 d5c4 
d2d4 g8f6 c2c4 e7e6 g1f3 d7d5 b1c3 c7c6 c1g5 b8d7 e2e3 f8e7 
g1f3 g8f6 c2c4 c7c5 b1c3 b8c6 d2d4 c5d4 f3d4 e7e6 g2g3 d8b6 
e2e4 c7c5 g1f3 b8c6 d2d4 c5d4 f3d4 g8f6 b1c3 e7e5 d4b5 d7d6 
e2e4 c7c5 g1f3 e7e6 b1c3 b8c6 d2d4 c5d4 f3d4 d8c7 g2g3 a7a6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
e2e4 c7c5 g1f3 b8c6 f1b5 g8f6 b5c6 d7c6 d2d3 f6d7 c1f4 g7g6 
e2e4 c7c5 g1f3 e7e6 d2d4 c5d4 f3d4 b8c6 b1c3 d8c7 f2f4 c6d4 
e2e4 e7e5 f1c4 g8f6 d2d3 c7c6 g1f3 f8e7 e1g1 d7d6 a2a3 e8g8 
g1f3 c7c5 c2c4 b8c6 d2d4 c5d4 f3d4 g8f6 b1c3 e7e6 c1g5 h7h6 
e2e4 e7e5 g1f3 b8c6 f1b5 a7a6 b5a4 g8f6 e1g1 f8e7 f1e1 b7b5 
d2d4 g8f6 c2c4 g7g6 b1c3 f8g7 e2e4 d7d6 g1f3 e8g8 f1e2 e7e5 
e2e4 e7e6 d2d4 d7d5 b1c3 d5e4 c3e4 b8d7 f1d3 g8f6 e4f6 d7f6 
....

When the applications starts, i load it and stores it into a hashtable that takes as argument the hash key from the board and it returns the list of "book moves" that are in that position (hash key)

the "book moves" are stored by the sequence of the game, if after "e2e4 c7c5 " comes a "g1f3" for the hash key that results of "e2e4 c7c5" moves it will be added "g1f3" to the list of that position, and so on.. i think you get the idea how i am doing this. Is this the "correct" implementation, right?

If it works for you as you want, it is definitely a correct implementation!

However, I have seen some un-optimized issues:
1) you have to work with text, text files then convert them to binary. Look like in that process, you have to generate, make moves so many times. It is not good for an engine when playing.
2) all moves don't have any weight: you don't know which move is better than the other one.
3) store some extra information into your hash table, I guess it has to grow up on size with very limited benefit.

You may consider:
1) avoid converting text-binary just by storing directly what you need in binary format. In that case, you need a "fixed" hash Zobrist table or use a fixed seed when generating randoms for that. Now you can read/write directly hash numbers and don't need any code to convert/generate moves.

2) Each move should come with a number as a score/weight. You can generate them when working with games: a draw game will give each move score 1, otherwise, give 2 for each move if they are from the winning side.

3) Don't touch your hash table. Instead, store your opening book data in an independent structure and search when needed.

I think you have some good knowledge about opening book and it is quite closed to Polyglot book idea. Thus it is better if you study and support the Polyglot book instead of investing more time in something behind that.

1) you have to work with text, text files then convert them to binary. Look like in that process, you have to generate, make moves so many times. It is not good for an engine when playing.

I do that only on application startup so the information is ready to use in all games during the application runtime, i am only reading that text file 1 time at startup, no more than that.

2) all moves don't have any weight: you don't know which move is better than the other one.

I undestand, but, how can i know a score from a move from a opening book generated from a PGN file? by calling evaluate() ?

[phhnguyen]

I undestand, but, how can i know a score from a move from a opening book generated from a PGN file? by calling evaluate() ?

No, it’s not kind of positional score but game score. Say, a none-draw game gives the winner 2 point, a draw gives him 1 point and the loser gets nothing. Thus you don’t need to use any engine. Just retrieve the game result from the PGN then add 2 or 1 or 0 (according to win/draw/loss)to every moves of opening line which extracted from that game.

It’s a kind of voting: an opening line from a won game should be better than one from a lost game, thus it (and all moves of that line) should be voted up.

Note that win/loss is the view from player’s side - you should take care about the side too. One opening line from a win game is good for white side but bad for black side and so on. Building one book is OK but it’s better to build two independent opening books and which one will be used depending on what side your engine is playing.