Author: Robert Hyatt
Date: 09:08:54 08/19/03
Go up one level in this thread
On August 18, 2003 at 14:53:40, Gian-Carlo Pascutto wrote: >On August 18, 2003 at 13:35:00, Sune Fischer wrote: > >>Don't give him any good ideas, he is your rival! :) >> >>So your perspective please, on scale from 1 to 10, how hard is it to implement >>and "debug", or is it a one time deal, life is peacy, no worries from there on? >> >>I'm mainly concerned about non thread safe libraries, could be nasty, or what? > >Probably 11 or 12. > >I had a fair amount of programming experience before I did it, >but this was by and far the hardest thing I have ever done. > >For starters, there's the issue of getting the thing running parallel. >You probably didn't consider parallelism when designing your engine. >I guess nobody does except if they've already written one once. So, >expect messyness. Non-thread-safe libs shouldn't be an issue. (I >don't use libs except for the C library so I wouldn't really know, >but I assume that whatever the ones you need do is not something >that is critical to the search itself, in which case you can limit >their use to a master thread) > >So, you've got the thing running in parallel. Of course it's totally >buggy, but you don't notice that yet. Now you need some kind of algorithm. >The ICGA has approximately 2 or 3 articles about parallel algorithms. >You can throw the ones about ABDADA, PVS and EPVS in the trash. They >promise nice numbers. They work like horsecrap (or a cold shower, if >you went to effort to try them. Do a test with Amy first and save >disappointment later). The only interesting one is the one >about DTS from Robert. If you read it, you're in for another unpleasant >surprise. He doesn't describe the algorithm in nearly enough detail to be >useful, in fact many important things are missing. Not only that, but >there's some nice things in there, like the fact that it only works >for nonrecursive search algorithms (aka Stone Age Programming). But >what is useful to you is that it is a general description of how a >good parallel algorithm could work and the things you'll encounter. > Actually, it isn't "stone age programming". For the _optimal_ parallel search, a non-recursive search is better. It lets you choose a split point anywhere you want. With a recursive search, this is not possible without a huge amount of complex code to let you back your way out of a recursive call stack to get back to the point where you want to do something interesting, then recursively get yourself back to where you were. The "non-recursive search" was very good for that. CB wasn't designed that way by choice, however. Early FORTRAN did not support recursion, which meant that the loop approach was the only solution. For DTS to work well, it needs to see the entire state of the current game tree. With recursion, that's not doable. As the saying goes, "you pay your money and you take your chances..." >Now, get a pencil and paper. Or a whiteboard. Think very very hard >about how you want to divide up the tree, what datastructures you will >need, and what messy things you can encounter. Make your own algorithm. > >Try a first implementation. Oops, you forgot a datastructure or you >can't handle something you need to be able to handle. Back to the >whiteboard. Lather, rinse, repeat. > >Now, you're done, and you try the first testrun. It crashes before >finishing ply 1. Second cold shower: your usual debugging methods >are useless now and you are *soo* screwed because it's impossible to >reproduce anything (that's nondeterminism for you). Think about a >way to debug stuff. Spend time writing the new debug routines. >Spend much more time studying large logs for what went wrong. >Fix bug. Lather, rinse, repeat. > >At some point, it works reasonable enough that you can do your first >speedup measurements. If your algorithm was reasonable enough, this >will already be something decent (e.g. >1.5). Think about improvements. >Implement. Crash. Test. Test. Test. Test. Crash. Debug. Test. > >DOESN'T THAT SOUND LIKE A LOT OF FUN???? > >Once things are running reasonable enough, I didn't have much problems >with parallelism, in the sense that you do have to take it into account >when adding stuff to your search, but once you've been to the above, it'll >look easy in comparison. >I generally ignore all parallel stuff until I know something works well >anyway. There's no reason to bother with parallel effects until you know >it works, and most stuff I try doesn't work. So no problems there. > >In Leiden, Frans Morsch said 'Implementing a parallel search takes a year'. >I think that's slightly exaggerated, but he programs in assembler, so it won't >have been too far off. I think that's a great exaggeration, unless he talks about a DTS-like algorithm. For DTS, it took me a _year_ of full-time debugging, to get it to work correctly. The current Crafty approach took a couple of weeks from starting to working reasonably. There were a few more weeks worth of refinement over time, of course. > >If you wonder why I bothered to go parallel, I had three consecutive months >where I could work fulltime round-the-clock on the engine. I think quite a >bit of the above gets much harder when it has the be done in a few hours >each evening. So I went ahead with it. I don't regret it, but I wouldn't >want to go back either. > >-- >GCP
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.