近些年來人工智能的熱度與日俱增，5G + AI + IoT幾乎成為了人們對於未來的定義。Deepmind開發的AlphaGo圍棋AI，在2016年先後擊敗了李世乭和柯潔，扯下了人類智慧的最後一塊遮羞布。被譽為強化學習之父的Rich Sutton老先生，也在2017年作為一名研究科學家加入了Google Deepmind。
University of Alberta, Edmonton, Canada
Richard S. Sutton, Univerisyt of Alberta, 2015
本人有幸上過的Rich Sutton老先生的課，對於強化學習瞭解一點皮毛。這裡我們就簡單介紹一下強化學習的基本知識，並利用深度強化學習（神經網絡+Q-Learning）來訓練一個簡單的遊戲AI。
在本文中，我們會設計一個AI agent（虛擬玩家），並從頭開始訓練它學習小遊戲貪吃蛇的玩法。我們會利用Keras和Tensorflow來實現一個深度強化學習算法。強化學習算法的核心就是虛擬玩家(agent)根據自身的狀態(state)做出動作(action)，並且得到反饋(reward)，並利用反饋來改進今後的策略(policy)。agent並不知道任何遊戲規則，我們的目的是讓這個系統自己不斷訓練，在學習中提高遊戲得分，並最終形成一個可行的遊戲策略。
我們會看到Deep Q-Learning算法是怎麼一步步學習遊戲的規則，從一開始的無所適從，隨處亂走，到僅僅5分鐘後就學習出了可行的策略並且在遊戲中輕鬆獲得50分以上。
左圖：剛開始訓練；有圖：訓練後。圖片來源：Mauro Comi
一、遊戲環境搭建
我們利用python和Pygame簡單搭建了基礎的遊戲環境，這樣我們就可以直觀地觀察agent的訓練過程了。從上圖中我們可以很清楚地看到，剛開始的時候，agent沒有任何策略，只能盲目地隨機走動。而在訓練後，agent的策略已經十分理想了。
二、馬爾可夫決策過程(MDP)
MDP是一個用於給策略制定建模的數學框架，常被用來研究最優化問題。強化學習利用MDP來做出決策，而不是像傳統的監督學習一樣依賴輸入(input)和對應的正確答案(target)來訓練。
在強化學習中，有兩個主要的部分：環境(environment)和虛擬玩家(agent)。每當agent做出動作(action)，環境就會依據agent當前所處的狀態(state)來給出反饋(reward)。在貪吃蛇遊戲中，如果我們假設吃到果實的reward為1，而因為撞牆或者撞到蛇的身體而game over的reward為-1的話。那麼我們就可以說，從果實旁邊(state)前進一步(action)的反饋(reward)是1。類似的，在牆邊(state)，向牆前進一步(action)的反饋(reward)就是-1。
agent的目標就是學習在給定的state（包括蛇的位置，果實的位置等等遊戲環境）下，什麼樣的action可以最大化reward。
agent用於做出決策的策略就是policy，我們可以把想象成state到action的映射，指導了agent在給定state下應該做出哪個action。例如在貪吃蛇遊戲中，state就是所有可能遊戲狀態的集合（蛇的位置，果實的位置，地圖的大小，蛇的長度等等），而action就是蛇的所有可能動作集合（向上，向下，向左，向右）。
下圖為一個MDP的簡單例子，由三個state，兩個action，兩個reward組成的馬爾可夫決策過程（MDP）：
由三個state，兩個action，兩個reward組成的馬爾可夫決策過程（MDP），圖片來自Wikipedia
二、Q-learning算法
Q-table是一個state和可能action的關聯矩陣，矩陣中的數值就是在訓練過程中根據reward算出該action的預期reward，代表了該action的成功率。利用Q-table，我們可以找出agent的最佳策略(policy)。
很明顯，Q-table只能處理有限個state，如果state的數量十分巨大的話我們很可能會遇到問題。這個時候就需要利用深度神經網絡了。
每當系統給出了reward，我們可以通過公式(Bellman equation)來更新Q-value：
Bellman equation
Q-learing部分的算法核心大致如下：
- 遊戲開始，隨機初始化Q-value
- 系統通過觀察獲取當前狀態(State)
- 根據狀態s, agent執行動作(action)。動作可以隨機生成，或者查詢已有的Q-table。在訓練初期階段，系統通常會傾向於隨機策略，來探索(exploration)更多的action和對應的reward。在訓練後期階段，系統會越來越依賴已有的知識(exploitation)。
- 當agent執行了action之後，環境(environment)會給出reward。然後agent到達下個狀態(state')並根據Bellman equation更新Q-value。
- 並且，對於每一步，存儲state, action, state', reward, 遊戲是否結束等信息，用於將來訓練神經網絡，這一步稱為Replay Memory。
- 持續重複上面三步驟，直到本輪遊戲結束。
三、深度神經網絡(Deep Neural Network)
State: 代表了agent觀察到了環境的狀態，我們也將state用於神經網絡的輸入。具體而言，state是包含了11個布爾變量的array。
Loss：深度神經網絡利用損失函數(loss function)來減少衡量真實結果和預測值的差距。神經網絡的目標是最小化lost。這我們這個例子自，損失函數是：
Deep Neural Network:
我們使用的深度神經網絡有3箇中間層(hidden layer)和120個神經元(neuron)。這個神經網絡使用state作為輸入，返回3個值，分別對應向左，向右，直走這三個動作。最後一層使用了Softmax函數。
Deep Neural Network by Mauro Comi
四、訓練結果
在訓練了短短5分鐘，在150輪遊戲之後，agent已經從毫無策略的亂走，到摸索出了一套有效的策略，並且能夠獲得50分以上的遊戲成績了！
如圖，橫座標為遊戲輪數，縱座標為遊戲得分。可以看出，在前50輪，得分很低，agent主要在探索環境。而在後50輪，agent不再執行隨機探索策略，而是利用已經學習到的policy做出動作，所以得到了較高的得分。
五、總結
到這裡，我們就已經學習了強化學習的基本知識，並且瞭解了Deep Q-learing算法的基本原理，還通過貪吃蛇這個小遊戲檢驗了DQN算法的效果。
大家覺得短短5分鐘的訓練效果怎麼樣呢？感興趣的朋友可以查看源碼驗證一下，甚至可以改進算法提升一下訓練效果~
reference:
https://towardsdatascience.com/how-to-teach-an-ai-to-play-games-deep-reinforcement-learning-28f9b920440a
https://github.com/maurock/snake-ga
我是零度橙子，科技達人，谷歌認證雲計算架構師，AWS認證devops專家，歡迎大家關注我，瞭解有用有趣的科技知識～
