13
$\begingroup$

How do I choose the best algorithm for a board game like checkers?

So far, I have considered only three algorithms, namely, minimax, alpha-beta pruning, and Monte Carlo tree search (MCTS). Apparently, both the alpha-beta pruning and MCTS are extensions of the basic minimax algorithm.

$\endgroup$
14
$\begingroup$

tl;dr:

  • None of these algorithms are practical for modern work, but they are good places to start pedagogically.

  • You should always prefer to use Alpha-Beta pruning over bare minimax search.

  • You should prefer to use some form of heuristic guided search if you can come up with a useful heuristic. Coming up with a useful heuristic usually requires a lot of domain knowledge.

  • You should prefer to use Monte Carlo Tree search when you lack a good heuristic, when computational resources are limited, and when mistakes will not have outsize real-world consequences.

More Details:

In minimax search, we do not attempt to be very clever. We just use a standard dynamic programming approach. It is easy to figure out the value of difference moves if we're close to the end of the game (since the game will end in the next move, we don't have to look very far ahead). Similarly, if we know what our opponent will do in the last move of the game, it's easy to figure out what we should do in the second last move. Effectively we can treat the second last move as the last move of a shorter game. We can then repeat this process. Using this approach is certain to uncover the best strategies in a standard extensive-form game, but will require us to consider every possible move, which is infeasible for all but the simplest games.

Alpha-Beta pruning is a strict improvement on Minimax search. It makes use of the fact that some moves are obviously worse than others. For example, in chess, I need not consider any move that would give you the opportunity to put me in checkmate, even if you could do other things from that position. Once I see that a move might lead to a lose, I'm not going to bother thinking about what else might happen from that point. I'll go look at other things. This algorithm is also certain to yield the correct result, and is faster, but still must consider most of the moves in practice.

There are two common ways you can get around the extreme computational cost of solving these kinds of games exactly:

  1. Use a Heuristic (A* search is the usual algorithm for pedagogical purposes, but Quiescence search is a similar idea in 2 player games). This is just a function that gives an estimate of the value of a state of the game. Instead of considering all the moves in a game, you can just consider moves out to some finite distance ahead, and then use the value of the heuristic to judge the value of the states you reached. If your heuristic is consistent (essentially: if it always overestimates the quality of states), then this will still yield the correct answer, but with enormous speedups in practice.

  2. Use Rollouts (like Monte Carlo Tree Search). Basically, instead of considering every move, run a few thousand simulated games between players acting randomly (this is faster than considering all possible moves). Assign a value to states equal to the average win rate of games starting from it. This may not yield the correct answer, but in some kinds of games, it performs reliably. It is often used as an extension of more exact techniques, rather than being used on its own.

$\endgroup$
  • $\begingroup$ A* doesn't really seem to fit in the context of two-player games like the other algorithms do? Note on MCTS: typical implementations don't "consider all moves down to some fixed depth" and then start the rollouts; instead, typical implementations dynamically, gradually grow the tree search tree, growing it more in more promising parts (parts where many rollouts are nudged towards by Selection strategy), growing it less in the less promising parts. $\endgroup$ – Dennis Soemers Jul 16 '18 at 18:57
  • $\begingroup$ @DennisSoemers It's possible we have different terminologies? What you're describing sounds like MCTS with Quiescence search to me. You're right about A* being for standard search problems though, so I've updated the answer. Thanks! $\endgroup$ – John Doucette Jul 16 '18 at 19:08
  • $\begingroup$ So Monte Carlo algorithm goes to a prescribed depth and then checks which of its childs nodes looks more promising and then simulates that child node to see if it's going to lose or win and then propagates the value back up and then repeats. But as the game progresses like checkers the branching factor increases hence more nodes will propagate from the root node. So if I don't have that much memory then this algorithm with be ineffective as the game goes deeper right? $\endgroup$ – Joey Jul 16 '18 at 19:09
  • $\begingroup$ Nope MCTS doesn't first go to a fixed depth and then starting "rolling". See mcts.ai/about $\endgroup$ – Dennis Soemers Jul 16 '18 at 19:11
  • 1
    $\begingroup$ @MiguelSaraiva On its own, MCTS is not something you'd usually use for a modern application. Combined with something like a DNN to provide a learned heuristic would be pretty good though. $\endgroup$ – John Doucette Apr 20 at 19:45
