3 ms·
Monte-Carlo seems more akin to how humans play games. Alpha-Beta pruning is the classical computer science algorithm, easier to understand, describe, and analy
by dragontamer 8y ago
Monte-Carlo seems more akin to how humans play games.
Alpha-Beta pruning is the classical computer science algorithm, easier to understand, describe, and analyze... but very inhuman. Its an exhaustive search, like a breadth-first search.
Monte-Carlo has a lot of variations. Classically, the original MCTS algorithms for Go would play all the way to the end of a game before searching other parts of the tree. In effect, its a depth-first search, you play until you make a conclusion (potentially a "bad" conclusion). The reasoning is simple: on the average, a lot of "samples" of playthroughs will lead to a better estimate for win/loss probability. Think of it as a random-sample of the win/loss potential of a move.
EDIT: Cleaned up the above paragraph.
MCTS implemented by AlphaZero is different however. It uses a neural-net to find "interesting" positions to guide the search, and the same neural net also evaluates the position (who is winning or losing). It seems like a very good way to have a single neural network mostly perform double-duty (aside from the two output nodes). Most of the input layers / early hidden-layers can be "recycled" between the "explore" function and the "evaluation" function.
EDIT: I don't know how AlphaZero gets its "exploration" network trained up however. Its possible that the original randomized MCTS algorithm (search randomly... which btw, performs way better than you'd expect...) might be used to "bootstrap" the exploration weights.
So MCTS just naturally works with neural nets very well.
- FartyMcFarter 8y ago> Its an exhaustive search, like a breadth-first search. It's actually neither of those. An exhaustive search would definitely not be able to search as deeply as state of the art alpha-beta chess engines can. There's a lot of pruning going on. Minimax search (with or without alpha beta pruning) is depth-first search, not breadth-first. Iterative deepening means that you start with a low depth search and progressively increase depth, using the results from the previous depth to do move ordering which increases the efficiency of pruning.
- dragontamer 8y agoThe pruning in Alpha-beta is very much a heuristic that is applied on top of the template. For example, Stockfish may recognize that some moves are "forced" and will iterate a specific variation deeper. Nonetheless, the classical chess search algorithm is exhaustive. Breadth-first search with Alpha-Beta pruning is how it is taught at universities. Stockfish uses iterated deepening as you've said, but that's very similar to Breadth-first search. Stockfish is also multithreaded and got a hash-table to remember previously searched positions (even positions from "another" branch of the tree). I think my point is that Quiescence search is an explicitly programmed feature of Stockfish. Under certain conditions, Stockfish will search deeper (but not all conditions). MCTS on the other hand is almost ENTIRELY a quiescence search. MCTS analyzes "deeper" positions, while Stockfish analyzes more exhaustively. ------ And again: classical MCTS (probably not AlphaZero) will keep going until it evaluates a position as "win", "loss", or "draw". It will NOT return until it gets that kind of evaluation. Positions of "win" are seen as a "win" with a multi-armed bandit, and are explored further and analyzed further. Positions of "loss" or "draw" will be seen as a miss in the multi-armed bandit, but the "exploration" phase of the algorithm will randomly search a position anyway. The multiarmed bandit heuristic is to search "winning" positions more, but to "explore" losing positions less. Ex: every time you search a winning position 10,000 times, you want to search losing positions 100 times. The precise formula involves a logarithm, division, and I think a square-root. The formula has some statistical guarantees about finding results that I never really understood, but hope to research and math-out one day. MCTS has a more elegant statistical theory behind it. But its still very much a manually tweaked process: how much time to dedicate "exploring" bad moves, and how much time spent "exploiting" good moves (analyzing and making sure a "good" move is as good as you think it is). Alpha-Beta search doesn't have any concept of this, and requires a Quiescence search engine "tacked on" for the feature. AlphaZero was interesting in that this manual tweaking of MCTS was left to the neural network training. Its a very elegant use of neural nets to improve the MCTS template.
- FartyMcFarter 8y ago> Nonetheless, the classical chess search algorithm is exhaustive. Minimax search is brute-force, exhaustive search. As soon as you add any pruning (such as alpha-beta pruning, or the myriad search tricks used in chess engines), that's no longer the case. That is unless we're quibbling on the semantics of "exhaustive". > Breadth-first search with Alpha-Beta pruning is how it is taught at universities. Again, no. Minimax search (regardless of any applied pruning) proceeds by visiting the possible successors of a node one at a time, immediately recursing on each of them. See wikipedia's pseudocode for it: https://en.wikipedia.org/wiki/Minimax#Pseudocode https://en.wikipedia.org/wiki/Minimax#Pseudocode Or for a chess-specific source, see: https://www.chessprogramming.org/index.php?title=Minimax https://www.chessprogramming.org/index.php?title=Minimax
- dragontamer 8y agoAlpha Beta pruning results in the same answer as classical Minimax search. Alpha Beta pruning is an optimization: there's no need to search the whole tree to know that a branch can be pruned (but still result in the same answer as minimax). Minimax with Alpha Beta pruning gives you the best position for a given depth. ("Best" as defined by Minimax to the same depth without pruning).
- java-man 8y ago> Monte-Carlo seems more akin to how humans play games. I don't think random choices is how humans play chess, or games in general. I would say it's pattern memory: one learns to play by building a hierarchy of patterns that lead to a prediction of outcome, thus making it possible to select outcome(s) that lead to success.
- ur-whale 8y agoMonte-carlo algorithm don't make random choices. The "randomness" part is simply a device used to approximate expected values (integrals) in very large spaces.
- java-man 8y agotrue, but my point still holds: there is very little randomness in the way brain works. yes, it is present, but not as a primary device to deal with large search space. we don't have a definitive answers on how the brain works, but I think, in this discussion, sparsity and hierarchy are those devices.
- dragontamer 8y agoHmmm, you're right in that humans don't play randomly. But Monte-Carlo in this instance meant "MCTS", and not "random play". I apologize for the imprecision. MCTS is very methodological despite the name. Especially in the AlphaZero implementation, where there's no random play during inference / during games (!!). So where did the "Monte Carlo" name come from? The "original" MCTS algorithm used random play to guestimate the strength of a position. But the "real" theory behind MCTS is the math revolving around multi-armed bandit problems. Given a large number of slot machines (in Chess or Go, the positions are conceptually seen as "slot machines" in a casino), the goal of MCTS is to find the slot-machine that gives the highest probability of winning. In effect: classic MCTS rolls out a position all the way to the final result: win, loss, or draw. Not really in AlphaZero, but this is how MCTS was originally designed. AlphaZero shortcuts this process with a neural-network to guestimate the endgame result. But still: the MATH, and the precise order which the search tree conducts is very heavily based in multi-armed bandit theory and random samples. Even if the algorithm in practice doesn't use randomization, all the math and understanding of the search tree is derived from randomized ideals. I think MCTS well-represents the human thinking of the typical expert. Every play is read all the way to the end of the game instinctively. Experts study the pawn-king-rook endgame not necessarily because they expect to see pawn-king-rook endgames... but because the pawn-king-rook endgame is of huge importance to middle-game pawn development. Learning to see how middle-game (and even early-game) moves develop into endgame is pretty much what being an expert is about. And MCTS best emulates that kind of thinking. True, chess is very tactical. But humans are generally bad at exhaustive searches and tactics. Humans win with positional play, and with better understanding of endgame positions. ---------- So rest assured, when I say "Monte Carlo", I'm not talking about a typical monte-carlo algorithm. I'm talking about Monte Carlo Tree Search, which is a very, very different theoretical basis than Alpha-Beta pruning.