Scan

[Fabien Letouzey]

Hi all,

In this post I want to explain Scan a little bit for everybody. A technical description for programmers will follow.

I would say Scan's search is like Damage's: deep but full of holes. It's different though, and relies mostly on evaluation to make pruning decisions.

Evaluation is similar in structure to Dragon's but in a more basic form. 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 before the tournament. Somewhat surprisingly, this is enough to approximate a lot of draughts concepts like position (e.g. centre control), mobility of men, runaways, and even some locks. Other concepts like king mobility and left/right balance are computed separately.

Scan also has multi-core search (designed for 4 cores), 6-piece endgame tables (2 GB due to simplistic compression), and a self-generated opening book (about 100k positions but not searched deeply).

I intend to release Scan in the near future. It's a lot of work because I don't use Windows and haven't implemented any standard protocol yet. However IIUC, I can now compile Moby Dam on my Mac and use it as help to try to implement DXP. I estimate that this is going to take a few weeks, and am hopeful for an end-of-July release.

Fabien.

[BertTuyt]

Fabien, if you want I can integrate Scan into my Engine framework.
This way it is able to communicate with the Damage GUI (Version 2015) via Guide.
For all interested I will share the Damage GUI.

Bert

[Fabien Letouzey]

Fabien, if you want I can integrate Scan into my Engine framework.
This way it is able to communicate with the Damage GUI (Version 2015) via Guide.
For all interested I will share the Damage GUI.

I have no idea what that is. I guess you mean to "link" the Scan source code to some code of yours that takes care of the Guide I/O? If so, this replaces the text protocol by an API, right? This still feels like a lot of work I guess. On the other hand I would do anything to avoid OS-specific socket code (which is why we never use them in chess).

Also, Scan is now in C++11.

[Rein Halbersma]

Fabien, if you want I can integrate Scan into my Engine framework.
This way it is able to communicate with the Damage GUI (Version 2015) via Guide.
For all interested I will share the Damage GUI.

I have no idea what that is. I guess you mean to "link" the Scan source code to some code of yours that takes care of the Guide I/O? If so, this replaces the text protocol by an API, right? This still feels like a lot of work I guess. On the other hand I would do anything to avoid OS-specific socket code (which is why we never use them in chess).

Also, Scan is now in C++11.

Yes, socket management should be abstracted from in a GUI, e.g. by doing plain text I/O over ssh like this chess Arena tutorial shows.

So if e.g. the Damage or Dam 2.2 GUIs would simply connect to an .exe in Windows, people could connect to it from Linux/Mac using ssh. The message protocol can remain layer 2 DamExchange, but the socket layer 1 is then obsolete.

In any case, without such changes in GUI architecture, a platform independent socket library is Boost.Asio (also available as a standalone library, and also going to be part of C++17, so worthwhile investment to make).

[Fabien Letouzey]

Now technical details for the programmers.


Search

Algorithm: Safe PVS from Fruit (no TT cutoff and less pruning at PV nodes). Not important but I use it as a habit (signature algorithm). No aspiration.

SMP: "modern" (recursive) form of YBWC. Designed for 4 cores; probably bad above that. One implementation detail is that I put all the local search variables into a struct that is passed around and occasionally modified. This allows to have a lot of commmon code like a single "search_move" function that takes care of extension/reduction of the move as well as PVS/LMR re-search.

No ETC(!).

Pruning: "ProbCut" and LMR. By "ProbCut" I mean only the essence of it: reduce depth & widen window, that's all there is to it really. I didn't try any of the statistical stuff from Buro's paper. As a side note: Damage is also using LMR and I think Dragon as well, so it looks like a safe bet in draughts. I'm still missing, compared to chess, some low-depth pruning algorithm.

Move ordering: TT and history; no killers.

Extend only single legal moves. LMR reductions are 1 or 2 plies depending on "lateness".

