DTS-Algorithm Split Block

[JacobusOpperman]

Hi all.
I am currently trying to implement the Dynamic Tree Splitting (DTS) Algorithm to optimize my chess engine for multiple core processors. What is the data structure of the SPLIT BLOCK? I understand the SPLIT BLOCK must contain move lists, alpha and beta values etc. for each node up to the current ply. I have thought about one huge global multidimentional array but I don't think that will be practical because it will be to big. The problem is that the movelist to a specific node is local to that specific iteration of the alpha beta algorithm and I can't access it form outside that specific alpha beta function. I have also thought about passing the move lists on from all previous iterations that the alpha beta function has visited - I will then have all the move lists from all nodes that the alpha beta function has visited from the root node up to the current node which is only a subset of the game tree - I will then only be able to access movelists etc. of all nodes that are in the path of the search from the root node to the current node.

[BB+]

One thing you can do (and I think some Crafty versions have used it) is instead of having a local allocation for move lists, you instead have a local pointer to some place in a pre-allocated global slab for moves (quite large, say 64K or 1M entries). I'm not sure this answers your question or not, but if nothing else, it would be easier to pass around.

[JacobusOpperman]

Thank you BB+ for your reply - you have answered my question perfectly! I now think that pointers will do the job!

[hyatt]

Hi all.
I am currently trying to implement the Dynamic Tree Splitting (DTS) Algorithm to optimize my chess engine for multiple core processors. What is the data structure of the SPLIT BLOCK? I understand the SPLIT BLOCK must contain move lists, alpha and beta values etc. for each node up to the current ply. I have thought about one huge global multidimentional array but I don't think that will be practical because it will be to big. The problem is that the movelist to a specific node is local to that specific iteration of the alpha beta algorithm and I can't access it form outside that specific alpha beta function. I have also thought about passing the move lists on from all previous iterations that the alpha beta function has visited - I will then have all the move lists from all nodes that the alpha beta function has visited from the root node up to the current node which is only a subset of the game tree - I will then only be able to access movelists etc. of all nodes that are in the path of the search from the root node to the current node.

Parallel search dictates all of this, it is not a choice. Anything that is modified during a search has to be replicated if you are going to be doing N searches in parallel. IE below the split point, you need N different novelists, at the split point and above you only need one. DTS is quite good, but it doesn't dictate everything you do, because there are different ways of writing a search in general. So all it requires is enough private/thread-local data to be able to carry out a sub-tree search without wrecking what another thread is doing. In Crafty, since I do a recursive search and therefore can't quite do exactly what DTS does, a split block contains everything, for simplicity. But I do NOT copy a parent split block to its children, I only copy what is necessary, which does NOT include things from plies before the split point except for things like the repetition list.

The very first step in doing a parallel search is to take the search, q-search, eval, and anything else used (SEE, move ordering, move generation, hashing, etc) and take an inventory of EVERY variable that is used. Categorize them as either (purely local to a specific search (thread-local), global never changing (read only), global but modified (this is the dangerous one as locks are required to preserve integrity) and then things shared between some threads but not others. This lets you separate all the variables into categories. Some are easy to handle (global read-only is obviously trivial - you have to do nothing). Then once you have that, you then ask yourself "OK, some of these variables are used by a specific thread and allowing other threads to access them would make this not work (movelist for example), so do I need to replicate them entirely, or do I just need a part of the values (assuming an array)? If you look at Crafty's current "thread.c" code you will see CopyFromParent() when a parent splits into multiple child processes, and a CopyToParent() when a child completes the search and then returns some data back to the parent (PV, score, statistical data like nodes searched, etc). You can get an idea of what I copy, and for each variable array, how much of the array I copy.

If you don't start here first, you are going to be debugging for many years, because the bugs are subtle and hard to find. It is far better to design around them from the start. Because you will STILL have enough bugs to keep you busy.

BTW for Cray Blitz specifically, the 1989 or so source is publicly available. www.cis.uab.edu/hyatt/crafty/crayblitz. If you can read FORTRAN, you can see exactly what is done.

[JacobusOpperman]

Dr. Hyatt - thank you so much for your reply! I understand the DTS-algorithm much better now and I will definitely take a look at the Cray Blitz FORTRAN source code!

[BB+]

See also http://zct.sourceforge.net of course, the only open source DTS implementation.

[hyatt]

See also http://zct.sourceforge.net of course, the only open source DTS implementation.

I suppose Cray Blitz is "open source" since I posted it for anyone to look at use, and I don't think there were any restrictions on how it is used, directly.

I find it hard to look at fortran after programming in C for 30+ years now, however.