12
$\begingroup$

I am currently new to artificial intelligence but I am very intrigued by it. I am currently researching three algorithms, namely:

Minimax, Alpha-beta pruning and Monte Carlo tree search.

As you may have figured out, these are all tree search algorithms. My question is simple. How do I choose which algorithm is best for something like a checkers board game?

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.

$\endgroup$
13
$\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
2
$\begingroup$

Playing chess with a blind search algorithm like Monte Carlo tree search is a very good idea, because it helps to raise the energy consumption of your 64 core workstation. Using the maximum capacity of a cpu and ignoring any possible kind of heuristics is a best practice method in proofing real scientific progress. One advantage of Minimax in contrast to the Monte Carlo algorithm is, that Minimax has a Nash equilibrium which makes it well suited for a mathematical terminology and an abstract introduction into game theory. This helps to focus away from the original problem (how to play chess) into a more general discussion about zero-sum games and payoff matrix. The third strategy on your list (alpha beta-prunning) sounds also well suited for running a server farm under maximum load without ever finding out the best move.

My advice is similar to your own perception: if you have understood the minimax strategy, all the other algorithm are much easier to implement. And minimax is the right choice, if you're planning to stay away from rules of thumb which are implemented as a symbolic planner in LISP.

Minimax algorithm

$\endgroup$
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$
1
$\begingroup$

The selection from among those and others mentioned in other answers to the question is important, yes, and there are conceptual overlaps, but those are not algorithms.

Minimax, Alpha-beta pruning, Monte Carlo tree search are approaches to dealing with the spanning trees of the graphs associated with Markov chains to find an optimum next move based on metrics derived from vertices and edges. There are many potential algorithms that could realize each approach in software.

The best approaches and the best algorithms to realize them depend on many things.

  • Dimensions of the data paths
  • Hardware utilization options exposed through the operating system, cluster, and language employed
  • Desired performance criteria and priorities
  • Time requirements
  • Skill and knowledge of the development team

Although many frameworks available in Python, Java, and other languages will provide ways to overlap concepts and rapid prototype, you cannot just learn one and the others will fall into place. You can hack through to a working solution for your current problem, but if you want to develop the ability to reliably create reliable software, there are no such shortcuts.

In my experience, the thing to start with is neither of the three. It is the commitment to diligence and thoughtfulness in ML software development. If we, as engineers and researchers do not commit to this, then the unreliability of smart systems we create will, in 50 years, rival the unreliability of cell phone connections. We could, to the detriment of safety and economic stability, exceed the maintainability issues characteristic of much of the middle tier software in production today.

I encourage those entering into this powerful and future-critical field to aim much higher than that.

$\endgroup$

Your Answer

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

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