本文來自AI新媒體量子位（QbitAI）
這篇文章打算教你使用強化學習中的Q-learning算法，讓電腦精通一個簡單的遊戲。文中代碼所用語言是Ruby。
為了展示算法内部的工作機制，我們将會教它去玩一個非常簡單的一維遊戲。當然這個算法也可以被應用于更複雜的遊戲中。
我們的遊戲叫做“抓住芝士”，玩家P需要移動到芝士C那裡（抓住它！），同時不能落入陷阱O中。
每抓到一塊芝士，玩家就會得一分，而每次落入陷阱，玩家就會減一分。當玩家得分達到5分或者-5分時遊戲結束。下面的動畫展示的是一個人類玩家玩遊戲的過程。
請注意，為了簡化這個遊戲，所有的陷阱O和芝士C的位置都是不變的。你可以從這裡找到關于遊戲的Ruby源代碼以及相應Q-learning算法的實作過程：
https://github.com/daugaard/q-learning-simple-game
Q-learning是一種強化學習算法。強化學習是指受到行為心理學啟發的一系列機器學習方法，它的前提是你可以通過獎勵或懲罰行為來教會算法在之前經驗的基礎上采取特定的行動。這跟用食物獎勵教會狗狗坐好是一個道理。
Q-learning算法通過在表格中記錄遊戲中所有可能的狀态，和這些狀态下玩家可能的行為來運作。對于每個遊戲狀态S和玩家行為A，表格中記錄的數值Q代表着在S狀态下采取行為A可能獲得的獎勵。這意味着為了能夠得到最大獎勵，在特定狀态下，隻需要依據表格采取擁有最大潛在獎勵的行為。
現在我們來看一下上面描述的那個遊戲。
根據玩家所處的位置，這個遊戲一共有12種可能的狀态（重申一下：陷阱和芝士的位置是不變的），在每個狀态下玩家可以采取的行動就是向左或者向右。
Q值表格看起來像是下面這樣，注意這隻是我們這個問題下Q表格一種可能的形式，其中的數值可能跟實際有出入。
你可以從Q值表格中看出，當裡在采取向左的行為、靠近陷阱時，玩家會得到負面的獎勵；而向右走、靠近芝士時，玩家可能會得到正面的獎勵。
Q值表格的初始化就是指将表格中所有的Q值随機指派，這象征着在初始階段AI對遊戲沒有任何了解。為了讓它學會如何玩這個遊戲，我們必須設計出一個能夠根據經驗不斷更新Q值表格的算法。
我們采取的步驟如下：
第1步：初始化Q值表格，随機指派
第2步：在遊戲進行中反複執行以下操作:
2a) 從0到1中生成一個随機數 — 如果數字大于門檻值e，選擇随機行為，否則就依據Q值表格選擇目前狀态下獎勵最大的行動。
2b) 采取2a中選擇的行動
2c) 在行動完成後得到獎勵r
2d) 結合下式和獎勵r更新Q值表格
可以看出，更新Q值表格的過程中将會使用新得到的目前狀态和行為的獎勵資訊，以及未來可能采取的行為的相關資訊，但這不需要周遊未來所有的可能得到，隻需Q表格就能完成。這使得Q-learning成為一個相當快速的學習算法，但同時也意味着算法一開始會采取一些随機的行為，是以在玩過幾局遊戲之前，不要對你的AI有任何指望。
我們遊戲通常使用human player class（人類玩家）作為玩家。human player class的搭建過程如下所示，class通過兩個函數運作：構造器函數（constructor）和get_input函數。
get_input函數在遊戲進行中的每一次疊代中都會被調用，然後依據鍵盤上的輸入傳回玩家行動的方向。
為了構造Q-learning AI player class，我們将會使用一個新的class，包括Q值表格和基于上述算法的get_input函數。
如下所示，我們定義了這個新class和它的構造器。注意這裡我們新定義了一個attribute/特性： game。這被用來在Q-learning算法中記錄遊戲得分，進而更新Q值表格。
此外，在構造器中我們為每個在上述算法中列出的學習參量定義了attribute，然後初始化我們的随機數生成器。
下一步，我們将定義一個函數負責用随機數初始化Q值表格。狀态的數量用遊戲的map_size表示，每個狀态即對應着一個玩家的位置。
最終，我們采用了如下所示的get_input函數。首先，停頓0.05秒，保證我們能夠看清AI玩家移動的步驟。
随後我們将會檢查這是否是程式第一次運作，如果是的話就對Q值表格進行初始化。（步驟1）
如果不是第一次運作，那麼我們就對遊戲進行評估，因為從上一次遊戲的結果中就能得到Q-learning算法所需要的輸入——獎勵r。如果遊戲的得分增加了，那麼得到的獎勵為1；如果得分減少了，得到的獎勵為-1；得分不變獎勵為0.（步驟2c）
接着我們把結果狀态設定為遊戲的目前狀态（在我們的例子中即為移動玩家），然後使用下式更新我們的Q值表格。（步驟2d）
在上述最後一步更新過Q值表格後，我們為下一次運作保留之前的分數和狀态。
然後我們依據門檻值e，從随機或者基于Q值表格選擇出一個行為（步驟2a），函數傳回這個行為（步驟2b）。
這就完成了我們Q-learning算法的實作，你可以從上文中的github位址裡看到有關算法和遊戲的所有源碼。
我們讓Q-learning玩家進行了10次遊戲，結果如下：
你可以看出在第1次遊戲中，玩家還在不斷嘗試，包括漫無目的地左右移動。這是由于Q值表格的随機初始化導緻的。然而當玩家得到一些分數、落入一些陷阱後，它很快就學會了如何避免陷阱，徑直走向芝士。
在第7次和第8次遊戲運作中，玩家事實上采取了最優的獲勝方案，在37步移動中得到了5次芝士。
然後在第9次和第10次遊戲中，獲勝經曆的總步數又變成了39步。這是由門檻值e影響的，它的存在會使得算法有時候會采取随機移動，而不是采用優化的移動。這種随機性的設定會非常有必要的，它能夠保證算法能夠正确地探索整個遊戲，而不被局域最優值卡住。
這篇推送展示了如何将使用Q-learning來教會AI去玩“抓住芝士”這個簡單的遊戲。你可以想象，随着遊戲複雜的提升，Q制表格的大小将會呈現爆炸式增長。一種避免這種情況發生的方法就是把Q值表格替換為一個神經網絡。
DeepMind的研究者們探索了這種方法，發表了相關的論文。這這篇文章中，他們成功使用了神經網絡通過Q-learning來訓練AI去玩Atari出品的2600種遊戲。
論文：
Playing Atari with Deep Reinforcement Learning
位址：
https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf
— 完 —
本文作者：王瀚宸
原文釋出時間：2017-08-20