Avoiding game-tree pathology in 2-player adversarial search

Inon Zuckerman, Brandon Wilson, Dana S. Nau

פרסום מחקרי: פרסום בכתב עתמאמרביקורת עמיתים

7 ציטוטים ‏(Scopus)

תקציר

Adversarial search, or game-tree search, is a technique for analyzing an adversarial game to determine what moves a player should make in order to win a game. Until recently, lookahead pathology (in which deeper game-tree search results in worse play) has been thought to be quite rare. We provide an analysis that shows that every game should have some sections that are locally pathological, assuming that both players can potentially win the game. We also modify the minimax algorithm to recognize local pathologies in arbitrary games and cut off search accordingly (shallower search is more effective than deeper search when local pathologies occur). We show experimentally that our modified search procedure avoids local pathologies and consequently provides improved performance, in terms of decision accuracy, when compared with the minimax algorithm. In addition, we provide an experimental evaluation on the African game of Kalah, which shows the improved performances of our suggested error-minimizing minimax algorithm when there is a large degree of pathology.

שפה מקוריתאנגלית
עמודים (מ-עד)542-561
מספר עמודים20
כתב עתComputational Intelligence
כרך34
מספר גיליון2
מזהי עצם דיגיטלי (DOIs)
סטטוס פרסוםפורסם - מאי 2018

טביעת אצבע

להלן מוצגים תחומי המחקר של הפרסום 'Avoiding game-tree pathology in 2-player adversarial search'. יחד הם יוצרים טביעת אצבע ייחודית.

פורמט ציטוט ביבליוגרפי