Welcome, Guest. Please Login or Register.
Mar 28th, 2024, 2:11pm

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 12275 times)
nbarriga
Forum Guru
*****



Almost retired Bot Developer

   


Gender: male
Posts: 119
Thinking about starting a bot
« on: Nov 20th, 2013, 10:01pm »
Quote Quote Modify Modify

Hi everybody, after a long time away from Arimaa, I was thinking about (re)starting a bot. I don't have much free time, so my ambitions are not high.
 
My plan is to build a simple, well designed C++11 bot suitable for people to use as a base for their own bots. It would include basic techniques: alphabeta(negamax, negascout or aspiration window), Hash move, Null move, killer move, history heuristic and maybe counter move heuristics.
 
At this point I'm deciding on basic stuff and could use some input:
 
1) Is everybody doing step-by-step search, or has anyone tried move-by-move? Is there strong evidence that one is better than the other?
 
2) Do bots usually generate all the steps or moves and then prune, or do you have an incremental move generation technique?
 
3) Has anyone experimented with parallel alphabeta (YBWC or ABDADA or something simpler)? Are bots playing at postal speeds significantly stronger that regular speed, or regular ones significantly stronger that Fast/Blitz, so that parallelism would be expected to help?
 
4) Any general tips/advice?
IP Logged
rbarreira
Forum Guru
*****



Arimaa player #1621

   


Gender: male
Posts: 605
Re: Thinking about starting a bot
« Reply #1 on: Nov 24th, 2013, 9:18am »
Quote Quote Modify Modify

on Nov 20th, 2013, 10:01pm, nbarriga wrote:

1) Is everybody doing step-by-step search, or has anyone tried move-by-move? Is there strong evidence that one is better than the other?
 
2) Do bots usually generate all the steps or moves and then prune, or do you have an incremental move generation technique?  

 
There is some confusion between these terms, so I'm not sure there's a difference any more. Either way you're exploring the tree of Arimaa moves, even if there are some differences in the details of how you do that.
 
It's definitely a bad idea to generate all moves for a position whenever your search function is called. Generating thousands of moves when you might have a cutoff means a lot of wasted effort to generate moves which will never be looked at. There are only two remaining options AFAIK - either generate the steps and recurse on each step, or generate moves in batches. To my knowledge, no one has ever done the latter but I think it's a sensible option as well.
 
A related (but different) question is how you do your iterative deepening - in my bot I deepen by whole moves on each iteration. I was never convinced that deepening step by step made much sense, but perhaps I misunderstand how the other bots do it.
 
Quote:
3) Has anyone experimented with parallel alphabeta

 
Yes, all of the current top bots use parallel search. All of them use YBWC I think.
 
