I would like to know if having a really good evaluation function is as good as using any of the extensions of alpha-beta pruning, such as killer moves or quiescence search?
$\begingroup$
$\endgroup$
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
To build on Neil's answer a bit, you're right that the better your evaluation function gets, the less work your optimization function will need to perform. If your evaluation function gets good enough, you won't need to search at all.
This is not just an academic idea though! It's actually fairly widely used, and has been key to solving several games.
The first example I'm aware of is Tesauro's TD-Gammon player, from 1995. Tesauro used the ideas of reinforcement learning and self-play to train a Neural Network to act as an evaluation function. TD-Gammon played with just a 2-move lookahead using the best evaluation function that was found, and was deemed better than most (all?) human expert players at the time.
More recently, AlphaGo Zero used similar techniques to solve Go, but learning both an evaluation function and (separately) a function to randomize over possible moves.
answered Jul 23, 2018 at 13:34
-
$\begingroup$ Also worth noting: it seems likely that this is how human experts play most games. Checker's is the most famous example, where search algorithms would require a 50+ move lookahead to find moves that human experts intuited. $\endgroup$ Jul 23, 2018 at 21:15
$\begingroup$
$\endgroup$
A perfect evaluation function would mean that you only had to do a local search - i.e. maximise over next set of decisions - in order for an agent to behave optimally in an environment.
As such if you could somehow create that function, it would make a search with alpha-beta pruning redundant.
In practice, evaluation functions for complex environments are usually approximate, and significant improvement can be made by adding a deeper search.
Optimisations in search algorithms and improvements in evaluation function work together to make more efficient and closer-to-optimal solutions overall. An evaluation function provides global/general knowledge about the environment and goals. A tree search function provides local focus on solving a relatively small subset of the optimisation problem that is currently relevant.
answered Jul 23, 2018 at 7:24