用AI自動化貪吃蛇遊戲的實驗與思考

機緣巧合下，我用pygame做了一個簡單的貪吃蛇遊戲。但是我是個手殘，我操作不動，這貪吃蛇的速度又會變快，我手跟不上。

考慮到現在大家都在說ai自動化，所以我在想能不能做個自動玩貪吃蛇的ai，我可以直接看他玩貪吃蛇。

最開始我的思考是我需要尋路算法，所以我簡單地寫了bfs跟dijk兩種算法，簡單地跑了兩局，我發現他很難達到地圖的理論上限。也就是蛇身填滿整個地圖所有區塊。

那我就想知道，這個算法本身的實力極限到底在哪。我直覺的認為如果跑越多次，平均出來的數值應該會越穩定，假設一個實力是能考90分的學生，他可能因爲一次粗心考了80，這不代表他的實力是80，而是要看長期下來是多少才準。我現在面對的是還不知道實力是多少，這個長期要多長我才能有把握說這個學生的實力大概就是幾分呢？

這個多長的值，本身應該具備什麼樣的思考呢？他是一個結論定案的時間，也就是說超過這個時間點之後，後續的實驗不會影響我的判斷了，對我來說也就是無效的，會浪費資源，所以這是一個臨界值。

第一次嘗試

對於某算法Ａ考慮其定值m是他的理想分數，在k次實驗之後，k次實驗的平均分數應該會等於m。

\frac{1}{k} \sum_{i=1}^{k} n_i = m

這樣的思考很快就碰壁了，因為不應該會等於，而應該是足夠接近。考慮微積分無限逼近的想法，如果實驗次數接近無限，確實會讓分數無限接近理想值，但是也只是無限逼近，依然存在為小偏量 $\epsilon_{n}$ 。並且這樣讓我有一個可以針對的目標，盡可能讓 $\epsilon_{n} \rightarrow0$ 。

第二次嘗試

對於某算法Ａ考慮其定值m是他的理想分數，在k次實驗之後，k次實驗的平均分數與m的差值絕對值會給定小數 $\epsilon_{n}$ 。

\exists K \in \mathbb{N}, \ \text{s.t.} \ \forall k > K, \quad \left| \frac{1}{k} \sum_{i=1}^{k} n_i – m \right| < \epsilon_n

如果是這樣的話，考慮單次實驗樣本 $n_{i}$ 實際上就是理想值加上該次樣本的運氣偏差。可以寫成

\text{let } n_i = m + \epsilon_i

這個式子帶回上面的命題後會得到

\begin{align} \left| \frac{1}{k} \sum_{i=1}^{k} n_i – m \right| &= \left| \frac{1}{k} \sum_{i=1}^{k} (m + \epsilon_i) – m \right| \\ &= \left| m + \frac{1}{k} \sum_{i=1}^{k} \epsilon_i – m \right| \\ &= \left| \frac{1}{k} \sum_{i=1}^{k} \epsilon_i \right| < \epsilon_n \end{align}

得出的是單次偏差量的總平均應該會小於原本設定的任意小數 $\epsilon_{n}$ ，這並不是結論，因為我依然不知道該怎麼樣設定k。只能再繼續嘗試能不能找到更多線索。

有一個思考缺口，或是說在假設上比較影響判斷的東西，就是單次偏量的正負值並沒有做嚴格的約束，這會讓運氣好的時候跟運氣不好的時候的貢獻度被各自抵銷。統計上的常態操作就是平方，讓偏量為正的同時擴大大偏量的貢獻度。

所以在上面的不等式上兩邊都掛平方

\begin{align} \left| \frac{1}{k} \sum_{i=1}^{k} \epsilon_i \right|^2 &= \left( \frac{1}{k} \sum_{i=1}^{k} \epsilon_i \right)^2 \\ &= \frac{1}{k^2} \left( \sum_{i=1}^{k} \epsilon_i \right)^2 \\ &= \frac{1}{k^2} \left( \sum_{i=1}^{k} \epsilon_i^2 + 2 \sum_{1 \leq i < j \leq k} \epsilon_i \epsilon_j \right) < \epsilon_n^2 \end{align}

