In order to be able to look-up a chess position in an EG table base,
the indexing scheme must ensure that each position is translated into a
unique number. The indexing scheme largely determines the size of the
EGTB files, so the number of illegal positions that an indexing scheme
allows should therefore be kept to a minimum.

I can think of an indexing scheme that allows absolutely NO illegal
positions, so the size of the EGTB will be the theoretical minimal.

Here's the idea:
================

Before the index is calculated, each position is transposed by making
maximum use of all possible symmetries. If there are pawns on the
board, the stmK is constrained to the a-d files. If there are no pawns
on the board, the stmK is contrained to the a1-d1-d4 triangle. Nothing
new till here!

A 'data tree' is built by placing men in the following order:

depth = 0: stmK-sntmK pair, this forms 1806 (with Pawns) or 462 (no
Pawns) BRANCHES AT THE ROOT.
depth = 1: stm Pawns (placed as a group to minimize the index range),
and the possible squares
depend on the location of the sntmK (preventing unblockable
checks).
depth = 2: sntm Pawns, again: placed as a group and only considering
remaining free pawn squares.
depth = 3-6: stm Q-R-B-N
depth = 7-10: sntm Q-R-B-N

stm = side to move
sntm = side not to move

Ground rule is that, during the creation of all subtrees, the only
possible squares for placement of men are those that
result in legal chess positions (to prevent 'broken positions' in the
data structure). The maximal depth of such
an EGTB tree is 10, depending on the type of endgame.

The index of a position is simply the location of the position at the
leaves, counting from left to right. To calculate the index of a
position, the lookup routine has to traverse the tree from left to
right and add all the leaves that were visited to locate the position
(only branches 'to the left' of the position need to be visited). But
this might actually be a pretty fast calculation. Anyway, the endresult
will be that EGTB index range is minimal, resulting in small data files
and fast lookups.

My questions:
- does this make sense?
- did anyone try it before?
- if the answer is yes: what were the results?

Stef

