又是壓線的一天，這幾天都極限寫完，沒時間校稿...
如果有哪裡寫錯了或是有不清楚的地方再麻煩留言告訴我了!
hackMD原稿
昨天用了幾個例子說明排序的重要性，除了排序著手之外還有其他很多的優化方式，今天再來分享一個特殊的搜索方式，最早應該是Louis Victor Allis提出來證明五子棋是先手必勝的遊戲，論文我放在底下了，有興趣的可以去看看，Proof Number Search 跟 Dependency-Based Search也是他提出來的，後面有機會再來分享。
以下內容會用五子棋來舉例，這邊有非常詳細的五子棋規則，不懂的人可以去看看，這邊就不再多解釋規則了，只跟大家統一一下術語免得會看不懂。
活三：再下一手可以造成活四的情況。
死四：再一手就能造成連五，但對方已經擋住其中一邊了。
活四：兩邊都沒有被擋住的連四。
雙四(四四)：不管是活四還死四，只要同時有兩個四就算是雙四。
雙活三(三三)：同時有兩個活三，使對方無法阻擋，雖然在某些規則下是禁著。
三四：有一個活三加上一個死四。
Threat翻譯成中文是威脅的意思，但是在電腦對局這塊通常都是翻譯成迫著空間搜索，至少我看到的中文論文都是這麼翻譯，或是乾脆簡稱TSS。
迫著指的是在某種局面下，玩家被迫下出特定的走步，否則就會輸掉。
以五子棋為例，下圖X為白棋的迫著點，白棋被逼迫只能去下在X的位置防守
雙方一次只能下一手的情況下，只要盤面同時出現兩個迫著，那對方就沒有辦法阻止你獲得勝利，比如：活四、雙四、四三等情況。
還有一種叫做延遲迫著(Delayed Threat)，如果對方不做出反應，需要多步後才能實現獲勝。
活三就是一種Delayed Threat，如下圖，雖然他也會產生兩個迫著點，只要不擋，接下來黑棋就能造出活四來獲勝了，但白棋只要擋住其中一邊，下一個回合黑棋只能夠造出死四，並不能夠獲勝。
但他還是跟迫著有相同效果，就是對方不能不做出反應。
雙活三有四個延遲迫著，白棋仍然無法防守。
而這些能造成對方迫著的走步所形成的區域就是迫著空間，如下圖黑棋下在X的地方都可以產生對白棋產生迫著。
當然此範例只有下在A點能夠產生四個延遲迫著取得勝利。
迫著空間搜索可以大幅降低搜索的範圍，提高程式效率，以五子棋來說要找到這些迫著也並不需要什麼困難的算法，成本相當的低，更重要的是輪到對方時，搜索空間的範圍會被限制得很小，如果是死四的話就只有一種擋法，整個對局樹會被剪裁得非常小。
在檢查某一排(直的橫的斜的)有幾個迫著時，可以使用Sliding Window來實作，沒錯就是Leetcode分類有的那個Sliding Window，如果還不會的話可以先去刷個幾題XDD。
這邊要特別注意，如果是黑棋活三的話，白棋也可以去造出一個死四強迫黑棋去擋，有可能被白棋反迫著到遊戲結束，不能預設對方一定要馬上擋，遇到有延遲迫著的情況時，要把反迫著的選點都加入進去搜索。
如果最後迫著空間搜索的結果都失敗，就代表還沒有可以靠著連續死四、活三等迫著的贏法，還是得接著原本的搜索了。
比起五子棋，像是西洋棋跟象棋也是有迫著的遊戲，但是就比較少人會使用，畢竟這兩個遊戲在前半盤幾乎沒有只使用迫著就獲勝的可能，而且迫著的選擇也會比五子棋多不少。
例如在西洋棋、象棋中的將軍，被將軍的一方會有三種選擇：
這三種選擇產生的變化就比五子棋多很多了，但是在殘局時棋子數量變少，隨著棋局開始收斂，迫著空間搜索又變得非常適合，比如象棋的殘局題目，通過連續的將軍(連續的迫著)來將死對手。
如下圖，紅方可以通過連續將軍獲得勝利。
感謝知名業餘圍棋高手吳冠毅大大提供範例圖。
大家可以想一下怎麼做，解答我放在最下面。
解答：兵五進一、士6進5、車三進二。
iThome鐵人賽
看影片追技術