Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Expectiminimax
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
{{Short description|Variation of the minimax algorithm}} {{Infobox algorithm |class=[[Search algorithm]] |image= |data= |time=<math>\mathcal{O}(b^mn^m)</math>, where <math>n</math> is the number of distinct dice throws |best-time=<math>\mathcal{O}(b^m)</math>, in case all dice throws are known in advance |average-time= |space= |optimal= |complete= }} The '''expectiminimax''' algorithm is a variation of the [[minimax]] algorithm, for use in [[artificial intelligence]] systems that play two-player [[zero-sum game]]s, such as [[backgammon]], in which the outcome depends on a combination of the player's skill and [[games of chance|chance elements]] such as dice rolls. In addition to "min" and "max" nodes of the traditional minimax tree, this variant has "chance" ("[[move by nature]]") nodes, which take the [[expected value]] of a random event occurring.<ref name="RussellNorvig2009">{{cite book |last1=Russell |first1=Stuart Jonathan |last2=Norvig |first2=Peter |last3=Davis |first3=Ernest |title=Artificial Intelligence: A Modern Approach |date=2010 |publisher=Prentice Hall |isbn=978-0-13-604259-4 |pages=177β178 }}</ref> In [[game theory]] terms, an expectiminimax tree is the game tree of an [[extensive-form game]] of [[perfect information|perfect]], but [[incomplete information]]. In the traditional [[minimax]] 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 [[utility|utility values]] of their children, chance nodes take a weighted average, with the weight being the probability that child is reached.<ref name="RussellNorvig2009"/> 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).<ref name="RussellNorvig2009"/> 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".<ref name="RussellNorvig2009"/>
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)