Re-Pair compression questions

[syzygy]

The decision tree is constructed by a greedy algorithm. First all possible predicates are evaluated for all positions in the tablebase, and the predicate that causes the largest reduction in entropy is chosen as the root of the decision tree. The procedure is repeated for a leaf node in the decision tree, by evaluating all possible predicates for all positions in the tablebase that correspond to the leaf node. The procedure stops when the tree has reached a given depth in all leaf nodes, or when no leaf node is worth splitting further because the entropy reduction would be too low.

Very interesting.

To construct the decision tree it might be sufficient to run tests on a large enough sample of all positions.

Does your algorithm also deal with partial don't cares such as positions with a drawing capture than can be encoded either as draw, cursed loss or loss?

[petero2]

The decision tree is constructed by a greedy algorithm. First all possible predicates are evaluated for all positions in the tablebase, and the predicate that causes the largest reduction in entropy is chosen as the root of the decision tree. The procedure is repeated for a leaf node in the decision tree, by evaluating all possible predicates for all positions in the tablebase that correspond to the leaf node. The procedure stops when the tree has reached a given depth in all leaf nodes, or when no leaf node is worth splitting further because the entropy reduction would be too low.

Very interesting.

To construct the decision tree it might be sufficient to run tests on a large enough sample of all positions.

Does your algorithm also deal with partial don't cares such as positions with a drawing capture than can be encoded either as draw, cursed loss or loss?

Yes, I already have code to sample a random subset of the positions. It can even adaptively add more samples until the confidence that it has found the best predicate is large enough. It works well near the root of the decision tree, but the deeper the tree becomes the fewer positions correspond to a single leaf node, so the sampling becomes less efficient.

My algorithm does deal with don't cares and partial don't cares, but I don't know how efficient it is compared to what you do.

Full don't cares (i.e. where there is a known optimal capture) are always encoded as 0, and the corresponding positions are not considered when building the decision tree.

Positions corresponding to partial don't cares are included when building the decision tree. When encoding the table, the partial don't cares are used to ignore "impossible" predictions from the decision tree, which has the effect that the stored value can become closer to 0 compared to if partial don't cares were ignored.

For example, assume the decision tree prediction for a position is 02134, which means:

Code: Select all

0, i.e. loss,         is the      most likely result
2, i.e. draw,         is the 2:nd most likely result
1, i.e. blessed loss, is the 3:rd most likely result
3, i.e. cursed win,   is the 4:th most likely result
4, i.e. win           is the 5:th most likely result

Without partial don't cares handling, this would mean the WDL values would be encoded as:

Code: Select all

WDL+  encoding
0     0
2     1
1     2
3     3
4     4

Further assume that the best capture has a value of 2 (draw). This means that the values 0 and 1 are impossible, so the encoding is modified to:

Code: Select all

WDL+  encoding
0     -   cannot happen
2     0
1     -   cannot happen
3     1
4     2

Also, my indexing scheme uses a fixed piece ordering, where "slower" pieces contribute with a higher factor to the index than "faster" pieces. There is no optimization to find the piece ordering that compresses best.

I have uploaded the source code to github in case you want to look at it, even though it is currently in a quite hacky state:

https://github.com/peterosterlund2/tbcomp