Returning to my tablebases after a while...
I am working out my last size optimization and I don't get the index function.
Let's take an example: KQQR-K
The array should be built (as far as I understand) this way:
In what way is the index wrong?
Does it not work as a minimal perfect hash?
White king: KW
Black king: KB
ix: 0..2016 (inside of envelope calculation as the outside was already overwritten
To compute an index from all pieces you might consider KB+64*(R+64*(ix+2017*KW)).
This is not minimally perfect as it does not take into avvount that two pieces are not allowed on same square and as "the unique triangle" does not give you unicity of positions as for instance: WKa1, Ra2 is equivalent to WKa1, Rb1 with rest of pieces mirrored along diagonal.
You have to make different groups and for each find the max-index...
1) WK & BK
... with an index for pawn-less you get 462 index numbers
2) if you have any pawns index them right after the kings, because they will reduce the possible number of squares for all following pieces, but not the other way round. max index = 6 rows = 48
3) n-like men (like your 2 queens):
the total squares left = x = 64 - 2kings = 62
the max index is then x * (x-1) / 2
or in general terms with n pieces x! / (n! * (x-n)!)
4) for single pieces the index is just the squares left
for your rook the max index = 64 - 2 - 2 = 60
then for each group you calculate the index
1) for the Kings you just look the value up in a table
2) for pawns the index is the square number - 8
3) for groups the index is harder to calculate
you have to order the pieces first.
for you 2 queen example: q1 = queen on the higher square, q2 = queen on the lower square
q1 * (q1-1)/ 2 + q2
if you now want to add a 3rd queen it would look like this: (again q1 > q2 > q3)
q1 * (q1-1) (q1-2) / 3! + q2 * (q2-1)/ 2! + q3
If it gets too complicated, try simplifying, say by using simple indexing and no mirroring and suchlike. Let every piece have 64 possible positions, kings too.
That is what I'll do next.
ps. "totally wrong" is not a good explanation of what is wrong with something. Try to give some example of how you notice a problem. Tell a story.
I have had recently confusion with indexing of similar pieces myself.
After some discussion in Winboard forum, someone pointed me to a solution
given in this forum by syzgyz here. From his explanation I wrote a simple c code
to test it.
for groups the index is harder to calculate
you have to order the pieces first.
for you 2 queen example: q1 = queen on the higher square, q2 = queen on the lower square
q1 * (q1-1)/ 2 + q2
if you now want to add a 3rd queen it would look like this: (again q1 > q2 > q3)
q1 * (q1-1) (q1-2) / 3! + q2 * (q2-1)/ 2! + q3
Ok I got this working, but it would be nice if I could inverse the formula: given a specific index (X), is there a formula which can generate q1, q2, q3, q4?
(And this without looping until you get there).
Thats very expensive! And you don't need it at all.
Where do you want to use that?
I cant think of any way other than looping at the moment:
Loop i = 63 to 0
if (index < i * (i-1) (i-2) (i-3) / 4!) {
q1 = i + 1;
break;
}
index -= q1 * (q1-1) (q1-2) (q1-3) / 4!;
Loop j = i to 0
if (index < j * (j-1) (j-2) / 3!) {
q2 = j + 1;
break;
}
index -= q2 * (q2-1) (q2-2) / 3!;
... and so on
... so you have to loop in the worst case 64 times. Maybe this helps you a little. Anyway, make sure that you lookup the factorials, calculating them each time new would be a waste of resources. Still the division is expensive and I can't think of a better way at the moment.
I'll study on that
I precalculate the factorials for speed before generating or probing.
I need the reverse function to be able to delete invalid positions and insert them on the fly when probing/decompressing.
I'm thinking now to create a few files with precomputed "same-men" indices. It will cost about 64 MB of memory so a function would be nicer.