World Draughts Forum

It is currently Wed Jan 17, 2018 13:57

All times are UTC+01:00




Post new topic  Reply to topic  [ 162 posts ]  Go to page Previous 1 2 3 4 511 Next
Author Message
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 22:05 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
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:
 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:
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:
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


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 22:19 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith the output of the initial search of Scan on my faster system (included the modified evaluation table index).

Bert

Code:
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

>


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 22:26 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 238
Real name: Fabien Letouzey
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.


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 22:33 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Herewith a screenshot of the optimization options i always use.

Bert


Attachments:
Optimization.png
Optimization.png [ 22.44 KiB | Viewed 2044 times ]
Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 22:36 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1560
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.

Quote:
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

Image
White to move has a pending capture 31x22

Quote:
"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

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

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


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 23:13 
Offline

Joined: Wed Apr 14, 2004 16:04
Posts: 1560
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.

Image
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

Image

Image


Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 23:33 
Offline

Joined: Thu Sep 24, 2009 18:17
Posts: 35
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:
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:
i8(&brd, (S01 | S02 | S06 | S07 | S11 | S12 | S16 | S17))

etc.


Last edited by Harm Jetten on Fri Jul 10, 2015 00:40, edited 1 time in total.

Top
   
 Post subject: Re: Scan
PostPosted: Thu Jul 09, 2015 23:57 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Quote:
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 :D .
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


Top
   
 Post subject: Re: Scan
PostPosted: Fri Jul 10, 2015 00:25 
Offline

Joined: Wed Sep 01, 2004 19:42
Posts: 1303
Fabien, in Scan you init a sqrt array.
Code:
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:
mob += sqrt(king_mobility(bd, from));
mob -= sqrt(king_mobility(bd, from));

Bert


Top
   
 Post subject: Re: Scan
PostPosted: Fri Jul 10, 2015 07:56 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 238
Real name: Fabien Letouzey
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:
inline double sqrt(int n) {
   return Sqrt[n];
}

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


Top
   
 Post subject: Re: Scan
PostPosted: Fri Jul 10, 2015 08:05 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 238
Real name: Fabien Letouzey
Rein Halbersma wrote:
Image
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.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 19, 2015 19:07 
Offline

Joined: Tue Jul 07, 2015 07:48
Posts: 238
Real name: Fabien Letouzey
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.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 19, 2015 22:04 
Offline

Joined: Thu Jun 20, 2013 17:16
Posts: 573
Real name: Krzysztof Grzelak
Thank you for the program. Unfortunately, when running I get an error 0xc000007b.


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 19, 2015 23:18 
Offline

Joined: Thu Sep 24, 2009 18:17
Posts: 35
Krzysztof,

Try installing the latest Redistributable Package for Visual Studio 2013: vcredist_x64.exe at
https://www.microsoft.com/en-us/download/details.aspx?id=40784


Top
   
 Post subject: Re: Scan
PostPosted: Sun Jul 19, 2015 23:26 
Offline

Joined: Thu Jun 20, 2013 17:16
Posts: 573
Real name: Krzysztof Grzelak
Harm Jetten wrote:
Krzysztof,

Try installing the latest Redistributable Package for Visual Studio 2013: vcredist_x64.exe at
https://www.microsoft.com/en-us/download/details.aspx?id=40784


I have it installed and still the error is.


Top
   
Display posts from previous:  Sort by  
Post new topic  Reply to topic  [ 162 posts ]  Go to page Previous 1 2 3 4 511 Next

All times are UTC+01:00


Who is online

Users browsing this forum: No registered users and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB® Forum Software © phpBB Limited