Cumulative building of a shared search tree

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

noobpwnftw
Posts: 193
Joined: Sun Nov 08, 2015 10:10 pm

Cumulative building of a shared search tree

Post by noobpwnftw » Wed Dec 28, 2016 10:50 am

I started this project a few years ago, in an attempt to build an opening book for Chinese chess(Xiangqi) automatically. It became stable last year and has been running ever since. Now it can be used as a fairly comprehensive opening book while actually it behaves more like a shared search tree with distributed workers extending its leaf nodes, and can be used as an "cheatsheet" for certain difficult positions, or working straight as a coordinated lazy-smp-style searcher. Although it has sieve policy during extending of the leaf nodes but due to the search space complexity I have no idea how it would become in the future, nor does it worth the effort after all.

In principle, it is a shared persistent hash storage with a set of utilities(background retrograde optimizer, distributed search coordinator, etc).

I wonder if there is any similar attempts made in chess, or any ideas regarding such kind of work. If there is enough potential I would also like to port my work from Chinese chess to chess and give it a try.

What do you think?

noobpwnftw
Posts: 193
Joined: Sun Nov 08, 2015 10:10 pm

Re: Cumulative building of a shared search tree

Post by noobpwnftw » Wed Dec 28, 2016 1:37 pm

Despite being used as a normal opening book, chess engines can probe it from root/low level depth search to get pre-calculated(stored) PV or sort of moves to improve their search, while in the same time deeper search results can contribute to the shared search tree in the form of leaf discovery.

While individual chess engines optimize on their own search/evaluation implementation, certain information can be shared by the nature of the chess game itself.

For example if you run Fishtest with one version which can probe the book against the other version which cannot, it will very likely to end up one-sided, because the shared search tree will be developed extensively for the positions involved.

You may argue that there are too many positions like this, but my observation from Chinese chess is that the search space will become convergent over time, after a large scale semi-brute-force development of leaf nodes.

elcabesa
Posts: 661
Joined: Sun May 23, 2010 11:32 am
Contact:

Re: Cumulative building of a shared search tree

Post by elcabesa » Thu Dec 29, 2016 7:29 am

I'm attempting building a similar tool for my chess engine.
Is your project available?

noobpwnftw
Posts: 193
Joined: Sun Nov 08, 2015 10:10 pm

Re: Cumulative building of a shared search tree

Post by noobpwnftw » Thu Dec 29, 2016 6:51 pm

Yes, it now contains about 300 million filtered positions(nodes) of which each move is evaluated & scored by no less than 20 plies.
It also includes DTC&DTM EGTB probing.

English version of my web query interface is:
http://www.chessdb.cn/query_en/

I'm currently in the process of building Chinese chess EGTB for up to 1TB physical memory(267,240,600,000 index space) which is I assume somewhere equivalent to 7-man tablebases for chess.

As you can imagine, it takes a good while(maybe forever) to run so I have some time to think about porting it to chess.

Main concern for me is that there are many variations of chess, and for some of them the search tree cannot be shared.

I also worry about the castling condition would introduce significant amount of "duplication", can we make the assumption that if the king and rook are in their original position, castling is always possible? I maybe wrong but I think it is very rare that castling can be the only good move or be considerably better than any other move for either side. Then we can ignore this information in the database and filter the move out during each query.

Sven
Posts: 3573
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Cumulative building of a shared search tree

Post by Sven » Thu Dec 29, 2016 7:27 pm

noobpwnftw wrote:I also worry about the castling condition would introduce significant amount of "duplication", can we make the assumption that if the king and rook are in their original position, castling is always possible? I maybe wrong but I think it is very rare that castling can be the only good move or be considerably better than any other move for either side. Then we can ignore this information in the database and filter the move out during each query.
The typical assumption in chess endgame tablebases is that castling rights are *not* available even if king and rook are on the appropriate squares. But I think one could provide additional EGT for positions with castling rights. These would be much smaller than other EGT with the same number of pieces since each available castling right restricts the possible squares of at least one piece (a rook) to one of 64. Each move that reduces the available castling rights would be a conversion either to a different "special" EGT (if the opponent has castling rights as well) or to a "standard" EGT.

noobpwnftw
Posts: 193
Joined: Sun Nov 08, 2015 10:10 pm

Re: Cumulative building of a shared search tree

Post by noobpwnftw » Thu Dec 29, 2016 11:20 pm

You are right, in the endgames it is possible to make a subset for each castling condition if we have the "standard" tablebases, where this subset contains only the outcome of conversion to non-castling positions.

