Book learning

[bob]

Well, the example is very extreme, of course. But it could very well hapen that a variation that was believed to be good for the opponent was played a lot, and that the common defense against it was move A, which thus got many plays, but rather poor score. Then a novelty B was found in this position, which basically refuted the previous move. It was played a few times, much less than A, but with a very good score, which convinced people that it indeed was a refutation. So they stopped playing the previous move, and B never got the chance to get anywhere near the number of plays that A has. This makes scenarious where A has 40% out of 1000 plays while B has 60% out of 100 plays not unrealistic. Polyglot would continue to prefer the poor move by 400:60. And even worse, it would not discourage the preceeding move from being played, as all the 600 points scored against it because it was met by the inferior reply A continue to count, while they are in fact no longer relevant, as good players will meet it with move B for sure.

Now I know of course that serious book builders would select the games from which they build the book by date, pay attention to the ratings, etc., exactly to cleanse the input data from such misleading cues. But this is a case that could very well be handled automatically, by proper application of minimax. If the 40% vs 60% scores for move A and B would lead to fafor B over A in play by 90% vs 10%, the average score of this node should be set to 58% (90% x 60% + 10% x 40%), so 42% for the opponent's preceding move, based on 1/(0.81/100 + 0.01/1000) = 122 'virtual' games, rather than at 640 out of 1100 games (58%).

Why not mini-max the book with alpha-beta upon update? Doesn't that remove the problems of refutations being discovered converging slowly?

I think mini-max of the book is a very good way to customize a book for a given program. In general you want your program to come out of book with a position that it thinks is good. A significant percentage of Komodo's losses in tournament games happens when we come out of book with what Komodo considers a losing (or close to losing) position.

However I believe that for this to work the program being tuned must search every book position to ensure there is a valid choice (at least from the programs point of view.) For example:

In position P the book gives Ne5 and d4, but both moves are inferior to c3 which is not in the book. In this case, any mini-max that involves position P will be in error. It might be a good line if c3 is allowed and thus the computer will avoid it when playing white, or as black think it's a great position to force white into.

So my idea for mini-maxing the book is to evaluate every position and insert the computers choice, if different, into the book also. In the cases where the computer has it's own TN you might also consider verifying the new choice with additional thinking time to avoid gratuitously adding moves to the book (that might also get recursively expanded upon.)

I have never seen a book that didn't have some kind of omission such as this. Cilkchess lost a game to "King" one year because the book did not consider an obvious choice. In general I have not payed a lot of attention to the book in our programs and it has cost us dearly. There are a few programs that do not test very well or rank very high on the rating lists but get much better results in tournaments because of exceptionally good book preparation. Once you get a terrible position it's difficult to recover even against a program 2 or 3 hundred ELO weaker.

There are ways to handle some of that, but I don't think minimaxing is the solution. We did that in Cray Blitz. And in early Crafty versions. The problem is you will _always_ accept gambits since that move wins material and the rest do not.

You can do this minimaxing at least two different ways. The simplest is to simply follow each book line to the end, perhaps do a search there, and then minimax the scores back to the root. Only catch is that you have to change things for black, since when you play black you now want the lowest score, not the highest, if you use the same book for both sides. The other is to search down the book lines, but do a real search at each node as well to see if there is a better move than the book alternative(s).

We finally ended up with a manual system in Cray Blitz. We did the search, but only printed things out when we "thought" we had a better move than the book move, or when the search said that a book move flagged as good really appeared to be bad. That was a pain...

[Don]

Well, the example is very extreme, of course. But it could very well hapen that a variation that was believed to be good for the opponent was played a lot, and that the common defense against it was move A, which thus got many plays, but rather poor score. Then a novelty B was found in this position, which basically refuted the previous move. It was played a few times, much less than A, but with a very good score, which convinced people that it indeed was a refutation. So they stopped playing the previous move, and B never got the chance to get anywhere near the number of plays that A has. This makes scenarious where A has 40% out of 1000 plays while B has 60% out of 100 plays not unrealistic. Polyglot would continue to prefer the poor move by 400:60. And even worse, it would not discourage the preceeding move from being played, as all the 600 points scored against it because it was met by the inferior reply A continue to count, while they are in fact no longer relevant, as good players will meet it with move B for sure.

