Day12 Horizon Effect
===
今天來分享一個電腦對局很常出現的現象，跟一些改進方式。

## Horizon Effect

Horizon Effect (水平線/地平線效應)是電腦對局中很常會遇到的問題，指的是**程式在設定的搜尋深度內無法看到某些遠處潛在威脅或機會，導致對局面的評估不夠精確。**
通常我們的程式在使用搜索演算法的時候都會給定一個搜索深度，如同前幾天所介紹的，如果在設定的搜索深度還無法判斷勝負(搜索到葉節點)，則會停止搜索，交由審局函數對此盤面做評分。

### 超出搜索深度
但是這樣會出現一個問題，局勢的某些關鍵變化可能發生在這個**搜尋深度之外**，超過程式能看見的範圍，這些看不見的變化就是水平線之外的變化。
假設程式只能看五步的變化，那麼在第六步或之後出現的重大威脅，是會被忽略的，如被將死或失去關鍵棋子，程式在這一輪搜尋中**無法預見這些變化，導致做出錯誤的決策**。
以人類的角度來說就是這個棋你算得不夠深，就像是我下圍棋時常說：啊！這棋我沒算到。

### 推遲失敗
沒算到的情況還算好理解，還有一種可能是**你算到了但是最後誤判了**。
水平線效應會**推遲不可避免的威脅**，程式可能會選擇一些表面看似可以延遲威脅的步數，但其實這只是暫時的解決，威脅會在未來幾步內發生。**由於威脅超過了設定的搜尋深度，程式誤以為問題已經解決，或是有其他更好的地方可以選擇。**

以昨天的五子棋為例，假設搜索深度定為5(搜索五手)，對方是可以在五手獲勝的，但是你有多個地方可以造出無用的死四來拖延時間，這樣就超出了程式的搜索深度了，因為多交換了幾個死四跟擋住，會導致程式誤判，有種眼不見為淨的感覺，只要我看不到，那我就沒有輸。

比如下圖當黑棋下在 A 點之後(假設沒有禁手)，白棋不管擋哪邊，再輪到黑棋就能造出活四，再來白棋一樣不管擋哪邊都無法阻止黑棋在第五手時取得勝利。


白棋雖然能夠算到這個失敗的結果，但是其他分支可能中間去下了X中的其中一個點，造成黑棋迫著，如此一來要算到自己失敗的結果就得搜索得更深了，造成其他分支到了設定的搜索深度後就會直接使用審局函數做評估，經過審局函數的節點並不一定能夠判斷出自己即將輸掉，因而誤判局勢。
比如下圖-1代表失敗，1代表獲勝，-1~1之間的值代表經過審局函數評估的分數，愈靠近1代表對我方愈有利，因為是Max層所以不會選到 A 節點，但其實B、C、D節點最終也將通往失敗。


在其他棋類中也會有相同的情況，比如象棋被將死前把一些棋子塞過來送死也能推遲失敗。

### AlphaGo
下圖為2016年AlphaGo與李世石大戰第四局的精彩畫面！
身為圍棋愛好者的我，每一盤都是全程關注直播，前三盤下完時，我都以為李世石要被完封了，直到李世石下出驚人的神之一手，這神之一挖，我永生難忘。


雖然這手棋後來經過研究，其實並沒有辦法逆轉局勢，但他卻造成了AlphaGo的bug，成為人類唯一贏過AlphaGo的一盤棋。

那我們就來一起研究研究AlphaGo在這邊到底是發生了什麼事情?

Demis Hassabis也在他的twitter發文說錯誤在第79手，但是AlphaGo直到87步才意識到下錯了。


他指的「意識」是指AlphaGo的 value network的輸出，在第79手時，它的勝率大約是70%，然後在第87手大幅下降。


這邊我們來看一下第78~87手發生了什麼事情，懂圍棋的可以自己看棋譜，不懂的這邊小弟我替大家解釋一下，這邊黑棋從83手開始都有點像是在「送死」，看不出有什麼作用，也不像是所謂的棄子戰術，但都是白棋不得不應的，有點類似迫著。


後續黑棋一直掙扎到97手，此時人類才發現AlphaGo好像是誤算了，怎麼開始愈下愈怪了，只是一直找先手下。


這邊當然有很多出bug的可能，但我自己覺得很有可能是水平線效應造成的，當程式無法搜尋到足夠深度時，它可能會錯誤地評估局勢，認為自己處於有利位置，但實際上並不是如此。

### 解決方式
其實這個問題算是無解，只要沒有辦法搜索到底就總會產生相同的情況，只能想辦法減輕水平線效應帶來的影響，比如通過動態調整搜索寬度與深度來優化，這種有威脅的盤面我們可能就要減少搜索寬度增加搜索深度，以下就來介紹一種比較常見的作法。

## Quiescence Search
當搜尋到達預定的深度限制時，會通過審局函數對該局面進行評估。但在某些情況下，這種評估可能是不準確的，因為局面可能處於動盪狀態，例如有一個直接的攻殺、將軍或迫著尚未解決，你局面停在一個關鍵時刻，這樣的評分往往不能反映真實的優劣。
Quiescence Search（寧靜搜索）就是用來解決「搜尋不穩定」的問題，避免評估一些尚未達到「寧靜」狀態的局面。
這種情況下，直接停止搜尋並評估局面會導致錯誤的決策。寧靜搜索的目的是讓搜尋繼續深入，直到局面變得「寧靜」，即沒有重大威脅或激烈變動時，才進行評估。

何謂「寧靜」？
寧靜（quiescent）指的是局面進入相對穩定狀態，沒有直接威脅或攻擊，不同的遊戲則有不同的做法，這邊都是可以自行定義的，例如：

* 沒有即將有棋子被吃掉。
* 沒有迫著。
* 沒有將軍或直接的戰術威脅。

當程式在某個節點達到最大搜尋深度時，它會檢查該局面是否「寧靜」：
* 如果局面已經「寧靜」，則直接交給審局函數評分。
* 如果局面「不寧靜」，則會繼續搜尋「非寧靜」的走步，直到找到一個寧靜局面為止。

寧靜搜索不會對所有可能的步數進行搜尋，而是只搜尋那些能夠解決或影響當前不穩定狀態的關鍵步數。比如上面五子棋的範例，我們在進行寧靜搜索時，局面「寧靜」之前，就只會搜索那些能夠阻止迫著的點。

## Reference
* [Horizon Effect](https://www.chessprogramming.org/Horizon_Effect)
* [Quiescence Search](https://www.chessprogramming.org/Quiescence_Search)