Arimaa Forum (http://arimaa.com/arimaa/forum/cgi/YaBB.cgi)
Arimaa >> Bot Development >> Time spent on search vs. evaluation
(Message started by: n00bftw on May 20th, 2014, 12:45pm)

Title: Time spent on search vs. evaluation
Post by n00bftw on May 20th, 2014, 12:45pm
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!

Title: Re: Time spent on search vs. evaluation
Post by leon_messerschmidt on May 25th, 2014, 1:16am
For my (unfinished) bot it is about 2/3 searching and 1/3 evaluating at the moment.

Title: Re: Time spent on search vs. evaluation
Post by ddyer on Oct 3rd, 2014, 1:53pm
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.





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