這裡可以看出一些東西了，平均偏差平方後可以被分為單次偏差平方和加上交叉項，會小於總偏差量的平方乘上次數的平方。

在我的場景（貪吃蛇算法分數）我暫時可以簡單的說交叉項期望值0，所以直接讓他消失。並且有趣的是單次偏差平方和除一次k實際上就是該分佈 $X$ 的變異數 $Var(X)=\sigma^2$ 。

所以我可以得到

\frac{\sigma^2}{k} < \epsilon_n^2 \quad \Longrightarrow \quad \sigma^2 < k \, \epsilon_n^2 \quad \Longrightarrow \quad k > \frac{\sigma^2}{\epsilon_n^2}

也就是說我只要給定好我想要的最大偏差量，然後通過幾次實驗來確認一下實驗自身變異數，我就可以知道我最少應該要實驗幾次能讓我得出的分數線不超過多少偏差了。

比如說假設我的bfs貪吃蛇標準差大概是500，並且我想要讓他跟理想值差距最多50分，也就是五顆蘋果，我可能需要起碼實驗100局。

k>\frac{500^2}{50^2}=\frac{250000}{2500}=100

如果我想要偏差降低到一顆蘋果也就是10，我起碼需要實驗，誤差降低五倍，我的實驗次數需要提升5的平方倍，起碼要2500次。

k>\frac{500^2}{10^2}=\frac{250000}{100}=2500

這就完了嗎？不不不，如果對於單局我們都知道應該會不準，那如果把實驗k次本身看做一個事件，那麼對於該事件來說，本身也存在了這次的k次實驗跟下一次的k次實驗不會有相同結論的情況，也就是說上面的

k > \frac{\sigma^2}{\epsilon_n^2}

是有可能不會每次都成立的，連續運氣不好的k次實驗是有可能超出設定的偏差界線 $\epsilon_n$ 的，而上面的不等式其實沒有作出任何保證，意思就是說如果真的爆了，那就只能說一句運氣不好。這顯然不可被接受。

需要把k次實驗也視為單一事件，我們希望在我們設置的偏差邊界下，k次實驗的結論能被普遍簡單的復刻，或者說能得到一個大概率事件的保證，讓事件的結果不會是一個因為運氣好或不好恰好得到的數字。所以加上機率描述，變成了

對於某個演算法貪吃蛇Ａ，記其單局分數期望值為m。

claim：對任意偏差量 $\epsilon_n$ ，任意良率 $\delta$ ，存在定值k使得實驗k次後的平均分數與m的差值不超過 $\epsilon_n$ 的機率超過良率 $\delta$

這裡直接套Chebyshev’s Inequality，關於這個的證明就後續再證，可以得到

Chebyshev’s Inequality本身是針對單次事件，而我們討論的對象是k次實驗的均值，所以需要除k。

\begin{align} \mathbb{P}\left( \left| \frac{\sum_{i=1}^{k} n_i}{k} – m \right| \leq \epsilon_n \right) &\geq 1 – \frac{\sigma^2}{k \epsilon_n^2} > \delta \\ &\Longleftrightarrow \quad k > \frac{\sigma^2}{(1 – \delta)\, \epsilon_n^2} \end{align}

最終可以得到，實驗次數應該是要大於變異數以及1-置信度與可接受偏差的平方。

回到前面的例子，假設我的bfs貪吃蛇標準差大概是500，並且我想要讓他跟理想值差距最多50分，且我希望置信度可以在0.95，也就是不管做幾批次，大概率都能落在5個蘋果以內。則我需要做2000次實驗。

\frac{500^2}{(1-0.95)(50^2)}=\frac{250000}{125}=2000

結論

k > \frac{\sigma^2}{(1 – \delta)\, \epsilon_n^2}

有了這個結論，我就可以對我的實驗成本做測算，我想要達到什麼的誤差層級以及有多少的置信水平，我可能需要有多少的資源來做到對應的保證。後續也才能知道我可能需要實驗幾次，為什麼需要實驗這麼多次。

Strive-Wang

貪吃蛇學習-累積平均

發表留言取消回覆

貪吃蛇學習-累積平均

第一次嘗試

第二次嘗試

結論

分享此文：

發表留言 取消回覆

發表留言取消回覆