Algorithm(s) for parallel tree search (Mr. Hyatt? Others?)

dshmeh · Post by **dshmeh** » Wed Jul 01, 2009 12:50 am

Would you please suggest a textbook or other book and/or reference or way to design parallel node search algorithm? I am experienced C/C++ programmer and am interested in researching this topic. Thanks.

bob · Post by **bob** » Wed Jul 01, 2009 1:11 am

dshmeh wrote:Would you please suggest a textbook or other book and/or reference or way to design parallel node search algorithm? I am experienced C/C++ programmer and am interested in researching this topic. Thanks.

The paper I wrote on the DTS parallel search algorithm is on my web page at www.cis.uab.edu/faculty/hyatt

The source for Crafty is available and has a ton of comments explaining how it works. There really isn't a "book" on the topic. alpha/beta search is a difficult computational problem to parallelize. It is inherently sequential in how it establishes the bound and then prunes against that bound. This means you can't search other branches until the first branch is completed to establish the bound.

My current approach is relatively simple, gives good performance for reasonable numbers of processors, and doesn't completely wreck the internal structure of the program.

Dann Corbit · Post by **Dann Corbit** » Wed Jul 01, 2009 1:12 am

dshmeh wrote:Would you please suggest a textbook or other book and/or reference or way to design parallel node search algorithm? I am experienced C/C++ programmer and am interested in researching this topic. Thanks.

Dann Corbit · Post by **Dann Corbit** » Wed Jul 01, 2009 1:29 am

bob wrote:
dshmeh wrote:Would you please suggest a textbook or other book and/or reference or way to design parallel node search algorithm? I am experienced C/C++ programmer and am interested in researching this topic. Thanks.
The paper I wrote on the DTS parallel search algorithm is on my web page at www.cis.uab.edu/faculty/hyatt

The source for Crafty is available and has a ton of comments explaining how it works. There really isn't a "book" on the topic. alpha/beta search is a difficult computational problem to parallelize. It is inherently sequential in how it establishes the bound and then prunes against that bound. This means you can't search other branches until the first branch is completed to establish the bound.

My current approach is relatively simple, gives good performance for reasonable numbers of processors, and doesn't completely wreck the internal structure of the program.

With the /faculty/ subdirectory, I get an error, though (ironically) this does work:
http://www.cis.uab.edu/faculty/

This link:
http://www.cis.uab.edu/hyatt/
Seems to work, and the folder with the paper is:
http://www.cis.uab.edu/hyatt/pubs.html

bob · Post by **bob** » Wed Jul 01, 2009 1:59 am

Dann Corbit wrote:
bob wrote:
dshmeh wrote:Would you please suggest a textbook or other book and/or reference or way to design parallel node search algorithm? I am experienced C/C++ programmer and am interested in researching this topic. Thanks.
The paper I wrote on the DTS parallel search algorithm is on my web page at www.cis.uab.edu/faculty/hyatt

The source for Crafty is available and has a ton of comments explaining how it works. There really isn't a "book" on the topic. alpha/beta search is a difficult computational problem to parallelize. It is inherently sequential in how it establishes the bound and then prunes against that bound. This means you can't search other branches until the first branch is completed to establish the bound.

My current approach is relatively simple, gives good performance for reasonable numbers of processors, and doesn't completely wreck the internal structure of the program.
With the /faculty/ subdirectory, I get an error, though (ironically) this does work:
http://www.cis.uab.edu/faculty/

This link:
http://www.cis.uab.edu/hyatt/
Seems to work, and the folder with the paper is:
http://www.cis.uab.edu/hyatt/pubs.html

I had forgotten about the web page reorganization. www.cis.uab.edu/hyatt/ is the right place for everything now. Thanks...

dshmeh · Post by **dshmeh** » Wed Jul 01, 2009 2:17 am

cap.connx.com ! what an incredible site!

Thanks for the reference and thank you Dr. Hyatt.

dshmeh · Post by **dshmeh** » Wed Jul 01, 2009 2:20 am

BTW, I grew up ('til 18) in Birmingham. I've been in Miami since graduating from LSU for about 20 years. I do miss that special fall air and the hills.

diep · Post by **diep** » Wed Jul 01, 2009 7:12 pm

dshmeh wrote:BTW, I grew up ('til 18) in Birmingham. I've been in Miami since graduating from LSU for about 20 years. I do miss that special fall air and the hills.

Good to explain, maybe it can serve as a replacement to see the Hills on TV?

Vincent

dshmeh · Post by **dshmeh** » Thu Jul 02, 2009 12:46 am

yea, who cares about my hills. Only hill climbing algorithms, etc matter here

Algorithm(s) for parallel tree search (Mr. Hyatt? Others?)

Algorithm(s) for parallel tree search (Mr. Hyatt? Others?)

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others

Re: Algorithm(s) for parallel tree search (Mr. Hyatt? Others