以動態搜尋深度控制降低遊戲樹搜尋中的地平線效應

Reduce the Horizon Effects of Game Tree Search with Dynamic Search-depth Control

虞希舜(Hsi-Shun Yu)

指導教授 ： 許永真

國立臺灣大學/電機資訊學院/資訊工程學研究所/碩士(2021年)

https://doi.org/10.6342/NTU202101041

摘要

在遊戲樹搜尋過程中，某一方面臨不可避免的損失時，不正面應對問題尋求最小損失，而藉由以無意義的強迫手段逼使對方接應，使對手來不及在深度限制內下出得分手，這就是地平線效應(Horizon Effect)。
地平線效應發生率很高，大幅降低搜尋品質，所以早在1973就被發現並定名，但經過半個世紀，仍未有確切的解決方法。
在這篇論文中，將發現並定義地平線效應的關鍵原素：迫著(Forcing Move)與潛伏好手(Lurking Killer)，說明在遊戲樹搜尋過程中找出這兩種著手的方法，以及如何利用找出的著手動態控制搜尋深度，來大幅降低地平線效應的影響。

關鍵字

地平線效應 ； 遊戲樹搜尋 ； 電腦象棋

並列摘要

In the game tree search process, when one side is facing unavoidable loss, it does not face the problem and seeks the minimum loss. Instead, it uses meaningless forcing-move to force the opponent to respond, so the opponent is unable to make scoring-move within the depth limit. This is the Horizon Effect.
The horizon effect, which has a high incidence and significantly reduces the quality of searches, was discovered and named as early as 1973, but after half a century, there is still no definite solution.
In this paper, I will discover and define the key elements of the horizon effect: Forcing Move and Lurking Killer, explain how to find these two types of moves in the game tree search process, and how to use the found moves to dynamically control the search depth to significantly reduce the negative impact of the horizon effect.

並列關鍵字

Horizon Effects ； Game Tree Search ； Computer Chess

參考文獻

[1] H. J. Berliner. Some necessary conditions for a master chess program. In Pro-

ceedings of the 3rd International Joint Conference on Artifi cial Intelligence.

Stanford, CA, USA, August 20–23, 1973: 77–85., 1973.

[2] e. a. Browne, Cameron B. A survey of monte carlo tree search methods. IEEE

Transactions, 43(1), 2012.