Computer Checkers / Pattern based evaluations

[fierz]

I just finished implementing a full pattern-based evaluation in my checkers engine Cake (now in version 1.89d, www.fierz.ch/checkers.htm), with very nice results (www.fierz.ch/cake186.php).

Pattern-based means that I am using a part of the board - eg.g. one quarter of the board, which in 8x8 checkers only contains 8 squares; so that there are 5^8 possible piece configurations, to generate an evaluation weight for each configuration, and optimizing those weights with gradient descent against a database of a few 100'000 games played at bullet speed between different engines.

I got the pattern idea from Ed Gilbert, who used it in his KingsRow engine, who in turn got the idea from Fabien Letouzey's international draughts engine Scan, and Fabien may have gotten the idea from Othello programming.

Does anyone know where this idea actually originated, and which games it is useful for, and which not?

cheers
Martin

[Rein Halbersma]

AFAIK, such board patterns with 3-valued indices were invented by Fabien Letouzey in 2015. If there are prior uses, Fabien might know. Are you using 5-valued indices? Obviously, games with many piece types suffer in indexing efficiency, and games with long range piece interaction might also be hampered by small local patterns.

[Rein Halbersma]

Btw, very nice blog on your website, amazing that you have edged out Ed for now. Nitpick: Buro might have pioneered the use of logistic regression in Othello but he didn’t invent the technique itself. It has been well known in statistics since at least the 1950s. He got the idea from his statistician wife IIRC from his papers acknowledgements.

[fierz]

Thanks Rein for the nitpick; I didn't realize that. I should have married a statistician too

In Cake, I use a combination of 2-, 3- and 5-valued indices.

Ed & amazing: It must be hard programming in a "vacuum" like he was after creating the first English-checkers pattern-based engine two to three years ago. Having a clear goal in the form of Ed's new machine-learned engines kept me motivated, and I knew exactly what I had to shoot for. I assume he will catch up with me quickly again, now that he has a target

[Xann]

Does anyone know where this idea actually originated, and which games it is useful for, and which not?

Hi Martin!

In games, patterns gained popularity in the 80's. They appear naturally in Othello because edges act like a "micro world": edge discs can only be flipped by edge moves. The Iago -> Bill -> Logistello progression (read "The Evolution of Strong Othello Programs") is a good overview. I consider Bill as a key step where patterns were used for all evaluation features rather than just edges.

In image recognition, patterns seem much older still (maybe 1959!) under the name 'n-tuple networks'. Note that, due to image size, random sampling was used instead of connected squares.

As Rein said, patterns are affected negatively by multiple factors:
- large board
- many piece types
- long-range pieces

They are applicable in other games, like Lines of Action.

Fabien.

[Rein Halbersma]

Thanks Rein for the nitpick; I didn't realize that. I should have married a statistician too

See https://www.jair.org/index.php/jair/art ... 0146/24043 for the first appearance of Logistello.

In Cake, I use a combination of 2-, 3- and 5-valued indices.

Ed & amazing: It must be hard programming in a "vacuum" like he was after creating the first English-checkers pattern-based engine two to three years ago. Having a clear goal in the form of Ed's new machine-learned engines kept me motivated, and I knew exactly what I had to shoot for. I assume he will catch up with me quickly again, now that he has a target

I knew of course about your decades long friendly rivalry, so it's no surprise in itself that you caught up with and for the moment surpassed Ed, but you did it very fast. As you said, it helps that nowadays there are many accessible explanations of the technique and that you had a target, but nice result regardless .

About the "vacuum" thing: I guess Ed's port for his 10x10 patterns to the 8x8 program was not pushed to the limit by strong rival 8x8 programs such as Cake. But in the 10x10 arena, the competition with Scan was just as fierce so these patterns and the infrastructure to quickly build up test games and tune the weights was pretty battle hardened I think.

[derjack]

This is called N-tuple network and first 'big' usage was for othello AFAIK. In logistello it was trained the way we call now Texel's tuning method, so using logistic regression for win/loss labeled positions. The pattern-based evaluation is used in more games i.e. connect4 or state-of-the-art 2048 bots learned using temporal difference learning.

Personally for my othello bot, I had more success combining the n-tuples with other features than n-tuples alone. Also I found training with search-based labeled positions was better than labeled win/loss. I see it as trying to match my current eval into some eval+depth, so it can get more accurate. And this worked for eval params in general, be it handcrafted eval, n-tuples or NN.

As for your patterns, do you use the same patterns regardless of side to move? I found that using patterns for different current player (thus doubling weights, but patterns are fast anyway) was better than 'shared' one, especially for zugzwangish games.

[fierz]

Thanks for your answers!

I should maybe mention first that I never found any good accessible explanations of how to do a pattern optimization (just as I have never found any good accessible explanation of new concepts such as NNUE); until a few weeks ago I was using a Texel-kind of tuning method for first 400 then about 4000 parameters (3-backrank instead of 2-backrank = 4096-256 additional parameters), it was taking a few days to complete, horrible. Ed explained everything to me, patiently, by email; also on magic multipliers for fast indexing; so most of the increased strength of the latest pattern-based Cake is thanks to him. I only just "finished" adding patterns and training, so there are still a lot of things that could be tried - but my gut feeling is that none of them will make such a large difference any more (things like adding more games, adding games of the latest engines = higher quality, adding games with more variety in openings, adding games of weaker engines... ).

@Rein: I don't think I did it very fast - it took me about 2.5 years! Much of it has to do with other priorities though Actually, I do admit to being surprised; KingsRow is certainly technically better, and searches a lot faster than Cake - Ed is a real programmer, unlike me.

@Fabien: so if you had to put a name on it: would you say that Kai-Fu Lee and Sanjoy Mahajan (Bill) pioneered the pattern-based approach? Or rather Michael Buro? Or someone else?

@Jacek:
- I also use a combination of "old" features (of my handcrafted eval) with patterns. However, I have removed some parts that clearly are unimportant (= faster eval, and better result in matches as a result), and just haven't gotten round to removing more - it's on my todo list, I'm sure that I can remove a lot more that has become redundant due to the patterns; but it requires a re-optimization of the remaining parameters + a large enough test match to verify that nothing is broken, so is time consuming.
- I optimize on result alone. Optimizing to the score of a shallow search is also on the todo list. I think in chess that is what people are doing? Or a combination of result and eval?
- I tried making some of my patterns side-to-move aware (Cake 1.89c didn't have this, Cake 1.89d has it, but not for all patterns); 1.89d did a tiny bit better vs KingsRow, but the difference was statistically insignificant. I left it in anyway.

cheers
Martin

[fierz]

PS: what is actually the current status of computer Othello (8x8)? I couldn't find much with a quick google search...

[Xann]

@Fabien: so if you had to put a name on it: would you say that Kai-Fu Lee and Sanjoy Mahajan (Bill) pioneered the pattern-based approach? Or rather Michael Buro? Or someone else?

Indeed, I think that Bill was the first program to exclusively use patterns to encode evaluation features (which were manually selected). Michael Buro progressively made patterns more general and found that adding rectangular shapes in the corners helped. That made patterns enter the realm of 'feature construction'.

PS: what is actually the current status of computer Othello (8x8)? I couldn't find much with a quick google search...

Richard Delorme will answer this one, but my guess is: solvable but nobody cares enough to do it. It seems that development of top programs stopped around 2010.

My experience in Othello seems to match that of draughts: 8x8 is too small for computers and the middle game is bypassed. Endgame search (resp. tables in draughts) is directly accessed by the opening-book construction search. 10x10 feels just right in both cases.

Fabien.