| |
Main
Date: 16 Jan 2007 01:39:52
From:
Subject: Generate and store EGTB's as a data tree
|
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
|
|
| |
Date: 03 Feb 2007 00:03:04
From:
Subject: Re: Generate and store EGTB's as a data tree
|
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>
|
| | |
Date: 14 Feb 2007 17:48:59
From: Vincent Diepeveen
Subject: Re: Generate and store EGTB's as a data tree
|
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
<[email protected] > wrote in message
news:[email protected]...
> 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>
>
>
|
| |
Date: 29 Jan 2007 16:06:44
From: Vincent Diepeveen
Subject: Re: Generate and store EGTB's as a data tree
|
<[email protected] > wrote in message
news:[email protected]...
> 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
>
|
| |
Date: 16 Jan 2007 23:41:29
From:
Subject: Re: Generate and store EGTB's as a data tree
|
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.
[email protected] 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
|
|
