Mysterious behaviour in book lines explained ?

[Mark Mason]

Hi,

There is a thread in the Rybka forum about the anomalies and strange behaviour of moves disappearing and red/green markings changing by themselves in ctg books. I have an idea as to why this may happen which suggests it is not a bug but a feature and thought I would post it here as well in case anyone can throw any light on it. I will try to explain. The book is made up of a complex tree pattern with branches going off in all directions containing lines and sub-lines. Within this complex pattern, at various points it will be the case that different lines in the differerent branches will actually create the same position eg. the same position can occur after 10 moves in one line and after 15 moves in a different line that started with a different move sequence.

Now here is the point - if you mark a move red in a particular line it will not only prevent that move being played in that line, it will also have the effect of "closing off" that position from any other line in which a different sequence of moves would have led to that same position ie. the red marking "closes off" several branches of the tree, even though you only meant to influence the move choice in one particular line. This means that moves in other lines that would lead to that same "closed off" position will now be turned red automatically even though you have not changed the move marking yourself !!

I was told this by a Russian friend on the Playchess server and did not believe him until he demonstrated it with a number of examples and to my surprise sure enough after I marked a move red in one line, other moves in other lines had turned red by themselves, which I would never have known about until wondering why the book did not choose a move that it used to choose. His English was not good so he could not explain the theory of this in mathematical terms, but it certainly happens. Ever since this I no longer mark moves red but instead mark them "??" which has the same effect of stopping them being selected (so long as you have tournament moves checked in book options). I do also wonder what other "side effects" there are from manually annotating moves in a ctg tree,

I hope this throws some light on the topic and if anyone can explain it more clearly than I have attempted I would be grateful !

Mark

[Edmund]

I assume the ctg opening book format works like transposition tables. There is one entry per position indexed with a hash-key. Probably the hash-key would be longer than in normal tt due to the high risk of collisions in such a huge tt or it would even be unique. So if you change the entry - the information about a certain position. The book will also use that knowledge for any other transpositions that lead to that position.

Regards Edmund

PS:

The book is made up of a complex tree pattern with branches going off in all directions containing lines and sub-lines.

I couldn't imagine that the opening books are built up like that. Because that would mean that you would always have to play a game from the beginning, if you wanted to get information about a position. Otherwise the position wouldn't be found. But thats not the case. With ctg I can just go to any position and look it up in the book. That means there has to be some sort of direct lookup.

[Mark Mason]

If you go to this thread and down almost to the bottom to the post by "bnc" on 5th June 8.43 there is far more explanation of what I was trying to describe:

http://rybkaforum.net/cgi-bin/rybkaforu ... ;pid=61370

the key thing is that annotations like ?? or ?! are specific to the MOVE in question but red/green markings are specific to the POSITION and are therefore subject to being affected by transpositions. So if you don't want a particular MOVE to be chosen use ?? but if you don't want a particular POSITION to be reached (via whatever move sequence) use red/green markings.

Mark

[bob]

If you go to this thread and down almost to the bottom to the post by "bnc" on 5th June 8.43 there is far more explanation of what I was trying to describe:

http://rybkaforum.net/cgi-bin/rybkaforu ... ;pid=61370

the key thing is that annotations like ?? or ?! are specific to the MOVE in question but red/green markings are specific to the POSITION and are therefore subject to being affected by transpositions. So if you don't want a particular MOVE to be chosen use ?? but if you don't want a particular POSITION to be reached (via whatever move sequence) use red/green markings.

Mark

I do not believe that is the correct interpretation. We do not store "moves" in the book at all, just positions. To discover the moves from a position, you just generate all legal moves, make them one at a time and see if the resulting _position_ is in the database. This means that bad "moves" show up as bad "positions" in the data base. We don't store moves in the opening book database at all as that would make the size of the book incredibly large...

[Rubinus]

CTG (stinking file size):
a) color (red/green etc) - no for moves, but target position
Example: 1.e4 e6 (c6) 2.d4 d5 and 1.d4 d5 2.e4 de4!, but must green also 2.-e6 and c6 -> else after 1.e4 e6(c6) 2.d4 is engine whitout book.
b) delete move - delete 1 halfmove both sides -> funny disappearance moves ... (count stays)
c) probability -> color, count, selfknowledge (+-125), mark (!, ? etc.), no manual directly such as e.g. *.abk.

[pijl]

If you go to this thread and down almost to the bottom to the post by "bnc" on 5th June 8.43 there is far more explanation of what I was trying to describe:

http://rybkaforum.net/cgi-bin/rybkaforu ... ;pid=61370

the key thing is that annotations like ?? or ?! are specific to the MOVE in question but red/green markings are specific to the POSITION and are therefore subject to being affected by transpositions. So if you don't want a particular MOVE to be chosen use ?? but if you don't want a particular POSITION to be reached (via whatever move sequence) use red/green markings.

Mark

I do not believe that is the correct interpretation. We do not store "moves" in the book at all, just positions. To discover the moves from a position, you just generate all legal moves, make them one at a time and see if the resulting _position_ is in the database. This means that bad "moves" show up as bad "positions" in the data base. We don't store moves in the opening book database at all as that would make the size of the book incredibly large...