Now I know of course that serious book builders would select the games from which they build the book by date, pay attention to the ratings, etc., exactly to cleanse the input data from such misleading cues. But this is a case that could very well be handled automatically, by proper application of minimax. If the 40% vs 60% scores for move A and B would lead to fafor B over A in play by 90% vs 10%, the average score of this node should be set to 58% (90% x 60% + 10% x 40%), so 42% for the opponent's preceding move, based on 1/(0.81/100 + 0.01/1000) = 122 'virtual' games, rather than at 640 out of 1100 games (58%).

Why not mini-max the book with alpha-beta upon update? Doesn't that remove the problems of refutations being discovered converging slowly?

I think mini-max of the book is a very good way to customize a book for a given program. In general you want your program to come out of book with a position that it thinks is good. A significant percentage of Komodo's losses in tournament games happens when we come out of book with what Komodo considers a losing (or close to losing) position.

However I believe that for this to work the program being tuned must search every book position to ensure there is a valid choice (at least from the programs point of view.) For example:

In position P the book gives Ne5 and d4, but both moves are inferior to c3 which is not in the book. In this case, any mini-max that involves position P will be in error. It might be a good line if c3 is allowed and thus the computer will avoid it when playing white, or as black think it's a great position to force white into.

So my idea for mini-maxing the book is to evaluate every position and insert the computers choice, if different, into the book also. In the cases where the computer has it's own TN you might also consider verifying the new choice with additional thinking time to avoid gratuitously adding moves to the book (that might also get recursively expanded upon.)

I have never seen a book that didn't have some kind of omission such as this. Cilkchess lost a game to "King" one year because the book did not consider an obvious choice. In general I have not payed a lot of attention to the book in our programs and it has cost us dearly. There are a few programs that do not test very well or rank very high on the rating lists but get much better results in tournaments because of exceptionally good book preparation. Once you get a terrible position it's difficult to recover even against a program 2 or 3 hundred ELO weaker.

There are ways to handle some of that, but I don't think minimaxing is the solution. We did that in Cray Blitz. And in early Crafty versions. The problem is you will _always_ accept gambits since that move wins material and the rest do not.

You can do this minimaxing at least two different ways. The simplest is to simply follow each book line to the end, perhaps do a search there, and then minimax the scores back to the root. Only catch is that you have to change things for black, since when you play black you now want the lowest score, not the highest, if you use the same book for both sides. The other is to search down the book lines, but do a real search at each node as well to see if there is a better move than the book alternative(s).

We finally ended up with a manual system in Cray Blitz. We did the search, but only printed things out when we "thought" we had a better move than the book move, or when the search said that a book move flagged as good really appeared to be bad. That was a pain...

Yes, there is not perfect solution.

I'm not so sure the gambit stuff is a problem - it was a few years ago but programs have come a long way. Just for fun I tested the smith morra gambit with Komodo immediate after the pawn is accepted by black. I have to say that I agree completely with the assessment:

after 1.e4 c5 2. d4 cxd4 3. c3 dxc3

At 5 ply and beyond the score is within about 1/5 pawn of even. On earlier depths Komodo even thinks white has an advantage, but at 13 ply and beyond black is given a small advantage (which in my opinion is correct.) Most gambits are at least slightly unsound against a strong player with a cool head.

At 19 ply Komodo thinks black has an 18/100 pawn advantage.

Houdini at similar depths has the score very close to zero. We could argue about which assessment is more accurate but the point is that neither program is very concerned about being down a pawn.

With mini-max, we are not really going to evaluate THAT exact position either, we are going to see a tree of possibilities and then analyze THEM, which is likely to get us much closer to the truth about whether to offer the pawn or not.

I think your real point is that programs do not always evaluation positions evenly, they all over-value some position and under-value others. I agree with that.

However I believe the real point of minimax is to get positions that YOUR program likes. It's objective goodness is usually a matter of debate anyway but my working theory right now is that if you can come out of book with positions that your program likes, it's hard to do better than that because it means the pieces are more in harmony with your programs way of thinking.

Don't you just hate it when you come out of book and the program moves the pieces back to squares it prefers?

[bob]

