Author: Robert Hyatt
Date: 07:53:44 07/19/99
Go up one level in this thread
On July 19, 1999 at 09:53:36, Vincent Diepeveen wrote: >On July 18, 1999 at 13:05:23, Francis Monkman wrote: > >> >>On July 18, 1999 at 12:56:35, Robert Hyatt wrote: >> >>>The idea sounds attractive, until you realize that the game tree search is >>>an exponential problem, not a linear one..... That makes it _very_ difficult >>>for such a task to be done on computers... >> >>But why not treat the computers as nodes in a tree, with sub-delegation >>software? (Just a thought -- but I built a working parallel audio synthesizer >>out of multiple TMS99000s back in '84, so I've been 'thinking parallel' for a >>while -- though not in chess. That's why I thought of you. Hope you don't mind) >> >>Say the machines are in a pool. Starting from root, one machine picks the next n >>(=number of legal moves) machines' addresses. Then they in turn pick 'em off the >>stack, and so on. Crazy? >> >>Francis > >Sounds like a deep blue parallellizing approach :) > I don't see where. DB uses _all_ processors on _every_ move. For any ply-1 move, the first 4 plies (one move each) are searched by one cpu. At this point the tree is split among _all_ the SP processors. Each processor then steps thru 4 plies (4 moves) and then uses its own private set of chess processors to search stuff there in parallel. And it gets a lot more complex after that as Hsu has a lot of 'pre-search' tricks to keep things busy... (See his thesis for details). DB's search is as good as anything we are doing when you use that many processors. It probably is better. Using 4 is not _nearly_ as hard as using 500. >Well Francis, i fear it's a bit off reality. > >Deep Blue had a similar approach: >first 4 ply: 1 SP processor >ply 5..8 : 30 SP processors >ply 8..12 : 480 hardware processors > >above is a similar idea, also not working that well. > >There are great dependancies: after first move has been searched one >can efficiently give other processors a job. Till then they're doing >nothing (assuming game start). > >example problem in your approach: if a processor finds somewhere that it >wins material, then isn't it a shame in your approach that they all >have done work for nothing, as they all are searching the same gamespace!
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.