Author: Guido
Date: 11:28:51 09/10/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. > 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 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.