Well, the example is very extreme, of course. But it could very well hapen that a variation that was believed to be good for the opponent was played a lot, and that the common defense against it was move A, which thus got many plays, but rather poor score. Then a novelty B was found in this position, which basically refuted the previous move. It was played a few times, much less than A, but with a very good score, which convinced people that it indeed was a refutation. So they stopped playing the previous move, and B never got the chance to get anywhere near the number of plays that A has. This makes scenarious where A has 40% out of 1000 plays while B has 60% out of 100 plays not unrealistic. Polyglot would continue to prefer the poor move by 400:60. And even worse, it would not discourage the preceeding move from being played, as all the 600 points scored against it because it was met by the inferior reply A continue to count, while they are in fact no longer relevant, as good players will meet it with move B for sure.

Now I know of course that serious book builders would select the games from which they build the book by date, pay attention to the ratings, etc., exactly to cleanse the input data from such misleading cues. But this is a case that could very well be handled automatically, by proper application of minimax. If the 40% vs 60% scores for move A and B would lead to fafor B over A in play by 90% vs 10%, the average score of this node should be set to 58% (90% x 60% + 10% x 40%), so 42% for the opponent's preceding move, based on 1/(0.81/100 + 0.01/1000) = 122 'virtual' games, rather than at 640 out of 1100 games (58%).

Why not mini-max the book with alpha-beta upon update? Doesn't that remove the problems of refutations being discovered converging slowly?

I think mini-max of the book is a very good way to customize a book for a given program. In general you want your program to come out of book with a position that it thinks is good. A significant percentage of Komodo's losses in tournament games happens when we come out of book with what Komodo considers a losing (or close to losing) position.

However I believe that for this to work the program being tuned must search every book position to ensure there is a valid choice (at least from the programs point of view.) For example:

In position P the book gives Ne5 and d4, but both moves are inferior to c3 which is not in the book. In this case, any mini-max that involves position P will be in error. It might be a good line if c3 is allowed and thus the computer will avoid it when playing white, or as black think it's a great position to force white into.

So my idea for mini-maxing the book is to evaluate every position and insert the computers choice, if different, into the book also. In the cases where the computer has it's own TN you might also consider verifying the new choice with additional thinking time to avoid gratuitously adding moves to the book (that might also get recursively expanded upon.)

I have never seen a book that didn't have some kind of omission such as this. Cilkchess lost a game to "King" one year because the book did not consider an obvious choice. In general I have not payed a lot of attention to the book in our programs and it has cost us dearly. There are a few programs that do not test very well or rank very high on the rating lists but get much better results in tournaments because of exceptionally good book preparation. Once you get a terrible position it's difficult to recover even against a program 2 or 3 hundred ELO weaker.

There are ways to handle some of that, but I don't think minimaxing is the solution. We did that in Cray Blitz. And in early Crafty versions. The problem is you will _always_ accept gambits since that move wins material and the rest do not.

You can do this minimaxing at least two different ways. The simplest is to simply follow each book line to the end, perhaps do a search there, and then minimax the scores back to the root. Only catch is that you have to change things for black, since when you play black you now want the lowest score, not the highest, if you use the same book for both sides. The other is to search down the book lines, but do a real search at each node as well to see if there is a better move than the book alternative(s).

We finally ended up with a manual system in Cray Blitz. We did the search, but only printed things out when we "thought" we had a better move than the book move, or when the search said that a book move flagged as good really appeared to be bad. That was a pain...

Yes, there is not perfect solution.

I'm not so sure the gambit stuff is a problem - it was a few years ago but programs have come a long way. Just for fun I tested the smith morra gambit with Komodo immediate after the pawn is accepted by black. I have to say that I agree completely with the assessment:

after 1.e4 c5 2. d4 cxd4 3. c3 dxc3

At 5 ply and beyond the score is within about 1/5 pawn of even. On earlier depths Komodo even thinks white has an advantage, but at 13 ply and beyond black is given a small advantage (which in my opinion is correct.) Most gambits are at least slightly unsound against a strong player with a cool head.

At 19 ply Komodo thinks black has an 18/100 pawn advantage.

Houdini at similar depths has the score very close to zero. We could argue about which assessment is more accurate but the point is that neither program is very concerned about being down a pawn.

With mini-max, we are not really going to evaluate THAT exact position either, we are going to see a tree of possibilities and then analyze THEM, which is likely to get us much closer to the truth about whether to offer the pawn or not.

I think your real point is that programs do not always evaluation positions evenly, they all over-value some position and under-value others. I agree with that.

