1
$\begingroup$

Suppose the following properties of a board game:

  1. High branching factor in the beginning of the game (~500) which slowly tends towards 0 at the end of the game

  2. Evaluation of the any given board state isn't hard to create and can be quite accurate

And that we want to create an AI to play such board game.

What method of tree searching should be applied for the AI?

Considering the absurd branching factor (at least for most of the game), the Monte Carlo method of search is appealing. The problem is that from what I've seen usually monte carlo search methods are used on games with both high branching factor and no easy evaluation function. However that is not the case for this board game as previously stated.

I'm simply curious how this property of evaluation should influence my decision. For example: Should I replace simulations and playouts with an evaluation function? At that point, would alpha-beta pruning minimax work better? Is there some hybrid which would be optimal?

Improve this question
$\endgroup$
  • $\begingroup$ There are a bunch of "add-ons" to minimax that may work for you. Some of them are MTD(f), best node search, PVS, etc. I don't know which one would be the best for your game though. $\endgroup$ – Varun Vejalla Aug 21 '20 at 5:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.