2006 | OriginalPaper | Buchkapitel
Dual Lambda Search and Shogi Endgames
verfasst von : Shunsuke Soeda, Tomoyuki Kaneko, Tetsuro Tanaka
Erschienen in: Advances in Computer Games
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We propose a new threat-base search algorithm which takes into account threats by both players. In full-board Semeais in Go or Shogi endgames, making naive attack moves often result in losing the game. The reason is that a player must first make a defense move if the opponent has a better attack move than his own. Some attack moves weaken the defense of the player who made the move. Thus, players must be aware of the threats by both players to avoid such naive attack moves. However, existing threat-based search algorithms are only aware of threats by one player, and cannot detect such naive attacks efficiently. We propose a solution to this problem, by applying
λ
-search mutually recursively so that it searches the best move by taking into account threats by both players. We call this search algorithm
dual λ
-search
. Dual
λ
-search can handle inversions efficiently compared to previous algorithms by making passes for both players. We implemented dual
λ
-search with
Df-pn
as the driver, and made experiments with difficult Shogi-endgame problems. We showed the effectiveness of our algorithm by solving 32 problems out of 97. It includes solving problems that even one of the strongest Shogi program had not yet been able to solve correctly.