Dann Corbit wrote:I am wondering about Dieter's bitbase system.
Why did you not create every 5 man file? It seems a small cost.
What have your experiments shown for Elo difference?
Is the format of your bitbase files public?
I am guessing you just use the nalimov index scheme and the object of the lookup is 2 bits wide. Is that right?
Do you memory map the bitbase files? Do you load them into ram?
Dann, answers to your questions in the order they appear, and at the
end a sample, that shows how I implemented it.
I created kppkp and krpkr. kppkp needs "only" 2*18MB, krpkr needs
1806*48*61*60/5*2 = ~120MB already.
Loading all 5 men bitbases into RAM is too much for current desktop systems.
An idea would be to dynamically load interesting ones, depending on the
current board position.
No experiments about the Elo difference done.
The format is not public - the problem is, that it would be lots of work,
to document it. It is only documented by the actual implementation with
basically no comments
The implementation was more or less "ad hoc".
I am using an indexing scheme rather similar to the scheme of Nalimov. But they
differ in details - for example in the major to minor/pawn ordering of
the pieces for index calculation. Also I have no ep positions stored
(the probe function will just return BB_WORTHLESS in case, ep is set).
Nalimov shrinks the index space a bit, by avoiding to store some
"contact checks" - I don't use this idea. Would be a lot of work
to implement it, and make indexing functions much more complicated.
Space requirements can easily be calculated. For kxky and kxyk, x,y no pawn:
462*62*61
For kxkp
1806*48*61
etc. For win/draw devide by 8, win/draw/loss devide by 5 (see below).
462 is the number of legal K-K positions, where the white K is always
mirrored to the a1-d1-d4 triangle, and when on the diagonal a1-h8, the black
K is mirrored to the a1-h1-h8 triangle. 1806 is the number of legal
K-K positions, where the white K is always mirrored to the left half
of the board. That part of the index is calculated by a simple lookup
to a precalculated table (kk_array[wk][bk]).
For win/draw/loss tables, I store 5 positions in each byte (Heinz
stores 4 positions). Lookup works by:
- Code: Select all
static unsigned wdl_tab[5] = {1, 3, 9, 27, 81};
/* Careful: index evaluated twice! (Could be easily avoided) */
#define RES_WDL_POS(table, index, res) \
do \
{ \
unsigned ti = (index)/5; \
unsigned tim = (index)%5; \
res = (table[ti]/wdl_tab[tim])%3; \
} while(0)
3^^5=243, so 5 positions fit in one byte.
I load them into memory (no memory mapping, which would not port easily).
I am using a different method for "finding" the correct bitbase/probing function,
than the one described by Heinz. I basiscally use some tables indexed by the
the men on the board. I have pawn=1, knight=2, ...
So to access the kxky bitbases, I just use irec_kxky_tab[piece1-1][piece2-1].probefunc().
The caller will take care to get piece1 and piece2 into the right order. if piece1>piece2,
colors/board/stm will be mirrored (for positions without pawns, board
mirroring will not be needed). For example for kxky, I have:
(Some lines are a bit long - I fear the formatting will be f**ked up when displayed.)
- Code: Select all
typedef struct irec4_tab
{
int (*probe_func)(unsigned char **, int, int, int, int, int, int, int, int *);
const char *name;
unsigned char *bb_table[2];
unsigned long crc32[2];
unsigned flags;
unsigned len;
} IREC4_TAB;
/* [5][5] would be sufficient */
static IREC4_TAB irec_kxky_tab[5][8] =
{
/* Pawn */
{
{probe_kpkp, "kpkp", {NULL, NULL},{0x1b2bedd1UL, 0}, WDL, WDL_SIZE(KPKP_SIZ)}, /* kpkp */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0}, /* kpkn */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0}, /* kpkb */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0}, /* kpkr */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0} /* kpkq */
},
/* Knight */
{
{probe_kmkp, "knkp", {NULL, NULL},{0x0043461bUL, 0xff21e06bUL}, 0, WD_SIZE(KXKP_SIZ)}, /* knkp */
{probe_kmkm, NULL, {NULL, NULL},{0, 0}, NOTB, 0}, /* knkn */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0}, /* knkb */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0}, /* knkr */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0} /* knkq */
},
/* Bishop */
{
{probe_kmkp, "kbkp", {NULL, NULL},{0xfd331caeUL, 0x43c588e9UL}, 0, WD_SIZE(KXKP_SIZ)}, /* kbkp */
{probe_kmkm, NULL, {NULL, NULL},{0, 0}, NOTB, 0}, /* kbkn */
{probe_kmkm, NULL, {NULL, NULL},{0, 0}, NOTB, 0}, /* kbkb */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0}, /* kbkr */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0} /* kbkq */
},
/* Rook */
{
{probe_khkp, "krkp", {NULL, NULL},{0xf75df9cfUL, 0xd8ac90daUL}, WDL, WDL_SIZE(KXKP_SIZ)}, /* krkp */
{probe_khkm, "krkn", {NULL, NULL},{0xa3546575UL, 0x24edf19aUL}, 0, WD_SIZE(KXKY_SIZ)}, /* krkn */
{probe_khkm, "krkb", {NULL, NULL},{0xe6c2486eUL, 0xe7e1f204UL}, 0, WD_SIZE(KXKY_SIZ)}, /* krkb */
{probe_khkh, "krkr", {NULL, NULL},{0xa9d9fc99UL, 0}, WDL, WDL_SIZE(KXKY_SIZ)}, /* krkr */
{NULL, NULL, {NULL, NULL},{0, 0}, 0, 0} /* krkq */
},
/* Queen */
{
{probe_khkp, "kqkp", {NULL, NULL},{0x0ddf01e2UL, 0x09bc5e65UL}, WDL, WDL_SIZE(KXKP_SIZ)}, /* kqkp */
{probe_khkm, "kqkn", {NULL, NULL},{0x34954cd1UL, 0x2a1882fcUL}, 0, WD_SIZE(KXKY_SIZ)}, /* kqkn */
{probe_khkm, "kqkb", {NULL, NULL},{0x1993ac58UL, 0xae6a84d1UL}, 0, WD_SIZE(KXKY_SIZ)}, /* kqkb */
{probe_khkh, "kqkr", {NULL, NULL},{0x6c9d0eeaUL, 0x1d46e24dUL}, WDL, WDL_SIZE(KXKY_SIZ)}, /* kqkr */
{probe_khkh, "kqkq", {NULL, NULL},{0x06dcf330UL, 0}, WDL, WDL_SIZE(KXKY_SIZ)} /* kqkq */
}
};
For example the line
/* Knight */
{
{probe_kmkp, "knkp", {NULL, NULL},{0x0043461bUL, 0xff21e06bUL}, 0, WD_SIZE(KXKP_SIZ)}, /* knkp */
means, for knight vs. pawn, use the probe_kmkp (minor vs. pawn) function, "knkp"
means that the files on disk will be knkp.bbw and knkp.bbb; the two
NULL pointers will become dynamically allocated memory to the actual
data for wtm and btm when loaded from disk to RAM; then two CRC
checksums, to validate, that the files are not corrupted; the 0 means this is a win draw table -
for win/draw/loss there would appear the constant WDL, WD_SIZE() is a macro, that calculates
the size in bytes from the number of positions - it is the number of entries devided
by 8 rounded up.
The actual probing function then looks like
- Code: Select all
/* code assumes A1 is 0, H1 is 7 and H8 is 63 */
/* Nalimov's trick for saving a bit of space */
#define EXCLUDE3(sq, sq1, sq2, sq3) (sq-((sq>sq1)+(sq>sq2)+(sq>sq3)))
#define KXKP_INDEX(wk, bk, x, p) \
(kkpos[wk][bk]*61*48 + EXCLUDE3(x,wk,bk,p)*48 + (p)-8)
#define RES_WD_POS(table, index, res) \
do \
{ \
unsigned ti = index/8; \
unsigned tim = index%8; \
res = (table[ti]>>tim)%2; \
} while(0)
#define MIRROR_LEFTRIGHT(p) ((p)^7)
int probe_kmkp(unsigned char **table, int side, int piece1, int piece2,
int wk, int bk, int x, int p, int *score)
{
unsigned index;
int bit;
int res;
if (!table[side])
return BB_WORTHLESS;
if (col(wk) >= 4)
{
/* mirror the board left to right */
wk = MIRROR_LEFTRIGHT(wk);
bk = MIRROR_LEFTRIGHT(bk);
x = MIRROR_LEFTRIGHT(x);
p = MIRROR_LEFTRIGHT(p);
}
index = KXKP_INDEX(wk, bk, x, p);
RES_WD_POS(table[side], index, bit);
if (bit == BB_DRAW)
{
*score = 0;
res = BB_EXACT;
}
else
{
/* P-side wins, look for exceptions */
if (piece1 == bishop)
{
if (bk == A1 && p == A2 && (wk == C1 || wk == C2 || wk == C3))
return BB_WORTHLESS;
if (bk == A8 && p == A7 && (wk == C8 || wk == C7 || wk == C6))
return BB_WORTHLESS;
}
else
{
/* KNKP: Many exceptions */
if ((bk == A1||bk == A2) && (p==A2||p==A3||p==A4) && Distance(wk,bk) <= 3)
return BB_WORTHLESS;
if ((bk == A8||bk == A7) && (p==A7||p==A6||p==A5) && Distance(wk,bk) <= 3)
return BB_WORTHLESS;
}
if (side == black)
{
*score = 500;
res = BB_LOWER_BOUND;
}
else
{
*score = -500;
res = BB_UPPER_BOUND;
}
}
return res;
}
Note, that I always return the same score above, when won. This means, that
there might be no progress. But it does not matter, really - when the position
is at the root of the search, lookup will be done in the real TBs. Heinz
uses some scoring heuristics, that will guarantee, that there will be progress.
I was too lazy to implement it. It would not have any advantage either, when
you have TBs available at the root - just use some more time.
All of above is pure easy technics. Delfi seems to do wizzard things, however
Regards,
Dieter
Posted: 17 Jun 2005, 13:14