從 2048 學習遊戲對局 AI 設計
在我大四的時候，我修了一門名為「電腦對局理論」的課，老師教了許多棋盤類相關遊戲的輸贏理論、各種狀態搜尋演算法，以及用 2048 遊戲的 AI 實作貫穿了整堂課，包含了 TD learning、n-tuple network、狀態搜尋等等，我覺得用 2048 這個遊戲來貫穿遊戲對局 AI 的永字八法真的太神了！
這篇用來記錄我吸收整理後的學習筆記，我非常非常推薦入門者也用 2048 這套教材學習。這門課真的讓人收穫滿滿，讚嘆吳毅成教授以及助教學長們~~
2048 遊戲規則
如果你還不熟悉 2048 的規則，可以直接在 2048 的網頁版 玩玩看。盤面上所有的磚塊上數值都是 $2$ 的冪次方 $(2^k)$，每次玩家都可以往「上、下、左、右」其中一個方向滑動盤面，滑動後所有磚塊都會往該方向併攏，如果有兩塊磚塊數值一樣 $(2^k)$ 被併攏在一起的話就會融合成一個新磚塊 $(2^{k+1})$，並且讓玩家賺到 $2^{k+1}$ 的分數。玩家完成滑動後，系統會在沒有磚塊的地方隨機生成一個數值為 $2$ 或 $4$ 的新磚塊，再讓玩家繼續下一輪的滑動，雙方反覆直到玩家再也沒辦法滑動盤面為止。
遊戲結束時，所有合併磚塊時得到的分數加總起來就是玩家的分數了。在玩遊戲的過程中，會因為合併而不斷產生更大數值的方塊，例如 $1024、2048$ 甚至更大的數字，而隨著盤面上數值不同無法合併的磚塊愈來愈多，盤面就愈來愈容易被塞滿而結束，因此要如何一邊賺分數、一邊盡量不把盤面玩死，就是一大挑戰。本篇要介紹的就是如何設計一支「很會玩 2048 的AI」。
順道一題，課程中所使用的遊戲是 2048 的變種 - 2584，是用費波納契數列當成盤面數值，例如 $2$ 和 $3$ 合併成 $5$ 這樣，這會讓遊戲變得更困難一些。不過設計 AI 時的概念還是和 2048 很相同的，因此本篇會繼續以 2048 為例。
Agent 的動作
2048 玩法超級單純，玩家只有四種動作可以做：「往上滑」、「往下滑」、「往左滑」、「往右滑」。因此我們設計的 AI agent 也是每次都將在四個方向中擇一動作。
貪心地玩 2048
在開始介紹 learning 相關的技法之前，先來介紹一個單純以貪心為圭臬的策略，雖然「貪心」聽起來不明智，但其實光這樣已經可以玩得很高分了。這個策略就是：對於每個能滑的方向，計算光是這個滑動能賺多少分數，然後永遠選擇能賺最多分數的滑動方向。
以上圖為例，向左或向右滑動可以合併 $2+2$ 和 $8+8$，因此可以賺 $20$ 分；而向上或向下滑動可以合併 $2+2$，因此可以賺 $4$ 分。我們要貪心地選擇能賺最多分的方向，所以會選擇向左(或向右)滑。
由於我們玩遊戲的目標本就是盡量「賺很多的分數」，所以貪心地選擇當下能賺分最多的方向是很有幫助的！唯一的問題在於，滑完後盤面長怎樣，其實對於遊戲的「前途」是很重要的，亂糟糟大小相間的盤面大概過沒多久就會玩死了，但這個貪心策略絲毫不考慮滑完以後盤面會變得怎麼樣。
想像一個情境：
往左滑，雖然可以賺較多分，卻把盤面弄成爛攤子，馬上就要死了
往上滑，雖然當下沒賺分，卻能變成很有前途的盤面，一堆分數等著我們繼續賺
這樣當然是要選擇往上囉!
因此，在每次選擇該往哪邊滑的時候，我們不只要考慮當下能賺幾分，還要考慮滑完之後的盤面有沒有「前途」。
考慮前途地玩 2048
假設我們有一個神奇函數，只要把滑動後的盤面丟進去，它就能預估「出現這個盤面過後，還能夠再賺多少分數才會遊戲結束」，也就是所謂的「這個盤面多有前途」。有了這個函數的話，我們就能讓 agent 更聰明地選擇方向了，那就是永遠選擇「該次滑動賺的分數」加上「滑完的盤面預計還能賺的分數」最高的滑動方向。
以上圖為例，往右滑能賺 $8$ 分，並且估計能再賺 $100$ 分才結束遊戲，因此往右滑能賺到的分數總共是 $108$；而往下滑能賺 $0$ 分，並且估計能再賺 $300$ 分才結束遊戲，因此往下滑能賺到的分數總共是 $300$，所以我們設計的 agent 該選擇往下滑。
要注意的是，這個策略是完全仰賴估算「前途」的函數的，估算「前途」的函數愈準確，這個策略就會愈強大。至於這個神奇函數怎麼來，我們可以透過經驗來調整，而經驗怎麼累積，則是來自於一場又一場的遊戲。這就是所謂的強化學習！接下來我們將探討如何利用強化學習，訓練出能夠估算「某個盤面到死前還能賺多少分數」的函數。
估計「前途」的函數
想要準準地估算某個盤面還能再賺多少分才死，最好的方法就是看看這些盤面在實際的遊戲中究竟賺了幾分。
以上圖為例，假設上圖是某一局遊戲從開局到結束的過程，並且遊戲結束後總共賺了 987 分。有了這個數據，我們就能知道這局遊戲過程出現的每個盤面分別有多少「前途」了！要注意的是我們只在乎「滑動後」的盤面有多少潛力，因為只有滑往什麼方向是我們可以決定的，系統要在哪裡跳出新磚塊不是我們能決定的。
舉例來說，在這場遊戲中，出現
盤面之後又賺了 987 分才結束；出現
盤面之後又賺了 983 分才結束…等等，我們把這個數據存下來，然後下次我們再遇到盤面時，我們就可以估計這個盤面還能再賺 987 分；或是下次再遇到盤面時，我們就可以估計這個盤面還能再賺 983 分！
只要我們一直不斷地玩遊戲，蒐集所有出現過的盤面以及最後結果，我們就有愈來愈多的數據用來幫助我們在玩遊戲的過程中預估每個盤面的潛力值。而隨著經驗愈來愈多，我們的預估也會愈來愈準確，代表 agent 愈來愈聰明，所以蒐集到的遊戲數據也會愈來愈有參考價值。
不過，一定會有相同的盤面在不同場遊戲中重複出現，並且得到不一樣的最終分數，這樣到底該用哪次的分數當估計值呢？舉例來說：
同樣是盤面，可能在三場不同的遊戲中有三種不同的賺分結果，那麼未來再次出現盤面時，該估計它有多少前途呢? 10 分嗎？5000 分嗎？還是 150 分呢？又或是三者平均在一起的 1720 分呢？
取平均數還算合理，不過缺點在於像 10 分或是 5000 分這種極端值會主導平均值；再者，因為 agent 會不斷吸取經驗幫助判斷，讓自己變得愈來愈「懂玩」，因此愈舊的遊戲數據愈不具參考價值，不應該讓所有數據等比例地平均。
那麼有沒有更好的做法呢？我們可以設定一個 learning rate，然後每次獲得新的觀測值時，都把舊的預測值以新的觀測值為目標向前更新一小步，這跟 stochastic gradient descent 的更新 model 概念滿像的，一樣都是要往目標更新 learning rate 的一小步，不一樣的地方是這個演算法是沒有 model 的，而是直接對於每個盤面的值做更新，因此也不會有計算 gradient 的成分。
應用在 2048 上，我們可以把所有盤面的潛力值初始化為 $0$，然後設定 learning rate 為 $0.1$。以盤面為例：
- 在某場遊戲中觀測到賺分為 10 時，我們就可把此盤面的潛力值更新為 $0+(10-0)*0.1=1$
- 後來在某場遊戲中觀測到賺分為 5000 時，我們又可以把它的潛力值更新為 $1+(5000-1)*0.1=500.9$
- 再後來在某場遊戲中觀測到賺分為 150 時，又可以把它的潛力值更新為 $500.9+(150-500.9)*0.1=465.81$
往後再遇到新的觀測值時，還會再不斷更新下去，並且逐漸收斂成一個穩定又可信的值。這就是蒙地卡羅(Monte Carlo)法！蒙地卡羅法的精神就是不斷在隨機的環境中取得觀測結果，藉以推估某個動作或某個狀態會有怎麼樣的未來。以 2048 為例，儘管每次系統都會在不同的地方生成新方塊，使得每場遊戲的結果總是變幻莫測，我們也能夠透過每次玩完遊戲後取得的最終結果，當成觀測值來調整估計值。
不過 2048 這個遊戲有個稍微不太適合蒙地卡羅法的地方，那就是玩 2048 的過程中不太會有「決定性的一步」，像是「玩出了這個盤面我就要大賺了」之類的；相反的，就算是同樣的盤面，最後玩出的分數也會忽高忽低，就像上圖舉的例子一樣。這會導致每個盤面的估計值都難以收斂，也難以變得可信。不過並非每個遊戲都會有這個問題，以圍棋或是西洋棋為例，那種「吃掉別人」或是「做出陣型」的盤面就是「決定性的一步」，通常都會導致差不多的結果(贏過對方)，因此依然很適合蒙地卡羅的。
那可以用什麼策略來取代蒙地卡羅呢？我們再看一眼這個遊戲過程例子：當出現盤面後，這場遊戲又賺了 987 分才結束，但我們現在不想迷信這個 987，因為我們認為並不會在每場遊戲都一直賺到987。那麼要更新盤面的估計值時，該拿什麼當目標呢？我們可以試試盤面的估計值再加上 4！為什麼這是一個更好的目標，我們可以看看以下這兩種宣稱，哪種更為合理？
- 1.玩出盤面後，很容易導致賺到 987 分
- 2.玩出盤面後，很容易導致在下一步能賺 4 分並且滑成盤面
後者較為合理，對吧！人生也是差不多的概念，若你十年後會成為億萬富翁，不一定是因為你今天特別做了什麼；但若你明天醒來有麵包當早餐，那就是因為你今天有記得去買。接下來我們來介紹以這個概念為核心的「Temporal difference learning」
Temporal difference learning
Temporal difference learning, 簡稱 TD learning，是reinforcement learning (強化學習) 的種類之一。關於 TD learning 的詳細說明，可以參考 TD learning 的維基百科，簡而言之他的特色在於，依據目前的模型對於其他相關狀態的預測來達成學習，而非等到確切結果揭曉。
關於 TD learning 的特色和好處，它的 paper 中也有給一個不錯的例子
Suppose you wish to predict the weather for Saturday, and you have some model that predicts Saturday’s weather, given the weather of each day in the week. In the standard case, you would wait until Saturday and then adjust all your models. However, when it is, for example, Friday, you should have a pretty good idea of what the weather would be on Saturday – and thus be able to change, say, Saturday’s model before Saturday arrives.
意思是，假設你要訓練一個 model，根據前幾天的天氣來預測星期六的天氣。若不使用 TD learning，你就一定要等到實際星期六的天氣來臨才能知道 ground truth 為何，藉以更新 model。然而如果星期五已經揭曉是個大太陽，model 卻還會預測成暴風雨暴風雪，那就算還沒到星期六，你也能大概知道星期六和星期五會是類似的好天氣，並且這個 model 會把它錯估成壞天氣，所以你可以在這時就先調整 model，而不用真的等到星期六揭曉。這就是 TD learning 的精神！
不過這樣講得好像會誤導成直接拿星期五的天氣當成星期六的天氣來當 ground truth，並不是這樣的。為了更透徹地了解 TD learning 如何運作，我們來一步一步探討每一個盤面如何使用 TD learning 更新估計值。
請記得，不管是使用蒙地卡羅法還是 TD learning，訓練 AI 的順序都是：
- 1.把所有的盤面潛力值初始化為 0
- 2.玩一場遊戲
- 3.用這場遊戲的數據，更新遊戲中出現過的每個盤面的潛力估計值
- 4.用新的策略 (新的盤面潛力值) 再玩一場遊戲
不斷重複 3 和 4，直到收斂。
為了方便理解，我們用這張簡化後的遊戲為例子來演示。這場遊戲只有 4 次滑動就結束，總共賺了 $2+0+4+2=8$ 分。一開始，所有盤面 $A, B, C, D$ 的估計值都是 $0$。注意，我們只在意「滑動後」的盤面。
以下的更新中，我們使用 learning rate $lr = 0.1$
首先，對於 $D$ 盤面來說，它是這場遊戲的最後一個盤面，沒有「下一個盤面」了，而且沒有再賺分就結束了，因此它的學習目標就是 $0$ 分。
因此更新 $V(D) \leftarrow 0+0.1*(0-0)=0$
接著，對於 $C$ 盤面來說，它在這場遊戲中的「下一個盤面」是 $D$ 盤面，並且是賺了 $2$ 分後成為 $D$ 盤面的，因此它的學習目標是 $2+V(D)$。注意，這個目標絲毫不管真正到結束後賺了幾分，它只全然相信 $V(D)$ 會是對的，又以目前的 $V(D)$ 值來說，$2+V(D)=2$。
因此更新 $V(C) \leftarrow 0+0.1*(2-0)=0.2$
再來，對於 $B$ 盤面來說，它在這場遊戲中的「下一個盤面」是 $C$ 盤面，並且是賺了 $4$ 分後成為 $C$ 盤面的，因此它的學習目標是 $4+V(C)$。注意，這個目標絲毫不管真正到結束後賺了幾分，它只全然相信 $V(C)$ 會是對的，又以目前的 $V(C)$ 值來說，$4+V(C)=4.2$。
因此更新 $V(B) \leftarrow 0+0.1*(4.2-0)=0.42$
最後，對於 $A$ 盤面來說，它在這場遊戲中的「下一個盤面」是 $B$ 盤面，並且是賺了 $0$ 分後成為 $B$ 盤面的，因此它的學習目標是 $0+V(B)$。注意，這個目標絲毫不管真正到結束後賺了幾分，它只全然相信 $V(B)$ 會是對的，又以目前的 $V(B)$ 值來說，$0+V(B)=0.42$。
因此更新 $V(A) \leftarrow 0+0.1*(0.42-0)=0.042$
如此一來就完成一輪的更新，可以帶著這個新策略去玩一場新的遊戲了！你可能會覺得很可疑，明明 $A$ 盤面過後賺了 $8$ 分才結束，現在卻只把 $V(A)$ 更新為 $0.042$ 沒問題嗎？不用擔心，這只是因為我們設定 learning rate 為 $0.1$ 所造成的，隨著更新的次數愈來愈多，盤面的估計值都會逐漸收斂成一個穩定可信的數字。learning rate 的大小如何選擇以及如何更新，就需要靠實驗來決定了。
TD-$\lambda$
我們來比較看看蒙地卡羅法和 TD learning 的特色：蒙地卡羅法每次用的都是「真正」的數據，但非常浮動；而 TD learning 相對穩定，但都是使用「傳來」的數據。
| Variance | Error | |
|---|---|---|
| Monte Carlo | 高 | 無 |
| TD learning | 低 | 有 |
這兩種沒有誰好誰壞，只有誰更適合某種遊戲。如果想要綜合兩種的特色，可以使用 TD-$\lambda$！TD learning 本來就有一個參數 $\lambda$ 來決定「多少比例考慮實際賺分的結果」，而蒙地卡羅法其實就是 TD-$1$，完全只考慮「實際賺分結果」；而剛才介紹的 TD learning 其實就是 TD-$0$，完全只考慮「下一個狀態」。
當 $\lambda$ 介於 $0$ 和 $1$ 之間時，所有賺分和未來狀態的組合都會被考慮進去。
以這張圖為例，這場遊戲總共賺了 $a+b+c+d$ 分，而在 TD-$1$ (蒙地卡羅) 中，$A$ 盤面的學習目標即為 $b+c+d$；在 TD-$0$ 中，$A$ 盤面的學習目標即為 $b+V(B)$；在介於 $0$ 到 $1$ 之間的 TD-$\lambda$ 中，以下所有都會是目標：
- $b+V(B)$
- $b+c+V(C)$
- $b+c+d+V(D)$
- $b+c+d$
而這些值會以 $\lambda$ 為比例組合起來，成為 $A$ 盤面的學習目標。第一項是 $(1-\lambda)$，除了最後一項是 $\lambda^k$ 以外，其他每一項都是前一項係數乘以 $\lambda$。
| 項 | 係數 |
|---|---|
| $b+V(B)$ | $1-\lambda$ |
| $b+c+V(C)$ | $\lambda*(1-\lambda)$ |
| $b+c+d+V(D)$ | $\lambda * \lambda * (1-\lambda)$ |
| $b+c+d$ | $\lambda * \lambda * \lambda$ |
$target(A) \leftarrow$
$(1-\lambda)\times(b+V(B))$
$+ (\lambda * (1-\lambda))\times(b+c+V(C))$
$+ (\lambda * \lambda * (1-\lambda))\times(b+c+d+V(D))$
$+ (\lambda * \lambda * \lambda)\times(b+c+d)$
我們可以觀察到，每一項的係數，與後面所有項的係數和，都呈現 $(1-\lambda):\lambda$ 的比例。我們也可以觀察到，當 $\lambda=0$ 時，唯一的目標就是 $b+V(B)$；當 $\lambda=1$ 時，唯一的目標就是 $b+c+d$。
我們來一步一步探討使用 $TD-\lambda$ 時要如何更新每個盤面的估計值。為了不要讓時間複雜度拉高到 $n^2$，可以使用動態規劃的技巧。我們先來看看相鄰的盤面的目標之間有什麼樣的關係，以盤面 $B$ 的學習目標 $target(B)$ 為例：
| 項 | 係數 |
|---|---|
| $c+V(C)$ | $1-\lambda$ |
| $c+d+V(D)$ | $\lambda * (1-\lambda)$ |
| $c+d$ | $\lambda * \lambda$ |
再看一眼 $A$ 的學習目標 $target(A)$，是不是很眼熟呢？
| 項 | 係數 |
|---|---|
| $b+V(B)$ | $1-\lambda$ |
| $b+$$c+V(C)$ | $\lambda*$$(1-\lambda)$ |
| $b+$$c+d+V(D)$ | $\lambda *$$\lambda * (1-\lambda)$ |
| $b+$$c+d$ | $\lambda *$$\lambda * \lambda$ |
我們可以發現 $target(B)$ 與 $target(A)$ 有著這樣的關係：
$target(A) = b+(1-\lambda) * V(B)+\lambda * target(B)$
這也是一場遊戲中所有相鄰盤面的目標之間的關係。
我們再用剛才的例子來演示一次使用 TD-$\lambda$ 時如何更新每個盤面的估計值。我們使用 learning rate $lr = 0.1$，以及 $\lambda=0.3$。
首先，對於 $D$ 盤面來說，它是這場遊戲的最後一個盤面，毫無懸念，它的學習目標就是 $0$ 分
$target(D) \leftarrow 0$
$V(D) \leftarrow 0+0.1*(0-0)=0$
接著，對於 $C$ 盤面來說，它賺了 $2$ 分後成為 $D$ 盤面，而它的學習目標 $target(C)$ 為 $d+(1-\lambda) * V(D) + \lambda * target(D)$，代入各項變數後可知
$target(C) \leftarrow 2 + 0.7 * 0 + 0.3 * 0=2$
$V(C) \leftarrow 0+0.1*(2-0)=0.2$
再來，對於 $B$ 盤面來說，它賺了 $4$ 分後成為 $C$ 盤面，而它的學習目標 $target(B)$ 為 $c+(1-\lambda) * V(C) + \lambda * target(C)$，代入各項變數後可知
$target(B) \leftarrow 4 + 0.7 * 0.2 + 0.3 * 2 = 4.74$
$V(B) \leftarrow 0+0.1*(4.74-0)=0.474$
最後，對於 $A$ 盤面來說，它賺了 $0$ 分後成為 $B$ 盤面，而它的學習目標 $target(A)$ 為 $b+(1-\lambda) * V(B) + \lambda * target(B)$，代入各項變數後可知
$target(A) \leftarrow 0 + 0.7 * 0.474 + 0.3 * 4.74 = 1.7538$
$V(A) \leftarrow 0+0.1*(1.7538-0)=0.17538$
如此一來就完成一輪更新了！$\lambda$ 的選擇也會影響訓練出來的 AI 是強是弱，而這也要靠實驗才能得知最適合的參數了！
N-tuple network
也許你會注意到，上述的演算法存在一個實務上的問題，那就是所有可能的盤面組合太多了！2048 的盤面總共有 16 格，而每一格都可能是 $[空格, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048]$ 總共 12 種 (如果能玩到更高分的話，就會有更多種了)，因此所有的盤面總共有 $12^{16}=1.8\times10^{17}$ 種或者更多！為了計算每一種盤面的估計值，我們需要開一個大小為 $1.8\times 10^{17}$ 的表格來儲存，這不只會使記憶體用量無法負荷，更無解的是玩遊戲的過程中大多只會不斷遇到「從未見過」的盤面，那些曾經見過、更新過的盤面幾乎再也不會遇到，因此 AI 根本練不起來。
不過，訓練 AI 的精隨就是見微知著！就像訓練圖像辨識的 AI 時，也會讓它學到物品的特徵，而非一定要是曾經看過一模一樣的圖才知道那是什麼物品。而對於 2048 遊戲的盤面來說，也能藉由學習特徵來讓相似的盤面能夠被預測出類似的潛力值。
經由前人的研究結果發現，對於 2048 遊戲來說，光是盤面上取一小塊，就能成為很有用的特徵。我們可以選取一塊位置作為盤面的「feature」，而計算估計值時也只會對盤面上的那一小塊feature 做操作。這就稱為 N-tuple network。
以上圖為例，當我們以盤面的「左下六塊」當成 feature 時，A 盤面和 B 盤面會被視為一樣的盤面，也就是說當某次遊戲中出現了 A 盤面，並且對於 
這個 feature 的潛力值做了更新後，在下一次的遊戲若出現了 B 盤面，就算 B 盤面是不曾看過的新盤面，也會受益於曾經出現過的 A 盤面擁有的 feature，得知 B 盤面的潛力值。
這樣一來，記憶體用量的問題也解決了。$12^6$ 大概只有三百萬左右，這個規模是不是合理多了呢？要維護每一種 feature 對應的估計值，只需要長度為三百萬的表格就能達成，而且也讓訓練的過程容易出現重複的 feature，善加運用經驗。
在你開始想抗議「難道其他十格就真的 don’t care 嗎!?」的同時，我們先來討論這個問題：下圖的 A1、A2、A3 是不是應該要有一模一樣的估計值呢？明明是完全等價的盤面，卻會取到不同的估計值，這對訓練過程是一大傷害。(A1 右轉 90 度後成為 A2；A1 水平翻轉後成為 A3)
因此當我們在對盤面取 feature 時，同樣的位置應該要在四個旋轉方向x兩種鏡像總共八種 isomorphism 中各取一次。以 A1 圖來舉例，「左下角六塊」的 feature 應該要取以下八次，並把八個估計值加總起來，成為 A1 這個盤面真正的估計值。
你可以檢查看看，是不是 A2 和 A3 也會取到同樣的八個 isomorphism 呢？這樣一來，A1、A2、A3 就會得到一模一樣的估計值了！另外，盤面中也不會有任何一格成為 don’t care，每一格都會在某個 isomorphism 中被用到。再說，剛才舉例的 A 盤面和 B 盤面也不會有完全相同的估計值了，他們的相似之處會讓他們有相似的估計值，但它們的不同之處則也會讓他們的估計值有些微的差別。一切是不是更合理了呢？
要訓練出更厲害的 AI，可以在盤面上取更多不同種 feature。以助教的 paper 為例，總共取了以下四種 feature：
四種 feature 乘上每種有八個 isomorphism，總共會是 $32$ 個值相加成為這個盤面的估計值。而四組 feature 則是總共會需要長度為 $12^6 \times 4$ 的表格來儲存每個 feature 對應的值。當然也能選擇 4 格、5 格或 7 格的 feature，那樣一種 feature 所占用的記憶體就會是 $12^4、12^5、12^7$ 等等。feature 要取什麼形狀、什麼位置，以及要取哪些，都是我們可以發揮創意、實驗看看效果的地方，唯一要注意的是不要取到了重複的 feature。舉例來說，以下兩者在旋轉對稱後其實就是重複的 feature，因此就不要取成兩種 feature 了。
由於盤面的前途的估計值是所有 feature 的對應值的加總，所以更新盤面估計值時也要把更新的量平均分給每個 feature。舉例來說，假設我們設計的演算法是四個 feature，再乘上八個 isomorphism 就有 $32$ 個 feature。假設目前某個盤面的 $32$ 個 feature 對應值加起來是 $100$，代表這個盤面目前的估計值是 $100$，並且這個盤面的更新目標為 $200$，這個差距是 $+100$，再乘以 learning rate $0.1$，得知這個盤面的估計值要再 $+10$。因此，這個盤面上的 $32$ 個 feature 所對應的值通通要一視同仁地加上 $\frac{10}{32}=0.3125$，不管他們原先的值是大是小。如此一來，經過不斷的訓練後，相似的「有前途盤面」所共有的 feature 就會擁有很大的值；相似的「快死了」盤面所共有的 feature 就會有很小的值，甚至是負數。
遊戲狀態搜尋
當我們把 AI 訓練好，準備迎接挑戰時，還有什麼手段可以使得 agent 能更加聰明地選擇動作呢？那就是加入「狀態搜尋」。
我們來看看這個例子。當 agent 玩到 A 盤面時，有兩種滑動方向可以選擇：「向上」和「向下」，分別能得到 A1 盤面和 A2 盤面。若不考慮 A1 盤面和 A2 盤面分別的估計值為何，光用常識判斷，哪一種盤面比較有前途呢？
往上滑出的 A1 盤面中只有一個空格，不管系統跳出方塊 2 還是方塊 4，這場遊戲都死定了；往下滑出的 A2 盤面中也只有一個空格，但不管系統跳出方塊 2 還是方塊 4，都還能再玩好幾步、再賺一些分數，因此往下滑比較好…。這是完全沒有仰賴 A1 和 A2 的估計值，只靠對未來的想像就能得出的結果！
你可能會好奇，如果模型訓練得夠好，不就能光從估計值就知道 A2 比 A1 好了嗎？這是沒錯，但是不管是多厲害的模型，總會有一些誤差，舉例來說，一個厲害的模型在上述這類「送死」和「死裡逃生」的盤面比較中有 $90$% 會選擇「死裡逃生」，但若加了這層搜尋檢查，就可以讓它變成 $100$%。而且，搜尋不只可以在遊戲快結束時幫忙判斷如何死裡逃生，在遊戲過程的任何一步決策考慮「往後看幾步」都能夠對判斷很有幫助，因為 2048 終究是一個愈接近遊戲結束，估計值愈可信的遊戲。
不只是 2048，很多對局遊戲也都很適合這種「多想幾步的小劇場」，例如玩西洋棋會有這樣的小劇場：「現在是不是該用士兵把他的士兵吃掉呢、但這樣他就會用騎士反吃我的士兵了，但我也能因此把他的騎士吃掉，他比較虧…」光是一個動作，就先預想好了未來好幾步，藉以做出最正確的判斷。
Expectimax search 追求最高的期望效益
我們來一步一步演示在 2048 遊戲中，如何在估算每個盤面的潛力值時，以「多看一步」來取代用模型取值估計。因為是多看一步，所以我們要把系統所有可能產生新方塊的結果列舉出來，然後依每一種可能，再計算一次能賺的最多分數是滑往哪個方向。由於系統是隨機產生方塊，因此每一個空格出現方塊的機率都相等，而且出現 2 和 4 的機率也固定為 9:1，系統不會故意為難我們或做球給我們，因此最適合的搜尋演算法就是 Expectimax search。
舉個例子：現在 agent 拿到了 A 盤面，我們想要知道若是往左滑的話，產生的 B 盤面有多少前途？原本我們會直接用訓練好的模型算出 B 盤面的估計值，現在我們要「多看一步」，把滑動後的所有產生新方塊的可能，以及對應的機率，列舉出來：
圖中用紅框圈出的部分就是新產生的方塊。
接下來對於每一個產生新方塊後的盤面，列舉出所有可以滑的方向以及賺分、估計前途。以 B1 盤面為例，可以滑的方向有「向上」、「向下」、「向右」。
- B1 向上滑可以賺 4 分，並得到 B1_U 盤面
- B1 向右滑可以賺 0 分，並得到 B1_R 盤面
- B1 向下滑可以賺 4 分，並得到 B1_D 盤面
假設根據我們訓練出的模型，$V(B1_U)=100, V(B1_R)=100, V(B1_D)=50$，那麼可知 agent 在得到 B1 盤面時，一定會選擇往上滑(共可賺 $104$ 分)。因為 agent 一定會選擇最高分的動作，所以可以肯定是 $104$，不需用機率列舉。因此，我們可以宣稱「若系統下一步產生的是 B1 盤面，我們可以賺 $104$ 分」。
用同樣的方法，我們也可以算出若是出現的是 B2, B3, B4, B5, B6，可以賺到幾分。舉例來說：
- 「若系統下一步產生的是 B1 盤面，我們可以賺 $104$ 分」
- 「若系統下一步產生的是 B2 盤面，我們可以賺 $68$ 分」
- 「若系統下一步產生的是 B3 盤面，我們可以賺 $40$ 分」
- 「若系統下一步產生的是 B4 盤面，我們可以賺 $120$ 分」
- 「若系統下一步產生的是 B5 盤面，我們可以賺 $72$ 分」
- 「若系統下一步產生的是 B6 盤面，我們可以賺 $200$ 分」
這些乘上各個盤面出現的機率再加總，就是 B 盤面藉由「多看一步」得知的估計值了：
$V_{search}(B)=\frac{9}{30}\times 104+\frac{1}{30}\times 68+\frac{9}{30}\times 40+\frac{1}{30}\times 120+\frac{9}{30}\times 72+\frac{1}{30}\times 200=77.733$
儘管從模型得知的 $V(B)$ 不一定是 $77.733$，$V_{search}(B)$ 也會比 $V(B)$ 可信，因為是多看一步後的結果。
你可能會好奇，能不能「多看兩步」呢？換句話說，在計算 $B1_U$ 的估計值時，能不能不要用模型給的 $V(B1_U)$，而是也透過「多看一步」算出 $V_{search}(B1_U)$ 呢？當然可以，只不過搜尋的複雜度是呈指數上升的，在決定動作時若搜尋愈多層，所花的時間就會愈多。
做個總結，在 Expectimax search 的搜尋小劇場中，輪到對方動作時，要「列舉所有的可能以及對應的機率」；輪到自己動作時，要「選擇對自己最有利(最高分)的選項」。
Minimax search 做最壞的打算
而另一種搜尋演算法就是 Minimax search，這適用於對方永遠會「最壞」、「最不手下留情」、「對我方最不利」的情況。以五子棋為例，如果對方已經連成四子我們卻不擋，對方一定會直接連五；以西洋棋為例，如果我們把國王暴露在對方的狩獵範圍卻不逃，對方一定會直接吃掉…等等。我們在「多看一步」時，不能期待對方的動作呈隨機分布，而是要預設對方一定會做出對我方最不利的動作。
雖然 2048 不屬於這一類，但我們還是用以上的例子來演示看看如何把 minimax search 應用在這裡，假想 2048 的系統是個會和玩家「作對」的系統吧。
我們再看一次剛剛的例子：現在要估計 B 盤面的前途
然後我們列舉出了 6 種系統可能產生新磚塊的樣子
注意我們已經不再在意每個產生新磚塊的樣子分別是多少機率，因為新磚塊的產生不再是隨機分布。
接著我們對於每個產生新磚塊後的盤面，計算出我們能夠拿到多少分數：
- 「若系統下一步產生的是 B1 盤面，我們可以賺 $104$ 分」
- 「若系統下一步產生的是 B2 盤面，我們可以賺 $68$ 分」
- 「若系統下一步產生的是 B3 盤面，我們可以賺 $40$ 分」
- 「若系統下一步產生的是 B4 盤面，我們可以賺 $120$ 分」
- 「若系統下一步產生的是 B5 盤面，我們可以賺 $72$ 分」
- 「若系統下一步產生的是 B6 盤面，我們可以賺 $200$ 分」
這時，我們認為系統一定會對我們「最不利」，也就是說，系統一定會在 B 盤面時產生 B3 盤面！因此我們可以得知 $V_{search}(B)=40$，不是依據機率分布算出的期望值 $77.73$，而是「最壞的情況」— $40$。
不過我仍然認為就算 2048 可以為難玩家，也還是不適合使用 minimax search，因為玩家和系統對於「有前途」的估計可能不同：可能對系統來說，它的模型算出來 B3 盤面對玩家較為有利，B4 盤面對玩家較為不利，因此系統會選擇產生 B4 盤面。大家訓練出來的模型都不同，minimax search 就不會比 expectimax search 好到哪裡去。
minimax search 應該比較適合雙方對於盤面好壞有類似看法的遊戲，以五子棋為例，當我方想著「要是他下在那個位置連成五子，我就輸定了」的同時，對方一定也想著「要是我下在那個位置連成五子，我就贏定了」，這樣就很適合 minimax search 了。
做個總結，在 minimax search 的搜尋小劇場中，輪到對方動作時，要選擇「對自己最不利(最低分)」的選項；輪到自己動作時，要選擇「對自己最有利(最高分)」的選項。