Author: Vincent Diepeveen
Date: 12:09:10 09/10/02
Go up one level in this thread
On September 10, 2002 at 14:28:51, Guido wrote:
>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.
>>
>
>
>This is not clear for me. What do you intend for RAM on the indices
>(indexes?) ? I suppose you speak of additional tables for indexing and not of
>EGTBs.
>
>
>>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.
>>
>
>
>It is not necessary to have a table for 1891 positions and one for 1128
>position.
>The 62*61/2 table can be used for all the case N*(N-1)/2 with N <= 62.
>All these tables are contained inside the biggest. So 62*61/2 is the
>biggest table because kings are already positioned.
I do get the idea i could reuse it somehow but i don't understand it
completely.
suppose i have a chess board sized table [5][5]
for a board of 5x5 to place 2
pieces. lefttop = 0 of course. and entry 0 is illegal
because 2 pieces cannot be on the same square and
also second piece is at a higher square than the first:
table[5][5] = {
{-1, 0, 1, 2, 3},
{-1,-1, 4, 5, 6},
{-1,-1,-1, 7, 8},
{-1,-1,-1,-1, 9},
{-1,-1,-1,-1,-1} }
Now suppose i use this table to index it for 2 similar pieces
after 1 piece has been put already on the board.
then i do not see how i index into this table
anymore.
Can you give example how i index in this table after i have put
1 piece on the board?
Thanks,
Vincent
>
>>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
>>
>
>
>See what I said above.
>
>
>>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.
>>
>
>
>For 3 pieces or more IMHO it is convenient to use an algorithm not a table.
>In one direction (from positions to index) the algorithm is enough
>simple, in the inverse (from index to positions) you need to solve a
>diophantine equation with one only valid solution. But in both cases the
>cpu time could be made very short having a table of binomial
>coefficients.
>
>
>>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.
>>
>
>
>I discussed this point with Bob (he was right) in a past thread. The
>problem for my program is not very simple and for now I prefer not to
>take it into account.
>I consider only the case where ep capture is possible in the next move.
>
>
>>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?
>>
>
>
>The dimension of this table is for me:
>1806*48*47*60*59 or 1806*48*47*60*59/2 if AA are identical.
>IMHO it is difficult to avoid that a pawn occupies a king position
>because this would make indexing variable depending on the kings positions.
>I write a program that computes occupations of EGTBs until 9 men. My
>indexing scheme was designed by myself so it is similar but not identical
>to your and Heinz's scheme, also if many tables have the same
>dimensions.
>
>Ciao
>Guido
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.