Day11 Threat Space Search
===

昨天用了幾個例子說明排序的重要性，除了排序著手之外還有其他很多的優化方式，今天再來分享一個特殊的搜索方式，最早應該是[Louis Victor Allis](https://en.wikipedia.org/wiki/Victor_Allis)提出來證明五子棋是先手必勝的遊戲，論文我放在底下了，有興趣的可以去看看，Proof Number Search 跟 Dependency-Based Search也是他提出來的，後面有機會再來分享。

## 五子棋術語
以下內容會用五子棋來舉例，這邊有非常詳細的[五子棋規則](https://chiuinan.github.io/game/game/intro/ch/c41/ms52/rule/5ch_rule.htm)，不懂的人可以去看看，這邊就不再多解釋規則了，只跟大家統一一下術語免得會看不懂。

活三：再下一手可以造成活四的情況。



死四：再一手就能造成連五，但對方已經擋住其中一邊了。



活四：兩邊都沒有被擋住的連四。


雙四(四四)：不管是活四還死四，只要同時有兩個四就算是雙四。


雙活三(三三)：同時有兩個活三，使對方無法阻擋，雖然在某些規則下是禁著。


三四：有一個活三加上一個死四。


## Threat Space Search
Threat翻譯成中文是威脅的意思，但是在電腦對局這塊通常都是翻譯成**迫著空間搜索**，至少我看到的中文論文都是這麼翻譯，或是乾脆**簡稱TSS**。

### Threat
迫著指的是在某種局面下，玩家被迫下出特定的走步，否則就會輸掉。
以五子棋為例，下圖X為白棋的迫著點，白棋被逼迫只能去下在X的位置防守


雙方一次只能下一手的情況下，只要盤面同時出現兩個迫著，那對方就沒有辦法阻止你獲得勝利，比如：活四、雙四、四三等情況。


### Delayed Threat
還有一種叫做延遲迫著(Delayed Threat)，如果對方不做出反應，需要多步後才能實現獲勝。

活三就是一種Delayed Threat，如下圖，雖然他也會產生兩個迫著點，只要不擋，接下來黑棋就能造出活四來獲勝了，但白棋只要擋住其中一邊，下一個回合黑棋只能夠造出死四，並不能夠獲勝。
但他還是跟迫著有相同效果，就是對方不能不做出反應。


雙活三有四個延遲迫著，白棋仍然無法防守。


### Threat Space
而這些能造成對方迫著的走步所形成的區域就是迫著空間，如下圖黑棋下在X的地方都可以產生對白棋產生迫著。


當然此範例只有下在A點能夠產生四個延遲迫著取得勝利。


迫著空間搜索可以**大幅降低搜索的範圍**，提高程式效率，以五子棋來說要找到這些迫著也並不需要什麼困難的算法，成本相當的低，更重要的是輪到對方時，搜索空間的範圍會被限制得很小，如果是死四的話就只有一種擋法，整個對局樹會被剪裁得非常小。
在檢查某一排(直的橫的斜的)有幾個迫著時，可以使用**Sliding Window**來實作，沒錯就是Leetcode分類有的那個Sliding Window，如果還不會的話可以先去刷個幾題XDD。

這邊要特別注意，如果是黑棋活三的話，白棋也可以去造出一個死四強迫黑棋去擋，有可能被白棋反迫著到遊戲結束，不能預設對方一定要馬上擋，**遇到有延遲迫著的情況時，要把反迫著的選點都加入進去搜索。**

如果最後迫著空間搜索的結果都失敗，就代表還沒有可以靠著連續死四、活三等迫著的贏法，還是得接著原本的搜索了。

## 其他棋類應用
比起五子棋，像是西洋棋跟象棋也是有迫著的遊戲，但是就比較少人會使用，畢竟這兩個遊戲在前半盤幾乎沒有只使用迫著就獲勝的可能，而且迫著的選擇也會比五子棋多不少。
例如在西洋棋、象棋中的將軍，被將軍的一方會有三種選擇：
1. 逃跑
2. 擋住對方的路徑
3. 吃掉對方

這三種選擇產生的變化就比五子棋多很多了，但是在殘局時棋子數量變少，隨著棋局開始收斂，迫著空間搜索又變得非常適合，比如象棋的殘局題目，通過連續的將軍(連續的迫著)來將死對手。

如下圖，紅方可以通過連續將軍獲得勝利。


感謝知名業餘圍棋高手吳冠毅大大提供範例圖。
大家可以想一下怎麼做，解答我放在最下面。

## Reference
* [Go-Moku and Threat-Space Search](https://www.researchgate.net/publication/2252447_Go-Moku_and_Threat-Space_Search)
* [五子棋規則](https://chiuinan.github.io/game/game/intro/ch/c41/ms52/rule/5ch_rule.htm)
* [AlphaZero演算法結合快贏策略或迫著空間實現於五子棋](https://etds.lib.ntnu.edu.tw/thesis/detail/da8499e71517ac31e79e84d29238e3ec/?seq=19#)
* [以區域相關攻擊為主的六子棋搜尋演算法](https://www.airitilibrary.com/Article/Detail/U0030-1510201315190385)

解答：兵五進一、士6進5、車三進二。