Anybody tried Logistello's book learning for chess?

[Rémi Coulom]

This algorithm worked extremely well for Othello:
https://skatgame.net/mburo/ps/book.pdf

I like the algorithm description. It looks clever, and proved to be very efficient for Othello. I will probably implement it for 9x9 Go. I wonder if anybody tried it for chess.

I quickly researched the question with Google, and was surprised to find no report of applying this algorithm to chess.

Rémi

[bob]

This algorithm worked extremely well for Othello:
https://skatgame.net/mburo/ps/book.pdf

I like the algorithm description. It looks clever, and proved to be very efficient for Othello. I will probably implement it for 9x9 Go. I wonder if anybody tried it for chess.

I quickly researched the question with Google, and was surprised to find no report of applying this algorithm to chess.

Rémi

I do part of what he suggests, but I have never tried the idea of adding to the book. MchessPro did this, and quite well. My book format is not very conducive to adding moves, since I store positions, with no path links or anything at all. I would have to simply copy-and-insert to add moves, which could take some time with a large book file.

However, I have had the idea on my to-do list for a long time, since it did work well for Marty's code...

[Rémi Coulom]

I do part of what he suggests, but I have never tried the idea of adding to the book. MchessPro did this, and quite well. My book format is not very conducive to adding moves, since I store positions, with no path links or anything at all. I would have to simply copy-and-insert to add moves, which could take some time with a large book file.

However, I have had the idea on my to-do list for a long time, since it did work well for Marty's code...

Thanks Bob. From the description of the book learning of MChessPro I found on the chessprogramming wiki, it seems different from the method of Logistello:
http://chessprogramming.wikispaces.com/Book+Learning

Logistello computes a "best alternative" move in every position, and evaluates it, so that the book can be min-maxed.

Rémi

[mvk]

Logistello computes a "best alternative" move in every position, and evaluates it, so that the book can be min-maxed.

Rémi

That is very much what I described two days ago?

[Rémi Coulom]

Logistello computes a "best alternative" move in every position, and evaluates it, so that the book can be min-maxed.

Rémi

That is very much what I described two days ago?

Yes, it looks similar. Thanks for the link, I had not noticed that post. I took a look at Linke's thesis:
http://e-collection.library.ethz.ch/ese ... 905-02.pdf
It is indeed not necessary to consider more than one alternative.

Logistello's method is what he calls "best-first expansion" when it is used in self-play. But Logistello also expanded its book from the games played against a variety of opponents, and also from strong games it did not play.

So, from my quick look, I suppose the mechanism of what you do is very similar, only the expansion strategy is different. My impression is that book learning is always done better by playing against a variety of opponents.

Rémi

[mvk]

Logistello's method is what he calls "best-first expansion" when it is used in self-play. But Logistello also expanded its book from the games played against a variety of opponents, and also from strong games it did not play.

So, from my quick look, I suppose the mechanism of what you do is very similar, only the expansion strategy is different. My impression is that book learning is always done better by playing against a variety of opponents.

Rémi

I apply several methods to expand the book. But the book is always minimaxed, and each node evalated with an exclusion search.

• - popular lines from the PGN corpus (this forms the foundation of the book. say, the 1M most frequent positions)
  - dropout expansion
  - lost server games
  - lost private games, against several strong opponents.
  - lines from the PGN corpus, where the 'repertoire' playing side (if any) gets a bad position (and no side blunders)
  - moves from non-blundering games from the PGN corpus and immediately exiting the repertoire

The 'corpus' is the set of PGN games from online sources, such as millionbase.
The 'repertoire' is the subset of the book reachable during play.
With each node I associate a 'path error pair', which is a tuple accumulating the error for each side needed to reach that position from the root. (0 when playing the main line, increasing when deviating from the main lines). The path error determines if a position is playable or not. For server play I allow 0.1 pawn for the own side's path error. For tournaments this is closer to 0.02.
Path errors pairs along converging lines are normalised by giving priority to the smallest sum. That makes them well-defined.

It is worth noting that the root score, the white and black path errors in a node, and the node score, are related.

[Rémi Coulom]

Thanks for your explanations. I am planning something similar. Did you measure the strength improvement you get from your book compared to other books?

[mvk]

Thanks for your explanations. I am planning something similar. Did you measure the strength improvement you get from your book compared to other books?

Yes I did. I pitted this system against a Crafty, with its own book learning on, and the relative gain was in the 50-80 elo range by the time I removed Crafty from my testing pool.

[bob]

I do part of what he suggests, but I have never tried the idea of adding to the book. MchessPro did this, and quite well. My book format is not very conducive to adding moves, since I store positions, with no path links or anything at all. I would have to simply copy-and-insert to add moves, which could take some time with a large book file.

However, I have had the idea on my to-do list for a long time, since it did work well for Marty's code...

Thanks Bob. From the description of the book learning of MChessPro I found on the chessprogramming wiki, it seems different from the method of Logistello:
http://chessprogramming.wikispaces.com/Book+Learning

Logistello computes a "best alternative" move in every position, and evaluates it, so that the book can be min-maxed.

Rémi

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 even tried doing searches at each book position, but that has the same problem, namely co-mingling deep book position scores with searches done closer to the root.

The thing about MchessPro that I liked was that the book grew after every game, rather than what I eventually settled on, just learning something about the existing book moves. Which has the embarrassing problem of eventually learning that EVERY opening is bad unless you are ranked #1...

[Rémi Coulom]

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.