QS: in quiet positions, I generate all "exchanges" (I move, he takes, I take) regardless of the expected material gain. That's not really pattern-based let alone learning; it's just a special move generator using bitboards conditions. This doesn't bring much though.


Evaluation

Material, king position (PST), king mobility.

The rest is covered by Othello patterns (which I considered to call "regions" in draughts to avoid confusion with existing pre-selected patterns which have a variable size), except that the shapes are 2D (4x4 squares) instead of mostly 1D (board lines in Othello, though we did use rectangles in the corners). The pattern score is a sum of 16 local scores. Patterns are very versatile and can approximate a lot of local concepts. Note that, to my knowledge, Dragon has been using this for about 8 years and now has a much more advanced version. So as for LMR, evaluation learning seems a safe bet in draughts. The maths are not too easy though ...

Left/right balance is scored separately as it cannot be locally approximated.

No breakthrough table!

The feature coefficients were learned by logistic regression of game results (still Othello stuff). I suggested a few papers in the Olympiad thread. After a historical quirk, this is called "Texel's Tuning Method" in chess. You will find a lot of information on this as it recently became very popular, though its application to games is actually 20 years old. Here I think Dragon differs a lot and uses different techniques.

Following chess, separate midgame/endgame scores are accumulated for all features and finally combined using interpolation.


Data structures: I started Scan using old code so there is still a mix of bitboards (e.g. for move generation) and arrays (for pattern evaluation).


6-piece DB in RAM, 2GB due to simplistic compression.


During the tournament, I used a separate GUI written in Java. It communicated with the engine (which is written in C++) using text. The protocol is very simplistic and not standard. It was very loosely modeled on UCI though more in spirit than details.


Last but not least, all Scan development/testing was done using fast games only (about 5s per game I guess). I insist because there is a lot of inertia against them: fast games are good enough to make most decisions.

[BertTuyt]

Fabien, thanks for sharing all these details.
In the meantime I was able to compile (without errors) the Scan source code with the Microsoft Visual Studio Community Edition 2013. This development environment is now completely free for non commercial usage.
A few things I needed to change before all worked (In 64bit mode), and as I'm not a hyper C++ expert (like Rein), there might be better and simpler options to solve the mentioned issues.
Or it might be that the soon to be published version 2015 solves a few issues.

So in random order:
* I got a strange error min (and max) is not a member of std. I solved it to add #include <algorithm)
* Same for isdigit, but here the #include didn't work, so i just removed the std:: and then all seemed to work.
* To switch off all special Microsoft security errors (for some input output functions), I added _CRT_SECURE_NO_WARNINGS in the Preprocessor Definitions (Project Properties, C/C== Preprocessor)
* To enable 64bit intrinsic I switched USE_INLINE to true, #define USE_INLINE TRUE
* I had to slightly change intrinsic definitions, and added #include <intrin.h> in the bit.h header file:

// inline int bit_first (bit_t b) { assert(b != 0); return __builtin_ctzll(b); }
inline int bit_first(bit_t b) { unsigned long uBit; assert(b != 0); _BitScanForward64(&uBit, b); return (uBit); }
// inline int bit_count (bit_t b) { return __builtin_popcountll(b); }
inline int bit_count(bit_t b) { return __popcnt64(b); }

A remaining question.
in the bd.trit[square] which you use to calculate the index for a specific region , I assume the value is 1 for empty, 0 for a white man, and 2 for a black man.
In case of white and black king is the value than also 1 (as empty) ?

Data structures: I started Scan using old code so there is still a mix of bitboards (e.g. for move generation) and arrays (for pattern evaluation).

