Welcome, Guest. Please Login or Register.
Jul 23rd, 2019, 12:44pm

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum Thinking about starting a bot


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Thinking about starting a bot
« Previous topic | Next topic »
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Thinking about starting a bot  (Read 9722 times)
lightvector
Forum Guru
*****



Arimaa player #2543

   


Gender: male
Posts: 196
Re: Thinking about starting a bot
« Reply #15 on: Nov 30th, 2014, 11:00pm »
Quote Quote Modify 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: male
Posts: 15
Re: Thinking about starting a bot
« Reply #16 on: Dec 1st, 2014, 9:04pm »
Quote Quote Modify 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: male
Posts: 196
Re: Thinking about starting a bot
« Reply #17 on: Dec 1st, 2014, 10:16pm »
Quote Quote Modify 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
Pages: 1 2  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Arimaa Forum » Powered by YaBB 1 Gold - SP 1.3.1!
YaBB 2000-2003. All Rights Reserved.