How would a probabilistic version of minimax work?
For example, we may choose a move that could result in a very bad outcome, but that outcome might just be extremely unlikely so we might think it would be worth the risk.
$\begingroup$
$\endgroup$
2
-
$\begingroup$ What about Reinforcement learning? $\endgroup$ – DuttaA Dec 20 '19 at 3:20
-
1$\begingroup$ You might want to look up 'Markov decision process' and how it is used in reinforcement learning. This is probabilistic minimax in essence. $\endgroup$ – Lustwelpintje Dec 20 '19 at 13:20
Add a comment
|
$\begingroup$
$\endgroup$
Yes, there is at least one probabilistic version of minimax, which is called expectiminimax. In expectiminimax, in addition to min and max nodes, there are also chance nodes, which perform a weighted sum of the successors, so the probabilities associated with chance nodes must be known. Given that expectiminimax assumes the existence of random events (represented by the chance nodes), the decisions are thus based on expected values.
Section 5.5 of the book Artificial Intelligence: A Modern Approach provides a description of the expectiminimax algorithm, which was introduced by Donald Michie in Game-playing and game-learning automata (1966). The paper Optimal strategy in games with chance nodes (2007) also gives a decent description of the expectiminimax algorithm.
