[Theory of Computer Game 13]

Lambda Search

Chinese 遊戲AI

written by LiaoWC on 2022-02-18

Lambda search 是一種搜尋 lambda move 的演算法，也是一種 threat space search。

Lambda move

以下皆使用五子棋來舉例。

  • λ0-move：直接贏的 move。

    例如對白色來說，如果現在換白色下，下圖三角形位置是它的 λ0-move。

    untitled-29.png

  • λ1-move：對方不理的話我方有 λ0-move 獲勝方式或是下這 move 後對方沒有可以獲勝的 λ0-move。

    下圖三角形位置為白色的 λ1-move，因為如果不擋的話，白色可以靠上圖的 λ0-move 的方式獲勝。

    untitled-30.png

    下圖三角形位置為白色的 λ1-move，這一步能夠讓黑色失去用 λ0-move 的獲勝的方式。

    untitled-31.png

  • λ2-move：對方不理的話我方有 λ1-move 獲勝方式或是下這 move 後對方沒有可以獲勝的 λ1-move。

    下圖三角形位置為白色的 λ2-move。白色下了這個 λ2-move 之後形成活三，如果黑色不擋的話，白色可以再成活四而獲勝。。

    untitled-32.png

  • λ3-move：對方不理的話我方有 λ2-move 獲勝方式或是下這 move 後對方沒有可以獲勝的 λ2-move。

  • λ4、λ5、λ6……以此類推

Lambda tree

可以使用 lambda tree 判斷有沒有可以獲勝的 lambda move。Lambda tree 的繪製使用了以 AND-OR tree 呈現的 Minimax tree，我方勝計為 1，負計為 0。我方回合取 max ⇒ OR，對方回合取 min ⇒ AND。

untitled-33.png

以上圖為例，假設現在輪到黑色下，對應的 λ1-tree 為：

untitled-34.png

方形是輪到黑色下，圓形是輪到白色下。上圖中白色都只有一個位置可以下是因為如果不下那裡黑色就能獲勝。第一層 node 是這面盤面當前肉眼可現的 threat。黑色下 B 白色勢必下 A，之後延伸出更多的 threat。樹長完之後可以發現 root 是 1 表示黑色的 λ1-tree 的值為 1，依照 B ⇒ A ⇒ D ⇒ C ⇒ F 的下法黑色必勝。

More examples

請問下圖有哪些位置是白色的 λ2-move？

untitled-35.png

答案：三角形和方形的地方都是白色的 λ2-move。圓形並不是。三角形是白色的 λ1-move（進攻者的角度）但同時也是白色的 λ2-move（防守者的角度），因為如果白色下三角形處，黑色就需要去擋白色，不能去下方形，使得方形處變成不是黑色能獲勝的 λ1-move。

untitled-36.png

圓形處並不是白色的 λ2-move。以防守的角度看，圓形不能使得黑色沒有可獲勝的 λ1-move；以進攻的角度看，圓形處沒辦法達成「若黑色不理，白色在這裡可以靠 λ1-move 獲勝」，因為黑色可以直接去下方形處使得白色無法獲勝。

總結來說，判斷 lambda move 時要注意以下幾點：

  1. 一個位置可以是多種 lambda move。
  2. Lambda move 可以從進攻/防守兩個角度判斷。
  3. 判斷 lambda move 要比對全域各個的 threat 之間的交互關係，而非只看一個區域。

Reference

  • Allis, L. V., Searching for solutions in games and artificial intelligence, Ph.D. Thesis, University of Limburg, Maastricht, 1994.
  • Allis, L. V., Herik, H. J. van den, and Huntjens, M. P. H. (1996). Go-Moku Solved by New Search Techniques. Computational Intelligence, Vol. 12, pp. 7–23.
  • 本篇棋盤使用 gogui 繪製(https://github.com/Remi-Coulom/gogui)
«️ TSS (Threat Space Search)