Scan

BertTuyt · Post by **BertTuyt** » Thu Jul 09, 2015 22:05

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.

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]];

The Index Table init code is below (quick and dirty , as i didnt give it much thoughts

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;
	}
}

additional code in the eval_init

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();
}

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

BertTuyt · Post by **BertTuyt** » Thu Jul 09, 2015 22:19

Herewith the output of the initial search of Scan on my faster system (included the modified evaluation table index).

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

>

Fabien Letouzey · Post by **Fabien Letouzey** » Thu Jul 09, 2015 22:26

BertTuyt wrote:Herewith the output of the initial search of Scan on my faster system (included the modified evaluation table index).

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 · Post by **BertTuyt** » Thu Jul 09, 2015 22:33

Herewith a screenshot of the optimization options i always use.

Bert

Rein Halbersma · Post by **Rein Halbersma** » Thu Jul 09, 2015 22:36

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.

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.

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.

With "pending" I meant that the side to move has to make a capture

White to move has a pending capture 31x22

"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?).

With "threatened" I meant indeed that the opponent will have to make capture on the last move

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.

I 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.

Thanks for your explanation, all is clear now

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).

Rein Halbersma · Post by **Rein Halbersma** » Thu Jul 09, 2015 23:13

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

Harm Jetten · Post by **Harm Jetten** » Thu Jul 09, 2015 23:33

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)

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;
}

to be called like

Code: Select all

i8(&brd, (S01 | S02 | S06 | S07 | S11 | S12 | S16 | S17))

etc.

BertTuyt · Post by **BertTuyt** » Thu Jul 09, 2015 23:57

Wouldn't your large arrays cause memory stalls due to not fitting in the L1/L2 caches?

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 care

.
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

BertTuyt · Post by **BertTuyt** » Fri Jul 10, 2015 00:25

Fabien, in Scan you init a sqrt array.

Code: Select all

void math_init() {

   for (int i = 0; i < 256; i++) {
      Sqrt[i] = std::sqrt(double(i));
   }
}

But in the 2 sqrt calls in the program, you seem to use the sqrt() function.

Or do I miss something?

Code: Select all

mob += sqrt(king_mobility(bd, from));
mob -= sqrt(king_mobility(bd, from));

Bert

Fabien Letouzey · Post by **Fabien Letouzey** » Fri Jul 10, 2015 07:56

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?

The missing piece is in math.h:

Code: Select all

inline double sqrt(int n) {
   return Sqrt[n];
}

I don't like directly using arrays from a different module.

Fabien Letouzey · Post by **Fabien Letouzey** » Fri Jul 10, 2015 08:05

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
...

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.

Fabien Letouzey · Post by **Fabien Letouzey** » Sun Jul 19, 2015 19:07

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.

Krzysztof Grzelak · Post by **Krzysztof Grzelak** » Sun Jul 19, 2015 22:04

Thank you for the program. Unfortunately, when running I get an error 0xc000007b.

Harm Jetten · Post by **Harm Jetten** » Sun Jul 19, 2015 23:18

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

Krzysztof Grzelak · Post by **Krzysztof Grzelak** » Sun Jul 19, 2015 23:26

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

I have it installed and still the error is.

World Draughts Forum

Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan

Re: Scan