Scan
Re: Scan
I tried the Index table appoach based upon bitboards.
A little bit ugly, as it uses a 1M array ( so a huge waste of memory).
However the implementation seems to be 5% faster as the original (and more speedup is possible when the incremental update of the non bitboard based code is omitted.
Maybe not scalable to larger patterns.
here some code.
The Index Table init code is below (quick and dirty , as i didnt give it much thoughts
additional code in the eval_init
and the value of const bit_t Mask_Index = U64(0x31863); // Evaluation Index Mask
Last but not least, as the main bitboard difference between Damage and Moby Dam compared with Scan are the trailing zeros in the bitboards (so first 6 positions), and all 3 use ghost squares, it is very simple (i guess, just a shift operation on the bitboards) to inject the Scan Eval into both programs (when the non bitboard code is omitted), so maybe interesting to test.
I used my old computer to do these tests, I can try to run the modified Scan on my faster system, and measure the speed.
Bert
A little bit ugly, as it uses a 1M array ( so a huge waste of memory).
However the implementation seems to be 5% faster as the original (and more speedup is possible when the incremental update of the non bitboard based code is omitted.
Maybe not scalable to larger patterns.
here some code.
Code: Select all
value1 += Weight[4 + 0 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD1)) | (Mask_Index & (empty >> SFLD1)) << 2]];
value1 += Weight[4 + 1 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD2)) | (Mask_Index & (empty >> SFLD2)) << 2]];
value1 += Weight[4 + 2 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD3)) | (Mask_Index & (empty >> SFLD3)) << 2]];
value1 += Weight[4 + 3 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD4)) | (Mask_Index & (empty >> SFLD4)) << 2]];
value1 += Weight[4 + 4 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD11)) | (Mask_Index & (empty >> SFLD11)) << 2]];
value1 += Weight[4 + 5 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD12)) | (Mask_Index & (empty >> SFLD12)) << 2]];
value1 += Weight[4 + 6 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD13)) | (Mask_Index & (empty >> SFLD13)) << 2]];
value1 += Weight[4 + 7 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD14)) | (Mask_Index & (empty >> SFLD14)) << 2]];
value1 += Weight[4 + 8 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD21)) | (Mask_Index & (empty >> SFLD21)) << 2]];
value1 += Weight[4 + 9 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD22)) | (Mask_Index & (empty >> SFLD22)) << 2]];
value1 += Weight[4 + 10 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD23)) | (Mask_Index & (empty >> SFLD23)) << 2]];
value1 += Weight[4 + 11 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD24)) | (Mask_Index & (empty >> SFLD24)) << 2]];
value1 += Weight[4 + 12 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD31)) | (Mask_Index & (empty >> SFLD31)) << 2]];
value1 += Weight[4 + 13 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD32)) | (Mask_Index & (empty >> SFLD32)) << 2]];
value1 += Weight[4 + 14 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD33)) | (Mask_Index & (empty >> SFLD33)) << 2]];
value1 += Weight[4 + 15 * 6561 + pIndex[(Mask_Index & (blackman >> SFLD34)) | (Mask_Index & (empty >> SFLD34)) << 2]];
Code: Select all
void index_init(void) {
int i, j, iarray[8], ivalue, imodulo;
bit_t black, empty;
for (i = 0; i < 6561; i++) {
ivalue = i;
for (j = 7; j >= 0; --j) { // Calculate number 3-base
imodulo = ivalue % 3;
iarray[j] = imodulo;
ivalue -= imodulo;
ivalue /= 3;
}
black = 0; // Set Black Index
if (iarray[0] == 2) black |= 0x1;
if (iarray[1] == 2) black |= 0x2;
if (iarray[2] == 2) black |= 0x20;
if (iarray[3] == 2) black |= 0x40;
if (iarray[4] == 2) black |= 0x800;
if (iarray[5] == 2) black |= 0x1000;
if (iarray[6] == 2) black |= 0x10000;
if (iarray[7] == 2) black |= 0x20000;
empty = 0; // Set empty Index
if (iarray[0] == 1) empty |= 0x1;
if (iarray[1] == 1) empty |= 0x2;
if (iarray[2] == 1) empty |= 0x20;
if (iarray[3] == 1) empty |= 0x40;
if (iarray[4] == 1) empty |= 0x800;
if (iarray[5] == 1) empty |= 0x1000;
if (iarray[6] == 1) empty |= 0x10000;
if (iarray[7] == 1) empty |= 0x20000;
pIndex[black | (empty << 2)] = i;
}
}
Code: Select all
void eval_init() {
Weight.load("eval");
pIndex = (int*)calloc(1048576, sizeof(int)); // Alloc memory for Evaluation Index Table
memset(pIndex, -1, 1048576); // Clear Evaluation Index Table
index_init();
}
Last but not least, as the main bitboard difference between Damage and Moby Dam compared with Scan are the trailing zeros in the bitboards (so first 6 positions), and all 3 use ghost squares, it is very simple (i guess, just a shift operation on the bitboards) to inject the Scan Eval into both programs (when the non bitboard code is omitted), so maybe interesting to test.
I used my old computer to do these tests, I can try to run the modified Scan on my faster system, and measure the speed.
Bert
Re: Scan
Herewith the output of the initial search of Scan on my faster system (included the modified evaluation table index).
Bert
Bert
Code: Select all
White to play ...
> 32-28
* * * * * 01 02 03 04 05
* * * * * 06 07 08 09 10
* * * * * 11 12 13 14 15
* * * * * 16 17 18 19 20
- - - - - 21 22 23 24 25
- - O - - 26 27 28 29 30
O - O O O 31 32 33 34 35
O O O O O 36 37 38 39 40
O O O O O 41 42 43 44 45
O O O O O 46 47 48 49 50
Black to play ...
7/11.3 +6 100017 0.02 6.67 17-22 28x17 11x22 34-30 19-23 33-28 22x33
8/12.6 -5 304254 0.05 6.34 20-25 37-32 17-22 28x17 12x21 31-26 7-12
9/14.1 +6 1009517 0.16 6.43 17-22 28x17 11x22 37-32 12-17 34-30 19-23
10/15.3 -4 3303895 0.46 7.15 19-23 28x19 14x23 34-29 23x34 39x30 20-24
11/16.0 +6 5726573 0.82 7.00 19-23 28x19 14x23 34-29 23x34 39x30 10-14
12/17.4 -5 17334529 2.21 7.85 20-25 37-32 17-22 28x17 12x21 34-30 25x34
13/18.3 +5 42936758 5.23 8.21 20-25 31-27 19-23 28x19 14x23 34-30 25x34
13/20.2 +5 83402752 10.00 8.34 20-25 31-27 19-23 28x19 14x23 34-30 25x34
* * * * * 01 02 03 04 05
* * * * * 06 07 08 09 10
* * * * * 11 12 13 14 15
* * * * - 16 17 18 19 20
- - - - * 21 22 23 24 25
- - O - - 26 27 28 29 30
O - O O O 31 32 33 34 35
O O O O O 36 37 38 39 40
O O O O O 41 42 43 44 45
O O O O O 46 47 48 49 50
White to play ...
I play 20-25
>
-
- Posts: 285
- Joined: Tue Jul 07, 2015 07:48
- Real name: Fabien Letouzey
Re: Scan
BTW Link-Time Optimisation (LTO) is important when compiling Scan. You are most likely already using it but I prefer to be on the safe side. It's sometimes called Whole-Program Optimisation. In practice, it means that the compiler can inline functions from other modules. Harm is also using it, and in fact we nearly have the same compilation options.BertTuyt wrote:Herewith the output of the initial search of Scan on my faster system (included the modified evaluation table index).
-
- Posts: 1635
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Re: Scan
Ah, yes I misread, sorry. Ok, that resolves my question about long sacrificial intros with a bigger counter-capture. I can see now how your QS is carefully controlled.Fabien Letouzey wrote: I don't understand where the sacrifice is coming from. My definition of "exchange" is: I move, he takes, I take (3 plies). The special move generator makes sure that I will be able to capture on the 3rd ply.
Let's assume that my opponent cannot capture on the 4th ply; I would expect this to happen > 50% of the time. Then I lose the initiative, my opponent can do whatever. Therefore, for me, "my score has dropped even more" has no bearing as it's not even my turn anymore. It's my opponent's turn to worry about his score and position.
With "pending" I meant that the side to move has to make a captureMaybe "pending" is what I call a "pin"? I move a piece, and this allows the opponent to capture another one I was defending? No I haven't tried it. I assumed most would be bad in random positions (contrary to exchanges). Probably some restrictions should be added. I also assumed that "pins" would be rarer than exchanges, especially interesting ones.