5
$\begingroup$

N.B The reason why I only chose these three algorithms was due to time I have available in understanding them. From a little research, I found that these algorithms are basically interweaved into the minimax algorithm. So if I can understand one then the other two will just fall into place.

Given this context, I would recommend starting out with Minimax. Of the three algorithms, Minimax is the easiest to understand.

Alpha-Beta, as others have mentioned in other answers, is a strict improvement on top of Minimax. Minimax is basically a part of the Alpha-Beta implementation, and a good understanding of Alpha-Beta requires starting out with a good understanding of Minimax anyway. If you happen to have time left after understanding and implementing Minimax, I'd recommend moving on to Alpha-Beta afterwards and building that on top of Minimax. Starting out with Alpha-Beta if you do not yet understand Minimax doesn't really make sense.

Monte-Carlo Tree Search is probably a bit more advanced and more complicated to really, deeply understand. In the past decade or so, MCTS really has been growing to be much more popular than the other two, so from that point of view understanding MCTS may be more "useful".

The connection between Minimax and MCTS is less direct/obvious than the connection between Minimax and Alpha-Beta, but there still is a connection at least on a conceptual level. I'd argue that having a good understanding of Minimax first is still beneficial before diving into MCTS; in particular, understanding Minimax and its flaws/weak points can provide useful context / help you understand why MCTS became "necessary" / popular.


To conclude, in my opinion:

  • Alpha-Beta is strictly better than Minimax, but also strongly related / built on top of Minimax; so, start with Minimax, go for Alpha-Beta afterwards if time permits
  • MCTS has different strengths/weaknesses, is often better than Alpha-Beta in "modern" problems (but not always), a good understanding of Minimax will likely be beneficial before starting to dive into MCTS
$\endgroup$
  • $\begingroup$ Is there any other algorithm that you would suggest that I could also use? That's at like a alpha beta pruning level $\endgroup$ – Joey Jul 16 '18 at 19:31
  • $\begingroup$ @Joey Hmm no not really. Minimax is a very natural starting point, I'd extremely strongly recommend that if you're just getting started. That was basically the first algorithm developed for games like chess/checkers/tic tac toe/whatever. Afterwards, hundreds if not thousands of improvements were developed on top of it, many of which you can probably find at chessprogramming.wikispaces.com/Search . Alpha-Beta is the most natural enhancement to look into on top of Minimax. $\endgroup$ – Dennis Soemers Jul 16 '18 at 19:35
  • $\begingroup$ @Joey Monte-Carlo Tree Search is a little bit different (doesn't necessarily have Minimax as a basis), is interesting, fun, popular, and highly relevant in "modern" AI. Still, foundations are important, I wouldn't recommend starting with MCTS immediately if you don't understand Minimax + Alpha-Beta yet, even though it may technically be possible. $\endgroup$ – Dennis Soemers Jul 16 '18 at 19:37
  • $\begingroup$ Thank you for that site. It's a wealth of knowledge that I can now read up. The hardest put about learning new stuff is finding the correct material to help you understand. So thanks again for the site $\endgroup$ – Joey Jul 16 '18 at 19:51
  • $\begingroup$ @Joey I'm not 100% sure if chessprogramming is the easiest site to learn from (and there seems to be a scary notice at the top that the site may be disappearing at end of July). If I remember correctly, many descriptions are rather short / probably not easy to understand if you're a beginner in the field. It will at least be a good, comprehensive collection of names of all kinds of algorithms / enhancements though, and you can try to look up the original sources or google all those names for more detailed info elsewhere. $\endgroup$ – Dennis Soemers Jul 16 '18 at 19:53
1
$\begingroup$

I you have to choose between Minimax and Alpha-Beta pruning you should choose Alpha-beta. It is more efficient and fast because it can prune a substantial part of your exploration tree. But you need to order the actions from the best to the worst depending on max or min point of view, so the algorithm can quickly realize if the exploration is necessary.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.