Author: Simon Finn
Date: 16:43:16 09/09/02
Go up one level in this thread
On September 09, 2002 at 14:33:53, Vincent Diepeveen wrote:
>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.
Nalimov needs tables because his index scheme is irregular,
due to avoidance of non-blocking checks.
I think your simpler index scheme can be implemented with
fewer index tables (because it's more regular) at the
cost of a small run-time overhead.
>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 don't think you need these tables.
>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.
Right.
Each of the 1806 subspaces (where a "subspace" is the set
of positions defined by the kings) should use
48 * 61 * (60 * 59) / 2 or
47 * 61 * (60 * 59) / 2 or
46 * 61 * (60 * 59) / 2 positions
depending on whether either or both of the kings is on the
central 6 ranks.
So I want two tables here - both indexed by king position
(1) A table that records whether the multiplier for the
(first) pawn is 48, 47 or 46.
(2) A table that records the database index of the first
entry of each subspace.
[These tables are only necessary for databases containing pawns.
For pawnless databases, table (1) is clearly unnecessary.
Table (2) is also unnecessary since (in the absence of pawns)
all the subspaces have the same size so the start index of
each subspace can be found by a simple multiplication.]
For convenience, let's define some useful functions:
FI(N) counts the number of ways of placing I
identical pieces on N empty squares.
F0(N) = 1
F1(N) = N
F2(N) = (N * (N-1)) / 2
F3(N) = (N * (N-1) * (N-2)) / 6
F4(N) = (N * (N-1) * (N-2) * (N-3)) / 24
GI(M,N) counts the number of placements
that we've already examined before we place
the first of I identical pieces on square M
(numbering the first square 0 and the last N-1).
If I've got the maths right (it's late), we can
compute these as:
G1(M,N) = M
G2(M,N) = (M == 0) ? 0 : G2(M-1,N) + F1(N-M-1)
G3(M,N) = (M == 0) ? 0 : G3(M-1,N) + F2(N-M-1)
G4(M,N) = (M == 0) ? 0 : G4(M-1,N) + F3(N-M-1)
It's probably a good idea to precompute these
and store them in tables, unless you can find
a simple "closed form" for them. Each GI(M,N)
table has fewer than 4096 entries, so this
doesn't take much space (and the tables are
the same for all databases).
>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.
It can be done with much less RAM and a small (5 iteration max) loop
for each man.
Here's how we calculate the offset (within a subspace) of a position.
I don't want to write the actual code, so I'll do an example.
Suppose we have (after normalising the king positions):
White: K on b2, pawns on a2, c4, d2
Black: K on b4, bishop on c3
corresponding to board indexes (a1 = 0, b1 = 1, a2 = 8, ...)
White: K on 9, pawns on 8, 26, 11
Black: K on 25, bishop on 18
First we turn the K positions into a subspace number
(since we have pawns, this ranges from 0 to 1805).
Then we use table 1, indexed by subspace number,
to see that we have 46 squares available for occupation
by pawns.
So the number of positions in this subspace is F3(46) * F1(59).
We normalise the pawn indexes, sorting them into
ascending order 8, 11, 24.
For each piece that we place, we compute a number
which is its board index MINUS the number of
already-placed men that have smaller board indices.
For each pawn that we place, we do the same thing
except that we also subtract 8 (since the back rank
is inaccessible to pawns).
(This requires a small loop - over the positions of
at most 5 previously placed men.)
This gives us the numbers:
8-8 = 0 for the pawn on a2
11-2-8 = 1 for the pawn on d2 (-2 for P on a2, K on b2)
26-4-8 = 14 for the pawn on c4 (-4 for P on a2, K on b2, P on d2, K on b4)
18-3 = 15 for the bishop on c3 (-3 for P on a2, K on b2, P on d2)
This number is the "M" index for the corresponding man.
Then the index of this position within its subspace is:
((G3(0,46) + G2(1,45-0) + G1(14,44-1)) * F1(59)) + G1(15,59)
or more generally
((G3(p1,46) + G2(p2,45-p1) + G1(p3,44-p2)) * F1(59)) + G1(b1,59)
where p1,p2,p3 and b1 are the magic numbers (adjusted board indices)
that we computed for the pawns and the bishop respectively.
Finally we add the index of the first position within the subspace
and we get the database index for the entire position.
I hope the basic idea is clear from this sketch
(even though the details may well be off-by-one).
Simon
>
>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 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.