Still, this is what I believe that many programs do.
I've used the approach with only storing target positions with the Baron. As I did not have statistics or scores in that book either, a book entry was just the 8 bytes of the position's zobrist key. Small enough to keep in memory in a separate hashtable. Any move leading to a position in this hashtable would be played directly.

But this had a few drawbacks. Engaging into unwanted transpositions was hard to prevent without blocking the position (which could be the best option in a different line). So in order to have a bit more control over which moves can be played from a position, I created a new book format with the position+move principle. You're right that these book files are significantly larger and because of this also require a kind of index structure on disk as the book is too large to keep in memory. But with the current sizes of harddisks that is hardly a problem.
Judging from the sizes of the .ctg and shredder book, they are probably using position+move.

Richard.

[bob]

If you go to this thread and down almost to the bottom to the post by "bnc" on 5th June 8.43 there is far more explanation of what I was trying to describe:

http://rybkaforum.net/cgi-bin/rybkaforu ... ;pid=61370

the key thing is that annotations like ?? or ?! are specific to the MOVE in question but red/green markings are specific to the POSITION and are therefore subject to being affected by transpositions. So if you don't want a particular MOVE to be chosen use ?? but if you don't want a particular POSITION to be reached (via whatever move sequence) use red/green markings.

Mark

I do not believe that is the correct interpretation. We do not store "moves" in the book at all, just positions. To discover the moves from a position, you just generate all legal moves, make them one at a time and see if the resulting _position_ is in the database. This means that bad "moves" show up as bad "positions" in the data base. We don't store moves in the opening book database at all as that would make the size of the book incredibly large...

Still, this is what I believe that many programs do.
I've used the approach with only storing target positions with the Baron. As I did not have statistics or scores in that book either, a book entry was just the 8 bytes of the position's zobrist key. Small enough to keep in memory in a separate hashtable. Any move leading to a position in this hashtable would be played directly.

But this had a few drawbacks. Engaging into unwanted transpositions was hard to prevent without blocking the position (which could be the best option in a different line). So in order to have a bit more control over which moves can be played from a position, I created a new book format with the position+move principle. You're right that these book files are significantly larger and because of this also require a kind of index structure on disk as the book is too large to keep in memory. But with the current sizes of harddisks that is hardly a problem.
Judging from the sizes of the .ctg and shredder book, they are probably using position+move.

Richard.

I can simply flag a move as "do not play" which flags the resulting "position" as "do not reach". Then no matter how one transposes the moves, Crafty will not play any move that leads to the position that I told it to avoid, which seems totally reasonable. Each position also has some statistical data (how many times played, learn information, etc) that can be used to further refine the decision "to reach this position or to not reach this position"...

But I'd bet nobody stores moves, as it is beyond redundant when you already have the Zobrist keys...

[pijl]

But I'd bet nobody stores moves, as it is beyond redundant when you already have the Zobrist keys...

That's one lost bet
I do. And I have a strong suspicion that SMK does that in Shredder, and Matthias Feist in the .ctg format.

As far as I'm concerned, it is not about blocking positions. It is about blocking positions from certain move orders.

Example:
Suppose Crafty is black and you decide to play a Petrov in a tournament against a specific opponent. Will it go for a Ruy in the following line:
1.e4 e5 2.Nf3 Nf6 3.Bb5
with 3..Nc6?
Of course, there's nothing wrong with the Ruy. But perhaps you should not be happy about it as you:
1. Decided to avoid the Ruy with the Petrov
2. May have better moves to reach an advantage (like c6 followed by d5, or by a direct Nxe4), throwing the both of you out of book.

This is just one example, but the initial poster of this thread obviously had some lines where he wanted to block a move instead of a position.

Richard.

[Tony]

But I'd bet nobody stores moves, as it is beyond redundant when you already have the Zobrist keys...

That's one lost bet
I do. And I have a strong suspicion that SMK does that in Shredder, and Matthias Feist in the .ctg format.

As far as I'm concerned, it is not about blocking positions. It is about blocking positions from certain move orders.

Example:
Suppose Crafty is black and you decide to play a Petrov in a tournament against a specific opponent. Will it go for a Ruy in the following line:
1.e4 e5 2.Nf3 Nf6 3.Bb5
with 3..Nc6?
Of course, there's nothing wrong with the Ruy. But perhaps you should not be happy about it as you:
1. Decided to avoid the Ruy with the Petrov
2. May have better moves to reach an advantage (like c6 followed by d5, or by a direct Nxe4), throwing the both of you out of book.

This is just one example, but the initial poster of this thread obviously had some lines where he wanted to block a move instead of a position.

Richard.

Robert does this to, but implicitly.

In Crafty, part of the book zobrist key depends on the parent. So blocking a position means blocking it from (through) that particular parent.

Tony

[pijl]

Robert does this to, but implicitly.

In Crafty, part of the book zobrist key depends on the parent. So blocking a position means blocking it from (through) that particular parent.

Tony

Ah, I looked in the Crafty code just now (20.14 but I doubt it changed much in this area lately) and saw the construction of the 'temp_hash_key' for each move from the root position in book.c. So basically Crafty uses rootposition (48bits)+position-after-bookmove(16 bits), encoded in a single zobrist key. Indeed, that seems equivalent to my position (64 bits)+move(16 bits) to me. Only difference is that I use a longer zobrist key for the position.
Richard.