N-ary Gray codes

[rjgibert]

I was wondering if n-ary gray codes are used in EGTBs or Bitbases?

http://en.wikipedia.org/wiki/Gray_codes#n-ary_Gray_code

The idea is that consecutive entries in the table will always differ by the position of one piece moved by one square. This would make consecutive entries more highly correlated and therefore more compressible.

It's an interesting notion - but I'm a little sceptical. You could probably build a proof of concept easily enough by taking an existing database and reworking it. See if it's better.

Normal indexing tends to do a similar thing - the lowest bit will correspond to some piece moved by 1 square.

The general concept might work even if this specific idea doesn't. The general principle here is to rework the indexing scheme in such a way as to group wins together (or draws or losses.)

One obvious scheme (and perhaps it's being used) is to have separate index for each piece, where you order them by the percentage of wins or losses. These could even be ordered in creative ways. For instance you might start by finding which piece on which square produces the most wins. Make that index zero. The second best square might be index 1 and so on. You could do another pass by starting with results of the first pass and order them in a similar way. For instance you might find that a white pawn on e7 gives the most wins - so make that square index zero for the pawn. Then you might build a second order index for the white king - perhaps discovering that a white king near this pawn on some square is the best location over all the database examples. Then you would make that index zero for the white king. You would probably have to settle on just 1 or 2 passes of this. But you could do these independently too - i.e. reorder indexes by the best square on average for each piece considered separately.

It seems like I read that something like this is being done already - some effort is taken to index the right pieces in the right order, but I think this is done to optimize the locality of the references for caching purposes - for instance sliding pieces should be in the most significant bits and pawn moves should be arranged so that pushing a pawn forward gets the next slot in the table.

I had a somewhat similar idea in combination with gray codes. With gray codes, any ordering of the squares 0 to 63 can be accommodated for a given piece.

[diep]

I was wondering if n-ary gray codes are used in EGTBs or Bitbases?

http://en.wikipedia.org/wiki/Gray_codes#n-ary_Gray_code

The idea is that consecutive entries in the table will always differ by the position of one piece moved by one square. This would make consecutive entries more highly correlated and therefore more compressible.

It's an interesting notion - but I'm a little sceptical. You could probably build a proof of concept easily enough by taking an existing database and reworking it. See if it's better.

Normal indexing tends to do a similar thing - the lowest bit will correspond to some piece moved by 1 square.

The general concept might work even if this specific idea doesn't. The general principle here is to rework the indexing scheme in such a way as to group wins together (or draws or losses.)

One obvious scheme (and perhaps it's being used) is to have separate index for each piece, where you order them by the percentage of wins or losses. These could even be ordered in creative ways. For instance you might start by finding which piece on which square produces the most wins. Make that index zero. The second best square might be index 1 and so on. You could do another pass by starting with results of the first pass and order them in a similar way. For instance you might find that a white pawn on e7 gives the most wins - so make that square index zero for the pawn. Then you might build a second order index for the white king - perhaps discovering that a white king near this pawn on some square is the best location over all the database examples. Then you would make that index zero for the white king. You would probably have to settle on just 1 or 2 passes of this. But you could do these independently too - i.e. reorder indexes by the best square on average for each piece considered separately.

It seems like I read that something like this is being done already - some effort is taken to index the right pieces in the right order, but I think this is done to optimize the locality of the references for caching purposes - for instance sliding pieces should be in the most significant bits and pawn moves should be arranged so that pushing a pawn forward gets the next slot in the table.

I had a somewhat similar idea in combination with gray codes. With gray codes, any ordering of the squares 0 to 63 can be accommodated for a given piece.

All this is interesting for compressing the EGTB, not to lookup.

Vincent

[Don]

I was wondering if n-ary gray codes are used in EGTBs or Bitbases?

http://en.wikipedia.org/wiki/Gray_codes#n-ary_Gray_code

The idea is that consecutive entries in the table will always differ by the position of one piece moved by one square. This would make consecutive entries more highly correlated and therefore more compressible.

It's an interesting notion - but I'm a little sceptical. You could probably build a proof of concept easily enough by taking an existing database and reworking it. See if it's better.

Normal indexing tends to do a similar thing - the lowest bit will correspond to some piece moved by 1 square.

The general concept might work even if this specific idea doesn't. The general principle here is to rework the indexing scheme in such a way as to group wins together (or draws or losses.)

One obvious scheme (and perhaps it's being used) is to have separate index for each piece, where you order them by the percentage of wins or losses. These could even be ordered in creative ways. For instance you might start by finding which piece on which square produces the most wins. Make that index zero. The second best square might be index 1 and so on. You could do another pass by starting with results of the first pass and order them in a similar way. For instance you might find that a white pawn on e7 gives the most wins - so make that square index zero for the pawn. Then you might build a second order index for the white king - perhaps discovering that a white king near this pawn on some square is the best location over all the database examples. Then you would make that index zero for the white king. You would probably have to settle on just 1 or 2 passes of this. But you could do these independently too - i.e. reorder indexes by the best square on average for each piece considered separately.

It seems like I read that something like this is being done already - some effort is taken to index the right pieces in the right order, but I think this is done to optimize the locality of the references for caching purposes - for instance sliding pieces should be in the most significant bits and pawn moves should be arranged so that pushing a pawn forward gets the next slot in the table.

I had a somewhat similar idea in combination with gray codes. With gray codes, any ordering of the squares 0 to 63 can be accommodated for a given piece.

All this is interesting for compressing the EGTB, not to lookup.

Vincent

I see your point, but I'm talking about both here to a certain extent.

My suggestion is to figure out which piece is least disruptive to the position and arrange to put those bits in the least significant positions. A move of this piece will not affect the caching behavior because 64 bits is pretty small and fits in the same line. If the compression of the database is superior we might even get an improvement in the lookup speed due to less cache thrash.

[diep]

I was wondering if n-ary gray codes are used in EGTBs or Bitbases?

http://en.wikipedia.org/wiki/Gray_codes#n-ary_Gray_code

The idea is that consecutive entries in the table will always differ by the position of one piece moved by one square. This would make consecutive entries more highly correlated and therefore more compressible.

It's an interesting notion - but I'm a little sceptical. You could probably build a proof of concept easily enough by taking an existing database and reworking it. See if it's better.

Normal indexing tends to do a similar thing - the lowest bit will correspond to some piece moved by 1 square.

The general concept might work even if this specific idea doesn't. The general principle here is to rework the indexing scheme in such a way as to group wins together (or draws or losses.)

One obvious scheme (and perhaps it's being used) is to have separate index for each piece, where you order them by the percentage of wins or losses. These could even be ordered in creative ways. For instance you might start by finding which piece on which square produces the most wins. Make that index zero. The second best square might be index 1 and so on. You could do another pass by starting with results of the first pass and order them in a similar way. For instance you might find that a white pawn on e7 gives the most wins - so make that square index zero for the pawn. Then you might build a second order index for the white king - perhaps discovering that a white king near this pawn on some square is the best location over all the database examples. Then you would make that index zero for the white king. You would probably have to settle on just 1 or 2 passes of this. But you could do these independently too - i.e. reorder indexes by the best square on average for each piece considered separately.

It seems like I read that something like this is being done already - some effort is taken to index the right pieces in the right order, but I think this is done to optimize the locality of the references for caching purposes - for instance sliding pieces should be in the most significant bits and pawn moves should be arranged so that pushing a pawn forward gets the next slot in the table.

I had a somewhat similar idea in combination with gray codes. With gray codes, any ordering of the squares 0 to 63 can be accommodated for a given piece.

All this is interesting for compressing the EGTB, not to lookup.

Vincent

I see your point, but I'm talking about both here to a certain extent.

My suggestion is to figure out which piece is least disruptive to the position and arrange to put those bits in the least significant positions. A move of this piece will not affect the caching behavior because 64 bits is pretty small and fits in the same line. If the compression of the database is superior we might even get an improvement in the lookup speed due to less cache thrash.

I found for supercompression of my EGTBs that PPM based compressors really worked well. Some supercompression guy also tested worlds best compressors at a few 5 men he downloaded from my ftp at the time.

PPM really kicks butt there as it is doing multidimensional compression, which is EXACTLY what EGTBs are about of course, as you can see indexation scheme also as a multidimensional form of representation.

6 pieces = 6 dimensions simply.

Now of course for compression more dimensions than 6 is interesting to find some sort of relationship to compress.

IMHO one should split compression and chess technical code from each other with respect to EGTBs, otherwise it gets one big buggy mess.