Since this is a competitive setting, you can assume that the others pick actions resulting in a worse outcome for your program. Then, minimax works by taking the predictions of future states, and working back to determine the utility of predecessor states. When your program has estimated the utility of the next states, it can easily select the best.<\/p>
Description<\/h3>
Minimax is a policy to select optimal utility actions assuming the worst from other programs. Typically, minmax is combined with a depth-first search algorithm that traverses the game tree, predicting what the opponents are likely to do and what your program should do. As such, there are two different levels in the search tree: 1) for the opponents and 2) for team-members.<\/p>
- The level in the game tree dealing with opponents is known as MIN<\/tt>, since they will typically minimize<\/strong> the utility of the outcome state.<\/li>
- Conversely, the search tree’s level dealing with team-members is known as MAX<\/tt>, since they will typically maximize<\/strong> the utility of the outcome state.<\/li><\/ol>
The minimax search, in effect, minimizes the maximum possible loss, or looking at it the other way, maximizes the minimum gain.<\/p>
![\"Min\/Max](\"http:\/\/euvolution.com\/futurist-transhuman-news-blog\/wp-content\/plugins\/wp-o-matic\/cache\/47380_minimax.png\")
<\/p>Application<\/h3>
Minimax is applied to many games with great success, especially when the branching factor is small (i.e. there are few options each turn), when the situation is deterministic, and the state is fully observable.<\/p>
However, in practice, there are significant challenges to applying Minimax to a logic game. Notably, the game tree is usually too large to search until the end, so good estimator functions are required for any state (and not just terminal states). This is not a trivial problem, and significantly affects the outcome of the algorithm. Most state estimation functions are hand written for each problem by experts.<\/p>
The pseudo-code for a minimax search looks like this:<\/p>
def<\/span> minimax(<\/span>node, depth)<\/span> if<\/span> node.is_terminal<\/span>(<\/span>)<\/span> or<\/span> depth == 0<\/span>: return<\/span> node.calculate_heuristic<\/span>(<\/span>)<\/span> if<\/span> node.is_opponent<\/span>(<\/span>)<\/span>: a = +inf for<\/span> child in<\/span> node.get_children<\/span>(<\/span>)<\/span>: a = min<\/span>(<\/span>a, minimax(<\/span>child, depth-1<\/span>)<\/span>)<\/span> else<\/span>: a = -inf for<\/span> child in<\/span> node.get_children<\/span>(<\/span>)<\/span>: a = max<\/span>(<\/span>a, minimax(<\/span>child, depth-1<\/span>)<\/span>)<\/span> return<\/span> a<\/pre><\/div><\/div>On the bright side, alpha-beta pruning can be implemented easily to improve the efficiency of the search.<\/p>
Theory<\/h3>
In classical statistical decision theory, an estimator
![\"\\delta\"](\"http:\/\/euvolution.com\/futurist-transhuman-news-blog\/wp-content\/plugins\/wp-o-matic\/cache\/47380_77a3b715842b45e440a5bee15357ad29_1.0pt.gif\" "\\"\\delta\\"")
is used to estimate a parameter ![\"\\theta](\"http:\/\/euvolution.com\/futurist-transhuman-news-blog\/wp-content\/plugins\/wp-o-matic\/cache\/47380_c4da9a79ba148a2e9a7bcd92255680be_1.39098pt.gif\" "\\"\\theta")
. Also assume a risk function ![\"R(\\theta,\\delta)\"](\"http:\/\/euvolution.com\/futurist-transhuman-news-blog\/wp-content\/plugins\/wp-o-matic\/cache\/77477_6a17165cc8bd2870b628562e395773c2_3.5pt.gif\" "\\"R(\\theta,\\delta)\\"")
, usually specified as the integral of a loss function. Given this framework, ![\"\\tilde{\\delta}\"](\"http:\/\/euvolution.com\/futurist-transhuman-news-blog\/wp-content\/plugins\/wp-o-matic\/cache\/77477_d99d347424268567155c1e3e57e466e0_1.0pt.gif\" "\\"\\tilde{\\delta}\\"")
is called “minimax<\/em>” if it satisfies:<\/p>![\"\\sup_\\theta](\"http:\/\/euvolution.com\/futurist-transhuman-news-blog\/wp-content\/plugins\/wp-o-matic\/cache\/77477_67b428b3c397981a5a7f4481a50c69d8_3.5pt.gif\" "\\"\\sup_\\theta")
<\/p>Resources<\/h3>
- See papers on minimax search<\/a> in the resources section on AI Depot<\/b>.<\/li><\/ul>
<\/p>","protected":false},"excerpt":{"rendered":"
Let’s say your program is in a competitive situation against others, and must predict possible consequences of actions to select the one with the best outcome. This is the case in many logic games like Tic-Tac-Toe, Othello, Chess or Go. … Continue reading
- Conversely, the search tree’s level dealing with team-members is known as MAX<\/tt>, since they will typically maximize<\/strong> the utility of the outcome state.<\/li><\/ol>