Author |
Topic: Time spent on search vs. evaluation (Read 1597 times) |
|
n00bftw
Forum Full Member
Arimaa player #9394
Gender: 
Posts: 15
|
 |
Time spent on search vs. evaluation
« on: May 20th, 2014, 12:45pm » |
 Quote  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:
Posts: 26
|
|
Re: Time spent on search vs. evaluation
« Reply #1 on: May 25th, 2014, 1:16am » |
Quote Modify
|
For my (unfinished) bot it is about 2/3 searching and 1/3 evaluating at the moment.
|
|
IP Logged |
|
|
|
ddyer
Forum Guru
Gender:
Posts: 66
|
|
Re: Time spent on search vs. evaluation
« Reply #2 on: Oct 3rd, 2014, 1:53pm » |
Quote 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
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print