Scan 3.1 now plays all variants on lidraughts!
You may have heard of Scan, the free and open source draughts engine authored by Fabien Letouzey. It is widely regarded as the strongest draughts engine around, taking first place in all recent editions of the ICGA International Draughts Computer Olympiad. It is also the engine that powers all computer play and analysis on Lidraughts, free and unlimited in true open source spirit!
There could hardly be a better occasion for the first Lidraughts blog post than the new version of Scan that has just been released! Scan 3.1 contains some enhancements that gain ELO in all variants, but its major new feature is the support for Frisian and Antidraughts. This means that Scan now knows all the variants that are available on Lidraughts!
But that is not all, the handicaps for the playing levels have also been much improved, including the existing variants. Fabien Letouzey made a weaker version of Scan's evaluation function available, which uses a Piece-Square Table (PST) instead of its usual (and much stronger) pattern-based evaluation. Combined with new ways to handicap its search, such as node and ply limits, the playing levels can be tuned much more precisely. This will be noticeable with the lower levels especially, as they are now not only tactically weaker, but also play with less positional knowledge. This should give them a playing style that is better suited for beginners, while the higher levels play as strong as ever.
The amazing thing about Scan's evaluation function is that it has been trained entirely by self play. Scan started with no prior knowledge of the game, except for the rule of thumb that 1 king equals 3 men, and of course the rules of play. From there it has learned all positional concepts on its own, using a pattern-based technique that came originally from the world of Othello engines. In Fabien's own words, from the World Draughts Forum: "Scan evaluates a position by looking only at small parts of the board (16 overlapping 4x4 squares) and adding the 16 local scores together. The scores come from statistical analysis of Scan games". In a nutshell Scan learns the positional values of occupying certain squares and complexes of squares, while it relies on a traditional alpha-beta search for calculation and tactics.
This is similar in spirit to neural network (NN) based engines like DeepMind's AlphaZero and LcZero. These also learn the game by self play, without any prior knowledge or human input. The machine learning techniques that make Scan's evaluation tick are quite different though, and much older than the recent NN innovations of DeepMind. Neural networks have a greater potential for abstraction (the limits of which are as of yet unknown), and are in principle capable of learning anything. Scan's pattern approach on the other hand works very well for draughts and 'draughts-like' games, but wouldn't work for games with a different structure like chess. A big advantage of Scan's approach over NNs is that it requires much less calculation power. This allows Scan to run full strength on any modern CPU, without the need for powerful GPU's for training or play.
Those that are interested in the more technical story behind Scan and its pattern evaluation, are well advised to visit the World Draughts Forum. There is a lot of information to be found from Scan's author Fabien Letouzey himself, and many interesting discussions with other experts in the field. Let's leave it with an interesting thought to ponder, quoted from this thread:
"How to apply patterns in your own play? The theory is that you shouldn't need to do anything special. That's because Scan mimicks the human eye to some extent: it has a local vision of the board. Let's translate Scan's construction to the human world: I would say that it looked at many games by amateurs who are strong only in tactics, and discovered which shapes are good or bad (led to wins and losses respectively in those games)."
The honest answer is: we don't know. There are many different engines around for international draughts, that can be used to assess Scan's relative strength. This is not so easy for Frisian and Antidraughts, although other engines do exist (mainly as experimental projects). We are likely witnessing the world's first engine that plays those variants on a truly superhuman level!
The Lidraughts team has been lucky to be able to test the playing levels for Frisian draughts with the current World Champion, Marten Walinga. This has established one thing beyond doubt: Scan is very very strong. And not only that, it seems to have a true positional understanding, by Marten's judgment:
"The positional play of Scan is remarkable. It is surprising how often its strategic choices lead to a better transition into the endgame. We can learn from Scan and use it for developing new ideas, it sets the bar high for a lot of players. For the following years I expect the training possibilities which Scan provides will increase the number of Frisian Draughts players."
As we don't have a world champion available for Antidraughts, this game is more difficult to assess. However, playing against Scan at the higher levels, it is safe to say that it deserves the qualifier 'superhuman'. We suggest you give it a try yourself!
An interesting question is what the future may bring. Because however strong Scan already is, its play is still likely nowhere near perfection! As of yet it is unknown how good an AlphaZero-based engine could be at the different draughts variants. Let's hope this question will be answered in the not too distant future, because this could lead to some spectacular draughts matches if nothing else!
Of course all the usual analysis options are available for the new variants as well. A computer analysis can be requested for any game played on Lidraughts, for imported games, and for study chapters you created. Just click the 'Request a computer analysis' button, at the bottom of the analysis screen.
This will run a full game analysis from the servers of Lidraughts, pointing out the mistakes and blunders by Scan's judgment (which should be taken very seriously). You can analyze as many games as you want this way, though only one at a time.
The analysis board can be used to analyze specific positions and try out variations. On the top-right there is a switch that enables Scan, which will run from the browser to evaluate the position currently on the board. By default it analyzes positions for a couple of seconds only, but if you want to go deeper, you can turn on infinite analysis from the 'hamburger menu' on the bottom right.
Along with Scan 3.1, several other improvements have been made to Lidraughts today:
Last but not least, some words of thanks. First and foremost to Fabien Letouzey, without whom all of this wouldn't have been possible in the first place! Thank you so much for all your hard work, your help with the PST and the handicaps, and thinking along with the adaptations required for Lidraughts. Thanks to Marten Walinga for testing the playing levels of Frisian and Frysk, your valuable input on how to improve their relative strength, and your professional opinion on Scan's strength and style. Thanks to Koos van Amerongen for testing the playing levels of Antidraughts and International Draughts, skilled in both opposites of the game. And thanks to Klaas Leijenaar for helping with the playing levels for International Draughts.