NO IMAGE
概述 (原始碼在最後)
早些年,IBM研發的深藍機器人戰勝了當時的國際象棋冠軍,引發了人們對人工智慧的關注, 去年,谷歌的alphaGo戰勝了李世石九段,又引發了一場人工智慧和機器學習的熱潮。隨著新演算法的和演算法變種的出現,人工智慧特別是機器學習領域又被推向了計算機行業的風口浪尖。如今人工智慧已經深入到生活的各個方面,比如手機上的siri,電腦上的小娜,離我們最近的可能是各種推送的廣告也越來越智慧化。本文講述一種基於機器學習的智慧五子棋的實現方式,以豐富我們的業餘生活。
現狀:
目前網上有一些五子棋AI程式,大部分是基於最大最小樹的剪枝演算法,或者是一些自定義的演算法,無法達到機器自我學習的目的,也基本沒有禁手規則。
在不考慮禁手的情況下,五子棋的走法並不複雜,傳統通過遞迴樹的方法已經可以讓機器達到很厲害的水平。
目的:
傳統演算法AI走棋套路固定,不靈活,下多了就沒意思,而本文實現的功能機器可以隨著遊戲的進行改變下棋的手法,從而提高靈活性,並加入禁手功能,讓遊戲更有樂趣。
設計:
首先,定義一個五子的棋學習問題:
任務T:下五子棋
效能標準:人機對戰中取得更高的勝率
訓練經驗:和人類下棋
列出這個問題後,根據米切爾的機器學習一書,我們缺少目標函式和目標函式的表示,這裡目標函式是以傳統的給棋盤定義一個分值的方法出。
分值包括棋盤上1子、2子、3子、4子、5子的個數,以及每顆子周圍的形勢、所處位置的好壞,目前我們用到了16種因素,這些因素分別記作X1,X2,X3,X4… 每一個因素都包含一個分值,記做θ1,θ2,θ3,θ4… 那麼期望H的表示式寫作(下面表示式省略了後面n個 .. θiXi):
這個函式是一個多維的一階線性函式,由此可以看出,我們可以把五子棋的下棋方法簡化成為在多維度上的分類的問題。
以上函式表示的是棋盤的實際值,那麼我們怎麼來獲取棋局的期望值呢?有一個方法:因為這盤棋最終會得到一個輸或者贏的結果,那麼這個結果期望可以用作最後一步前一步的期望,依次倒推,則可以使用下一步(我下一手後,對手再下一手)的實際值作為當前的期望。
下完後,根據最小二乘法,把每一步的誤差加起來,得到一個總誤差J(θ):
這裡,y(i)是第i步的期望輸出。
我們的目的是調整θi的取值來使誤差達到最小化,要求誤差的最小化,實際上就是當θ變化的時候,J(θ)變化最小,即J(θ)對θ求偏導,得到其最小的變化率,就是目的所在。
根據米切爾機器學習第四章,期望向量實際上與權向量θ的關係是一個負梯度的關係,所以θ(也叫做權)的表示式:
這個公式也叫做梯度下降法則,以下是J(θ)對θ求導過程:
代入上面的梯度公式,得到:
所以對於每個權,θi := θi n*Xi*(E-O) ,其中 n是係數,E是期望輸出,O是實際輸出。
利用這個公式,每走一步都對當前棋盤形勢對應的權進行調整。
演算法
另外,我們需要一個演算法來指導機器走棋,當然最簡單的方法是對每一個位置都進行模擬下子,得到對應的期望值,然後以期望值最高的一步作為最終下的點。
這裡使用的方法是使用最大最小搜尋樹,其原理是先模擬自己下一步棋,把下棋後的期望記下,然後在此基礎上,模擬對手下棋並再次計算期望,將期望差相減,得到差值最大的一步棋。主要的虛擬碼如下:
遍歷可走的位置:
下棋,計算期望
遍歷對手可走的位置:
對手下棋,計算期望
如果下的棋超過了上一輪下棋的期望,返回 #剪枝,該位置對手期望大,肯定不能走
如果超過了上一次的期望,記下
對手遍歷結束,返回本輪下棋最大期望
如果這輪期望差大於上一輪,則記下期望差,並記下下棋的位置 #要找出期望差最大的位置
遍歷結束,得到期望差最大的點
使用上述邏輯,我們基本可以打敗一般的對手,上述程式碼可以是遞迴的,傳統的下法是讓這個演算法遞迴n次,從而下出比較牛逼的棋,而我們並沒有這麼做,因為如果一味遞迴,就減弱了機器學習的意義,而且普通人下棋只會憑感覺,並不會考慮後面n手棋。
除錯和發現的問題
除錯是一個麻煩的過程,首先,我們沒有樣本,所以先按照網上的經驗給了權值一些適當的初始值,在除錯過程中,發現這些權值的大小直接影響機器的抉擇,某個值一定幅度的偏差會導致機器變得很傻逼。
另外,我們設計開始加入一些跟大局觀相關的因素,這是創新點,讓機器不走死套路。在除錯的時候發現,某些因素是錯誤的,會導致棋盤後期權重蓋過主因素,使機器變得越來越傻。另外,一些因素由於權值過高會直接影響到開局的落子。
另一個方面就是梯度下降演算法自帶的弊病,一是收斂速度比較慢,二是可能收斂到區域性最小值,我們僅靠個人下棋訓練沒辦法使其達到很高水平。相反,爛的下棋者會讓機器因為變得容易獲勝而強化爛的走棋線路。
經過幾百盤的對弈調整,最終把權調整到一個相對好的值。
當然,最後發現也存在不少的問題,主要有一下幾點:
1、目前對於棋盤的勝利因素考慮不夠周到,使得機器有時候還是會出現一些小失誤。
2、權重不夠好,比如有時候機會會下雙活三,而放棄堵黑棋的活三。
3、不支援手機,因為座標問題,還不支援手機點選
改進
繼續優化棋盤勝利因素,並手動匯入一些訓練樣本,得出最好的權值。
由於座標問題,暫時不支援手機瀏覽器,考慮改進支援。
另外再優化一下介面會更好,現在是一個網路版,可以直接訪問網頁進行遊戲。點選此處進行遊戲
參考文獻:
1、《機器學習》 ([美]米歇爾(Mitchell,T.M.) 2014年 機械工業出版社
2、《神經網路與深度學習》吳岸城 2016年6月
3、http://blog.chinaunix.net/uid-25267728-id-4678802.html
4、http://avicha.github.io/fivechess/
原始碼比較亂,多多包涵 http://lazypos.pw:8080/new.rar