Index function

[EricLang]

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:

Code: Select all

1. K = 0...9 (the unique triangle)
2. Q1 = 0...63
3. Q2 = Q1 + 1...63
4. R =  0...63
5. K = 0..63

First this formula I get from a previous post does not seem to give the right index:

Code: Select all

ix = q1 + q2*(q2-1)/2

Testing in delphi code:

Code: Select all

  for q1 := 0 to 63 do
    for q2 := q1 + 1 to 63 do
    begin
       ix = q1 + q2*(q2-1)/2 // gives the wrong index
    end;

How should I calculate the index for the delphi example?
And after that, how should I calculate the index for the 5-piece example?

[koistinen]

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.

[EricLang]

Well, the index function in the delphi example just gives totally wrong indices.

And I was wrong with my KQQK-K example. I forgot I already had a fixed array for all legal king-combinations in a no-pawn situation.

Code: Select all

1. WK+BK = 0...563 (all legal king combinations)
2. Q1 = 0...63
3. Q2 = Q1 + 1...63
4. R =  0...63

But that does not matter much.
How to get an index from any combination?
I am not very good in mathematics

[Codeman]

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

4th queen:
q1 * (q1-1) (q1-2) (q1-3) / 4! + q2 * (q2-1) (q2-2) / 3! + q3 * (q3-1)/ 2! + q4

4) for single pieces the index is just the square



Then you are able to calculate the total index:
i = kings_index * queens_maxindex * rook_maxindex + queens_index * rook_maxindex + rook_index


regards Edmund

[koistinen]

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.

[Daniel Shawul]

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.

Look in the following link
http://www.open-aurec.com/wbforum/viewtopic.php?t=49559

My quest begins here
http://www.open-aurec.com/wbforum/viewtopic.php?t=49545


P.S:

I forgot about the existence of this forum for a while. There are really
some good technical discussions about endgames which I enjoy reading now!

Good work guys
Daniel

[EricLang]

I think I can work it out now, thanks!

[EricLang]

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

4th queen:
q1 * (q1-1) (q1-2) (q1-3) / 4! + q2 * (q2-1) (q2-2) / 3! + q3 * (q3-1)/ 2! + q4

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).

[Codeman]

q1 * (q1-1) (q1-2) (q1-3) / 4! + q2 * (q2-1) (q2-2) / 3! + q3 * (q3-1)/ 2! + q4

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.

[EricLang]

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.

[EricLang]

Ok, good news. The precomputed file for 4 same pieces is just 2,5 MB so this saves me a lot of puzzling. To be continued...