Breadth-first search: revisiting

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Sergei S. Markoff
Posts: 224
Joined: Mon Sep 12, 2011 9:27 pm
Location: Moscow, Russia
Contact:

Breadth-first search: revisiting

Post by Sergei S. Markoff » Tue Sep 13, 2011 5:01 pm

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.
The Force Be With You!

smatovic
Posts: 1159
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Breadth-first search: revisiting

Post by smatovic » Tue Sep 13, 2011 9:01 pm

> 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
Posts: 442
Joined: Wed Mar 08, 2006 7:54 pm

Re: Breadth-first search: revisiting

Post by Dan Andersson » Tue Sep 13, 2011 10:07 pm

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

User avatar
sje
Posts: 4675
Joined: Mon Mar 13, 2006 6:43 pm

Re: Breadth-first search: revisiting

Post by sje » Fri Sep 16, 2011 1:25 pm

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
Posts: 442
Joined: Wed Mar 08, 2006 7:54 pm

Re: Breadth-first search: revisiting

Post by Dan Andersson » Fri Sep 16, 2011 11:31 pm

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
Posts: 1159
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: Breadth-first search: revisiting

Post by smatovic » Sat Sep 17, 2011 7:45 pm

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
Posts: 442
Joined: Wed Mar 08, 2006 7:54 pm

Re: Breadth-first search: revisiting

Post by Dan Andersson » Sat Sep 17, 2011 11:33 pm

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

Post Reply