Anybody tried Logistello's book learning for chess?

[bob]

I never got the minimaxing to work. I did that in Crafty for a while. But if you only minimax what is in the book, the scores that make it back to the root are REALLY "iffy" since the book is so selective.

I have little experience, but my impression is that minimaxing can work only if you include the best alternative in addition to the book moves. And once you have computed the best alternative move, you get a simple way to extend the book when the minimax value of the alternative becomes higher than the value of the book moves.

What is "best alternative"? I think I have my old minimaxing code somewhere to try again. For me, I took the learned book scores, + a search from the book position, but I ran into the usual "accept all gambits" issue since the searches have to be relatively shallow if the book is big. Also shallow searches often give REALLY wrong results. That led me to not continuing to do that particular idea. Perhaps there's a way to make it work however...

[Rémi Coulom]

The best alternative is the best non-book move. You can find the details of the algorithm in that paper:
https://skatgame.net/mburo/ps/book.pdf

Of course, the evaluation can be very wrong, but the book-growing mechanism should grow the book in a way that will eventually correct the error.

[hgm]

Note that it is not consistent to minimax scores if you construct a book with alternatives to the best move. When in a certain position you would play move A with 80% probability, and move B with 20% probability, the score of the node should be 0.8*score(A) + 0.2*score(B). And this should be propagated towards the root, where the preference of a move can be based on the availability of a better second-best move in the daughter.

Minimax is based on the idea that you would only play the best move.

[syzygy]

Note that it is not consistent to minimax scores if you construct a book with alternatives to the best move. When in a certain position you would play move A with 80% probability, and move B with 20% probability, the score of the node should be 0.8*score(A) + 0.2*score(B).

I prefer Marcel's path error approach, which is consistent with minimax.

[mvk]

Note that it is not consistent to minimax scores if you construct a book with alternatives to the best move. When in a certain position you would play move A with 80% probability, and move B with 20% probability, the score of the node should be 0.8*score(A) + 0.2*score(B). And this should be propagated towards the root, where the preference of a move can be based on the availability of a better second-best move in the daughter.

You don't have to do that.

In my setup, I don't even know what will become the repertoire moves until after minimax has been done and the path errors computed. And even then: the maximum allowable path error during play is something that can be changed while using the same book: I use 0.1p for online play, which is really wide (allowing any of 1.e4 1.d4 and 1.Nf3 for example), and about 0.02p for tournaments.

BTW, in principle I play all repertoire moves with the same probability. Unless I have played this position before against the same opponent, in which case the historic results can temporarily exclude or include moves.

It is all not rocket science, and the only surprise is that the computer chess community is so much behind in this area.

[hgm]

Playing all moves with the same probability doesn't seem the proper thing to do. It will lead to a very inhomogeneous distribution over the end-leaves of your opening tree. The path error approach will make the branching factor of the tree very branch-dependent: if the first move exhaust your entire error budget, there will be no room for branching any further (against optimal play). So if you had three moves in the root, and play the barely acceptable one with 33%, you have the worst of both worlds: a high chance to end up in a leaf (so the opponent could prepare for it) which is one of the poorest in your repertoire.

Under reasonable assumptions for how much preparation time T helps to improve your opponenents Elo (namely Elo boost proportional to log T) it can be shown that the optimal playing probability with which you should end up in each leaf node of your opening tree is proportional to exp(const*eval).

[mvk]

Playing all moves with the same probability doesn't seem the proper thing to do. It will lead to a very inhomogeneous distribution over the end-leaves of your opening tree. The path error approach will make the branching factor of the tree very branch-dependent: if the first move exhaust your entire error budget, there will be no room for branching any further (against optimal play). So if you had three moves in the root, and play the barely acceptable one with 33%, you have the worst of both worlds: a high chance to end up in a leaf (so the opponent could prepare for it) which is one of the poorest in your repertoire.

Your objections are IMHO too easy. None of the things you describe are bad, not even in theory, as long as you keep learning: a book that doesn't expand is a sitting duck anyway. Just download the games from ficsgames.org and observe if the effect you fear occurs. 0.1p is a very wide margin.

BTW, I found that I'm repeating myself, and I will therefore not keep the discussion going on longer.

[hgm]

Not making best use of the book you have now (by using sub-optimal playing frequency) does seem bad in parctice as well as theory. Expanding it by learning would only help in the future.

[mvk]

Not making best use of the book you have now (by using sub-optimal playing frequency) does seem bad in parctice as well as theory. Expanding it by learning would only help in the future.

I think you missed that the affinity immediately changes with the history against the same opponent. In effect, if move A loses it will not be played until the others have been tried with the same result. In theory that is also 'bad', because it increases predictability, but you need to know at what point the book graph is updated and what is in the book, which is hidden information. In reality, there are no real bad moves in the repertoire, otherwise the window is too wide. Your effect is surely in the pico-elo category and not exploitable.

[Rein Halbersma]

Under reasonable assumptions for how much preparation time T helps to improve your opponenents Elo (namely Elo boost proportional to log T) it can be shown that the optimal playing probability with which you should end up in each leaf node of your opening tree is proportional to exp(const*eval).

I would expect

Code: Select all

Prob(move) = exp(const * eval(move) ) / sum_{m in all_moves} exp(const * eval(m))

In the special case of N equivalent moves, it reduces to 1/N.