However I believe the real point of minimax is to get positions that YOUR program likes. It's objective goodness is usually a matter of debate anyway but my working theory right now is that if you can come out of book with positions that your program likes, it's hard to do better than that because it means the pieces are more in harmony with your programs way of thinking.

Don't you just hate it when you come out of book and the program moves the pieces back to squares it prefers?

Yes. That's why we tried the minimaxing idea in the first place, in addition to playing a book move that is an outright blunder because of poor human analysis. We found several lines in MCO10/11 where Evans would write in the footnote "and white is clearly winning." A very short search found that white got mated, or lost significant material. There, we gained.

However, there is another issue that I think is most important. The goal is _not_ to come out of book in a better position. that is almost always impossible unless your opponent screws up. You also don't want to come out in a dead draw unless you are playing a stronger opponent. We try to find positions where we have some things to play for that Crafty understands, knowing that we have to give the opponent some advantages in other things. We do pretty well in king safety, as an example, so if our king is somewhat weakened, we are willing to accept that to gain an advantage elsewhere that might be decisive later. It's not an easy task. And I don't think a program has a chance in hell of optimizing its own book in that manner... at least not today.

[Dann Corbit]

Well, the example is very extreme, of course. But it could very well hapen that a variation that was believed to be good for the opponent was played a lot, and that the common defense against it was move A, which thus got many plays, but rather poor score. Then a novelty B was found in this position, which basically refuted the previous move. It was played a few times, much less than A, but with a very good score, which convinced people that it indeed was a refutation. So they stopped playing the previous move, and B never got the chance to get anywhere near the number of plays that A has. This makes scenarious where A has 40% out of 1000 plays while B has 60% out of 100 plays not unrealistic. Polyglot would continue to prefer the poor move by 400:60. And even worse, it would not discourage the preceeding move from being played, as all the 600 points scored against it because it was met by the inferior reply A continue to count, while they are in fact no longer relevant, as good players will meet it with move B for sure.

Now I know of course that serious book builders would select the games from which they build the book by date, pay attention to the ratings, etc., exactly to cleanse the input data from such misleading cues. But this is a case that could very well be handled automatically, by proper application of minimax. If the 40% vs 60% scores for move A and B would lead to fafor B over A in play by 90% vs 10%, the average score of this node should be set to 58% (90% x 60% + 10% x 40%), so 42% for the opponent's preceding move, based on 1/(0.81/100 + 0.01/1000) = 122 'virtual' games, rather than at 640 out of 1100 games (58%).

Why not mini-max the book with alpha-beta upon update? Doesn't that remove the problems of refutations being discovered converging slowly?

I think mini-max of the book is a very good way to customize a book for a given program. In general you want your program to come out of book with a position that it thinks is good. A significant percentage of Komodo's losses in tournament games happens when we come out of book with what Komodo considers a losing (or close to losing) position.

However I believe that for this to work the program being tuned must search every book position to ensure there is a valid choice (at least from the programs point of view.) For example:

In position P the book gives Ne5 and d4, but both moves are inferior to c3 which is not in the book. In this case, any mini-max that involves position P will be in error. It might be a good line if c3 is allowed and thus the computer will avoid it when playing white, or as black think it's a great position to force white into.

So my idea for mini-maxing the book is to evaluate every position and insert the computers choice, if different, into the book also. In the cases where the computer has it's own TN you might also consider verifying the new choice with additional thinking time to avoid gratuitously adding moves to the book (that might also get recursively expanded upon.)

I have never seen a book that didn't have some kind of omission such as this. Cilkchess lost a game to "King" one year because the book did not consider an obvious choice. In general I have not payed a lot of attention to the book in our programs and it has cost us dearly. There are a few programs that do not test very well or rank very high on the rating lists but get much better results in tournaments because of exceptionally good book preparation. Once you get a terrible position it's difficult to recover even against a program 2 or 3 hundred ELO weaker.

My idea is similar to that. The chess book will contain a list of commonly played positions that have been deeply analyzed. These positions should be loaded into the hash table as pv nodes before every game. As the engine plays, it updates the hash positions (especially at long time control) and they get resaved after every game. Every so often, we should take the root position and let the engine ponder this position over an entire weekend.

PV nodes are special nodes and very rare. No sense starting from scratch every single time. Why not let your engine get a little bit smarter every time it plays?