White to move has a pending capture 31x22
With "threatened" I meant indeed that the opponent will have to make capture on the last move"Threatened" I guess is the opponent captures. I tried extending 1 ply (= forbidding standing pat), possibly only in restricted cases; no improvement. I didn't insist on this front though, despite the "double quiescence" from Buggy which sounds a bit mysterious to me (no captures for either player?).

White to move, black threatens 16x27
This means white of course has a "free tempo" to create damage for black (runaway to promotion line unopposed with 20-15 and 15-10, or make a counter-combination with 37-31 and 31x4). It's a well-known theme for draughts composers, and young draughts players are trained not to give free tempo to their opponent without double checking their calculations. Just speculating, but I think that Buggy's author (very strong player) did indeed use double quiescence to mean that eval() is only called when there are neither pending nor threatened captures. This will often explode the search tree, however, and some restrictions are necessary.
Thanks for your explanation, all is clear nowI think that's it, we just view QS differently. For me, QS is what you make it. In the 90's when everybody was extending tactical moves, it makes sense to reduce it to a minimum. But remember that I prune a lot, so I'd rather have some tactical safety at low depth. Static eval doesn't take that into account because I filter out capture positions during learning.

So if you are looking for tactical safety, may I suggest to try only exploring unforced exchanges in QS if the eval is, say, half a man below alpha? In this way, you avoid exploring exchanges for small positional gains but you would still find material-gaining tactics when you need them the most (you would miss some tactics when you are not too far behind positionally though).
-
- Posts: 1635
- Joined: Wed Apr 14, 2004 16:04
- Contact:
Re: Scan
Fabien Letouzey wrote: Maybe "pending" is what I call a "pin"? I move a piece, and this allows the opponent to capture another one I was defending? No I haven't tried it. I assumed most would be bad in random positions (contrary to exchanges). Probably some restrictions should be added. I also assumed that "pins" would be rarer than exchanges, especially interesting ones.

