Breadth-first search: revisiting

[Sergei S. Markoff]

Couple decades ago there was some papers about best-first-like alternatives to PVS/negascout (SSS*, A*, Dual*, conspiracy numbers, MT-class searches and so on). Inspite of great hopes all of them was finally declined, mostly because of bad null-move behavior in such trees and also because of (probably) lack of RAM to provide high tree storage rate. Anyway, I think this schemes has a good potential. The problem of null-move in this framework was not enough explored (we all remember later finding about restricting null-move in PV nodes and so on). Also experimental engines used usual TT to store tree without serious exploration of possible alternatives. For example, current RAM volumes are enoght to store the whole search tree for some reasonable search time. Moreover, there is a lot possibilities to store only relevant parts of the search tree (for example, excluding moves that had "obvious" refutations — by killers and winning captures) or use usual PVS as "quiescence" for breadth-first search.

[smatovic]

> or use usual PVS as "quiescence" for breadth-first search.

hmm, a breadth-first search until RAM is full and then a depth first search, imo this could give new ideas to use the full capacity of the upcoming many-core processors.

--
Srdja

[Dan Andersson]

Some of the BFS approaches were shown to be equivalent to depth-first-search techniques and fatally there were improved DFS variants. Others proved to be ungainly in practice except for some domains.

There is still ongoing research. The current front runner is what's called Monte-Carlo Tree Search. MCTS is currently used in go, general game playing and planning. Even that search has problems with game trees with trap plays.

For a short video lecture on the subject:
Trade-Offs in Sampling-Based Adversarial Planning
http://videolectures.net/icaps2011_ramanujan_sampling/
A load of other videos on that site concerning the same subject.

There are lots of other talks and papers if one searches for MCTS, exploitation versus exploration and other subjects.

MvH Dan Andersson

[sje]

Long ago I thought of a search technique akin to MC breadth first searching; more recently I think it may be worth another look given the success of MC techniques used in the perft() estimation domain.

Also, back in those days (ca. 1984) my single-core computer ran at 8 MHz and had less than 1 MB RAM. The machine in front of me today has four cores at 2.67 GHz and 24 GB RAM, so some of the breadth first criticisms of the old days may not be applicable today.

[Dan Andersson]

That size memory will fill up surprisingly fast So fast it often becomes beneficial to throw away information and/or not actually commit searches to the tree under a certain threshold of visits.

Size of memory is also only one factor in implementations. The disparity in speed between registers, cache and main memory has in some way made certain things worse. I.e. you trade space with time and get hit by extra architecture related penalties. Trade worker speed with number of workers and information sharing penalties gets bothersome both for algorithmic and architectural reasons.

Hybrid approaches trying to keep track of the game state and vital information like if the game is hot or cold and modifying search based on that seem more pragmatic.

Other interesting approaches I've come across combine randomized components to speed up search. Got really blown away by is the Nagging Search idea by Alberto Segre.

MvH Dan Andersson

[smatovic]

Other interesting approaches I've come across combine randomized components to speed up search. Got really blown away by is the Nagging Search idea by Alberto Segre.

Interesting,
do you have already some kind of expirience with the Nagging Search?

--
Srdja

[Dan Andersson]

I've used it a couple of times to get a bit of a speedup on some combinatorial searches when hooking up three computers at home, one i3 at 3.7 GHz, an AMD Kuma at 3.2 GHz and an old P3 Coppermine at 1.3 GHz. It handles heterogeneous and fault prone resources gracefully too.

MvH Dan Andersson