{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,1]],"date-time":"2025-11-01T21:37:53Z","timestamp":1762033073870,"version":"build-2065373602"},"reference-count":18,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2012,11,5]],"date-time":"2012-11-05T00:00:00Z","timestamp":1352073600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>The minimax algorithm, also called the negamax algorithm, remains today the most widely used search technique for two-player perfect-information games. However, minimaxing has been shown to be susceptible to game tree pathology, a paradoxical situation in which the accuracy of the search can decrease as the height of the tree increases. Alth\u00f6fer\u2019s alternative minimax algorithm has been proven to be invulnerable to pathology. However, it has not been clear whether alpha-beta pruning, a crucial component of practical game programs, could be applied in the context of Alh\u00f6fer\u2019s algorithm. In this brief paper, we show how alpha-beta pruning can be adapted to Alth\u00f6fer\u2019s algorithm.<\/jats:p>","DOI":"10.3390\/a5040521","type":"journal-article","created":{"date-parts":[[2012,11,5]],"date-time":"2012-11-05T11:09:37Z","timestamp":1352113777000},"page":"521-528","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Alpha-Beta Pruning and Alth\u00f6fer\u2019s Pathology-Free Negamax Algorithm"],"prefix":"10.3390","volume":"5","author":[{"given":"Ashraf M.","family":"Abdelbar","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, American University in Cairo, Cairo, Egypt"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2012,11,5]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/0004-3702(83)90004-8","article-title":"On the nature of pathology in game searching","volume":"20","author":"Pearl","year":"1983","journal-title":"Artif. Intell."},{"key":"ref_2","unstructured":"Delcher, A., and Kasif, S. (, January September). Improved Decision-Making in Game Trees: Recovering from Pathology. Proceedings of the National Conference on Artificial Intelligence, San Hose, CA, USA."},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"620","DOI":"10.1016\/j.artint.2006.01.006","article-title":"Is real-valued minimax pathological","volume":"170","author":"Gams","year":"2006","journal-title":"Artif. Intell."},{"key":"ref_4","unstructured":"Lu\u0161trek, M., and Bulitko, V. (, January July). Thinking too much: Pathology in Pathfinding. Proceedings of the 2008 Conference on ECAI, Patras, Greece."},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"211","DOI":"10.3233\/AIC-2008-0420","article-title":"Pathology in heuristic search","volume":"21","year":"2008","journal-title":"AI Commun."},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1016\/0004-3702(93)90108-N","article-title":"The multiplayer version of minimax displays game-tree pathology","volume":"64","author":"Mutchler","year":"1993","journal-title":"Artif. Intell."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/0004-3702(82)90002-9","article-title":"An investigation of the causes of pathology in games","volume":"19","author":"Nau","year":"1982","journal-title":"Artif. Intell."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/S0004-3702(83)80011-3","article-title":"Pathology on game trees revisited and an alternative to minimaxing","volume":"21","author":"Nau","year":"1983","journal-title":"Artif. Intell."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"1323","DOI":"10.1016\/j.artint.2010.08.002","article-title":"When is it better not to look ahead","volume":"174","author":"Nau","year":"2010","journal-title":"Artif. Intell."},{"key":"ref_10","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1016\/0004-3702(80)90037-5","article-title":"Asymptotic properties of minimax trees and game-searching procedures","volume":"14","author":"Pearl","year":"1980","journal-title":"Artif. Intell."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"65","DOI":"10.1080\/0952813X.2010.545997","article-title":"The pathology of heuristic search in the 8-puzzle","volume":"24","author":"Piltaver","year":"2012","journal-title":"J. Exp. Theor. Artif. Intell."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"261","DOI":"10.1016\/j.tcs.2005.09.073","article-title":"Bias and pathology in minimax search","volume":"349","author":"Sadikov","year":"2005","journal-title":"Theor. Comput. Sci."},{"key":"ref_13","first-page":"101","article-title":"Presence and Absence of Pathology on Game Trees","volume":"volume 4","author":"Beal","year":"1986","journal-title":"Advances in Computer Chess"},{"key":"ref_14","unstructured":"Wilson, B., Parker, A., and Nau, D. (, January July). Error Minimizing Minimax: Avoiding Search Pathology in Game Trees. Proceedings of International Symposium on Combinatorial Search (SoCS-09), Los Angeles, CA, USA."},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1016\/0004-3702(90)90070-G","article-title":"An incremental negamax algorithm","volume":"43","year":"1990","journal-title":"Artif. Intell."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"99","DOI":"10.1016\/S0004-3702(83)80006-X","article-title":"Searching for an optimal path in a tree with random costs","volume":"21","author":"Karp","year":"1983","journal-title":"Artif. Intell."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1016\/0004-3702(75)90019-3","article-title":"An analysis of alpha-beta pruning","volume":"6","author":"Knuth","year":"1975","journal-title":"Artif. Intell."},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0004-3702(01)00121-7","article-title":"Computer Go","volume":"134","year":"2002","journal-title":"Artif. Intell."}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/5\/4\/521\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:53:18Z","timestamp":1760219598000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/5\/4\/521"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,11,5]]},"references-count":18,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2012,12]]}},"alternative-id":["a5040521"],"URL":"https:\/\/doi.org\/10.3390\/a5040521","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2012,11,5]]}}}