My question is that if I want to build a large database for the opening stage, can I assume that castling is always possible from the piece positioning only? When I probe it, I skip the castling move if the I cannot do castling, where my opponent(ply-1) thinks I can do castling and evaluated as so. Since it is rather unrealistic that one would move his king or rook back and forth and then perform castling without having a "better" way of not moving around at all. In other words, would my opponent get any advantage if I simply give him the opportunity to castle as long as his pieces is in place? If there isn't, then the search tree(or hash) can be consistent with less information.

Sven
Posts: 3573
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany

Re: Cumulative building of a shared search tree

Post by Sven » Fri Dec 30, 2016 12:09 am

noobpwnftw wrote:You are right, in the endgames it is possible to make a subset for each castling condition if we have the "standard" tablebases, where this subset contains only the outcome of conversion to non-castling positions.
That was almost what I meant, but not exactly. However, I had misinterpreted your post such that I thought you were talking about castling rights in endgames, which in fact you weren't ...
noobpwnftw wrote:My question is that if I want to build a large database for the opening stage, can I assume that castling is always possible from the piece positioning only? When I probe it, I skip the castling move if the I cannot do castling, where my opponent(ply-1) thinks I can do castling and evaluated as so. Since it is rather unrealistic that one would move his king or rook back and forth and then perform castling without having a "better" way of not moving around at all. In other words, would my opponent get any advantage if I simply give him the opportunity to castle as long as his pieces is in place? If there isn't, then the search tree(or hash) can be consistent with less information.
I think it would be a mistake to make any assumption about the existence of castling rights just from the piece positions. Why would you want to save these four bits and sacrifice accuracy for it?

phhnguyen
Posts: 264
Joined: Wed Apr 21, 2010 2:58 am
Contact:

Re: Cumulative building of a shared search tree

Post by phhnguyen » Fri Dec 30, 2016 2:36 am

noobpwnftw wrote:In other words, would my opponent get any advantage if I simply give him the opportunity to castle as long as his pieces is in place? If there isn't, then the search tree(or hash) can be consistent with less information.
- Castle moves are legal ones, of course it is unfair game when one side could do when other side has fewer moves / options to make
- Not sure how you implement your opening tree. Usually it is based on hash keys. In chess programmers count castle rights into hash key (XOR the hash key with a small table of 4 random numbers for 4 castle rights). Thus even for 2 similar board positions (which all positions of all pieces are the same), their hash keys may be not the same if their castle rights are not matched

noobpwnftw
Posts: 193
Joined: Sun Nov 08, 2015 10:10 pm

Re: Cumulative building of a shared search tree

Post by noobpwnftw » Sat Dec 31, 2016 10:23 am

Storage size is not a problem, I wish to seek the possibility of saving the extra calculation/evaluation of the "same position" with different castling rights, it now seems not very viable after your discussion.

It would be pretty much the same as my current Chinese chess implementation, can you kindly have a look and give me your thoughts?

BTW, a bit information about the board representation from my current project: bit-wise representation of FEN (I call it "bitfen") would be far more useful than anything else, because if you have a database large enough, you will eventually have a method of uniform distribution(hash index) to split it. It would become more flexible/efficient to walk through the database with bitfen and it compresses very well with radix trees.

phhnguyen
Posts: 264
Joined: Wed Apr 21, 2010 2:58 am
Contact:

Re: Cumulative building of a shared search tree

Post by phhnguyen » Sat Dec 31, 2016 12:20 pm

noobpwnftw wrote:Storage size is not a problem, I wish to seek the possibility of saving the extra calculation/evaluation of the "same position" with different castling rights, it now seems not very viable after your discussion.

It would be pretty much the same as my current Chinese chess implementation, can you kindly have a look and give me your thoughts?

BTW, a bit information about the board representation from my current project: bit-wise representation of FEN (I call it "bitfen") would be far more useful than anything else, because if you have a database large enough, you will eventually have a method of uniform distribution(hash index) to split it. It would become more flexible/efficient to walk through the database with bitfen and it compresses very well with radix trees.
I am not clear about the kind of your database: is it a kind of opening book or just a database of games?

For opening book / tree, I believe using hash keys is still the most compact and fastest one. Each node of the tree is a record of a 64-bit integer for hashkey, you may add some more bit for extra info such as scores. You don't need to store but can compute some other "standard info from only hash keys such as move, castle right...

I have used that kind of opening book for my very old Xiangqi program Saola. It can display the opening tree with some info such as the move name, the opening name, score... for each node. In other hand, I used other techniques to store games into databases (kind of a simple database) on another program XB (Xiangqi Browser).

Post Reply