We also keep important statistics about winning percentage, frequency of play, etc. for every move and these statistics grow over time. Eventually, the book would become infallible.

OK, that will take a few trillion years, but in the mean time, it will produce a better and better book.

[Dann Corbit]

Well, the example is very extreme, of course. But it could very well hapen that a variation that was believed to be good for the opponent was played a lot, and that the common defense against it was move A, which thus got many plays, but rather poor score. Then a novelty B was found in this position, which basically refuted the previous move. It was played a few times, much less than A, but with a very good score, which convinced people that it indeed was a refutation. So they stopped playing the previous move, and B never got the chance to get anywhere near the number of plays that A has. This makes scenarious where A has 40% out of 1000 plays while B has 60% out of 100 plays not unrealistic. Polyglot would continue to prefer the poor move by 400:60. And even worse, it would not discourage the preceeding move from being played, as all the 600 points scored against it because it was met by the inferior reply A continue to count, while they are in fact no longer relevant, as good players will meet it with move B for sure.

Now I know of course that serious book builders would select the games from which they build the book by date, pay attention to the ratings, etc., exactly to cleanse the input data from such misleading cues. But this is a case that could very well be handled automatically, by proper application of minimax. If the 40% vs 60% scores for move A and B would lead to fafor B over A in play by 90% vs 10%, the average score of this node should be set to 58% (90% x 60% + 10% x 40%), so 42% for the opponent's preceding move, based on 1/(0.81/100 + 0.01/1000) = 122 'virtual' games, rather than at 640 out of 1100 games (58%).

Why not mini-max the book with alpha-beta upon update? Doesn't that remove the problems of refutations being discovered converging slowly?

I think mini-max of the book is a very good way to customize a book for a given program. In general you want your program to come out of book with a position that it thinks is good. A significant percentage of Komodo's losses in tournament games happens when we come out of book with what Komodo considers a losing (or close to losing) position.

However I believe that for this to work the program being tuned must search every book position to ensure there is a valid choice (at least from the programs point of view.) For example:

In position P the book gives Ne5 and d4, but both moves are inferior to c3 which is not in the book. In this case, any mini-max that involves position P will be in error. It might be a good line if c3 is allowed and thus the computer will avoid it when playing white, or as black think it's a great position to force white into.

So my idea for mini-maxing the book is to evaluate every position and insert the computers choice, if different, into the book also. In the cases where the computer has it's own TN you might also consider verifying the new choice with additional thinking time to avoid gratuitously adding moves to the book (that might also get recursively expanded upon.)

I have never seen a book that didn't have some kind of omission such as this. Cilkchess lost a game to "King" one year because the book did not consider an obvious choice. In general I have not payed a lot of attention to the book in our programs and it has cost us dearly. There are a few programs that do not test very well or rank very high on the rating lists but get much better results in tournaments because of exceptionally good book preparation. Once you get a terrible position it's difficult to recover even against a program 2 or 3 hundred ELO weaker.

There are ways to handle some of that, but I don't think minimaxing is the solution. We did that in Cray Blitz. And in early Crafty versions. The problem is you will _always_ accept gambits since that move wins material and the rest do not.

You can do this minimaxing at least two different ways. The simplest is to simply follow each book line to the end, perhaps do a search there, and then minimax the scores back to the root. Only catch is that you have to change things for black, since when you play black you now want the lowest score, not the highest, if you use the same book for both sides. The other is to search down the book lines, but do a real search at each node as well to see if there is a better move than the book alternative(s).

We finally ended up with a manual system in Cray Blitz. We did the search, but only printed things out when we "thought" we had a better move than the book move, or when the search said that a book move flagged as good really appeared to be bad. That was a pain...

Yes, there is not perfect solution.

I'm not so sure the gambit stuff is a problem - it was a few years ago but programs have come a long way. Just for fun I tested the smith morra gambit with Komodo immediate after the pawn is accepted by black. I have to say that I agree completely with the assessment:

after 1.e4 c5 2. d4 cxd4 3. c3 dxc3

At 5 ply and beyond the score is within about 1/5 pawn of even. On earlier depths Komodo even thinks white has an advantage, but at 13 ply and beyond black is given a small advantage (which in my opinion is correct.) Most gambits are at least slightly unsound against a strong player with a cool head.

At 19 ply Komodo thinks black has an 18/100 pawn advantage.

