So the question, and I would like to get peoples thoughts on this, is if there is a graceful way to minimax these scores while taking into consideration evidence taken from sibling moves.
I think the short answer is "no". A major problem with using move frequency is that pretty often a certain opening move is popular for a while and then a refutation is found, or a much better alternative, and the move is dropped out the repertoire, at least for strong players. So if you have a big book and weight on frequency, you will keep playing the "old" move for quite a while.
(Nevertheless frequency does sometimes work so it is not useless in general).
Move scores are also treacherous. I have spent quite a bit of time lately looking at correspondence games and strong players are very good at finding moves that will score one way at shallow depths and something very different if you go deep enough. So backing up a shallow depth score can get you into real trouble. But again, sometimes it works ok.
So the question, and I would like to get peoples thoughts on this, is if there is a graceful way to minimax these scores while taking into consideration evidence taken from sibling moves.
I think the short answer is "no". A major problem with using move frequency is that pretty often a certain opening move is popular for a while and then a refutation is found, or a much better alternative, and the move is dropped out the repertoire, at least for strong players. So if you have a big book and weight on frequency, you will keep playing the "old" move for quite a while.
(Nevertheless frequency does sometimes work so it is not useless in general).
Move scores are also treacherous. I have spent quite a bit of time lately looking at correspondence games and strong players are very good at finding moves that will score one way at shallow depths and something very different if you go deep enough. So backing up a shallow depth score can get you into real trouble. But again, sometimes it works ok.
In my case all the data is generated by super-grandmaster programs. Not the openings themselves, but the win/loss/draw frequency. But that is no help if the book has really bad moves in them, so it's a nightmare in the sense that any statistics are dependent on the moves the computers are forced to ply. Once you are out of book the number of samples is down to almost nothing.
I have come to the same conclusion that you have, there is nothing really graceful to be done - I might get something that works despite this, but it will be some sort of ugly hack.
There is a way to deal with this however and that is by building this book based on a monte carlo tree search. The tester would be modified to play moves using bandit theory and over time the actual result of any move would converge to the minimax score of the move. Weak moves would get almost no attention and strong moves would be played more often so that the win percentage would properly reflect the value of the move.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
jdart wrote:This is basically correct but you need to start evaluating at the leaf nodes of the book and back up the scores, using the minimax algorithm. For a large book and a lot of nodes, that is a lot of CPU time.
--Jon
I did this in early versions of Crafty. CPU for minimaxing is basically not an issue. The I/O however, is expensive if you use a large book.
But the problem is in the minimaxing. You are choosing an opening line based on whatever info you get at the end of that line, minimaxed with all of the alternatives along that line. That caused me great grief and I gave up on the idea. You choose lines based on a position that might have resulted from really lousy play. I eventually tried to minimax based on GM analysis, but I found positions where "white is clearly winning, but black had a forced mate" and gave up on that as well.
I even tried the idea of doing a search at each book position to be sure that there are no tactical errors along interior book paths. But shallow searches are confused by gambits and you can't trust them. Long searches on a large book becomes computationally intractable. Another approach I have tried (with better success) is to create a book, use book learning, and play millions of games against a variety of opponents and let the learning weed out the bad lines. But gambits are again a problem, since shallow searches won't understand the reason behind the gambit every time...
In short, most likely, hand-tuned books will still be the optimal solution for quite a while longer.
Hi Bob,
I built this large book for automated testing where I include every line played at least N times by human players from a large database of games using TWIC.
I have tens of thousands of games now of komodo vs other strong programs. I can see from the statistics that Komodo should play certain moves and avoid others. However, the statistics are deceiving and I am looking for a general solution. Mini-maxing the results (by win percentage) may be part of the solution but it's has serious sample size issues. You cannot go to some end node where only 5 games are played and mini-max a score back to the first move and expect this to be valid. From computer go with Monte Carlo it's clear that sample size trumps score in many cases so it pays to view the score of a node as having something to do with the total result, not just the success of the best move. For example if one move is played one time and is a win, you don't mini-max 100%.
In my data I have the situation where if Komodo plays 1. e4 it will win slightly more games. But if you look closely at the data you will see that Komodo does much better if the opponent plays 1... e5 - and not as well if the opponent plays 1 ... c5 and the data is pretty conclusive that really Komodo should play 1. d4. In other words 1. e4 looks good only because it has good success when the opponent plays 1. ..e5 and many of the games in the opening book had e5 as the response.
So the question, and I would like to get peoples thoughts on this, is if there is a graceful way to minimax these scores while taking into consideration evidence taken from sibling moves. MCTS solves this problem by controlling how often a move is played, playing the successful moves more often than the unsuccessful moves but still giving all moves some attention - and it's been proved that if you do this right it will have a mini-max effect. But the book is a testing book where each opening line is selected, not each move choice - we play all the lines, both sides as is common for rating and testing chess programs. I have about 28,000 lines which at least covers anything being playing relatively frequently.
You can do things such as only trusting samples larger than 1000 games but that is not very satisfying and probably not correct either. My sense of things here is that the score of any given node needs to be some combination of the combined result of all it's children AND the best response or responses - and this can be recursive.
Here is a canonical example:
At node N move A is played 5 times and scores 70%
move B is played 15 times and score 60%
What should be score of node N? With mini-max we would believe 70, if we combine all results it would be 62.5, but my intuition is that it should be something between the two.
I have had good success with my current book learning, and playing tens of millions of games on our cluster. But there is a drawback. The only book lines you consider are the book lines you choose to include by whatever means. IN Crafty, I can choose based on # of times played, or win/lose percentage, which drops moves that win less than some fixed percentage of the games, etc. But then you run into the book authors that will use this info against you, because they will know you will likely play the most popular moves, which gives them the chance to study those lines under a microscope and find that unexpected move that leads to a win...
That is the problem you have to solve to be successful in CC events.
But there is a drawback. The only book lines you consider are the book lines you choose to include by whatever means.
This is a result of the fact that most book formats (including mine) are based on a fixed size book that is basically a persistent hash table. A real learning book would be able to dynamically add new moves that the program's opponents have played, which would require something closer to a real database interface - in fact I have considered using a SQL db like mySQL for this. Then you are not limited to a fixed move set but can add lines that have been played against you. I don't know why this is not more commonly done, except that it is more complex to implement.
But there is a drawback. The only book lines you consider are the book lines you choose to include by whatever means.
This is a result of the fact that most book formats (including mine) are based on a fixed size book that is basically a persistent hash table. A real learning book would be able to dynamically add new moves that the program's opponents have played, which would require something closer to a real database interface - in fact I have considered using a SQL db like mySQL for this. Then you are not limited to a fixed move set but can add lines that have been played against you. I don't know why this is not more commonly done, except that it is more complex to implement.
I think a general solution is to to make sure that the computer would play one of those moves on it's own given the time control of the tournament the book is for. If not, the move the computer would play should be added. By doing this there are no blatant holes in the book where the only responses are losing move. Of course as you say you should have to option to add a move that is not in the book but could be critical. Also, if a move is playable you would want to be prepared against it, even if it's not of major interest. Any time your program is surprised by a move not in book it should be added and given proper treatment unless of course it's a blunder.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
One thing that is maybe important for a strong engine is that all book lines in the book are lines that the engine itself likes, rather than researched good lines.
Each tournament I've been involved in so far, there have been a few games where one of the top Engine operators has chatted "Hmmm X now out of book and says -50cp"
The way AB works, programs seem to play better when they have a plus score vs a minor score (-50 < cp < 50).
So if you were using analysis for the book, maybe it's better to do this with your own program.
But there is a drawback. The only book lines you consider are the book lines you choose to include by whatever means.
This is a result of the fact that most book formats (including mine) are based on a fixed size book that is basically a persistent hash table. A real learning book would be able to dynamically add new moves that the program's opponents have played, which would require something closer to a real database interface - in fact I have considered using a SQL db like mySQL for this. Then you are not limited to a fixed move set but can add lines that have been played against you. I don't know why this is not more commonly done, except that it is more complex to implement.
Adding lines to my current book would be quite trivial. But it doesn't solve the basic problem, that of using what is actually being played OTB, as opposed to doing real opening preparation to spring surprises or avoid surprises. But when you add to a book based on an engine's search, you just added ANOTHER set of problems that have to be dealt with.
I've used a format in the past so that I could dynamically add lines. Mchess Pro did the same. As have others likely done. But adding lines is problematic in itself, as I don't want to play moves in a serious game that were learned/stored in a fast game, or where a potential opponent actually "seeded" my book with bad moves, intentionally, which has happened in the past...
But there is a drawback. The only book lines you consider are the book lines you choose to include by whatever means.
This is a result of the fact that most book formats (including mine) are based on a fixed size book that is basically a persistent hash table. A real learning book would be able to dynamically add new moves that the program's opponents have played, which would require something closer to a real database interface - in fact I have considered using a SQL db like mySQL for this. Then you are not limited to a fixed move set but can add lines that have been played against you. I don't know why this is not more commonly done, except that it is more complex to implement.
I think a general solution is to to make sure that the computer would play one of those moves on it's own given the time control of the tournament the book is for. If not, the move the computer would play should be added. By doing this there are no blatant holes in the book where the only responses are losing move. Of course as you say you should have to option to add a move that is not in the book but could be critical. Also, if a move is playable you would want to be prepared against it, even if it's not of major interest. Any time your program is surprised by a move not in book it should be added and given proper treatment unless of course it's a blunder.
What about all the current opening moves a computer would not play by itself, but which are the ONLY way to avoid losing a game???
Richard Allbert wrote:One thing that is maybe important for a strong engine is that all book lines in the book are lines that the engine itself likes, rather than researched good lines.
Each tournament I've been involved in so far, there have been a few games where one of the top Engine operators has chatted "Hmmm X now out of book and says -50cp"
The way AB works, programs seem to play better when they have a plus score vs a minor score (-50 < cp < 50).
So if you were using analysis for the book, maybe it's better to do this with your own program.
I don't agree. What you want is winning chances in positions you play well, even if the score is -.5 right out of the book. Those even or slightly positive scores seem to lead to draws more than others, so I am continually looking for unbalanced positions where Crafty seems to handle them well. Those are the lines that lead to wins in important games. I don't think it is possible to force a significant advantage in the opening without the opponent making a mistake that could have been avoided. It is possible to force certain types of unbalanced positions where you give something to get something, with the idea that the something you give is not so damaging that the something you get becomes irrelevant...
For example, if your king safety eval is really good, you might accept a weakened king, knowing you have good chances of defending it via evaluation, in order to get some kind of potential endgame advantage if you can just survive that long..
But there is a drawback. The only book lines you consider are the book lines you choose to include by whatever means.
This is a result of the fact that most book formats (including mine) are based on a fixed size book that is basically a persistent hash table. A real learning book would be able to dynamically add new moves that the program's opponents have played, which would require something closer to a real database interface - in fact I have considered using a SQL db like mySQL for this. Then you are not limited to a fixed move set but can add lines that have been played against you. I don't know why this is not more commonly done, except that it is more complex to implement.
I think a general solution is to to make sure that the computer would play one of those moves on it's own given the time control of the tournament the book is for. If not, the move the computer would play should be added. By doing this there are no blatant holes in the book where the only responses are losing move. Of course as you say you should have to option to add a move that is not in the book but could be critical. Also, if a move is playable you would want to be prepared against it, even if it's not of major interest. Any time your program is surprised by a move not in book it should be added and given proper treatment unless of course it's a blunder.
What about all the current opening moves a computer would not play by itself, but which are the ONLY way to avoid losing a game???
Please note that when I say, "put the move in the book" I don't mean that is what it should play. The context here is figuring out some automatic or semi-automatic way to build a custom book for a given program so you have to start with something that is as comprehensive as possible and then figure out how to narrow down the choices to moves your program will do well with.
If you KNOW there is only 1 move and everything else loses, then of course you would want some mechanism to specify this so that time is not wasted with the computer having to learn that it's bad. On other other hand you probably WANT that move in the book if it's an opponent option, if your program thinks it is good chances are other programs and perhaps humans too will think so. You would want your program to be able to refute it.
Capital punishment would be more effective as a preventive measure if it were administered prior to the crime.