The easiest way to do parallel search is to split parallel searches from the root node only (i.e. from the position on the board when it's the bot's turn to play. I believe bot_marwin works this way.
 
A slightly harder way (employed by my bot) is to split parallel searches on the root and all other leftmost nodes in the search tree. These nodes are easy to parallelize because no cutoffs can ever happen on them, so you can have a special search function for these nodes which generates all moves and does all the parallel searching stuff (leaving the rest of the bot nearly free of threading complications).
 
Other than that, you can go all out and parallelize on all/nearly all types of nodes of the search, or employ fancier algorithms like DTS. I think bot_sharp works this way.
 
Quote:
Are bots playing at postal speeds significantly stronger that regular speed, or regular ones significantly stronger that Fast/Blitz, so that parallelism would be expected to help?

 
Take a look at the postal mixer games from this year and previous years. A few different bots have played there (usually searching between 2 to 4 hours per move). Bots definitely take advantage of the additional search time.
 
There have been a few experiments on the elo gained by doubling the search time - from what I remember, this was usually 50-100 elo. But that's when playing against the bot itself or sometimes other bots, never humans so far AFAIK.
« Last Edit: Nov 24th, 2013, 9:53am by rbarreira » IP Logged
lightvector
Forum Guru
*****



Arimaa player #2543

   


Gender: male
Posts: 197
Re: Thinking about starting a bot
« Reply #2 on: Nov 26th, 2013, 9:14pm »
Quote Quote Modify Modify

For my bot, Sharp's search is sort of a hybrid between steps and moves. Moves can be anywhere from 1-4 steps, potentially all mixed together in the same move list. Each move is represented as a 32-bit integer where each 8-bit chunk represents a single step, with an 8-bit chunk of 0 meaning no further steps in that move.
 
Iterative deepening is done step by step, although I'm testing changing it to deepen 2 steps at a time. I don't think it makes a big difference overall though. How fast you deepen is purely a tradeoff between how much time you want to waste re-searching the shallow nodes of the tree and how "bumpy" you want your search results and achieved depth to be. In the abstract, I don't know what it even means for one rate of deepening to make more or less sense than another. I think the question is purely empirical and bot-specific. For example, I've recall hearing in the past about a chess developer or two experimenting with different higher or lower fractional rates for iterative deepening given that their bot had many fractional search extensions. And in a different game with an exceptionally low branching factor, depending on the game and bot, it might make sense to deepen 2 or more ply at a time.
 
Increased search time is definitely helpful. For small speedups, it seems to be about 1 Elo per 1% speedup for Sharp in self-play, which roughly agrees with 50-100 Elo per doubling, since it takes around 70 1% speedups to produce a doubling.
 
Sharp's parallel search is a little more complicated, but is conceptually nice in that are no distinguished nodes and no distinguished threads. You can split anywhere sufficiently high up in the tree and all threads follow the exact same algorithm. Which is the roughly the following, with appropriate synchronization.
 
1. If the current node has an available move to be searched, grab the move, make the move and produce a child node, then set the child node to be the current node.
2. Otherwise, if there are no available moves but not all moves have been finished (other threads have grabbed moves at this node but not finished searching them) then leave the current node. Among nodes anywhere in the tree with available moves that have had at least one move finished (satisfying YBWC), choose the "best" one and set that node to be the current node.
3. Otherwise, if there are no available moves and all moves have been finished, then this is the last thread out of this node, so clean up the current node, report the result to the parent, and then set the parent node to be the current node.
4. Repeat.
 
Threads poll up the tree every few thousand nodes searched or so to see if the branch they're in has been beta-cutoff at some parent node, the exact same way they poll every few thousand nodes to see if the search has run out of time. Both are handled the same way too - if the current node or any of its parents have been beta cut or the search has run out of time, then behave exactly as if there are no available moves at the current node (so every loop will have case 2 or 3 above until the thread is out of the cut branch) and also don't report or record any results in the process (no pv, no hashmove, etc). Relative to the number of nodes searched, it's actually quite rare to have a parent be beta-cutoff, so on average the slight delay and wasted work due to the polling interval is minimal.
 
Note that case 2 above is also quite rare, happening less than a few dozens of times in a usual search, so averaged across the search it's cheap to walk around the tree to find another good place to parallelize at. And there can be only at most depth * # of threads many nodes open in the tree at a given time.  
 
The tricky part is synchronizing everything properly, which is doable but still fairly nontrivial. I implemented this brand of parallel search mostly for the learning experience, not because I thought it would be a particularly huge improvement over a simpler method.
 
« Last Edit: Nov 26th, 2013, 9:32pm by lightvector » IP Logged
nbarriga
Forum Guru
*****



Almost retired Bot Developer

   


Gender: male
Posts: 119
Re: Thinking about starting a bot
« Reply #3 on: Nov 26th, 2013, 10:04pm »
Quote Quote Modify Modify

Thanks for the answers.
 
I'm curious about your move representation. You use 8 bits for a step, so I'm guessing 3 bits for the piece type (to index your bitboard), 3 for the piece index and 2 for direction? Or maybe 3 for X coord, 3 for Y and 2 for direction, since there can only be 1 piece at each position, so no need to distinguish piece type?
 
I guess you could even compress it to 6 bits, 4 to index which of the 16 pieces, 2 for direction.  
 
I guess my question is, is it worth it to use such a compressed step representation? Packing more information into it usually makes it easier to generate and apply moves with less instructions.
 
 
And since we're on the topic Cheesy do you use traditional bitboard representation? Something like 2 times 6 times 64bit integers?
 
 
IP Logged
rbarreira
Forum Guru
*****



Arimaa player #1621

   


Gender: male
Posts: 605
Re: Thinking about starting a bot
« Reply #4 on: Nov 27th, 2013, 2:54pm »
Quote Quote Modify Modify

on Nov 26th, 2013, 9:14pm, lightvector wrote:

I don't know what it even means for one rate of deepening to make more or less sense than another.

 
I don't think it makes sense to give a player less than 4 steps in any search. It would seem to favor cheap and meaningless threats from the opposing player which can easily be defended with 1-3 extra steps.
 
on Nov 26th, 2013, 9:14pm, lightvector wrote:
For example, I've recall hearing in the past about a chess developer or two experimenting with different higher or lower fractional rates for iterative deepening given that their bot had many fractional search extensions.

 
AFAIK (and I could be wrong) fractional depth for extensions doesn't mean that a player will only be allowed a restricted set of moves in their search. It just means that the decision to extend or not extend will be taken based on a fractional value.
 
Obviously in quiescence search you only allow captures, but that's OK since q-search has the stand-pat option (which is a way out in case none of the allowed moves are good).
IP Logged
lightvector
Forum Guru
*****



Arimaa player #2543

   


Gender: male
Posts: 197
Re: Thinking about starting a bot
« Reply #5 on: Nov 28th, 2013, 12:51am »
Quote Quote Modify Modify

Sharp uses 6 of the bits for source location and 2 bits for direction, such that masking off the 2 direction bits gives you the location index. For single steps, the piece type can be found if you know the board state prior to that step by just looking at that index in the board.  
 
There is also a special byte for "pass", which is distinct from the 0 byte that indicates "no more steps". Passing indicates the actual end of the turn, flipping the side to move, while a step or two followed by a zero byte indicates that these might only be some of the steps in the turn - unless the player has already used all 4 steps, the next level of recursion will continue to generate more steps and/or partial moves for the same player.
 
Sharp uses a combined 0x88 board and bitboard. Having both representations together is convenient, and the cost of keeping both updated is negligible, at least for my bot (only a few percent of the time is spent making moves).  
 
on Nov 27th, 2013, 2:54pm, rbarreira wrote:

 
I don't think it makes sense to give a player less than 4 steps in any search. It would seem to favor cheap and meaningless threats from the opposing player which can easily be defended with 1-3 extra steps.

 
That problem seems largely orthogonal to whether you search full moves or steps. Terminating the search at *any* point has the same problem. If you terminate the search with Gold having just finished his turn, it would seem to favor cheap and meaningless threats by Gold on the last ply, which could easily be defended if only Silver got to take his turn at all.
 
If the answer to that problem is "But you evaluate the position taking into account that it's Silver's turn", then that's the same answer for what to do when Silver has been allowed to make only two steps instead of only zero steps: "But you evaluate the position taking into account that Silver still has 2 steps left".
 
If instead the answer to that problem is "The q-search generates captures and maybe some basic defense moves, so Silver is still allowed to refute Gold's meaningless threats in some basic ways", then the answer is again the same for when Silver has been allowed two steps instead of zero before the depth limit is hit and quiescence search is started: "The q-search generates captures and basic defense moves, so in the q-search Silver is still allowed to extend his 2 steps up to 4 steps in some basic ways to refute Gold's meaningless threats."
 
It's not at all the same as restricting the set of legal moves to just those with two steps. That would only be the case if you went so far as to flip the side-to-move back to Gold after Silver made his two steps, and then continued q-search and/or evaluation as if it were Gold's turn again, which I agree is obviously crazy.
 
And yes, it seems extremely reasonable to also allow a stand-pat move if the search will end in the middle of that player's turn.
 
The fractional extensions in chess bots work a bit differently, yes. Still, the same overall principle applies. 12 step searches are much better at tactics than 10 step searches. But 10 step searches are much better than 8 step searches, and way, way cheaper than 12 step searches. Every time you increase the depth by a step or two, the tactical accuracy improves a fair amount, and the time required also increases a lot. So you deepen at a granularity such that the amount of repeated work is still pretty small, in exchange for the strength of the bot's move being as smooth and consistent as possible when it runs out of time. Which is good since your playing strength is somewhat more heavily determined by your worst blunders than by your best moves.
 
« Last Edit: Nov 28th, 2013, 11:15am by lightvector » IP Logged
rbarreira
Forum Guru
*****



Arimaa player #1621

   


Gender: male
Posts: 605
Re: Thinking about starting a bot
« Reply #6 on: Nov 28th, 2013, 1:58pm »
Quote Quote Modify Modify

on Nov 28th, 2013, 12:51am, lightvector wrote:
If instead the answer to that problem is "The q-search generates captures and maybe some basic defense moves, so Silver is still allowed to refute Gold's meaningless threats in some basic ways", then the answer is again the same for when Silver has been allowed two steps instead of zero before the depth limit is hit and quiescence search is started: "The q-search generates captures and basic defense moves, so in the q-search Silver is still allowed to extend his 2 steps up to 4 steps in some basic ways to refute Gold's meaningless threats."
 
It's not at all the same as restricting the set of legal moves to just those with two steps. That would only be the case if you went so far as to flip the side-to-move back to Gold after Silver made his two steps, and then continued q-search and/or evaluation as if it were Gold's turn again, which I agree is obviously crazy.
 
And yes, it seems extremely reasonable to also allow a stand-pat move if the search will end in the middle of that player's turn.  

 
Oh, now I see what you mean. Perhaps those things are natural consequences of the way your search works (and that of other bots that deepen step by step). For mine those would probably require some slight changes, which is why I had never interpreted things in the way you explained.
 
I may give it a try on my bot when I have the time.
« Last Edit: Nov 28th, 2013, 2:00pm by rbarreira » IP Logged
Hippo
Forum Guru
*****




Arimaa player #4450

   


Gender: male
Posts: 883
Re: Thinking about starting a bot
« Reply #7 on: Dec 30th, 2013, 3:07am »
Quote Quote Modify Modify

OK ... turn based bots used to have evaluation expecting the side to move just changed. If you want to make good step based bot, your evaluation must consider remaining steps to the player change what almost means you have to make 4 well coordinated evaluation functions.
« Last Edit: Dec 30th, 2013, 3:07am by Hippo » IP Logged

lightvector
Forum Guru
*****



Arimaa player #2543

   


Gender: male
Posts: 197
Re: Thinking about starting a bot
« Reply #8 on: Dec 30th, 2013, 7:19am »
Quote Quote Modify Modify

Or you just write a single evaluation function and add a small bonus for having more steps left, and make that bonus also increase if there are racy-type positions, like hanging or threatenable pieces, advanced rabbits, trap fights with elephants at different traps, etc.
 
If you really want, you can make some evaluation coefficients for things also vary slightly by number of steps, but simplest is to just rely on the search to figure out the tactics that depend finely on the exact number of steps. Ideally, qsearch should do most of that job.
« Last Edit: Dec 30th, 2013, 7:26am by lightvector » IP Logged
n00bftw
Forum Full Member
***



Arimaa player #9394

   


Gender: male
Posts: 15
Re: Thinking about starting a bot
« Reply #9 on: Jul 3rd, 2014, 11:00am »
Quote Quote Modify Modify

on Nov 26th, 2013, 9:14pm, lightvector wrote:
I implemented this brand of parallel search mostly for the learning experience, not because I thought it would be a particularly huge improvement over a simpler method.
 

 
What kind of speedup do you see with your current implementation?  This isn't quite DTS, is it?  Might DTS do better?
IP Logged
Kushiel
Forum Full Member
***



Arimaa player #9913

   


Gender: male
Posts: 16
Re: Thinking about starting a bot
« Reply #10 on: Sep 30th, 2014, 11:35am »
Quote Quote Modify Modify

In your initial post you mentioned that you were amenable to people using your bot as a base for their own bots. If that's still your intention, would you mind describing how to obtain the source code?
 
Of course, if you've changed your mind on making it available to other developers that's 100% fine. I'm just really lazy about porting my python code to c/c++ from scratch since it's been forever since I've touched c/c++.
IP Logged
n00bftw
Forum Full Member
***



Arimaa player #9394

   


Gender: male
Posts: 15
Re: Thinking about starting a bot
« Reply #11 on: Nov 4th, 2014, 5:30pm »
Quote Quote Modify Modify

Kushiel, I'd recommend bot_opfor if you want a bot with code that's relatively readable and has most search improvements plus a good eval function.  It's what I'm tinkering with at the moment.
 
It's written in D tango (I'd recommend the bundled compiler for simplicity's sake), and I doubt you've used that (I certainly hadn't), but the syntax, at least, isn't too bad.
 
I'm also curious about parallelization strategies.  Parallelizing the search only from the root moves seems like the simple, sensible solution.  (That way you just run completely independent searches.)  Further improvements would only be necessary if certain searches from the root took much longer than others.  I doubt that's true but maybe it is.
IP Logged
lightvector
Forum Guru
*****



Arimaa player #2543

   


Gender: male
Posts: 197
Re: Thinking about starting a bot
« Reply #12 on: Nov 4th, 2014, 11:30pm »
Quote Quote Modify Modify

Parallelizing the root only is not so good. You want to search the first move to establish a strong alpha bound before starting any searches on any of the remaining moves. But the first move itself has no good alpha bound, so searching the first move can often take vastly longer than any other move. If you're not at least multithreading all the way down the PV, you're getting very little benefit until this initial part of the search is done.
 
It's also common to see positions in the middle of messy fights where there are only a few reasonable moves, because all 4 steps need to be spent doing a few particular things to avoid disaster. In these positions, you can get a very small number of moves each taking a lot of time to search, with all of the other thousands of moves being shredded apart by alpha-beta and rejected extremely fast.
IP Logged
aaaa
Forum Guru
*****



Arimaa player #958

   


Posts: 768
Re: Thinking about starting a bot
« Reply #13 on: Nov 10th, 2014, 8:32pm »
Quote Quote Modify Modify

I would actually go further and say that the root should ideally *not* be parallelized at all, as the goal should be to try to incrementally improve the settled move as quickly as possible (rather than finishing the iteration thus per se), devoting all processing power to each move in turn in a hopefully decent order, as established by earlier iterations.
IP Logged
n00bftw
Forum Full Member
***



Arimaa player #9394

   


Gender: male
Posts: 15
Re: Thinking about starting a bot
« Reply #14 on: Nov 30th, 2014, 9:16pm »
Quote Quote Modify Modify

on Nov 10th, 2014, 8:32pm, aaaa wrote:
I would actually go further and say that the root should ideally *not* be parallelized at all, as the goal should be to try to incrementally improve the settled move as quickly as possible (rather than finishing the iteration thus per se), devoting all processing power to each move in turn in a hopefully decent order, as established by earlier iterations.

 
I think I agree, though do you think that practically, that will always be beneficial?  In opfor at a search of depth 12, with a good alpha bound (as lightvector pointed out is obviously important), many searches from the root take less than 10 microseconds.  I've no idea what the result would be if one attempted to use multiple threads on one of those very quick searches, but my guess would be that the increased overhead would outweigh the benefits.  Perhaps not, though, as 10 microseconds is still a rather long time in computing terms.
 
lightvector, would you mind sharing what speedup your current parallel version gives over your sequential one?
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.