Houdini at similar depths has the score very close to zero. We could argue about which assessment is more accurate but the point is that neither program is very concerned about being down a pawn.

With mini-max, we are not really going to evaluate THAT exact position either, we are going to see a tree of possibilities and then analyze THEM, which is likely to get us much closer to the truth about whether to offer the pawn or not.

I think your real point is that programs do not always evaluation positions evenly, they all over-value some position and under-value others. I agree with that.

However I believe the real point of minimax is to get positions that YOUR program likes. It's objective goodness is usually a matter of debate anyway but my working theory right now is that if you can come out of book with positions that your program likes, it's hard to do better than that because it means the pieces are more in harmony with your programs way of thinking.

Don't you just hate it when you come out of book and the program moves the pieces back to squares it prefers?

When the gambit positions are analyzed at 35 ply or so, the engines properly understand them. So they cease to be a problem.

15 years ago, Evans gambit positions would withstand 48 hours of analysis and the engines would still cough up stupidity. Today, the engines choose the right moves after an hour.

[Don]

My idea is similar to that. The chess book will contain a list of commonly played positions that have been deeply analyzed. These positions should be loaded into the hash table as pv nodes before every game. As the engine plays, it updates the hash positions (especially at long time control) and they get resaved after every game. Every so often, we should take the root position and let the engine ponder this position over an entire weekend.

Those positions are quickly overwritten. I have not kept up with various learning algorithm features that some programs use, but I have to assume this type of thing has been tried or is being used. Is that the case?

The trick is to save the positions before they age out and to be able to bring them back in before every move. A hash table entry does not tend to survive very many moves.

Also it would seem that some positions would be far more critical than others. A simple minded approach might be to identify positions that have large scoring variations with depth - these would be more critical.

PV nodes are special nodes and very rare. No sense starting from scratch every single time. Why not let your engine get a little bit smarter every time it plays?

We also keep important statistics about winning percentage, frequency of play, etc. for every move and these statistics grow over time. Eventually, the book would become infallible.

OK, that will take a few trillion years, but in the mean time, it will produce a better and better book.

[Dann Corbit]

My idea is similar to that. The chess book will contain a list of commonly played positions that have been deeply analyzed. These positions should be loaded into the hash table as pv nodes before every game. As the engine plays, it updates the hash positions (especially at long time control) and they get resaved after every game. Every so often, we should take the root position and let the engine ponder this position over an entire weekend.

Those positions are quickly overwritten. I have not kept up with various learning algorithm features that some programs use, but I have to assume this type of thing has been tried or is being used. Is that the case?

The trick is to save the positions before they age out and to be able to bring them back in before every move. A hash table entry does not tend to survive very many moves.

Also it would seem that some positions would be far more critical than others. A simple minded approach might be to identify positions that have large scoring variations with depth - these would be more critical.

PV nodes are special nodes and very rare. No sense starting from scratch every single time. Why not let your engine get a little bit smarter every time it plays?

We also keep important statistics about winning percentage, frequency of play, etc. for every move and these statistics grow over time. Eventually, the book would become infallible.

OK, that will take a few trillion years, but in the mean time, it will produce a better and better book.

If pv nodes in the regular hash table are overwritten, then I suggest a separate pv node hash table that is permanent.

There are only a few million important pv positions in total (for book usage anyway).

[Don]

My idea is similar to that. The chess book will contain a list of commonly played positions that have been deeply analyzed. These positions should be loaded into the hash table as pv nodes before every game. As the engine plays, it updates the hash positions (especially at long time control) and they get resaved after every game. Every so often, we should take the root position and let the engine ponder this position over an entire weekend.

Those positions are quickly overwritten. I have not kept up with various learning algorithm features that some programs use, but I have to assume this type of thing has been tried or is being used. Is that the case?

The trick is to save the positions before they age out and to be able to bring them back in before every move. A hash table entry does not tend to survive very many moves.

Also it would seem that some positions would be far more critical than others. A simple minded approach might be to identify positions that have large scoring variations with depth - these would be more critical.

PV nodes are special nodes and very rare. No sense starting from scratch every single time. Why not let your engine get a little bit smarter every time it plays?

We also keep important statistics about winning percentage, frequency of play, etc. for every move and these statistics grow over time. Eventually, the book would become infallible.

OK, that will take a few trillion years, but in the mean time, it will produce a better and better book.

