775:
sides many times during the search if the move ordering is incorrect, each time leading to inefficiency. As the number of positions searched decreases exponentially each move nearer the current position, it is worth spending considerable effort on sorting early moves. An improved sort at any depth will exponentially reduce the total number of positions searched, but sorting all positions at depths near the root node is relatively cheap as there are so few of them. In practice, the move ordering is often determined by the results of earlier, smaller searches, such as through
440:×1×... is that all the first player's moves must be studied to find the best one, but for each, only the second player's best move is needed to refute all but the first (and best) first player move—alpha–beta ensures no other second player moves need be considered. When nodes are considered in a random order (i.e., the algorithm randomizes), asymptotically, the expected number of nodes evaluated in uniform trees with binary leaf-values is
284:
275:
will allow the opponent to force checkmate in two moves. Thus, other outcomes from playing move B no longer need to be considered since the opponent can force a win. The maximum score that the opponent could force after move "B" is negative infinity: a loss for the player. This is less than the minimum position that was previously found; move "A" does not result in a forced loss in two moves.
271:
their worst possible score. Whenever the maximum score that the minimizing player (i.e. the "beta" player) is assured of becomes less than the minimum score that the maximizing player (i.e., the "alpha" player) is assured of (i.e. beta < alpha), the maximizing player need not consider further descendants of this node, as they will never be reached in the actual play.
185:, etc.). It stops evaluating a move when at least one possibility has been found that proves the move to be worse than a previously examined move. Such moves need not be evaluated further. When applied to a standard minimax tree, it returns the same move as minimax would, but prunes away branches that cannot possibly influence the final decision.
759:
802:
alpha–beta limits its function return value into the inclusive range of α and β. The main difference between fail-soft and fail-hard implementations is whether α and β are updated before or after the cutoff check. If they are updated before the check, then they can exceed initial bounds and the algorithm is fail-soft.
270:
The algorithm maintains two values, alpha and beta, which respectively represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of. Initially, alpha is negative infinity and beta is positive infinity, i.e. both players start with
274:
To illustrate this with a real-life example, suppose somebody is playing chess, and it is their turn. Move "A" will improve the player's position. The player continues to look for moves to make sure a better one hasn't been missed. Move "B" is also a good move, but the player then realizes that it
1090:
is usually used in conjunction with alpha–beta so that a reasonably good move can be returned even if the algorithm is interrupted before it has finished execution. Another advantage of using iterative deepening is that searches at shallower depths give move-ordering hints, as well as shallow alpha
1069:
Over time, other improvements have been suggested, and indeed the
Falphabeta (fail-soft alpha–beta) idea of John Fishburn is nearly universal and is already incorporated above in a slightly modified form. Fishburn also suggested a combination of the killer heuristic and zero-window search under the
801:
Implementations of alpha–beta pruning can often be delineated by whether they are "fail-soft," or "fail-hard". With fail-soft alpha–beta, the alphabeta function may return values (v) that exceed (v < α or v > β) the α and β bounds set by its function call arguments. In comparison, fail-hard
287:
An illustration of alpha–beta pruning. The grayed-out subtrees don't need to be explored (when moves are evaluated from left to right), since it is known that the group of subtrees as a whole yields the value of an equivalent subtree or worse, and as such cannot influence the final result. The max
774:
are temporarily dominated by either a first player advantage (when many first player moves are good, and at each search depth the first move checked by the first player is adequate, but all second player responses are required to try to find a refutation), or vice versa. This advantage can switch
1058:. This is particularly useful for win/loss searches near the end of a game where the extra depth gained from the narrow window and a simple win/loss evaluation function may lead to a conclusive result. If an aspiration search fails, it is straightforward to detect whether it failed
292:
The benefit of alpha–beta pruning lies in the fact that branches of the search tree can be eliminated. This way, the search time can be limited to the 'more promising' subtree, and a deeper search can be performed in the same time. Like its predecessor, it belongs to the
267:, such as chess, checkers, and reversi. Each node in the tree represents a possible situation in the game. Each terminal node (outcome) of a branch is assigned a numeric score that determines the value of the outcome to the player with the next move.
297:
class of algorithms. The optimization reduces the effective depth to slightly more than half that of simple minimax if the nodes are evaluated in an optimal or near optimal order (best choice for side on move ordered first at each node).
754:
A chess program that searches four plies with an average of 36 branches per node evaluates more than one million terminal nodes. An optimal alpha-beta prune would eliminate all but about 2,000 terminal nodes, a reduction of 99.8%.
250:
proved its optimality in terms of the expected running time for trees with randomly assigned leaf values in two papers. The optimality of the randomized version of alpha–beta was shown by
Michael Saks and Avi Wigderson in 1986.
1646:
Like its A* counterpart for single-player games, SSS* is optimal in terms of the average number of nodes examined; but its superior pruning power is more than offset by the substantial storage space and bookkeeping
1022:
to search earlier parts of the tree that are likely to force alpha–beta cutoffs. For example, in chess, moves that capture pieces may be examined before moves that do not, and moves that have scored highly in
584:, which is much smaller than the work done by the randomized algorithm, mentioned above, and is again optimal for such random trees. When the leaf values are chosen independently of each other but from the
532:
330:) – the same as a simple minimax search. If the move ordering for the search is optimal (meaning the best moves are always searched first), the number of leaf node positions evaluated is about
534:. For the same trees, when the values are assigned to the leaf values independently of each other and say zero and one are both equally probable, the expected number of nodes evaluated is
426:
147:
673:
582:
749:
699:
762:
An animated pedagogical example that attempts to be human-friendly by substituting initial infinite (or arbitrarily large) values for emptiness and by avoiding using the
94:
1031:, where the last move that caused a beta-cutoff at the same tree level in the tree search is always examined first. This idea can also be generalized into a set of
1038:
Alpha–beta search can be made even faster by considering only a narrow search window (generally determined by guesswork based on experience). This is known as an
719:
614:
1794:
226:
had an early version for a checkers simulation. Richards, Timothy Hart, Michael Levin and/or Daniel
Edwards also invented alpha–beta independently in the
188:
Alpha Beta
Pruning can also be applied to the trees of any depths and is also possible to prune the entire subtrees rather than just leaves.
3112:
1672:
1335:
1066:(lower edge of window was too high). This gives information about what window values might be useful in a re-search of the position.
1787:
208:, who was writing a chess program. McCarthy invented alpha–beta search and recommended it to him, but Bernstein was "unconvinced".
443:
1091:
and beta estimates, that both can help produce cutoffs for higher depth searches much earlier than would otherwise be possible.
1895:
1087:
1024:
776:
3102:
2040:
1736:
1712:
1350:
1286:
2939:
1780:
950:
value := max(value, alphabeta(child, depth − 1, α, β, FALSE)) α := max(α, value)
979:
value := min(value, alphabeta(child, depth − 1, α, β, TRUE)) β := min(β, value)
2756:
2291:
2089:
1873:
223:
219:
17:
2575:
2394:
1763:
1681:
1543:
1450:
1526:
Saks, M.; Wigderson, A. (1986). "Probabilistic
Boolean Decision Trees and the Complexity of Evaluating Game Trees".
2196:
361:
110:
1102:
strategy. This can potentially make them more time-efficient, but typically at a heavy cost in space-efficiency.
2665:
1027:
through the game-tree analysis may be evaluated before others. Another common, and very cheap, heuristic is the
2535:
2206:
1960:
2374:
2716:
2134:
2109:
1878:
1202:
432:, or, equivalently, the search can go twice as deep with the same amount of computation. The explanation of
222:
calls an "approximation" in 1958 wrote that alpha–beta "appears to have been reinvented a number of times".
3066:
2492:
2246:
2236:
2171:
1950:
1227:
701:
limit, which is again optimal for these kind random trees. Note that the actual work for "small" values of
619:
100:
53:
428:. In the latter case, where the ply of a search is even, the effective branching factor is reduced to its
2286:
2266:
1573:
537:
162:
3117:
3000:
2751:
2721:
2379:
2221:
2216:
1940:
1142:
1137:
31:
3107:
3036:
2959:
2695:
2251:
2176:
2033:
170:
2009:
1983:
724:
3051:
2784:
2670:
2467:
2261:
2079:
1998:
2854:
678:
3056:
2655:
2625:
2281:
2069:
1945:
1917:
27:
Search algorithm that seeks to decrease the number of nodes in the minimax algorithm search tree
3081:
3061:
3041:
2660:
2565:
2424:
2369:
2301:
2271:
2191:
2119:
1988:
1955:
1836:
1044:. In the extreme case, the search is performed with alpha and beta equal; a technique known as
1484:"The Solution for the Branching Factor of the Alpha-Beta Pruning Algorithm and Its Optimality"
63:
2540:
2525:
2099:
1975:
1932:
1448:
Pearl, Judea (1980). "Asymptotic
Properties of Minimax Trees and Game-Searching Procedures".
2874:
2859:
2746:
2741:
2645:
2630:
2595:
2560:
2159:
2104:
2026:
1868:
1863:
1841:
1356:
8:
3031:
2650:
2600:
2437:
2364:
2344:
2201:
2084:
1993:
1829:
1147:
1127:
783:
2690:
1641:
169:. It is an adversarial search algorithm used commonly for machine playing of two-player
3010:
2869:
2700:
2680:
2530:
2409:
2314:
2241:
2186:
1965:
1890:
1549:
1505:
1425:
1390:
1083:
704:
231:
197:
1772:
587:
2995:
2964:
2919:
2814:
2685:
2640:
2615:
2545:
2419:
2349:
2339:
2231:
2181:
2129:
1912:
1853:
1759:
1742:
1732:
1726:
1708:
1699:
Heineman, George T.; Pollice, Gary; Selkow, Stanley (2008). "7. Path
Finding in AI".
1687:
1677:
1663:
1539:
1463:
1386:
1346:
1099:
1040:
845:
value := max(value, alphabeta(child, depth − 1, α, β, FALSE))
313:
1429:
1046:
875:
value := min(value, alphabeta(child, depth − 1, α, β, TRUE))
3076:
3071:
3005:
2969:
2949:
2909:
2879:
2834:
2789:
2774:
2731:
2585:
2226:
2163:
2149:
2114:
1637:
1553:
1531:
1509:
1495:
1459:
1417:
1394:
1382:
1290:
1261:
1181:
1132:
1032:
1028:
1018:
Further improvement can be achieved without sacrificing accuracy by using ordering
302:
294:
239:
215:
158:
46:
616:
interval uniformly at random, the expected number of nodes evaluated increases to
317:
242:
independently conceived the alpha–beta algorithm, publishing his results in 1963.
201:
2974:
2934:
2889:
2804:
2799:
2520:
2472:
2359:
2124:
2094:
2064:
1816:
1803:
798:
The pseudo-code for depth limited minimax with alpha–beta pruning is as follows:
316:, the maximum number of leaf node positions evaluated (when the move ordering is
103:
56:
2839:
1373:
Knuth, Donald E.; Moore, Ronald W. (1975). "An analysis of alpha-beta pruning".
288:
and min levels represent the turn of the player and the adversary, respectively.
2914:
2904:
2894:
2829:
2819:
2809:
2794:
2590:
2570:
2555:
2550:
2510:
2477:
2462:
2457:
2447:
2256:
1807:
1117:
321:
1746:
3096:
2954:
2944:
2899:
2884:
2864:
2635:
2610:
2482:
2452:
2442:
2429:
2334:
2276:
2211:
2144:
1907:
1704:
264:
227:
2929:
2924:
2779:
2354:
1756:
Analysis of
Speedup in Distributed Algorithms (revision of 1981 PhD thesis)
1667:
782:
Additionally, this algorithm can be trivially modified to return an entire
243:
211:
1754:
Fishburn, John P. (1984). "Appendix A: Some
Optimizations of α-β Search".
1500:
1483:
1408:
Abramson, Bruce (1 June 1989). "Control strategies for two-player games".
1266:
1249:
3046:
2849:
2844:
2824:
2620:
2605:
2414:
2384:
2319:
2309:
2139:
2074:
2050:
1858:
1722:
1625:
1535:
429:
247:
174:
2018:
1421:
2675:
2329:
1309:
1294:
235:
1728:
Heuristics: Intelligent Search
Strategies for Computer Problem Solving
2580:
2500:
2324:
1070:
name Lalphabeta ("last move with minimal window alpha–beta search").
1019:
260:
182:
166:
161:
that seeks to decrease the number of nodes that are evaluated by the
3015:
2515:
1007:
1003:
904:
900:
771:
786:
in addition to the score. Some more aggressive algorithms such as
2736:
2726:
2404:
1122:
1112:
1079:
763:
1691:
1608:
1606:
1161:
805:
The following pseudo-code illustrates the fail-hard variation.
787:
234:
in 1956 and suggested it to a group of his students including
2505:
283:
178:
1603:
1591:
527:{\displaystyle \Theta (((b-1+{\sqrt {b^{2}+14b+1}})/4)^{d})}
1922:
1846:
1250:"Computer science as empirical inquiry: symbols and search"
1095:
910:
The following pseudocode illustrates fail-soft alpha-beta.
758:
205:
1528:
27th Annual Symposium on Foundations of Computer Science
1902:
1885:
1802:
1203:"The Dartmouth Workshop--as planned and as it happened"
1698:
727:
707:
681:
622:
590:
540:
446:
364:
113:
66:
246:and Ronald W. Moore refined the algorithm in 1975.
743:
713:
693:
667:
608:
576:
526:
420:
278:
141:
88:
1248:Newell, Allen; Simon, Herbert A. (1 March 1976).
1228:"Human Level AI Is Harder Than It Seemed in 1955"
3094:
1521:
1519:
916:alphabeta(node, depth, α, β, maximizingPlayer)
811:alphabeta(node, depth, α, β, maximizingPlayer)
1225:
2034:
1788:
1662:
1628:; Korf, Richard (1987), "Search techniques",
1612:
1597:
1567:
1565:
1563:
1525:
1516:
1281:Edwards, D.J.; Hart, T.P. (4 December 1961).
1167:
421:{\displaystyle O(b^{d/2})=O({\sqrt {b^{d}}})}
230:. McCarthy proposed similar ideas during the
142:{\displaystyle O\left({\sqrt {b^{d}}}\right)}
1477:
1475:
1473:
1443:
1441:
1439:
1280:
1247:
2041:
2027:
1795:
1781:
1673:Artificial Intelligence: A Modern Approach
1560:
1372:
1366:
1082:algorithm and its variants are inherently
790:do not easily permit such a modification.
2048:
1624:
1499:
1470:
1436:
1316:. RLE and MIT Computation Center. Memo 41
1265:
1013:
1758:. UMI Research Press. pp. 107–111.
1753:
1407:
1401:
1333:
1200:
757:
282:
1343:Encyclopedia of Artificial Intelligence
1327:
14:
3095:
1179:
2022:
1776:
1721:
1481:
1447:
1307:
1287:Massachusetts Institute of Technology
1062:(high edge of window was too low) or
668:{\displaystyle \Theta (b^{d/log(d)})}
1571:
1301:
1274:
3113:Optimization algorithms and methods
1642:10.1146/annurev.cs.02.060187.002315
1226:McCarthy, John (27 November 2006).
1073:
24:
2090:First-player and second-player win
1676:(4th ed.). Hoboken: Pearson.
1219:
688:
623:
577:{\displaystyle \Theta ((b/2)^{d})}
541:
447:
25:
3129:
1630:Annual Review of Computer Science
1241:
2197:Coalition-proof Nash equilibrium
1002:alphabeta(origin, depth, −
934:the heuristic value of node
899:alphabeta(origin, depth, −
889:β := min(β, value)
859:α := max(α, value)
829:the heuristic value of node
770:Normally during alpha–beta, the
2010:List of graph search algorithms
1656:
1618:
1314:Artificial Intelligence Project
942:value := −∞
837:value := −∞
279:Improvements over naive minimax
2207:Evolutionarily stable strategy
1194:
1173:
744:{\displaystyle 0.925d^{0.747}}
685:
662:
657:
651:
626:
603:
591:
571:
562:
547:
544:
521:
512:
500:
456:
453:
450:
415:
398:
389:
368:
301:With an (average or constant)
263:can represent many two-player
83:
70:
13:
1:
2135:Simultaneous action selection
1201:McCarthy, John (2006-10-30).
1180:Marnur, Sachin (2024-04-23).
1154:
1098:, on the other hand, use the
793:
721:is better approximated using
358:×1×...×1) for even depth, or
3103:Game artificial intelligence
3067:List of games in game theory
2247:Quantal response equilibrium
2237:Perfect Bayesian equilibrium
2172:Bayes correlated equilibrium
1572:Levy, David (January 1986).
1464:10.1016/0004-3702(80)90037-5
1387:10.1016/0004-3702(75)90019-3
694:{\displaystyle d\to \infty }
254:
7:
2536:Optional prisoner's dilemma
2267:Self-confirming equilibrium
1345:. Wiley. pp. 159–171.
1334:Marsland, T.A. (May 1987).
1105:
10:
3134:
3001:Principal variation search
2717:Aumann's agreement theorem
2380:Strategy-stealing argument
2292:Trembling hand equilibrium
2222:Markov perfect equilibrium
2217:Mertens-stable equilibrium
1143:Principal variation search
1138:Combinatorial optimization
191:
32:Alphabeta (disambiguation)
29:
3037:Combinatorial game theory
3024:
2983:
2765:
2709:
2696:Princess and monster game
2491:
2393:
2300:
2252:Quasi-perfect equilibrium
2177:Bayesian Nash equilibrium
2158:
2057:
2007:
1974:
1931:
1815:
1613:Russell & Norvig 2021
1598:Russell & Norvig 2021
1488:Communications of the ACM
1310:"A Chess Playing Program"
1254:Communications of the ACM
1168:Russell & Norvig 2021
971:value := +∞
867:value := +∞
196:John McCarthy during the
99:
52:
42:
3052:Evolutionary game theory
2785:Antoine Augustin Cournot
2671:Guess 2/3 of the average
2468:Strictly determined game
2262:Satisfaction equilibrium
2080:Escalation of commitment
1701:Algorithms in a Nutshell
1341:. In Shapiro, S. (ed.).
1336:"Computer Chess Methods"
1283:The Alpha–beta Heuristic
309:, and a search depth of
89:{\displaystyle O(b^{d})}
3057:Glossary of game theory
2656:Stackelberg competition
2282:Strong Nash equilibrium
1918:Monte Carlo tree search
1451:Artificial Intelligence
1375:Artificial Intelligence
1207:www-formal.stanford.edu
766:coding simplifications.
3082:Tragedy of the commons
3062:List of game theorists
3042:Confrontation analysis
2752:Sprague–Grundy theorem
2272:Sequential equilibrium
2192:Correlated equilibrium
1014:Heuristic improvements
767:
745:
715:
695:
669:
610:
578:
528:
422:
289:
143:
90:
2855:Jean-François Mertens
1976:Minimum spanning tree
1501:10.1145/358589.358616
1482:Pearl, Judea (1982).
1410:ACM Computing Surveys
1308:Kotok, Alan (2004) .
1267:10.1145/360018.360022
1230:. Stanford University
1086:, a strategy such as
761:
746:
716:
696:
670:
611:
579:
529:
423:
286:
144:
91:
2984:Search optimizations
2860:Jennifer Tour Chayes
2747:Revelation principle
2742:Purification theorem
2681:Nash bargaining game
2646:Bertrand competition
2631:El Farol Bar problem
2596:Electronic mail game
2561:Lewis signaling game
2105:Hierarchy of beliefs
1961:Shortest path faster
1869:Breadth-first search
1864:Bidirectional search
1810:traversal algorithms
1707:. pp. 217–223.
1536:10.1109/SFCS.1986.44
1285:(Technical report).
1182:"Alpha Beta Pruning"
725:
705:
679:
620:
588:
538:
444:
362:
346:) for odd depth and
111:
64:
30:For other uses, see
3032:Bounded rationality
2651:Cournot competition
2601:Rock paper scissors
2576:Battle of the sexes
2566:Volunteer's dilemma
2438:Perfect information
2365:Dominant strategies
2202:Epsilon-equilibrium
2085:Extensive-form game
1896:Iterative deepening
1422:10.1145/66443.66444
1148:Transposition table
1128:Pruning (algorithm)
1088:iterative deepening
784:principal variation
777:iterative deepening
171:combinatorial games
39:
3011:Paranoid algorithm
2991:Alpha–beta pruning
2870:John Maynard Smith
2701:Rendezvous problem
2541:Traveler's dilemma
2531:Gift-exchange game
2526:Prisoner's dilemma
2443:Large Poisson game
2410:Bargaining problem
2315:Backward induction
2287:Subgame perfection
2242:Proper equilibrium
1891:Depth-first search
1731:. Addison-Wesley.
1664:Russell, Stuart J.
1530:. pp. 29–38.
1170:, p. 152-161.
1052:null-window search
1047:zero-window search
1000:(* Initial call *)
897:(* Initial call *)
768:
741:
711:
691:
665:
606:
574:
524:
418:
290:
232:Dartmouth workshop
198:Dartmouth Workshop
155:Alpha–beta pruning
139:
86:
38:Alpha–beta pruning
37:
18:Alpha-beta pruning
3118:Search algorithms
3090:
3089:
2996:Aspiration window
2965:Suzanne Scotchmer
2920:Oskar Morgenstern
2815:Donald B. Gillies
2757:Zermelo's theorem
2686:Induction puzzles
2641:Fair cake-cutting
2616:Public goods game
2546:Coordination game
2420:Intransitive game
2350:Forward induction
2232:Pareto efficiency
2212:Gibbs equilibrium
2182:Berge equilibrium
2130:Simultaneous game
2016:
2015:
1913:Jump point search
1854:Best-first search
1738:978-0-201-05594-8
1714:978-0-596-51624-6
1580:. pp. 98–102
1574:"Alpha-Beta Soup"
1352:978-0-471-62974-0
1041:aspiration window
1033:refutation tables
938:maximizingPlayer
927:node is terminal
833:maximizingPlayer
822:node is terminal
714:{\displaystyle d}
498:
413:
163:minimax algorithm
152:
151:
133:
16:(Redirected from
3125:
3108:Graph algorithms
3077:Topological game
3072:No-win situation
2970:Thomas Schelling
2950:Robert B. Wilson
2910:Merrill M. Flood
2880:John von Neumann
2790:Ariel Rubinstein
2775:Albert W. Tucker
2626:War of attrition
2586:Matching pennies
2227:Nash equilibrium
2150:Mechanism design
2115:Normal-form game
2070:Cooperative game
2043:
2036:
2029:
2020:
2019:
1797:
1790:
1783:
1774:
1773:
1769:
1750:
1718:
1695:
1650:
1649:
1622:
1616:
1610:
1601:
1595:
1589:
1588:
1586:
1585:
1569:
1558:
1557:
1523:
1514:
1513:
1503:
1479:
1468:
1467:
1445:
1434:
1433:
1405:
1399:
1398:
1370:
1364:
1363:
1361:
1355:. Archived from
1340:
1331:
1325:
1324:
1322:
1321:
1305:
1299:
1298:
1278:
1272:
1271:
1269:
1245:
1239:
1238:
1236:
1235:
1223:
1217:
1216:
1214:
1213:
1198:
1192:
1191:
1189:
1188:
1177:
1171:
1165:
1133:Branch and bound
1094:Algorithms like
1074:Other algorithms
1029:killer heuristic
750:
748:
747:
742:
740:
739:
720:
718:
717:
712:
700:
698:
697:
692:
674:
672:
671:
666:
661:
660:
641:
615:
613:
612:
609:{\displaystyle }
607:
583:
581:
580:
575:
570:
569:
557:
533:
531:
530:
525:
520:
519:
507:
499:
482:
481:
472:
427:
425:
424:
419:
414:
412:
411:
402:
388:
387:
383:
303:branching factor
295:branch and bound
240:Alexander Brudno
238:at MIT in 1961.
216:Herbert A. Simon
159:search algorithm
148:
146:
145:
140:
138:
134:
132:
131:
122:
95:
93:
92:
87:
82:
81:
47:Search algorithm
40:
36:
21:
3133:
3132:
3128:
3127:
3126:
3124:
3123:
3122:
3093:
3092:
3091:
3086:
3020:
3006:max^n algorithm
2979:
2975:William Vickrey
2935:Reinhard Selten
2890:Kenneth Binmore
2805:David K. Levine
2800:Daniel Kahneman
2767:
2761:
2737:Negamax theorem
2727:Minimax theorem
2705:
2666:Diner's dilemma
2521:All-pay auction
2487:
2473:Stochastic game
2425:Mean-field game
2396:
2389:
2360:Markov strategy
2296:
2162:
2154:
2125:Sequential game
2110:Information set
2095:Game complexity
2065:Congestion game
2053:
2047:
2017:
2012:
2003:
1970:
1927:
1811:
1801:
1766:
1739:
1715:
1684:
1659:
1654:
1653:
1623:
1619:
1611:
1604:
1596:
1592:
1583:
1581:
1570:
1561:
1546:
1524:
1517:
1480:
1471:
1446:
1437:
1406:
1402:
1371:
1367:
1359:
1353:
1338:
1332:
1328:
1319:
1317:
1306:
1302:
1279:
1275:
1246:
1242:
1233:
1231:
1224:
1220:
1211:
1209:
1199:
1195:
1186:
1184:
1178:
1174:
1166:
1162:
1157:
1152:
1108:
1076:
1016:
1011:
997:
908:
894:
796:
735:
731:
726:
723:
722:
706:
703:
702:
680:
677:
676:
637:
633:
629:
621:
618:
617:
589:
586:
585:
565:
561:
553:
539:
536:
535:
515:
511:
503:
477:
473:
471:
445:
442:
441:
407:
403:
401:
379:
375:
371:
363:
360:
359:
281:
257:
194:
127:
123:
121:
117:
112:
109:
108:
77:
73:
65:
62:
61:
35:
28:
23:
22:
15:
12:
11:
5:
3131:
3121:
3120:
3115:
3110:
3105:
3088:
3087:
3085:
3084:
3079:
3074:
3069:
3064:
3059:
3054:
3049:
3044:
3039:
3034:
3028:
3026:
3022:
3021:
3019:
3018:
3013:
3008:
3003:
2998:
2993:
2987:
2985:
2981:
2980:
2978:
2977:
2972:
2967:
2962:
2957:
2952:
2947:
2942:
2940:Robert Axelrod
2937:
2932:
2927:
2922:
2917:
2915:Olga Bondareva
2912:
2907:
2905:Melvin Dresher
2902:
2897:
2895:Leonid Hurwicz
2892:
2887:
2882:
2877:
2872:
2867:
2862:
2857:
2852:
2847:
2842:
2837:
2832:
2830:Harold W. Kuhn
2827:
2822:
2820:Drew Fudenberg
2817:
2812:
2810:David M. Kreps
2807:
2802:
2797:
2795:Claude Shannon
2792:
2787:
2782:
2777:
2771:
2769:
2763:
2762:
2760:
2759:
2754:
2749:
2744:
2739:
2734:
2732:Nash's theorem
2729:
2724:
2719:
2713:
2711:
2707:
2706:
2704:
2703:
2698:
2693:
2688:
2683:
2678:
2673:
2668:
2663:
2658:
2653:
2648:
2643:
2638:
2633:
2628:
2623:
2618:
2613:
2608:
2603:
2598:
2593:
2591:Ultimatum game
2588:
2583:
2578:
2573:
2571:Dollar auction
2568:
2563:
2558:
2556:Centipede game
2553:
2548:
2543:
2538:
2533:
2528:
2523:
2518:
2513:
2511:Infinite chess
2508:
2503:
2497:
2495:
2489:
2488:
2486:
2485:
2480:
2478:Symmetric game
2475:
2470:
2465:
2463:Signaling game
2460:
2458:Screening game
2455:
2450:
2448:Potential game
2445:
2440:
2435:
2427:
2422:
2417:
2412:
2407:
2401:
2399:
2391:
2390:
2388:
2387:
2382:
2377:
2375:Mixed strategy
2372:
2367:
2362:
2357:
2352:
2347:
2342:
2337:
2332:
2327:
2322:
2317:
2312:
2306:
2304:
2298:
2297:
2295:
2294:
2289:
2284:
2279:
2274:
2269:
2264:
2259:
2257:Risk dominance
2254:
2249:
2244:
2239:
2234:
2229:
2224:
2219:
2214:
2209:
2204:
2199:
2194:
2189:
2184:
2179:
2174:
2168:
2166:
2156:
2155:
2153:
2152:
2147:
2142:
2137:
2132:
2127:
2122:
2117:
2112:
2107:
2102:
2100:Graphical game
2097:
2092:
2087:
2082:
2077:
2072:
2067:
2061:
2059:
2055:
2054:
2046:
2045:
2038:
2031:
2023:
2014:
2013:
2008:
2005:
2004:
2002:
2001:
1999:Reverse-delete
1996:
1991:
1986:
1980:
1978:
1972:
1971:
1969:
1968:
1963:
1958:
1953:
1951:Floyd–Warshall
1948:
1943:
1937:
1935:
1929:
1928:
1926:
1925:
1920:
1915:
1910:
1905:
1900:
1899:
1898:
1888:
1883:
1882:
1881:
1876:
1866:
1861:
1856:
1851:
1850:
1849:
1844:
1839:
1827:
1821:
1819:
1813:
1812:
1800:
1799:
1792:
1785:
1777:
1771:
1770:
1764:
1751:
1737:
1719:
1713:
1696:
1682:
1668:Norvig, Peter.
1658:
1655:
1652:
1651:
1617:
1615:, p. 154.
1602:
1600:, p. 155.
1590:
1559:
1544:
1515:
1469:
1458:(2): 113–138.
1435:
1416:(2): 137–161.
1400:
1381:(4): 293–326.
1365:
1362:on 2008-10-30.
1351:
1326:
1300:
1273:
1260:(3): 113–126.
1240:
1218:
1193:
1172:
1159:
1158:
1156:
1153:
1151:
1150:
1145:
1140:
1135:
1130:
1125:
1120:
1118:Expectiminimax
1115:
1109:
1107:
1104:
1075:
1072:
1025:earlier passes
1015:
1012:
998:
991:(* α cutoff *)
975:child of node
962:(* β cutoff *)
946:child of node
912:
895:
887:(* α cutoff *)
871:child of node
857:(* β cutoff *)
841:child of node
807:
795:
792:
738:
734:
730:
710:
690:
687:
684:
664:
659:
656:
653:
650:
647:
644:
640:
636:
632:
628:
625:
605:
602:
599:
596:
593:
573:
568:
564:
560:
556:
552:
549:
546:
543:
523:
518:
514:
510:
506:
502:
497:
494:
491:
488:
485:
480:
476:
470:
467:
464:
461:
458:
455:
452:
449:
417:
410:
406:
400:
397:
394:
391:
386:
382:
378:
374:
370:
367:
280:
277:
265:zero-sum games
256:
253:
218:who used what
202:Alex Bernstein
193:
190:
150:
149:
137:
130:
126:
120:
116:
106:
97:
96:
85:
80:
76:
72:
69:
59:
50:
49:
44:
26:
9:
6:
4:
3:
2:
3130:
3119:
3116:
3114:
3111:
3109:
3106:
3104:
3101:
3100:
3098:
3083:
3080:
3078:
3075:
3073:
3070:
3068:
3065:
3063:
3060:
3058:
3055:
3053:
3050:
3048:
3045:
3043:
3040:
3038:
3035:
3033:
3030:
3029:
3027:
3025:Miscellaneous
3023:
3017:
3014:
3012:
3009:
3007:
3004:
3002:
2999:
2997:
2994:
2992:
2989:
2988:
2986:
2982:
2976:
2973:
2971:
2968:
2966:
2963:
2961:
2960:Samuel Bowles
2958:
2956:
2955:Roger Myerson
2953:
2951:
2948:
2946:
2945:Robert Aumann
2943:
2941:
2938:
2936:
2933:
2931:
2928:
2926:
2923:
2921:
2918:
2916:
2913:
2911:
2908:
2906:
2903:
2901:
2900:Lloyd Shapley
2898:
2896:
2893:
2891:
2888:
2886:
2885:Kenneth Arrow
2883:
2881:
2878:
2876:
2873:
2871:
2868:
2866:
2865:John Harsanyi
2863:
2861:
2858:
2856:
2853:
2851:
2848:
2846:
2843:
2841:
2838:
2836:
2835:Herbert Simon
2833:
2831:
2828:
2826:
2823:
2821:
2818:
2816:
2813:
2811:
2808:
2806:
2803:
2801:
2798:
2796:
2793:
2791:
2788:
2786:
2783:
2781:
2778:
2776:
2773:
2772:
2770:
2764:
2758:
2755:
2753:
2750:
2748:
2745:
2743:
2740:
2738:
2735:
2733:
2730:
2728:
2725:
2723:
2720:
2718:
2715:
2714:
2712:
2708:
2702:
2699:
2697:
2694:
2692:
2689:
2687:
2684:
2682:
2679:
2677:
2674:
2672:
2669:
2667:
2664:
2662:
2659:
2657:
2654:
2652:
2649:
2647:
2644:
2642:
2639:
2637:
2636:Fair division
2634:
2632:
2629:
2627:
2624:
2622:
2619:
2617:
2614:
2612:
2611:Dictator game
2609:
2607:
2604:
2602:
2599:
2597:
2594:
2592:
2589:
2587:
2584:
2582:
2579:
2577:
2574:
2572:
2569:
2567:
2564:
2562:
2559:
2557:
2554:
2552:
2549:
2547:
2544:
2542:
2539:
2537:
2534:
2532:
2529:
2527:
2524:
2522:
2519:
2517:
2514:
2512:
2509:
2507:
2504:
2502:
2499:
2498:
2496:
2494:
2490:
2484:
2483:Zero-sum game
2481:
2479:
2476:
2474:
2471:
2469:
2466:
2464:
2461:
2459:
2456:
2454:
2453:Repeated game
2451:
2449:
2446:
2444:
2441:
2439:
2436:
2434:
2432:
2428:
2426:
2423:
2421:
2418:
2416:
2413:
2411:
2408:
2406:
2403:
2402:
2400:
2398:
2392:
2386:
2383:
2381:
2378:
2376:
2373:
2371:
2370:Pure strategy
2368:
2366:
2363:
2361:
2358:
2356:
2353:
2351:
2348:
2346:
2343:
2341:
2338:
2336:
2335:De-escalation
2333:
2331:
2328:
2326:
2323:
2321:
2318:
2316:
2313:
2311:
2308:
2307:
2305:
2303:
2299:
2293:
2290:
2288:
2285:
2283:
2280:
2278:
2277:Shapley value
2275:
2273:
2270:
2268:
2265:
2263:
2260:
2258:
2255:
2253:
2250:
2248:
2245:
2243:
2240:
2238:
2235:
2233:
2230:
2228:
2225:
2223:
2220:
2218:
2215:
2213:
2210:
2208:
2205:
2203:
2200:
2198:
2195:
2193:
2190:
2188:
2185:
2183:
2180:
2178:
2175:
2173:
2170:
2169:
2167:
2165:
2161:
2157:
2151:
2148:
2146:
2145:Succinct game
2143:
2141:
2138:
2136:
2133:
2131:
2128:
2126:
2123:
2121:
2118:
2116:
2113:
2111:
2108:
2106:
2103:
2101:
2098:
2096:
2093:
2091:
2088:
2086:
2083:
2081:
2078:
2076:
2073:
2071:
2068:
2066:
2063:
2062:
2060:
2056:
2052:
2044:
2039:
2037:
2032:
2030:
2025:
2024:
2021:
2011:
2006:
2000:
1997:
1995:
1992:
1990:
1987:
1985:
1982:
1981:
1979:
1977:
1973:
1967:
1964:
1962:
1959:
1957:
1954:
1952:
1949:
1947:
1944:
1942:
1939:
1938:
1936:
1934:
1933:Shortest path
1930:
1924:
1921:
1919:
1916:
1914:
1911:
1909:
1908:Fringe search
1906:
1904:
1901:
1897:
1894:
1893:
1892:
1889:
1887:
1884:
1880:
1877:
1875:
1874:Lexicographic
1872:
1871:
1870:
1867:
1865:
1862:
1860:
1857:
1855:
1852:
1848:
1845:
1843:
1840:
1838:
1835:
1834:
1833:
1832:
1828:
1826:
1823:
1822:
1820:
1818:
1814:
1809:
1805:
1798:
1793:
1791:
1786:
1784:
1779:
1778:
1775:
1767:
1765:0-8357-1527-2
1761:
1757:
1752:
1748:
1744:
1740:
1734:
1730:
1729:
1724:
1720:
1716:
1710:
1706:
1705:Oreilly Media
1702:
1697:
1693:
1689:
1685:
1683:9780134610993
1679:
1675:
1674:
1669:
1665:
1661:
1660:
1648:
1643:
1639:
1635:
1631:
1627:
1621:
1614:
1609:
1607:
1599:
1594:
1579:
1575:
1568:
1566:
1564:
1555:
1551:
1547:
1545:0-8186-0740-8
1541:
1537:
1533:
1529:
1522:
1520:
1511:
1507:
1502:
1497:
1494:(8): 559–64.
1493:
1489:
1485:
1478:
1476:
1474:
1465:
1461:
1457:
1453:
1452:
1444:
1442:
1440:
1431:
1427:
1423:
1419:
1415:
1411:
1404:
1396:
1392:
1388:
1384:
1380:
1376:
1369:
1358:
1354:
1348:
1344:
1337:
1330:
1315:
1311:
1304:
1296:
1292:
1288:
1284:
1277:
1268:
1263:
1259:
1255:
1251:
1244:
1229:
1222:
1208:
1204:
1197:
1183:
1176:
1169:
1164:
1160:
1149:
1146:
1144:
1141:
1139:
1136:
1134:
1131:
1129:
1126:
1124:
1121:
1119:
1116:
1114:
1111:
1110:
1103:
1101:
1097:
1092:
1089:
1085:
1081:
1071:
1067:
1065:
1061:
1057:
1053:
1049:
1048:
1043:
1042:
1036:
1034:
1030:
1026:
1021:
1009:
1005:
1001:
995:
992:
989:
986:
982:
978:
974:
970:
966:
963:
960:
957:
953:
949:
945:
941:
937:
933:
930:
926:
922:
919:
915:
911:
906:
902:
898:
892:
888:
885:
882:
879:value < α
878:
874:
870:
866:
862:
858:
855:
852:
849:value > β
848:
844:
840:
836:
832:
828:
825:
821:
817:
814:
810:
806:
803:
799:
791:
789:
785:
780:
778:
773:
765:
760:
756:
752:
736:
732:
728:
708:
682:
654:
648:
645:
642:
638:
634:
630:
600:
597:
594:
566:
558:
554:
550:
516:
508:
504:
495:
492:
489:
486:
483:
478:
474:
468:
465:
462:
459:
439:
435:
431:
408:
404:
395:
392:
384:
380:
376:
372:
365:
357:
353:
349:
345:
341:
337:
333:
329:
325:
324:
319:
315:
312:
308:
304:
299:
296:
285:
276:
272:
268:
266:
262:
252:
249:
245:
241:
237:
233:
229:
228:United States
225:
224:Arthur Samuel
221:
220:John McCarthy
217:
213:
209:
207:
203:
199:
189:
186:
184:
180:
176:
172:
168:
164:
160:
156:
135:
128:
124:
118:
114:
107:
105:
102:
98:
78:
74:
67:
60:
58:
55:
51:
48:
45:
41:
33:
19:
2990:
2930:Peyton Young
2925:Paul Milgrom
2840:Hervé Moulin
2780:Amos Tversky
2722:Folk theorem
2433:-player game
2430:
2355:Grim trigger
1941:Bellman–Ford
1830:
1824:
1755:
1727:
1723:Pearl, Judea
1700:
1671:
1657:Bibliography
1645:
1633:
1629:
1626:Pearl, Judea
1620:
1593:
1582:. Retrieved
1577:
1527:
1491:
1487:
1455:
1449:
1413:
1409:
1403:
1378:
1374:
1368:
1357:the original
1342:
1329:
1318:. Retrieved
1313:
1303:
1282:
1276:
1257:
1253:
1243:
1232:. Retrieved
1221:
1210:. Retrieved
1206:
1196:
1185:. Retrieved
1175:
1163:
1093:
1077:
1068:
1063:
1059:
1056:scout search
1055:
1051:
1045:
1039:
1037:
1017:
999:
993:
990:
987:
984:
980:
976:
972:
968:
964:
961:
958:
955:
951:
947:
943:
939:
935:
931:
928:
924:
920:
917:
913:
909:
896:
890:
886:
883:
880:
876:
872:
868:
864:
860:
856:
853:
850:
846:
842:
838:
834:
830:
826:
823:
819:
815:
812:
808:
804:
800:
797:
781:
769:
753:
437:
433:
355:
351:
347:
343:
339:
335:
331:
327:
322:
310:
306:
300:
291:
273:
269:
258:
244:Donald Knuth
212:Allen Newell
210:
195:
187:
154:
153:
3047:Coopetition
2850:Jean Tirole
2845:John Conway
2825:Eric Maskin
2621:Blotto game
2606:Pirate game
2415:Global game
2385:Tit for tat
2320:Bid shading
2310:Appeasement
2160:Equilibrium
2140:Solved game
2075:Determinacy
2058:Definitions
2051:game theory
1859:Beam search
1825:α–β pruning
1636:: 451–467,
1295:1721.1/6098
1084:depth-first
923:depth == 0
818:depth == 0
430:square root
248:Judea Pearl
175:Tic-tac-toe
167:search tree
104:performance
57:performance
3097:Categories
2691:Trust game
2676:Kuhn poker
2345:Escalation
2340:Deterrence
2330:Cheap talk
2302:Strategies
2120:Preference
2049:Topics of
1946:Dijkstra's
1747:1035596197
1584:2021-10-19
1320:2006-07-01
1297:. AIM-030.
1234:2006-12-20
1212:2023-10-29
1187:2024-09-03
1155:References
1100:best-first
1078:Since the
1020:heuristics
983:value ≤ α
967:value
954:value ≥ β
863:value
794:Pseudocode
236:Alan Kotok
54:Worst-case
2875:John Nash
2581:Stag hunt
2325:Collusion
1989:Kruskal's
1984:Borůvka's
1956:Johnson's
1647:required.
689:∞
686:→
624:Θ
542:Θ
463:−
448:Θ
261:game tree
255:Core idea
183:Connect 4
101:Best-case
3016:Lazy SMP
2710:Theorems
2661:Deadlock
2516:Checkers
2397:of games
2164:concepts
1879:Parallel
1725:(1984).
1692:20190474
1670:(2021).
1430:11526154
1106:See also
1010:, TRUE)
973:for each
944:for each
914:function
907:, TRUE)
869:for each
839:for each
809:function
772:subtrees
318:pessimal
2768:figures
2551:Chicken
2405:Auction
2395:Classes
1578:MacUser
1554:6130392
1510:8296219
1395:7894372
1123:Negamax
1113:Minimax
1080:minimax
764:negamax
675:in the
342:×1×...×
192:History
165:in its
1994:Prim's
1817:Search
1762:
1745:
1735:
1711:
1690:
1680:
1552:
1542:
1508:
1428:
1393:
1349:
996:value
994:return
965:return
932:return
893:value
891:return
861:return
827:return
788:MTD(f)
2506:Chess
2493:Games
1966:Yen's
1804:Graph
1550:S2CID
1506:S2CID
1426:S2CID
1391:S2CID
1360:(PDF)
1339:(PDF)
1054:, or
988:break
959:break
884:break
854:break
737:0.747
729:0.925
320:) is
314:plies
179:Chess
157:is a
43:Class
2187:Core
1923:SSS*
1847:SMA*
1842:LPA*
1837:IDA*
1808:tree
1806:and
1760:ISBN
1743:OCLC
1733:ISBN
1709:ISBN
1688:LCCN
1678:ISBN
1540:ISBN
1347:ISBN
1096:SSS*
1060:high
985:then
969:else
956:then
940:then
929:then
881:then
865:else
851:then
835:then
824:then
214:and
200:met
2766:Key
1638:doi
1532:doi
1496:doi
1460:doi
1418:doi
1383:doi
1291:hdl
1262:doi
1064:low
1006:, +
903:, +
436:×1×
354:×1×
338:×1×
305:of
206:IBM
204:of
3099::
2501:Go
1903:D*
1886:B*
1831:A*
1741:.
1703:.
1686:.
1666:;
1644:,
1632:,
1605:^
1576:.
1562:^
1548:.
1538:.
1518:^
1504:.
1492:25
1490:.
1486:.
1472:^
1456:14
1454:.
1438:^
1424:.
1414:21
1412:.
1389:.
1377:.
1312:.
1289:.
1258:19
1256:.
1252:.
1205:.
1050:,
1035:.
981:if
977:do
952:if
948:do
936:if
925:or
921:if
918:is
877:if
873:do
847:if
843:do
831:if
820:or
816:if
813:is
779:.
751:.
487:14
259:A
181:,
177:,
2431:n
2042:e
2035:t
2028:v
1796:e
1789:t
1782:v
1768:.
1749:.
1717:.
1694:.
1640::
1634:2
1587:.
1556:.
1534::
1512:.
1498::
1466:.
1462::
1432:.
1420::
1397:.
1385::
1379:6
1323:.
1293::
1270:.
1264::
1237:.
1215:.
1190:.
1008:∞
1004:∞
905:∞
901:∞
733:d
709:d
683:d
663:)
658:)
655:d
652:(
649:g
646:o
643:l
639:/
635:d
631:b
627:(
604:]
601:1
598:,
595:0
592:[
572:)
567:d
563:)
559:2
555:/
551:b
548:(
545:(
522:)
517:d
513:)
509:4
505:/
501:)
496:1
493:+
490:b
484:+
479:2
475:b
469:+
466:1
460:b
457:(
454:(
451:(
438:b
434:b
416:)
409:d
405:b
399:(
396:O
393:=
390:)
385:2
381:/
377:d
373:b
369:(
366:O
356:b
352:b
350:(
348:O
344:b
340:b
336:b
334:(
332:O
328:b
326:(
323:O
311:d
307:b
173:(
136:)
129:d
125:b
119:(
115:O
84:)
79:d
75:b
71:(
68:O
34:.
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
