![]() | This article is rated B-class on Wikipedia's
content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
|
According to the StackOverflow question " Alpha-beta pruning: Fail-hard VS. Fail-soft" and first answer the pseudocode here is incorrect inasmuch as both versions (allegedly) demonstrate fail-soft. This should be confirmed and the psuedocode corrected if necessary. JoshuaGreen1981 ( talk) 00:55, 7 February 2022 (UTC)
Does this really deserve its own page? Alpha-beta pruning isn't a search algorithm at all, it's an optimization for the minimax algorithm. 193.130.71.68 ( talk) 11:53, 25 May 2011 (UTC)
In the description for this article, this appears: "If the move ordering for the search is optimal (meaning the best moves always searched first)"
As far as I can tell, the optimal search order for AB pruning is worst-first. The algorithm is looking to eliminate a subtree as early as possible, and the way to do this is to find a move in it that's worse than the current Alpha value; worst-first gives the best chance of doing this. Am I missing something? I'll update the description if I don't hear otherwise. -- === Jez === 11:48, 28 May 2007 (UTC)
The article is incorrect. Alpha beta pruning pertains to TWO types of pruning whereof the author only describes one.
I think all search strategies except minimax and alpha beta should be put in a single page - Arvindn
I put ordering heuristics here because they derive their power only from their interaction with alpha-beta search -- they have no advantage otherwise. The Anome
The article claims: The optimisation typically reduces the effective branching factor by two compared to simple Minimax, or equivalently doubles the number of ply that can be searched in a given time. Since the number of nodes to be searched (i.e. time required) increases exponentially with each ply, I don't think this is correct. Here's an example, with math... take a tree which had an effective branching factor of 6 before applying alpha-beta pruning... Assuming I had time to search 4 plys deep previous to pruning, I would have had time for 6^1+6^2+6^3+6^4=1554 nodes. If alpha-beta reduces the branching factor to 3 now, the article's claim is that I should have time to search 8 plys deep. However, that would be 3^1+3^2+3^3+...+3^8=9840 nodes. Clearly, reducing the effective branching factor by two does not buy one the time to search twice as many plies deep. Have I made an error in this reasoning? Unless I hear otherwise, I'll update the article. -- Ds13 22:31, 19 January 2006 (UTC)
The pseudo-code has been changed back-and-forth several times (see the *** below), so perhaps it's better to add some discussion here rather than to add to the article itself.
evaluate (node, alpha, beta) if node is a leaf return the heuristic value of node if node is a minimizing node for each child of node beta = min (beta, evaluate (child, alpha, beta)) if beta <= alpha return *** alpha or beta? *** return beta if node is a maximizing node for each child of node alpha = max (alpha, evaluate (child, alpha, beta)) if beta <= alpha return *** alpha or beta? *** return alpha
The pseudocode is correct, regardless of whether alpha or beta is returned at the cut-offs. In either case, the parent node knows (implicitly) that a cut-off occurred, and that the cut-off node is equal to or worse than the current best child node, and that therefore it must retain the current best child node. —Unknown
The pseudo code is *WRONG* in the same way as negamax (which is identical, clearly something is wrong): the heurestic evaluation must be negated whenever player 2 is to play. Also, if the root call was for player 2, the final result must be negated again. —The preceding unsigned comment was added by 208.65.183.75 ( talk) 07:39, 4 March 2007 (UTC).
Not true, although the description should be clearer. The heuristic is always from the perspective of the player executing the search, not the current player.
The code in the Talk page appears to be an implementation of MiniMax with Alpha Beta pruning. The code in the actual Wiki page appears to be an implementation of NegaMax. The difference is that MiniMax alternates between taking minimums and maximums, while NegaMax negates Alpha and Beta and the returned result so as to keep using maximums. It's simpler but quite possibly harder to understand. -- wadetb at gmail dot com
I implemented the pseudo code, and it does not work. My assumptions are as follow - the first time we call the routine, I assume the player making the first move is the "first" player. I assume the heuristic scores are such that a higher score is always better for the first player. I also assume the alpha and beta value parameters are non volatile (the are not modified on return.) Assuming the simplest case of two terminal nodes with scores of 1 and 2, I get the return value of -1 when I code the psuedo code as it's written. It's as if something is missing from the code, or there's specific behavior when return heuristic evaluations. When I looked up negamax, which looks almost identical, it passes in a parameter called 'color', which seems like it might fix this problem!—Preceding unsigned comment added by 15.203.233.76 ( talk) 19:51, 29 March 2010 (UTC)
The tree image at the top is quite helpful (especially compared with earlier versions), but would it be possible to show the values of Alpha and Beta somewhere? In the MiniMax page there is a description to go along with the image that describes the processing at each step. Something similar would help quite a lot on the Alpha-beta page.
it was quite beutyful and short ;) ---- ca1 84.16.123.194 ( talk) 16:05, 3 April 2008 (UTC)
It certainly is short, it may be beautiful. But it most certainly is NOT explanatory. It makes no mention of variable scope, which the pseudocode leaves ambiguous. XcepticZP ( talk) 13:41, 23 March 2009 (UTC)
The link below for the correct pseudocode from alpha-beta. It was taken from page 218 of "Algorithms in a Nutshell", http://oreilly.com/catalog/9780596516246
Pseudocode - http://cardforge.googlecode.com/files/alpha-beta%20pseudocode.gif
Mtgrares ( talk) 20:28, 19 November 2009 (UTC)
Could be make some mention of the use of alpha-beta pruning in games involving luck (such as dice)? Can alpha-beta pruning be used on such games? -- Doradus ( talk) 14:02, 18 January 2010 (UTC)
Hi,
The example code fragment says "return the heuristic value of node". It is somewhat ambiguous if the value must be calculated seen from the player-at-that-depth point of view or the the player at the root-level of the search tree. — Preceding unsigned comment added by Flok ( talk • contribs) 12:37, 19 July 2013 (UTC)
Since is a set, the function "average number of nodes evaluated" would be either be in the set or not in it, not "roughly" contained. The link to "Human Level AI Is Harder Than It Seemed in 1955" seems dead (at least for me, now), so I can't investigate the exact language McCarthy uses and am reluctant to make a call one way or the other. Can somebody with access to the original slides clarify this? 192.160.117.141 ( talk) 22:24, 23 January 2014 (UTC)
I have tried to address this; see the new text. Csaba Szepesvari ( talk) 00:19, 17 November 2017 (UTC)
A shorter but equivalent variant of the pseudocode in the article should be obtained if α and β are swapped, and α, β and the heuristic value are negated, between each depth, like this:
01 function alphabeta(node, depth, α, β, heuristicFactor) 02 if depth = 0 or node is a terminal node 03 return the heuristic value of node multiplied by heuristicFactor 04 for each child of node 05 α := max(α, -alphabeta(child, depth - 1, -β, -α, -heuristicFactor)) 06 if β ≤ α 07 break (* β cut-off *) 08 return α
(* Initial call *) alphabeta(origin, depth, - ∞, + ∞, 1)
Swapping and negating α and β effectively negates the interval [α, β], and each depth can focus only on maximizing the lower bound of the interval, instead of having to either maximize the lower bound or minimize the upper bound depending on who's turn it is. Hence saving code. But then the heuristic values also has to be negated between each depth; hence the heuristic factor and the minus sign in the max function.
Could anyone confirm that this code actually works? I haven't had a chance to test it. In that case we could include it as a variant in the article, as this is just about half the number of lines of code of the pseudocode that is currently in the article. — Kri ( talk) 13:29, 6 November 2014 (UTC)
Hello fellow Wikipedians,
I have just added archive links to one external link on
Alpha–beta pruning. Please take a moment to review
my edit. If necessary, add {{
cbignore}}
after the link to keep me from modifying it. Alternatively, you can add {{
nobots|deny=InternetArchiveBot}}
to keep me off the page altogether. I made the following changes:
When you have finished reviewing my changes, please set the checked parameter below to true to let others know.
An editor has reviewed this edit and fixed any errors that were found.
Cheers.— cyberbot II Talk to my owner:Online 23:59, 27 February 2016 (UTC)
Hello fellow Wikipedians,
I have just added archive links to 3 external links on
Alpha–beta pruning. Please take a moment to review
my edit. If necessary, add {{
cbignore}}
after the link to keep me from modifying it. Alternatively, you can add {{
nobots|deny=InternetArchiveBot}}
to keep me off the page altogether. I made the following changes:
When you have finished reviewing my changes, please set the checked parameter below to true or failed to let others know (documentation at {{
Sourcecheck}}
).
An editor has reviewed this edit and fixed any errors that were found.
Cheers.— cyberbot II Talk to my owner:Online 18:53, 22 March 2016 (UTC)
It leads to a page that doesn't provide any of the information indicated. — Preceding unsigned comment added by 67.168.176.62 ( talk) 08:13, 24 September 2016 (UTC)
The pseudo-code is casually described as being "fail-soft," before the definition of "fail-soft" is actually given:
The pseudo-code for the fail-soft variation of alpha-beta pruning is as follows:
"Fail-soft" is defined afterwards, but initially, the pseudo-code section is written as if the reader should already knows what the term "fail-soft" means. I think it would make sense to open the pseudo-code section with something like this:
Implementations of alpha-beta pruning can often be delineated by whether they are "fail-soft," or "fail-hard." A fail-soft alpha-beta function may return values (v) that exceed (v < α or v > β) the α and β bounds set by its function call arguments. In comparison, fail-hard alpha-beta limits its function return value into the inclusive range of α and β.
Some additional explanation of the implications of "fail-soft" and "fail-hard" would also be nice.
The article states that the algorithm is optimal and selects the same move as the standard minimax algorithm, but this depends on some unspoken assumptions. If the values of the leaf nodes are known, it will select the optimal move. But the usual context is a limited-depth search, where some (or most) of the leaf nodes have uncertain value. Alpha-beta will select the same move as the standard minimax algorithm if the search depth is the same, but if (as in usual applications) a bigger depth is allowed within the same time because of the pruning, the deeper search might reveal better insights that makes it choose another move. — Preceding unsigned comment added by 37.44.138.159 ( talk) 13:03, 12 March 2018 (UTC)
The section needs considerable rework, replace with reference to
Negamax#Negamax_with_alpha_beta_pruning, or remove. Among the issues:
The pseudo code for the section, in this article's context, should resemble the following:
function alphabeta(node, depth, α, β, color) is if depth = 0 or node is a terminal node then return color × the heuristic value of node value := −∞ for each child of node do value := max(value, −alphabeta(child, depth − 1, −β, −α, −color)) α := max(α, value) if α ≥ β then break (* cut-off *) return value
GamePlayerAI ( talk) 17:14, 30 May 2020 (UTC)
(* Initial call *) alphabeta(origin, depth, − ∞, + ∞, 1)
GamePlayerAI ( talk) 15:14, 1 June 2020 (UTC)
Rather than leave inaccurate information in the main article, I'm removing the disputed section. I'll leave the revisions here for the section's disputed code, as above. The subject (Alpha-beta pruning in Negamax) is also covered in Negamax#Negamax_with_alpha_beta_pruning.
I'll also note Alpha Beta Pruning is best understood with the Minimax algorithm. Although Alpha Beta Pruning is also applicable with Negamax, it's far less intuitive in describing and understanding it with Negamax.
GamePlayerAI ( talk) 18:30, 21 June 2020 (UTC)
Hi, I've created an image which shows the difference between a minimax and alpha-beta pruned search using trees diagrams. Could this be added to the article?
https://i.imgur.com/9AXbblz.png
Sgriffin53 ( talk) 13:26, 2 July 2021 (UTC)