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.

[Edmund]

In EGTBs you don't store the position at all in the entry.

The procedure is, to convert the position into an index number which is then directly used to address the value of the position.

see http://chessprogramming.wikispaces.com/ ... bases#toc7

[rjgibert]

In EGTBs you don't store the position at all in the entry.

The procedure is, to convert the position into an index number which is then directly used to address the value of the position.

see http://chessprogramming.wikispaces.com/ ... bases#toc7

Yes, of course. But what I am proposing is to convert the index to its n-ary gray code and using that to index the table.

This tranformation conditions the table to be more compressible, by making all consecutive entries differ by the location of one piece moved by just one square. Note that the moved by one square aspect is not illustrated in the ternary example in Wikipedia, but this property can be imposed.

This transformation is economical enough to calculate to be worthwhile requiring as many iterations as there are pieces (obviously, you would unroll the loop). It would essentially be a base 64 version, however, mixed base is easy to implement if you want to restrict a king to a 10 square region for instance when exploiting symmetry to reduce the size of the table. BTW, the reverse transformation is not needed.

[Zach Wegner]

An interesting idea at least. I think for it to work as expected, we first need to turn the square of each piece into a Gray code, since you can move in steps of numbers besides 1. This is rather straightforward for rooks and bishops, which would be 8-ary and 15-ary respectively. I don't know how this would work for the other pieces. Queens would have to be 27-ary at the very least, but I don't see any obvious way to do it.

Also, don't you only want the reverse transformation? I.e. you have the Gray code of a position, but then you want to convert into the incremental representation.

[rjgibert]

An interesting idea at least. I think for it to work as expected, we first need to turn the square of each piece into a Gray code, since you can move in steps of numbers besides 1. This is rather straightforward for rooks and bishops, which would be 8-ary and 15-ary respectively. I don't know how this would work for the other pieces. Queens would have to be 27-ary at the very least, but I don't see any obvious way to do it.

Also, don't you only want the reverse transformation? I.e. you have the Gray code of a position, but then you want to convert into the incremental representation.

The shift in location of a given piece does not have to correspond to a legal move in chess, though such a bias in selecting the next square for a piece shift in position would increase the correlation between between consecutive locations even more.

As for your next point, you are correct! It is a bit confusing about which version of the tranformation is needed, but I think by working through a simplified example, it can be made clear, which of the 2, the forward tranformation or the backward tranformation is needed. In order to keep the example simple, I'm going to use the ternary version from the Wikipedia article, which I've borrowed:

Code: Select all

loc    pos
000 -> 000
001 -> 001
002 -> 002
010 -> 012
011 -> 010
012 -> 011
020 -> 021
021 -> 022
022 -> 020
100 -> 120
101 -> 121
     .
     .
     .

A number of things make this example, contrary to what we actually want. Only 3 squares and all 3 pieces can occupy the same square. Nevertheless it manages to be useful in illustrating, which version of the tranformation--forward or reverese--is needed.

The column on the left is interpreted as the actual position e.g. for 012 the 1st piece board position is 0, the 2nd piece board position is 1, etc.

The column on the right are the actual locations in the table.

The 1st 3 entries, 000, 001 and 002 are unchanged by the tranformation. The desired properties are maintained.

The next position, 012, gets stored in location 010. Comparing position 012 with the prior position 002, the position of only one piece was change and the position 012 was stored in the next location 010. The desired properties are maintained.

Continuing in this manner, it is apparent that the property of only one piece changing location in consecutive locations in the table is preserved.

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

a) this won't work in EGTBs very well. If you already have a specific EGTB then there is no need to lookup a different position than this one, if it works for that 'other entry' it also works for this entry of course. Either you have an EGTB or you do not. In the first case you can look it up anyway.

b) Yet another kind of Gray code is the single-track Gray code (STGC), originally developed by N. B. Spedding (NZ Patent 264738 - October 28, 1994)[15]

How on planet earth can someone have a patent in software?

Maybe i should register a shitlot?

Vincent

[Edmund]

I think for chess other concepts for square ordering improve compression much better.

For example for bishops: first all the white, then all the black squares.

[rjgibert]

I think for chess other concepts for square ordering improve compression much better.

For example for bishops: first all the white, then all the black squares.

This can be accommodated by Gray Codes.

[hgm]

I don't think there is much point in this. For one, normal array ordering does displace only a single piece in 63 out of every 64 cases. Secondly, in chess displacing a single piece by only a single square can mean all the difference between winning and losing.

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