Author |
Topic: Thinking about starting a bot (Read 12305 times) |
|
lightvector
Forum Guru
Arimaa player #2543
Gender: 
Posts: 197
|
 |
Re: Thinking about starting a bot
« Reply #15 on: Nov 30th, 2014, 11:00pm » |
 Quote  Modify
|
I forget, and haven't tested in a long time. The last time, it seemed like the overhead from multithreading was minimal for not-too-large numbers of threads. Up to 4 threads, which is how many cores my desktop has, the nodes per second fairly closely scaled with the number of threads. This is not the same as a 4x speedup because of the wasted work and search inefficiency that's inevitable when parallelizing alpha-beta, but I don't remember it being drastically far off from that (probably at least >= 3x).
One thing that makes things nice is that the algorithm I implemented allows splitting and parallelizing in any way that maintains the "busy leaves" property: that the tree of nodes being actively searched is always the union of N paths where N is the number of threads, or equivalently that a thread never abandons a partially-searched node if it's the only thread at or in a subtree of that node (except if a beta cut occurs at that node or one of its ancestors). So as far as I'm concerned, there's no further work to be done on the fundamental algorithm, because already it has negligible overhead and gives complete flexibility. I might revisit if at some point in the future testing shows greater overhead with large numbers of threads.
The way that it's written, the code controlling the actual splitting policy is largely separate from the bulk of the multithreading infrastructure. I only have to tweak the functions that control when a thread wants to leave a node and where it jumps to when it does so, so I can change the splitting policy freely without touching any of the rest of the implementation. I haven't actually experimented a lot with the splitting policy though. I don't have any stats on it, the first few things I tried roughly seemed to work fine and I haven't gotten around to it again yet.
|
| « Last Edit: Nov 30th, 2014, 11:21pm by lightvector » |
 IP Logged |
|
|
|
n00bftw
Forum Full Member
Arimaa player #9394
Gender:
Posts: 15
|
|
Re: Thinking about starting a bot
« Reply #16 on: Dec 1st, 2014, 9:04pm » |
Quote Modify
|
Here's one thing that I still don't fully understand about parallel alpha-beta. Suppose a thread asks for help searching one of its child nodes. It will then continue on searching the next child node. At some point, the merge will need to occur in order for the work of the helper thread to be taken into account. (It could result in an update to the best score or a beta cut-off.) But the original thread that asked for help could be anywhere further down the tree. (If it is further up the tree, then that means it has reached a cutoff and should have cancelled its request for help.) Where, then, is the result of the helper thread stored? The state of the original thread is that it's searching further down the tree, and the helper thread is done and needs to look for new work. It seems like some other data structure is necessary to store the temporary state of any split point so that merging can be done later. If you follow me, how is this typically handled?
|
|
IP Logged |
|
|
|
lightvector
Forum Guru
Arimaa player #2543
Gender:
Posts: 197
|
|
Re: Thinking about starting a bot
« Reply #17 on: Dec 1st, 2014, 10:16pm » |
Quote Modify
|
I found it sufficient to just allocate a lock-protected node object with the following data every time you start searching a new node that you're allowing splitting at:
* queue of remaining unsearched moves (ex: array plus counter indicating the index of the next unsearched move).
* best score/alpha/move so far
* any other data you want to track, such as the PV
* count of how many results have been reported
* pointer to parent node
It's lock-protected because it's shared state about the search at that node, not thread-specific state. Threads grab moves from the queue, search them, then report the results back to the node. Once the final result is reported, the thread reporting the final result frees the node and reports the result to the parent node. (Beta cutoffs are handled as I described in an earlier post).
I used the words "allocate" and "free", but there's no need for dynamic memory allocation here. Busy-leaves guarantees that at most max_depth * threads (for example, 16*4) node objects can be needed at once so I just preallocate them all and reuse them in a pooled fashion. Some further cleverness makes it so that allocating and freeing from the pool only rarely requires a lock - most of the time the pool repeatedly hands the thread the same nodes it used before in a lock-free way.
At least in what I implemented, there's also no concept of "main" thread or "helper" thread. And there's no concept of "asking for help". The way it works is that there literally is a "search tree" consisting of chains of these node objects that threads allocate as they go. All threads are identical and work on the search tree in the same way - by repeatedly grabbing moves from nodes and reporting the results. Any thread that becomes free at any point scans the tree for the "best" node to join in and grabs a move from that node to work on, just like any other thread working on that node.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print