Search found 189 matches

by dragontamer5788
Mon Jun 24, 2019 4:31 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

In effect, the system I'm discussing here places CUT-nodes into a blocked list, while searching PV-nodes and ALL-nodes exhaustively in parallel. CUT-nodes continue to be sequential-only, but my hypothesis is that there are enough PV-nodes and ALL-nodes to keep a 16,000-thread machine busy It appear...
by dragontamer5788
Mon Jun 24, 2019 3:42 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

I admit I don't understand ABDADA yet. But as far as I'm aware, none of those schemes are work-efficient. Work-efficient means that if the serial implementation visits X nodes, then the parallel implementation visits exactly X nodes as well. That is to say: the parallel algorithm should perform exa...
by dragontamer5788
Sun Jun 23, 2019 2:55 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

From my understanding: a work-efficient parallel algorithm for Alpha-Beta search is already a "unicorn project" never seen before As you point out, Alpha-Beta pruning in parallel seems like an unsolved problem. But I hope to accomplish it in this topic. The algorithm to parallelize alpha-beta maxim...
by dragontamer5788
Sun Jun 23, 2019 2:27 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

Steven Edwards suggested a doubly-linked-list as data structure with spinlocks for parallel access, but I have never implemented and tested it: http://www.talkchess.com/forum3/viewtopic.php?t=40493#p425411 I took me some time to get into gpu programming and understand the architecture better, so so...
by dragontamer5788
Sat Jun 22, 2019 9:47 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

... I've searched for some of the words in your post, and apparently this old topic exists: http://www.talkchess.com/forum3/viewtopic.php?f=7&t=41853 I'll have to go through that topic and see what other parallel-methodologies were proposed and tried. I'll take a look at your code as well, and mayb...
by dragontamer5788
Fri Jun 21, 2019 5:35 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

Hello, Even if this is different in the objectives, you could consider as well Anka's work on Perft: https://github.com/ankan-ban/perft_gpu mph Thank you very much for this link. Its a good "companion project" because its looking at a lot of the bitboard-level optimizations, while my project is foc...
by dragontamer5788
Fri Jun 21, 2019 11:46 am
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

* Tomasulo's Algorithm -- https://en.wikipedia.org/wiki/Tomasulo_algorithm. Tomasulo's Algorithm is the CPUs use to discover which operations can be safely executed out-of-order. This algorithm "discovers" parallelism, even in the (seemingly sequential) CPU Assembly language. I hope to use Tomasulo...
by dragontamer5788
Thu Jun 20, 2019 8:38 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Re: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

Introduction ... As I program this, I'll update the thread. But I wanted to at least generate some discussion. Maybe someone else has made a system similar to mine that I should be aware of? Its always good to read other research papers on this subject. I tinkered a bit with gpu chess, maybe you fi...
by dragontamer5788
Thu Jun 20, 2019 7:50 pm
Forum: Computer Chess Club: Programming and Technical Discussions
Topic: Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search
Replies: 53
Views: 18571

Lazy-evaluation of futures for parallel work-efficient Alpha-Beta search

Introduction A few weeks ago, I theorized that GPUs can effectively perform work-efficient alpha-beta search. It led to a long discussion elsewhere on the internet, which pretty much ended with "If you think its possible, then you should do it". A couple of weeks later, here I am today ready to lea...