If pv nodes in the regular hash table are overwritten, then I suggest a separate pv node hash table that is permanent.

There are only a few million important pv positions in total (for book usage anyway).

The problem is that the chess program is capable of generating billions of PV entries over time. You could take a large opening book and seed them in the table as permanent entries, but at some point a decision has to be made about which generated entries to keep and which to discard. Perhaps this will work if you are really stingy about which entries are added to the permanent table. It could be any position chosen at the root for instance that is not already in the book.

So a possible scheme is to build a permanent hash table with several million position from modern opening theory and then be very stingy about adding positions.

[Dann Corbit]

My idea is similar to that. The chess book will contain a list of commonly played positions that have been deeply analyzed. These positions should be loaded into the hash table as pv nodes before every game. As the engine plays, it updates the hash positions (especially at long time control) and they get resaved after every game. Every so often, we should take the root position and let the engine ponder this position over an entire weekend.

Those positions are quickly overwritten. I have not kept up with various learning algorithm features that some programs use, but I have to assume this type of thing has been tried or is being used. Is that the case?

The trick is to save the positions before they age out and to be able to bring them back in before every move. A hash table entry does not tend to survive very many moves.

Also it would seem that some positions would be far more critical than others. A simple minded approach might be to identify positions that have large scoring variations with depth - these would be more critical.

PV nodes are special nodes and very rare. No sense starting from scratch every single time. Why not let your engine get a little bit smarter every time it plays?

We also keep important statistics about winning percentage, frequency of play, etc. for every move and these statistics grow over time. Eventually, the book would become infallible.

OK, that will take a few trillion years, but in the mean time, it will produce a better and better book.

If pv nodes in the regular hash table are overwritten, then I suggest a separate pv node hash table that is permanent.

There are only a few million important pv positions in total (for book usage anyway).

The problem is that the chess program is capable of generating billions of PV entries over time. You could take a large opening book and seed them in the table as permanent entries, but at some point a decision has to be made about which generated entries to keep and which to discard. Perhaps this will work if you are really stingy about which entries are added to the permanent table. It could be any position chosen at the root for instance that is not already in the book.

So a possible scheme is to build a permanent hash table with several million position from modern opening theory and then be very stingy about adding positions.

If the key to the permanent hash table is a 165 bit exact representation of the Epd string (or even the Epd string itself if we want to be lazy), then entries can never be overwritten.

How many PV nodes are there in a hash table with a billion nodes? I guess it is far less than one million (IOW, what percentage of nodes are pv nodes?).

If the percentage of pv nodes is higher than I imagine so that the permanent hash becomes too large, then we can go with the pv nodes that are actually played in the game for storage to the permanent hash. That is probably one node in a billion.

PV nodes are so rare that I think they are always worth keeping. In some sense it seems crazy to recalculate the same pv nodes every time we play a game of chess.

[Don]

If the key to the permanent hash table is a 165 bit exact representation of the Epd string (or even the Epd string itself if we want to be lazy), then entries can never be overwritten.

How many PV nodes are there in a hash table with a billion nodes? I guess it is far less than one million (IOW, what percentage of nodes are pv nodes?).

The percentage is pretty small.

If the percentage of pv nodes is higher than I imagine so that the permanent hash becomes too large, then we can go with the pv nodes that are actually played in the game for storage to the permanent hash. That is probably one node in a billion.

PV nodes are so rare that I think they are always worth keeping. In some sense it seems crazy to recalculate the same pv nodes every time we play a game of chess.

The issue is not how many PV nodes in a single search, but how many PV nodes there are in a search of every position in a book that contains several million positions.

A rough calculation tells me that you may have 5 million position in the "book" database and perhaps 300 PV nodes for each of them. However a lot of those are transpositions or otherwise redundant. I did a quick test with Komodo and there tends to be 200-600 PV nodes sitting in the hash table after an 18 ply search that takes a few seconds. I tried several positions after initializing the hash table.

So this may be feasible. The 5 million positions would be 50 million or more if you extracted every move of every game and if you stored all PV nodes of every position played through to the endgame. Typically in a 5 million game database you only extract positions seen N times. And you would want to do something similar when putting PV modes into permanent storage. You cannot dump several thousand new PV nodes after each game into the table and expect to never run out of space.

So I think with a few common sense rules you could effectively store all the position that really matter.


Don