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!
==Alpha-beta pruning== Bruce Ballard was the first to develop a technique, called *-minimax, that enables [[alpha-beta pruning]] in expectiminimax trees.<ref>{{cite journal |last1=Ballard |first1=Bruce W. |title=The *-minimax search procedure for trees containing chance nodes |journal=Artificial Intelligence |date=September 1983 |volume=21 |issue=3 |pages=327–350 |doi=10.1016/S0004-3702(83)80015-0 }}</ref><ref>{{cite book |doi=10.1007/11674399_3 |chapter=Rediscovering *-Minimax Search |title=Computers and Games |series=Lecture Notes in Computer Science |date=2006 |last1=Hauk |first1=Thomas |last2=Buro |first2=Michael |last3=Schaeffer |first3=Jonathan |volume=3846 |pages=35–50 |isbn=978-3-540-32488-1 }}</ref> The problem with integrating [[alpha-beta pruning]] into the expectiminimax algorithm is that the scores of a chance node's children may exceed the alpha or beta bound of its parent, even if the weighted value of each child does not. However, it is possible to bound the scores of a chance node's children, and therefore bound the score of the CHANCE node. If a standard iterative search is about to score the <math>i</math>th child of a chance node with <math>N</math> equally likely children, that search has computed scores <math>v_1, v_2, \ldots, v_{i-1}</math> for child nodes 1 through <math>i-1</math>. Assuming a lowest possible score <math>L</math> and a highest possible score <math>U</math> for each unsearched child, the bounds of the chance node's score is as follows: <math>\text{score} \leq \frac{1}{n} \left( ( v_1 + \ldots + v_{i-1}) + v_i + U \times (n - i) \right)</math> <math>\text{score} \geq \frac{1}{n} \left( ( v_1 + \ldots + v_{i-1}) + v_i + L \times (n - i) \right)</math> If an alpha and/or beta bound are given in scoring the chance node, these bounds can be used to cut off the search of the <math>i</math>th child. The above equations can be rearranged to find a new alpha & beta value that will cut off the search if it would cause the chance node to exceed its own alpha and beta bounds: <math>\alpha_i = N \times \alpha - \left( v_1 + \ldots + v_{i-1} \right) + U \times (n - i)</math> <math>\beta_i = N \times \beta - \left( v_1 + \ldots + v_{i-1} \right) + L \times (n - i)</math> The [[pseudocode]] for extending expectiminimax with fail-hard [[alpha-beta pruning]] in this manner is as follows: '''function''' *-minimax(node, depth, α, β) '''if''' node is a terminal node '''or''' depth = 0 '''return''' the heuristic value of node '''if''' node is a max or min node '''return''' the minimax value of the node '''let''' N = numSuccessors(node) // Compute α, β for children '''let''' A = N * (α - U) + U '''let''' B = N * (β - L) + L '''let''' sum = 0 '''foreach''' child of node // Limit child α, β to a valid range '''let''' AX = max(A, L) '''let''' BX = min(B, U) // Search the child with new cutoff values '''let''' score = *-minimax(child, depth - 1, AX, BX) // Check for α, β cutoff conditions '''if''' score <= A '''return''' α '''if''' score >= B '''return''' β sum += score // Adjust α, β for the next child A += U - v B += L - v // No cutoff occurred, return score '''return''' sum / N This technique is one of a family of variants of algorithms which can bound the search of a CHANCE node and its children based on collecting lower and upper bounds of the children during search. Other techniques which can offer performance benefits include probing each child with a heuristic to establish a min or max before performing a full search on each child, etc.
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)