The Brilliant Idea Behind Monte Carlo Tree Search

Before you read this article: Have you read my previous article on search algorithms?

Search Algorithms In a Nutshell

In the world of complex searching algorithms, we often find ourselves navigating between two distinct ends of the spectrum: simplicity and complexity.

Comparison of Breadth-first vs. Depth-first (https://www.freelancinggig.com/blog/2019/02/06/what-is-the-difference-between-bfs-and-dfs-algorithms/)

Most notably, (extremely) simple algorithms can be characterized as below:

• Breadth-first: exploring each level of nodes one by one
• Depth-first: exploiting a solution as long as possible

The problem is that both simple approaches operate in a rigid manner, without having any adjustable parameters.

Simulated Annealing as a great example for a complex search algorithm (https://ieatbugsforbreakfast.wordpress.com/2011/10/14/simulated-annealing-a-brief-introduction/)

Now, consider the converse — a sophisticated algorithm that employs a finely tuned blend of intelligent heuristics and hyperparameters. Below is the list of required arguments for Simulated Annealing:

“In order to apply the simulated annealing method to a specific problem, one must specify the following parameters: the state space, the energy (goal) function E(), the candidate generator procedure neighbour(), the acceptance probability function P(), and the annealing schedule temperature() AND initial temperature init_temp“

The unique strength of this approach lies in its adaptability. By fine-tuning the individual arguments assigned to each heuristic, such complex algorithms can be tailored to address specific scenarios effectively.

However, this adaptability comes at a cost — a lack of generalization. The algorithm’s fine-tuning may perform exceptionally well in one context but struggle in another.

This trade-off between adaptability and generalization presents its own set of challenges and potential problems. Explainability, for example, may be an issue: can you explain “why the energy function is chosen logarithmic” or “how the temperature relates to the…