Index function

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

Index function

Postby EricLang » Tue Oct 28, 2008 9:41 am

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?
EricLang
 
Posts: 33
Joined: Wed Sep 03, 2008 5:31 am

Re: Index function

Postby koistinen » Tue Oct 28, 2008 10:43 am

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.
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm

Re: Index function

Postby EricLang » Tue Oct 28, 2008 11:54 am

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 :)
EricLang
 
Posts: 33
Joined: Wed Sep 03, 2008 5:31 am

Re: Index function

Postby Codeman » Tue Oct 28, 2008 4:56 pm

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
Codeman
 
Posts: 85
Joined: Fri Oct 19, 2007 7:50 pm

Re: Index function

Postby koistinen » Tue Oct 28, 2008 7:42 pm

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.
koistinen
 
Posts: 80
Joined: Fri May 02, 2008 7:59 pm
Location: Stockholm

Re: Index function

Postby Daniel Shawul » Thu Oct 30, 2008 12:31 pm

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
Daniel Shawul
 
Posts: 2
Joined: Thu Jul 20, 2006 10:21 am

Re: Index function

Postby EricLang » Thu Nov 06, 2008 12:58 pm

I think I can work it out now, thanks!
EricLang
 
Posts: 33
Joined: Wed Sep 03, 2008 5:31 am

Re: Index function

Postby EricLang » Sat Nov 08, 2008 6:03 pm

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).
EricLang
 
Posts: 33
Joined: Wed Sep 03, 2008 5:31 am

Re: Index function

Postby Codeman » Sat Nov 08, 2008 6:55 pm

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.
Codeman
 
Posts: 85
Joined: Fri Oct 19, 2007 7:50 pm

Re: Index function

Postby EricLang » Sat Nov 08, 2008 7:27 pm

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
 
Posts: 33
Joined: Wed Sep 03, 2008 5:31 am

Re: Index function

Postby EricLang » Sat Nov 08, 2008 9:38 pm

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...
EricLang
 
Posts: 33
Joined: Wed Sep 03, 2008 5:31 am


Return to Endgame Tablebases

Who is online

Users browsing this forum: No registered users and 1 guest