parallel alpha-beta pruning possible?
After watching this presentation[1] by Brian Goetz, in which he discusses the fork-join framework and how it is intended to be used I was left with a major question. Around the end of the talk he said and I quote ...fork-join can be used for game-tree exploration... while the slides actually had -Move generation -Alpha-beta ... As soon as I saw/heard that I almost fell of my chair!!! He caught me completely by surprise simply because I've given this quite a bit of though myself... NOw, I'm not implying that I am nowhere near as smart or informed as he is but the 'objection' I have is pretty simple. I already have a parallel minimax (some of you have actually helped) so I know how that's done and it wasn't too hard because minimax is exhaustive search. No heuristics whatsoever...as long as you work with immutable data-structures God is on your side and all is well! HOWEVER, as soon as you introduce heuristics (even simplistic like alpha-beta pruning) you 've lost the ability to split the work in pieces. You've suddenly introduced coordination which only makes sense in a serial fashion. Since pruning a particular branch of the game-tree requires knowing how the previous branch did how can you ever fork? What if these 2 branches are on separate threads? How can you ever do that without locking? I am very excited that someone like Brian Goetz is claiming something like this even though I don't understand how such an inherently serial process could be efficiently forked. Can anyone help? [1] http://www.infoq.com/presentations/brian-goetz-concurrent-parallel Jim -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: parallel alpha-beta pruning possible?
You will get better results from a game-programming forum, or indeed from a google search for parallel alpha beta than from a bunch of clojure guys with no particular experience in your problem domain. On Oct 16, 1:27 pm, Jim - FooBar(); jimpil1...@gmail.com wrote: After watching this presentation[1] by Brian Goetz, in which he discusses the fork-join framework and how it is intended to be used I was left with a major question. Around the end of the talk he said and I quote ...fork-join can be used for game-tree exploration... while the slides actually had -Move generation -Alpha-beta ... As soon as I saw/heard that I almost fell of my chair!!! He caught me completely by surprise simply because I've given this quite a bit of though myself... NOw, I'm not implying that I am nowhere near as smart or informed as he is but the 'objection' I have is pretty simple. I already have a parallel minimax (some of you have actually helped) so I know how that's done and it wasn't too hard because minimax is exhaustive search. No heuristics whatsoever...as long as you work with immutable data-structures God is on your side and all is well! HOWEVER, as soon as you introduce heuristics (even simplistic like alpha-beta pruning) you 've lost the ability to split the work in pieces. You've suddenly introduced coordination which only makes sense in a serial fashion. Since pruning a particular branch of the game-tree requires knowing how the previous branch did how can you ever fork? What if these 2 branches are on separate threads? How can you ever do that without locking? I am very excited that someone like Brian Goetz is claiming something like this even though I don't understand how such an inherently serial process could be efficiently forked. Can anyone help? [1]http://www.infoq.com/presentations/brian-goetz-concurrent-parallel Jim -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: parallel alpha-beta pruning possible?
On 16/10/12 21:48, Alan Malloy wrote: You will get better results from a game-programming forum, or indeed from a google search for parallel alpha beta than from a bunch of clojure guys with no particular experience in your problem domain. The question is more around JDK7 and reducers. Google gives me loads of results but it's all the traditional 'lock and suffer' approach. What I meant is basically this: let's forget about parallelism for a second...once someone has minimax ready it is a matter of minutes to turn it into an alpha-beta but in doing so you introduce dependencies between the branches and this is fine in a serial scenario. The minute forking occurs however you lose coordination capabilities (at least this is my understanding). He said it very casually in the video that is why this has been bugging me so much... obviously I'm wrong I'm just trying to find someone that knows a lot around reducers/fork-join t give me clues...thanks for your time anyway :-) Jim -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: parallel alpha-beta pruning possible?
scenario. The minute forking occurs however you lose coordination capabilities (at least this is my understanding). He said it very casually in the video that is why this has been bugging me so much... Fork/Join is just threads, so I'm not sure why you'd lose coordination capabilities. You can use all the normal coordination stuff like locks and mutexes, etc. Granted, it won't be pretty :) jack. -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
Re: parallel alpha-beta pruning possible?
I would probably look at the work that Robert Hyatt has done around parallel search in Crafty. He's published his findings far and wide and may still be active online. He's a wealth of information and fairly nice guy. -- -- http://blog.fogus.me -- http://github.com/fogus -- -- You received this message because you are subscribed to the Google Groups Clojure group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
