Transposition driven scheduling

[Daniel Shawul]

Has anyone tried this algorithm for cluster search? The main advantage is that it is asynchronous and size of transposition tables grows with number of nodes. It has proven to be very effective for single-agent searches (IDA* and the like). Solving puzzles using TDS has given super-linear speed ups! Unfortunately there doesn't seem to be many attemps to use it for multi-agent searchs such as alpha-beta. I saw a paper from the inventors (Schaffer and Plaat) to use TDS + MTD(f). They mentioned the performance is as good as other contemporary parallelization methods (early 2000s), and may even outperform YBW since MTD(f) is faster than Negascout. I am not sure if this will hold at all if I try it now since ABDADA was mentioned as one of the algorithms that performed as good as the rest and this probably is not true now.

Anyway I want to try this not for Chess but for cluster search of UCT trees. It seems to be more suited for that than alpha-beta. I am trying to implement a cluster perft estimator which is a good playground. The perft estimator works pretty much like UCT growing trees and stuff. But if I just run separate perft estimators with out sharing nodes, it will not be very efficient. For the perft estimator that doesn't store the tree (depth-first searcher), this doesn't make a difference as one can simply run them independently and average the results. But perft-uct shapes the tree towards the larger subtrees to reduce variance as fast as possible and sharing is necessary. One idea i took from Mogo it to average the statistics of nodes at the upper parts of the tree. So every now and then, I call reduction operation (MPI_Allreduce to average) the statistics. This works well but its performance is limited. TDS scheduling OTOH is asynchronous and may be a better algorithm so I want to try it on perft first.

[bob]

Has anyone tried this algorithm for cluster search? The main advantage is that it is asynchronous and size of transposition tables grows with number of nodes. It has proven to be very effective for single-agent searches (IDA* and the like). Solving puzzles using TDS has given super-linear speed ups! Unfortunately there doesn't seem to be many attemps to use it for multi-agent searchs such as alpha-beta. I saw a paper from the inventors (Schaffer and Plaat) to use TDS + MTD(f). They mentioned the performance is as good as other contemporary parallelization methods (early 2000s), and may even outperform YBW since MTD(f) is faster than Negascout. I am not sure if this will hold at all if I try it now since ABDADA was mentioned as one of the algorithms that performed as good as the rest and this probably is not true now.

Anyway I want to try this not for Chess but for cluster search of UCT trees. It seems to be more suited for that than alpha-beta. I am trying to implement a cluster perft estimator which is a good playground. The perft estimator works pretty much like UCT growing trees and stuff. But if I just run separate perft estimators with out sharing nodes, it will not be very efficient. For the perft estimator that doesn't store the tree (depth-first searcher), this doesn't make a difference as one can simply run them independently and average the results. But perft-uct shapes the tree towards the larger subtrees to reduce variance as fast as possible and sharing is necessary. One idea i took from Mogo it to average the statistics of nodes at the upper parts of the tree. So every now and then, I call reduction operation (MPI_Allreduce to average) the statistics. This works well but its performance is limited. TDS scheduling OTOH is asynchronous and may be a better algorithm so I want to try it on perft first.

Several assumptions that are not proven/accepted. The most critical being "mtd(f) is faster than negascout." I spent over 6 months playing with mtd(f). If you use a very simple eval, it is good. But if you don't converge within 2-3-4 searches at one specific depth, it is slower. And with an eval that has lots of scoring terms, I could not even get CLOSE to the usual PVS search times, mtd(f) was always much slower, except for the rare cases.

[Daniel Shawul]

It looks like it is a tremendous win for computer Go according to this paper by one of its inventors. A speed up of 700x from 1200 processors while the other methods are stuck at 70x. Pretty impressive and could be the next milestone for computer Go imo. But i think Remi said that a speed up of 1,000,000 might not be enough to beat the best Go professionals without algorithmic improvements.