I have also seen this, and basically I have/had the same in Damage (and still some traces in the program nowadays), but im (still) working to make Damage 100% bitboard based (which is now 95% i guess). It might be that it is possible without time penalty to replace the i8 function ( static int i8(const Board & bd, int s0, int s1, int s2, int s3, int s4, int s5, int s6, int s7) { ) by a bitboard alternative, so you don't need to incrementally update the p_trit arrays(s), (and p_square).

In general, I found the Scan evaluation function (extremely beautiful in simplicity, with the real complexity is in the underlying data structure), and your code in general very elegant, very well structured, and a source of inspiration and motivation for everyone, to continue with Draughts program development.
So thanks again for sharing, and raising the bar.

Bert

[Fabien Letouzey]

A remaining question.
in the bd.trit[square] which you use to calculate the index for a specific region , I assume the value is 1 for empty, 0 for a white man, and 2 for a black man.
In case of white and black king is the value than also 1 (as empty) ?

Yes, king = empty. I didn't try king = man, as I assumed their mobility gives them completely different properties.

I have also seen this, and basically I have/had the same in Damage (and still some traces in the program nowadays), but im (still) working to make Damage 100% bitboard based (which is now 95% i guess). It might be that it is possible without time penalty to replace the i8 function ( static int i8(const Board & bd, int s0, int s1, int s2, int s3, int s4, int s5, int s6, int s7) { ) by a bitboard alternative, so you don't need to incrementally update the p_trit arrays(s), (and p_square).

To my knowledge this is exactly what Michel is doing, so it's certainly possible. I didn't carefully think about it because I assumed that:
1) bitboards would only easily allow base-4 indices instead of base 3. For 8 squares already this would waste 90% of the index space, not to mention larger patterns.
2) bitboards would "prefer" regularly-spaced, identically-shaped patterns. While this is what I have now, I preferred not to commit to such a design at an early stage.

Of course that was just intuition. I might be wrong on both counts.

[Catherine]

Hi Fabien
Before any word, i want to congratulate you for the performance of Scan.
We have now an idea of the strengh of Scan.
We saw only one of his games. It was published by Harm Jetten on Moby dam's site.
Please, can you post for us, all the games played by Scan during this tournament, or if you have some test games against others programs. Thank.

Catherine.

[Fabien Letouzey]

Please, can you post for us, all the games played by Scan during this tournament, or if you have some test games against others programs. Thank.

You will find them in the Olympiad thread.

[MichelG]

To my knowledge this is exactly what Michel is doing, so it's certainly possible. I didn't carefully think about it because I assumed that:
1) bitboards would only easily allow base-4 indices instead of base 3. For 8 squares already this would waste 90% of the index space, not to mention larger patterns.
2) bitboards would "prefer" regularly-spaced, identically-shaped patterns. While this is what I have now, I preferred not to commit to such a design at an early stage.

Of course that was just intuition. I might be wrong on both counts.

Dragon's implementation of the patterns are completely bitboard. This doesn't matter for speed though. Since dragon's eval table is so large, it does not fit in the cache anyway and the time to compute is dominated by the waiting time for memory access.

In dragon you can define a random 50-bit mask for each of its 24 patterns. You apply the mask to 3 bitfields of the position (white, black, kings), yielding 192 bits of information, and hash that (in a smart way) to a smaller number. It takes about 0.5 to 1 gigabyte of ram to store the 50 million weights.

I did some experimentation with the shapes. Some shapes give a slightly better regression results. 45 degrees rotated rectangles seem best, but it matters little on actual gameplay.

For now it sticks on rectangular 6x6 plus some triangle shapes.

Michel

[Rein Halbersma]

So in random order:
* I got a strange error min (and max) is not a member of std. I solved it to add #include <algorithm>
* Same for isdigit, but here the #include didn't work, so i just removed the std:: and then all seemed to work.

Bert

std::isdigit requires inclusion of the C++ header <cctype> and is just a using-declaration of the global C function ::isdigit which is in the C header <ctype.h>.

[Rein Halbersma]

Now technical details for the programmers.

Search

No ETC(!).

Why the exclamation mark? Because it was first tried in the Chinook checkers program? I don't recall many other programs using ETC successfully: did you use this in your other draughts/chess/Othello programs?

