The Two Questions
- Why does Monte Carlo work when a real opponent's behavior may not be random?
- If simulations are based on random moves, how can the modeling of the opponent's behavior work well?
Directed Graphs Over Trees
Games (or game-like strategic scenarios) should not be represented as trees. If the process paths being represented have the Markov property in that each decision lacks knowledge of history, a particular game state can be approached by more than one path, and there may be cyclic paths where a game state is revisited. Trees have neither feature.
It is best to use directed graph structures to think about these problems. The state of a game is a vertex and vertices are connected by unidirectional edges. This is normally drawn as shapes connected by arrows. When two arrows enter one shape or there is a closed path, it is not a tree.
The Scenario Outlined in the Question
In the case of the scenario outline in this question, there is a vertex representing a game state with 100 outgoing edges representing possible moves for player A. Ninety-nine of the edges lead to an obvious instant game win for A. Exactly one leads to an obvious instant game win for B.
Playing back the game to prior to the traversal of the incoming edge to the vertex before the final move, it cannot be assumed that game play allowed player B the same 100 options. Even if the same 100 were available to B, they would not necessarily be of similar value from B's perspective when deciding that previous move. More than likely, B will have had a different set of outgoing edges from which to choose, bearing little or no obvious resemblance to A's subsequent options.
Any game where this is not true, where the options remain constant, would be trivial even in comparison with tic-tack-toe.
The Monte Carlo Approach and Its Algorithm Development
Regarding the specification of a singular Monte Carlo algorithm, it does not exist. Goodfellow, Bengio, & Courville correctly state in their Deep Learning, 2016, that Monte Carlo algorithms (not a singular algorithm) draw a normally correct conclusion but with a non-deterministic occurrence of incorrect conclusion. There are varieties of approach details and associated algorithms in the literature.
- Cross-entropy (CE) method proposed by Rubinstein in 1997
- Continuation multilevel Monte Carlo algorithm; Collier, Haji–Ali, von Schwerin, & Tempone; 2000
- Sequential Monte Carlo algorithm; Drovandi, McGree, & Pettitt; 2012
- Distributed consensus approach from Bayes and Big Data: The Consensus Monte Carlo Algorithm; Scott1, Blocker, Bonassi, Chipman, George, & McCulloch; 2014
- Hamiltonian Monte Carlo, a Markov chain based algorithm designed to avoid, "The random walk behavior and sensitivity to correlated parameters;" Hoffman & Gelman; 2014
There are several more. All attempt to use chaotic perturbation to minimize duration and resource consumption of decisioning by approximating a Monte Carlo simulation from a Bayesian posterior distribution.
The simulation of stochastic nature is usually, in these approaches, accomplished by the injection of a chaotic sequence from a pseudo random number generator. They are generally not truly stochastic because acquiring entropy from within a digital system is another bottleneck presenting immense difficulties, but that's an entirely tangential topic.
Direct Answer to the Question
To correct the misconception in the question, this use of chaotic perturbation does not equalize the selection of moves (represented by edges in the game-play's directed graph). The probabilities of success for each available option are still roughly calculated and followed, but only roughly so because of the psuedo-noise injected by design.
These disturbances in the application of pure optimization achieve time and resource thrift for the majority of game states (represented by vertices) but concurrently sacrifice some reliability.
An Overview of Why the Sacrifice Works
The introduction of chaotic perturbations, mentioned above, modifies the conditions of the optimization search through the achievement of two very specific gains.
- Faster coverage of the contour being searched by increasing entropy (being less organized by adding synthetic Brownian motion) across the set of trials.
- Avoidance of local minima in convergence by being less presumptuous about the contour being searched (slightly less reliant on gradient and curvature hints).
This is true of both reinforced networks (containing real time feedback during actual use) or pre-trained networks of the supervised training type (with labelled data) or unsupervised training where convergence is determined by fixed criteria.