Compression in chess programs.

[Antonio Torrecillas]

I have a few days with the subconscious hammering with a new idea, only this does not materialize as an algorithm. So I describe the idea and see if someone comes up with something.
Most algorithms and heuristics are intended to minimize the nodes visited during the search. So that irrelevant nodes are removed from the tree without exploring. In other words, our programs are building a compressed representation of the search tree.(Lossy because only some nodes are chosen)
this is the idea I want to explore:
a data compression algorithm can be rephrased to be used in a chess program?
Somebody has explored such a possibility?

My apologies to force you to think about a so weird idea.
Best regards. Antonio.

[mcostalba]

In other words, our programs are building a compressed representation of the search tree.

No, "compressed" is the wrong word: "partial" is the correct one.

There is no compressed tree, there is a partial tree, a sub-tree indeed. Two completely different things.

[lucasart]

My apologies to force you to think about a so weird idea.
Best regards. Antonio.

Weird indeed. In fact, I don't think you can materialize it into an algorithm, because it doesn't mean anything.
As pointed out by Marco, compression is a bijective operation. Selective search is searching a subtree. Absolutely no comparison can be drawn, and I really have no clue where you're trying to go with that.

[Rémi Coulom]

I don't know if it can be used in chess, but compression ideas have been applied to other games.

Not really in the sense of exploring a small subtree. This is not really compression, just trying to be clever when sub-sampling the whole tree.

But in games such as hex or go it makes sense to analyze a position with a collection of rules. Rules are such as "whenever A plays here, B replies there". Combining such rules can be a way to represent a huge search tree with a small set of rules.

Then you need different kinds of algorithms to operate over such a representation of search trees.

Rémi

[smatovic]

why not to keep some kind of compressed search-tree in memory and reuse it for the next iteration...like an hash-table but as tree organized...

--
Srdja

[Antonio Torrecillas]

Thank you for all your answers.

First , I want to point out that I agree to the obvious fact that only a partial tree is stored.
But I disagree that a compression is a bijective relation.If we compress audio there is no point in storing +80 KHz frequencies.So there is a partial information stored in the output stream.
Throwing out the irrelevant data can be seen as a compression technique.
I don't want to discuss the correct word to express Partial vs Compressed.
What really is interesting is the fact that some techniques used in chess have similarities with compression ones.
I want to explore the possibilities that some techniques used in compression have to be useful in chess programs. The purpose of each is different though.
Rémi can you point me to some paper or open source program where I can dig the use in other games ?
Merci beaucoup.
A+, Antonio.

[syzygy]

I don't want to discuss the correct word to express Partial vs Compressed.

But if you don't care about the correct words, you can stick the label "compression" on anything...

[syzygy]

Data compression can be useful in chess, though. Not to prune the tree, but to compress endgame tablebases.

Of course any tablebase can be compressed to nothing: the rules of chess allow you to reconstruct (decompress) any tablebase from nothing. But to make the compression useful you have to find a compromise between tablebase size, random access time, and to a lesser degree compression time.

If your aim would really be to store the whole search tree in a compressed form (which imho has little to do with actual searching), it is sufficient to store the root position: the whole search tree can be reconstructed (decompressed) from the root position. (Of course you have to fix the search algorithm, and you have to clear the hash table, and you also need to restrict yourself to a single-threaded search.)

I don't see how lossy compression would apply to search trees. Lossy compression means that the compressed object contains less information, but, when decompressed, is still "perceived" as the same object. This means that "lossy" is tied to a perception model. Otherwise almost anything would qualify as "lossy compression". Just throw away 99% of your data, and you can "lossily compress" everything by 99%...

What would be the perception model for search trees? I don't know one. The only way a given search tree is "perceived" is by the final evaluation and pv returned (and maybe some further information that is displayed such as node count).

[Rémi Coulom]

Well, if you look at it this way, any form of machine learning can be considered a form of compression. The evaluation function is a lossy compression of a search tree. Machine learning has been applied a lot to games, in that spirit.

Rémi

[wgarvin]

Well, if you look at it this way, any form of machine learning can be considered a form of compression. The evaluation function is a lossy compression of a search tree. Machine learning has been applied a lot to games, in that spirit.

Indeed. Data compression is actually closely related to artificial intelligence.