Welcome, Guest. Please Login or Register.
Jun 17th, 2019, 11:59am

Home Home Help Help Search Search Members Members Login Login Register Register
Arimaa Forum Time spent on search vs. evaluation


   Arimaa Forum
   Arimaa
   Bot Development
(Moderator: supersamu)
   Time spent on search vs. evaluation
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Time spent on search vs. evaluation  (Read 1066 times)
n00bftw
Forum Full Member
***



Arimaa player #9394

   


Gender: male
Posts: 15
Time spent on search vs. evaluation
« on: May 20th, 2014, 12:45pm »
Quote Quote Modify Modify

I am curious as to the current tradeoffs between time spent searching vs. evaluation.  For example, if a single-threaded bot spends two minutes doing a typical alpha-beta search, how much of that time is spent evaluating moves and/or board positions, and how much of that time is spent generating steps/moves to search?
I realize that the answer will vary by bot and by board position.  I am wondering, though, if there are general ranges which are considered typical.
 
Thanks!
IP Logged
leon_messerschmidt
Forum Senior Member
****



Arimaa player #6344

   


Gender: male
Posts: 26
Re: Time spent on search vs. evaluation
« Reply #1 on: May 25th, 2014, 1:16am »
Quote Quote Modify Modify

For my (unfinished) bot it is about 2/3 searching and 1/3 evaluating at the moment.
IP Logged
ddyer
Forum Guru
*****






   
WWW

Gender: male
Posts: 63
Re: Time spent on search vs. evaluation
« Reply #2 on: Oct 3rd, 2014, 1:53pm »
Quote Quote Modify Modify

For traditional alpha-beta searches, improvement in the quality of the
evaluator trumps everything else.  
 
Ideally, you would work on a playing algorithm without consideration
of the search time, until you achieved the desired quality of play, and
then optimize what works.
 
In the real world, alpha-beta has very lumpy performance; you
pay a huge time penalty to increment the search depth, so you'll
be forced to select a depth and program to keep the performance
at that depth acceptable.  This leads to a lot of time wasted
optimizing things that don't really matter.
 
Another point to consider is that evaluator quality is ultimately  
an emergent property; If you could see all the way to the end,
you'd need only a trivial evaluator that reports win or loss.  
 
By "quality of the evaluator" you could think of approximating
the emergent properties that would be apparent in a deeper search,
if you could afford do one.
 
 
IP Logged

visit my game site: http://www.boardspace.net/
free online abstract strategy games
Pages: 1  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.