Author: Vincent Diepeveen
Date: 11:33:53 09/09/02
Hello,
Sorry to not always use the correct english words in next
piece of questions.
I want to improve my indexing. It was very primitif, it was
meant to be primitif in past times, but i promised myself
that after world champs 2002 i would try to improve it.
Basically my aim is different from Nalimov. My aim is to get
rid of positions where 2 pieces are on the same square (which
in itself is illegal). nalimov also reduces illegal positions
where side to move is in check, that's right now *not* my aim
at all.
Second aim i have is to not waste too much RAM on the indices.
Of course RAM sizes increase, but i can't afford 160MB of indices
or something. RAM size is more important than time needed to
calculate index. If i can do with 4MB of indices instead of
40MB that's way more important from my viewpoint.
That generating 6 men is taking way longer then, that's no major
issue. My old generator was way faster (about 100 times) than
the new one is, but the old one did kings at the end at 4096
positions... ...too inefficient.
My current scheme is very simple:
i start nowadays with the kings first.
There is 2 choices then
no pawn ==> 2 kings need 462 positions
otherwise ==> 2 kings need 1806 positions
that's obviously including mirroring.
What i then do is very primitif i want to improve it.
If there is no pawn and no similar pieces for the same side,
say KRB KBN, then it would need for the next piece 62 positions,
then 61, 60 and 59.
From my viewpoint this is an ideal scheme for KRB KBN because not
a single piece is at the same square. In my search all positions
could potentially happen then i assume. Obviously getting twice in
check is not really possible unless the position is derived from
a doublecheck. That's not my aim. For KRB KBN i am HAPPY with
462 * 62 * 61 * 60 * 59 = 462 * (62!/58!)
However i added 1 way of the same piece. I have a table 64 * 64
which assumes a piece has 62 board positions and then i calculate
index for such pieces if 2 are the same. This table is not too
big but it only works real well for if the same pieces are
I call this the XX table.
There is also a PP table which is for 2 pawns. In both cases i
assume the table needs (62*61) / 2 = 1891 positions for 2 pieces,
and 1128 for 2 pawns.
I also apply it for pieces after it. I list pieces in a certain
order. My order is real simple: first the 2 kings, then pawns of
the left side, then pawns of the right side, then all remaining pieces
and i start with 'white' (=first side) and the lowest piece (knight)
and stop at queen.
A simple loop it is sirs. This loop is the fastest way to do it.
Now i just need better tables.
So current scheme goes wrong if i have for example
KRPknn
Because i list that as:
KkPRnn
So i use then for this EGTB about:
1806*48*61*(62*61/2) = 1806 * 48 * 61 * 1891 positions
That's not ideal. There are 2 things to optimize. First big
optimization is that i don't use 62*61 for that table but less.
However i don't want keeping making tables to mirror, because i also
want a table for 3 and 4 the same pieces. And for the table for 4
the same pieces i don't want to use 64^4 = 4096^2 = 16M entries. Note
that i index everything in 64 bits. So that's a direct 128MB i need
for that single table. That's TOO big. I feel it can be done with less
RAM without needing a huge loop.
The Heinz writing in Advances in ICCA 9 is as usual unreadable here.
To my big amazement with this very primitif scheme i need very little
positions for all 5 men. About 34G.
Of course everything is without en passant here, because en passant is
a lineair overhead and very small. I never consider it for main calculations,
because it is a very small part of the total size of the egtb as you need
2 trivial conditions for it which limit the space incredible.
For the table calculation en passant doesn't matter at all in fact. It's
just an extra 'if then else' with basically the same math but then without
the 2 pawns and extra conditions. Not trivial to make, but it's not important
for this posting here which is only intended to improve my scheme.
Next 2 postings i will show how much i need for all 5 men and then
what i need for all 6 men. For the 5 men the above scheme is ok to use,
though it can be improved obviously. For the 6 men it's simply too rude.
What i want to improve when we talk about that 6 men KkPRnn
is 2 things
a) less space for tables to mirror for the same pieces
b) a method to take into account that the pawn doesn't always have
48 squares, but the Kk symmetry eliminates it. Of course
i can very primitively use a big table:
KkP = 64^3 positions.
But i run into trouble for for example
KkPPPP
or
KkPpAA where AA = any pieces you want to except king.
the problem is here again i need with my current dumb lookup
method 64^4. Any way to improve upon this such that i do not
need to put a pawn on the square of a king?
Thanks in advance,
Vincent
This page took 0.01 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.