White to move
Is the triplet 26/31/37 what you mean by a pin? In any case, I would call 37-32 26x37 32x41 an exchange (this particular one happens a lot in games). Is this not explored by your special QS generator? I guess there is similar tactical potential compared to unpinned exchanges, see e.g. the diagrams below with white to move


-
- Posts: 36
- Joined: Thu Sep 24, 2009 18:17
Re: Scan
Bert,
Wouldn't your large arrays cause memory stalls due to not fitting in the L1/L2 caches?
I was thinking of something simple like the following (in C, a la Moby Dam style)
to be called like
etc.
Wouldn't your large arrays cause memory stalls due to not fitting in the L1/L2 caches?
I was thinking of something simple like the following (in C, a la Moby Dam style)
Code: Select all
int i8(bitboard *bb, u64 mask)
{
u64 pcbit, empty;
int x;
empty = ALL50 - bb->white - bb->black + bb->kings;
x = 0;
while (mask != 0)
{
pcbit = mask & -mask;
mask -= pcbit;
x = 3*x + 2*((bb->black & ~bb->kings & pcbit) != 0) + ((empty & pcbit) != 0);
}
return x;
}
Code: Select all
i8(&brd, (S01 | S02 | S06 | S07 | S11 | S12 | S16 | S17))
Last edited by Harm Jetten on Fri Jul 10, 2015 00:40, edited 1 time in total.
Re: Scan
I'm quite sure the method proposed will cause memory stalls, but as long as the overall speed does not decrease (or even increase) I don't careWouldn't your large arrays cause memory stalls due to not fitting in the L1/L2 caches?