As this is an incremental indexing scheme (you can only calculate the
index of a position starting from another position's index), I think
the calculations could be made much faster by adding a small number of
'anchor' positions: positions together with their indices, to give the
position tree search a good starting point.

For example: let's assume we have an EGTB file with a size of 1,800 MB,
using 7 bits per position; it will contain approximately 2E9 positions.
Due to the compactness of the index scheme we could allow, say, 4%
additional storage for anchor positions (these could be stored as the
header to the EGTB). The file size would increase slightly, from 1800
MB to1872 MB. If each anchor position + index requires 288 bits (my
first guess), then there would be room for 2E6 achor positions. So each
set of 1000 consecutive positions can have one anchor, and the search
only needs to traverse 1000 positions (max) instead of 2E9 positions
(max): a speed-up factor of 2 million at the cost of a 4% larger EGTB
file.


wrote:
In order to be able to look-up a chess position in an EG table base,
the indexing scheme must ensure that each position is translated into a
unique number. The indexing scheme largely determines the size of the
EGTB files, so the number of illegal positions that an indexing scheme
allows should therefore be kept to a minimum.

I can think of an indexing scheme that allows absolutely NO illegal
positions, so the size of the EGTB will be the theoretical minimal.

Here's the idea:
================

Before the index is calculated, each position is transposed by making
maximum use of all possible symmetries. If there are pawns on the
board, the stmK is constrained to the a-d files. If there are no pawns
on the board, the stmK is contrained to the a1-d1-d4 triangle. Nothing
new till here!

A 'data tree' is built by placing men in the following order:

depth = 0: stmK-sntmK pair, this forms 1806 (with Pawns) or 462 (no
Pawns) BRANCHES AT THE ROOT.
depth = 1: stm Pawns (placed as a group to minimize the index range),
and the possible squares
depend on the location of the sntmK (preventing unblockable
checks).
depth = 2: sntm Pawns, again: placed as a group and only considering
remaining free pawn squares.
depth = 3-6: stm Q-R-B-N
depth = 7-10: sntm Q-R-B-N

stm = side to move
sntm = side not to move

Ground rule is that, during the creation of all subtrees, the only
possible squares for placement of men are those that
result in legal chess positions (to prevent 'broken positions' in the
data structure). The maximal depth of such
an EGTB tree is 10, depending on the type of endgame.

The index of a position is simply the location of the position at the
leaves, counting from left to right. To calculate the index of a
position, the lookup routine has to traverse the tree from left to
right and add all the leaves that were visited to locate the position
(only branches 'to the left' of the position need to be visited). But
this might actually be a pretty fast calculation. Anyway, the endresult
will be that EGTB index range is minimal, resulting in small data files
and fast lookups.

My questions:
- does this make sense?
- did anyone try it before?
- if the answer is yes: what were the results?

Stef

wrote in message
ups.com...
In order to be able to look-up a chess position in an EG table base,
the indexing scheme must ensure that each position is translated into a
unique number. The indexing scheme largely determines the size of the
EGTB files, so the number of illegal positions that an indexing scheme
allows should therefore be kept to a minimum.

I can think of an indexing scheme that allows absolutely NO illegal
positions, so the size of the EGTB will be the theoretical minimal.

Here's the idea:
================

Before the index is calculated, each position is transposed by making
maximum use of all possible symmetries. If there are pawns on the
board, the stmK is constrained to the a-d files. If there are no pawns
on the board, the stmK is contrained to the a1-d1-d4 triangle. Nothing
new till here!

A 'data tree' is built by placing men in the following order:

depth = 0: stmK-sntmK pair, this forms 1806 (with Pawns) or 462 (no
Pawns) BRANCHES AT THE ROOT.

You need to get a member of ICGA

www.icga.org

There is several articles on EGTBs there in different journals.

In diep i do not keep remove all illegal positions, but i do take care that
each piece is at an empty
square.

Actually i might store pawns in less than what you describe.

you would use

1806 * 24 * 23 ...

Where i'm using less than that in fact.
I'm 100% avoiding positions with a 2 figures on the same square.

What i do not remove is when for example white is the side to move,
has a pawn on a2 for example with a black king on b3.

That situation could happen, whereas the black king is illegal on b3.

I tend to recall nalimov removes a few of those illegals, but not all.

depth = 1: stm Pawns (placed as a group to minimize the index range),
and the possible squares
depend on the location of the sntmK (preventing unblockable
checks).
depth = 2: sntm Pawns, again: placed as a group and only considering
remaining free pawn squares.
depth = 3-6: stm Q-R-B-N
depth = 7-10: sntm Q-R-B-N

stm = side to move
sntm = side not to move

Ground rule is that, during the creation of all subtrees, the only
possible squares for placement of men are those that
result in legal chess positions (to prevent 'broken positions' in the
data structure). The maximal depth of such
an EGTB tree is 10, depending on the type of endgame.

The index of a position is simply the location of the position at the
leaves, counting from left to right. To calculate the index of a
position, the lookup routine has to traverse the tree from left to
right and add all the leaves that were visited to locate the position
(only branches 'to the left' of the position need to be visited). But
this might actually be a pretty fast calculation. Anyway, the endresult
will be that EGTB index range is minimal, resulting in small data files
and fast lookups.

My questions:
- does this make sense?
- did anyone try it before?
- if the answer is yes: what were the results?

Stef

Vincent,

I am not using 1806 * 24 * 23 ... and never said that I did (and by
the way, I think it should be 1806 * 48 * 47 ... , because you already
have mirrored, or else you wouldn't end up with 1806 KK positions).

The whole idea of my scheme is that there are *no* broken positions,
by definition. Of course I do account for the placement of previous
men. If a King is placed on a 'pawn square', then that square is not
available for pawns. Even more so: the sntmK cannot be in check, which
excludes even more squares for stm pawns, depending on the sntmK
position.

Stef

snip
Actually i might store pawns in less than what you describe.

you would use

1806 * 24 * 23 ...

Where i'm using less than that in fact.
I'm 100% avoiding positions with a 2 figures on the same square.
snip

hi,

if you do 1806 * 48 * 47 then you will get positions with a pawn on a square
where a king is located already.

In diep's egtb scheme i'm avoiding that.

Vincent

wrote in message
oups.com...
Vincent,

I am not using 1806 * 24 * 23 ... and never said that I did (and by
the way, I think it should be 1806 * 48 * 47 ... , because you already
have mirrored, or else you wouldn't end up with 1806 KK positions).

The whole idea of my scheme is that there are *no* broken positions,
by definition. Of course I do account for the placement of previous
men. If a King is placed on a 'pawn square', then that square is not
available for pawns. Even more so: the sntmK cannot be in check, which
excludes even more squares for stm pawns, depending on the sntmK
position.

Stef

snip
Actually i might store pawns in less than what you describe.

you would use

1806 * 24 * 23 ...

Where i'm using less than that in fact.
I'm 100% avoiding positions with a 2 figures on the same square.
snip