[[alternative]]A study on game tree search

[[abstract]]對局樹搜尋是人工智慧研究中之一重要領域。本研究提出若干空步策略來加強對局樹 搜尋的效率，這些方法包括單一空步(Single Null Move)、連續空步(Sequential Null Moves)、 混合空步(Mixed Null Moves)、以及空值誤差法(Null-Value Error) 。經實驗發現，以空值誤差法可改善七層對局樹的搜尋速度達11.8% 。同時，對更深 的搜尋，有更顯著改善的趨勢。本研究建立考慮產生節點數、搜尋節點數、和由審局 函數評估的節點數之效率評量模式，根據此模式發展出一加速方程式，藉此說明對局 樹搜尋之局部加速對整體效率的影響。此外，以真實的對局樹實驗比較Alpha-Beta 、Aspiration、PVS、PAB、Scout、Iterative Deepening等對局樹搜尋方法，發現無 論是否使用Iterative Deepening，PAB皆優於PVS ，而且，二者效率之差距隨搜尋深 度之遞增而加大，此項結果與早先以模擬樹實驗之研究結果不同。另外，由實驗資料 顯示Iterative Deepening 可增強PVS、PAB及Scout之效率，但是無法改善 Alpha-Beta和Aspiration的搜尋速度。