Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Expectiminimax
open-in-new
<p>The expectiminimax algorithm is a variation of the <a href="/facts/Minimax/GcCTKutW">minimax</a> algorithm, for use in <a href="/facts/Artificial_intelligence/lJGauQwX">artificial intelligence</a> systems that play two-player <a href="/facts/Zero-sum_game/ccouScgK">zero-sum games</a>, such as <a href="/facts/Backgammon/53mgqvtv">backgammon</a>, in which the outcome depends on a combination of the player's skill and <a href="/facts/Games_of_chance/YmtJH7lr">chance elements</a> such as dice rolls. In addition to "min" and "max" nodes of the traditional minimax tree, this variant has "chance" ("<a href="/facts/Move_by_nature/flbEnjxq">move by nature</a>") nodes, which take the <a href="/facts/Expected_value/1XV0JKL8">expected value</a> of a random event occurring. In <a href="/facts/Game_theory/zkEIj1ya">game theory</a> terms, an expectiminimax tree is the game tree of an <a href="/facts/Extensive-form_game/Yw9gQ7um">extensive-form game</a> of <a href="/facts/Perfect_information/bouFdU4l">perfect</a>, but <a href="/facts/Incomplete_information/8jAPdVTW">incomplete information</a>. </p><p>In the traditional <a href="/facts/Minimax/GcCTKutW">minimax</a> method, the levels of the tree alternate from max to min until the depth limit of the tree has been reached. In an expectiminimax tree, the "chance" nodes are interleaved with the max and min nodes. Instead of taking the max or min of the <a href="/facts/Utility/wlMDG74L">utility values</a> of their children, chance nodes take a weighted average, with the weight being the probability that child is reached. </p><p>The interleaving depends on the game. Each "turn" of the game is evaluated as a "max" node (representing the AI player's turn), a "min" node (representing a potentially-optimal opponent's turn), or a "chance" node (representing a random effect or player). </p><p>For example, consider a game in which each round consists of a single die throw, and then decisions made by first the AI player, and then another intelligent opponent. The order of nodes in this game would alternate between "chance", "max" and then "min". </p>