Arimaa Forum - Print Page


    
      
        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 20^th, 2014, 12:45pm)

Title: Time spent on search vs. evaluation
Post by n00bftw on May 20^th, 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 25^th, 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 3^rd, 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.