Pruning: "ProbCut" and LMR. By "ProbCut" I mean only the essence of it: reduce depth & widen window, that's all there is to it really. I didn't try any of the statistical stuff from Buro's paper.

Does your ProbCut test for both fail-low and fail-high? Stockfish only does the latter, did you try that?

As a side note: Damage is also using LMR and I think Dragon as well, so it looks like a safe bet in draughts. I'm still missing, compared to chess, some low-depth pruning algorithm.

Move ordering: TT and history; no killers.

Extend only single legal moves. LMR reductions are 1 or 2 plies depending on "lateness".

Surprising that your LMR is only 1 or 2 ply, I think the Stockfish version goes as far as 6 ply at high search depths, so much more aggressive.

QS: in quiet positions, I generate all "exchanges" (I move, he takes, I take) regardless of the expected material gain. That's not really pattern-based let alone learning; it's just a special move generator using bitboards conditions. This doesn't bring much though.

This is also surprising to me: I think most draughts programns only resolve pending captures for either side. How do you prevent search explosion when you initiate captures in QS?

[Fabien Letouzey]

Why the exclamation mark? Because it was first tried in the Chinook checkers program? I don't recall many other programs using ETC successfully: did you use this in your other draughts/chess/Othello programs?

Interesting. For some reason I put ETC into the draughts-only category, perhaps because of the larger expected number of transpositions (at least for me). I vaguely remember reading here that Bert was using it perhaps? And then if anyone else also mentioned it, I probably assumed it was common.

I actually used a slightly more general form (anything in 1 ply) in Fruit 1.0 and 1.5 by design. Someone tested it and it was a loss though. I removed it and never looked back.

Does your ProbCut test for both fail-low and fail-high? Stockfish only does the latter, did you try that?

Nice catch, it's fail-high only. In general I think pruning on fail-low is more complicated, as you're supposed to try desperate moves instead of pruning (in spirit with FP). So I basically consider that pruning also on fail-low is not only risky, but the expected reward is also small. Nonetheless Richard Delorme once told me that there was a gain to do both in Othello, but it's possible that he was after peanuts.

Surprising that your LMR is only 1 or 2 ply, I think the Stockfish version goes as far as 6 ply at high search depths, so much more aggressive.

Ryan Benitez told me about it during the development of Senpai, as it's apparently one of the rare novelties compared to 2005. But I don't have the patience to run "slow" games (which are normally necessary to test pruning ideas), or even interest to run 10^6 "random" experiments. Actually even the 2-ply reduction brought very little IIRC. Also ProbCut is my main pruning algorithm and it's already fairly aggressive, so perhaps it makes sense to be more cautious in LMR (which I still allow during ProbCut searches).

This is also surprising to me: I think most draughts programns only resolve pending captures for either side. How do you prevent search explosion when you initiate captures in QS?

I'm not sure I understand. I don't do anything about threats, and have no idea what draughts programs are typically doing (a common theme). As for "exchanges", I activate them only when there are no kings; does that answer your question?

[BertTuyt]

Interesting. For some reason I put ETC into the draughts-only category, perhaps because of the larger expected number of transpositions (at least for me). I vaguely remember reading here that Bert was using it perhaps? And then if anyone else also mentioned it, I probably assumed it was common.

Damage uses ETC, and to my knowledge also Moby Dam.
I'm able (in the Damage Test version) to switch on/off ETC, so I could (re)do a test if someone is interested in this?
I could use the standard 3 positions also used for the perft...

Bert

[Rein Halbersma]

This is also surprising to me: I think most draughts programns only resolve pending captures for either side. How do you prevent search explosion when you initiate captures in QS?

I'm not sure I understand. I don't do anything about threats, and have no idea what draughts programs are typically doing (a common theme). As for "exchanges", I activate them only when there are no kings; does that answer your question?

white to move

So at depth=0, what do you do here? Return eval() or try 27-21 and 27-22?