Author: Tony Werten
Date: 13:55:06 03/03/06
Go up one level in this thread
On March 03, 2006 at 13:34:56, Gerd Isenberg wrote:
>>I can confirm your findings. There are a few points however.
>>
>>I couldn't get your values to work, in a few cases the magic number seemed to
>>map different bitboards to the same index.
>
>
>Back home i double checked it and found no error so far, i also report the
>number of possible states (1,2,4,8,16,32,64) - all unique indices.
>Do we have the same square mapping?
No. I didn't realize that...
I have the diagonals "padded" to 8 bytes.
So: {a1-h8,a2-g8+h1,a3-f8+g1-h2,...}
My thought was that I only needed 1 mask (a1-h8) and just shift it up or down,
which means the "wrong" bits would fall off.
>
>>
>>I then run the deBruijn generator myself, to get stuck on 40 values or so, for
>>wich it couldn't get a magic number.
>
>Ok, i told something from modified De Bruijns, but i didn't post the exact way i
>modify them. You are right - the pure De Bruijns are not sufficent for all rays.
>
>Here some more code snippets i use,
>32-bit release run takes 13 minutes on my box:
>
>void DBG::deBruijnFound(BitBoard deBruijn) const
>{
> BitBoard ray;
> for (int x = 0; x < 11; x++) {
> for (int sq=0; sq < 64; sq++) {
> for (int dir=0; dir < 4; dir++) {
> if (notAllreadyFound(sq, dir) {
> int count = checkMagicNumber(deBruijn, sq, dir, ray);
> if ( count >= 0 ) {
> // store and report found magic
> }
> }
> }
> } // sq
> dB -= 0x0005012000030104; // some "random" const
> } // x
>}
>
>// return: number of found states
>// or -1 if failed
>int checkMagicNumber(BitBoard deBruijn, int sq, int dir, BitBoard &d)
>{
> static BitBoard notBoarder[4] = {
> 0x007e7e7e7e7e7e00, // noEast-soWest
> 0x007e7e7e7e7e7e00, // soEast-noWest
> 0x00ffffffffffff00, // _north-_south
> 0x7e7e7e7e7e7e7e7e // _east_-_west_
> };
> static BitBoard one = 1;
> int count = 0;
> BitBoard t = 0;
> d = attackGetter[dir](one<<sq) & notBoarder[dir];
> clearLocks();
> do {
> unsigned int idx = (unsigned int)((t * dB) >> (64 - 6));
> if ( locked(idx) ) return -1;
> lock (idx);
> count++;
> t = (t-d) & d;
> } while (t);
> assert ( count == (1 << popCount(d)) );
> return count;
>}
OK, try removing the loop (for (int x = 0; x < 11; x++) ) with the
0x0005012000030104 constant addition, and just pump in random numbers. XiniX
needed 30 secs. "Lock" in XiniX is just defined as:
check|=1<<idx and "locked" as: if (check & (1<<idx)) but that's because I knew I
was looking for (idx<64)
Tony
PS I have actually used larger masks in some cases (including the border as long
as they aren't >6 bits) to get more information for a movecount table. That way
I get mobility_free_squares for free, only on the full ranks (7 moves) it might
be off by 1.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.