It seems (in this case) that the program Scan was even a little faster with the large arrays.
And if (like Michel) the region size increases and the number of parameters grow to zillions (think Michel is now using 50M ), then bitboards might be the only option.
So calculate a hash based on the region and masked bitboards in that region, and then find the index (I think Michel mentioned the same several posts ago).
The main reason I tried the bitboard approach for the index is that I would like to have a full bitboard implementation and which only minor (or none) traces of mailboxes (think it is called this way in the chess world). Especially the incremental update of all these structures becomes a burden.......
As I also mentioned, it might be possible to include the Scan evaluation (without major changes), into a bitboard based program like Damage and Moby Dam, also with the "own" movegenerator.
Most likely (to be checked) only a simple shift of bitboards will be required to convert to Scan like Bitboards.
I'm very curious if it works, and what the performance would be on my faster system with 7P DB , and parallel search with 8 cores.
Bert
Re: Scan
Fabien, in Scan you init a sqrt array.
But in the 2 sqrt calls in the program, you seem to use the sqrt() function.
Or do I miss something?
Bert
Code: Select all
void math_init() {
for (int i = 0; i < 256; i++) {
Sqrt[i] = std::sqrt(double(i));
}
}
Or do I miss something?
Code: Select all
mob += sqrt(king_mobility(bd, from));
mob -= sqrt(king_mobility(bd, from));
-
- Posts: 285
- Joined: Tue Jul 07, 2015 07:48
- Real name: Fabien Letouzey
Re: Scan
The missing piece is in math.h:BertTuyt wrote:Fabien, in Scan you init a sqrt array.
But in the 2 sqrt calls in the program, you seem to use the sqrt() function.
Or do I miss something?
Code: Select all
inline double sqrt(int n) {
return Sqrt[n];
}
-
- Posts: 285
- Joined: Tue Jul 07, 2015 07:48
- Real name: Fabien Letouzey
Re: Scan
Consider my "exchange" as an attempt to translate ">= 0 capture" from chess, a key concept. Moving "pins" is not allowed (they are assumed absolute). The opponent must have a single way to capture the moving piece, and not be able to capture anything else with the same move. For completeness, the final capture is forward only (forward arrow?). This is just to simplify the code a little and focus more on "promising" tactical moves.Rein Halbersma wrote:
White to move
Is the triplet 26/31/37 what you mean by a pin? In any case, I would call 37-32 26x37 32x41 an exchange (this particular one happens a lot in games). Is this not explored by your special QS generator? I guess there is similar tactical potential compared to unpinned exchanges, see e.g. the diagrams below with white to move
...
-
- Posts: 285
- Joined: Tue Jul 07, 2015 07:48
- Real name: Fabien Letouzey
Re: Scan
Hi all,
Scan is now available on Harm Jetten's website:
http://hjetten.home.xs4all.nl/scan/scan.html
Many thanks to him!
It's the version that participated in the Computer Olympiad, with additional DXP support. Source code, an opening book, and 2-4 piece endgame tables are included. The 5-6 ones are available as separate downloads.
Enjoy Scan!
Fabien.
Scan is now available on Harm Jetten's website:
http://hjetten.home.xs4all.nl/scan/scan.html
Many thanks to him!
It's the version that participated in the Computer Olympiad, with additional DXP support. Source code, an opening book, and 2-4 piece endgame tables are included. The 5-6 ones are available as separate downloads.
Enjoy Scan!
Fabien.
-
- Posts: 782
- Joined: Thu Jun 20, 2013 17:16
- Real name: Krzysztof Grzelak
Re: Scan
Thank you for the program. Unfortunately, when running I get an error 0xc000007b.
-
- Posts: 36
- Joined: Thu Sep 24, 2009 18:17
Re: Scan
Krzysztof,
Try installing the latest Redistributable Package for Visual Studio 2013: vcredist_x64.exe at
https://www.microsoft.com/en-us/downloa ... x?id=40784
Try installing the latest Redistributable Package for Visual Studio 2013: vcredist_x64.exe at
https://www.microsoft.com/en-us/downloa ... x?id=40784
-
- Posts: 782
- Joined: Thu Jun 20, 2013 17:16
- Real name: Krzysztof Grzelak
Re: Scan
I have it installed and still the error is.Harm Jetten wrote:Krzysztof,
Try installing the latest Redistributable Package for Visual Studio 2013: vcredist_x64.exe at
https://www.microsoft.com/en-us/downloa ... x?id=40784