第一視角的強化學習

陳凱

如在夢境中一般，他跌跌撞撞行進在幽暗的洞穴迷宮中，他依稀記起自己此行的目標——盡快找到那難以估價的寶藏，并避免遭到巨型蜘蛛的攻擊?？墒?，下一步，是由此通往哪里，而此前，自己又是從哪條路來到此處，他卻完全沒有了印象，在火把的閃光中，他注意到狹窄通道的墻上留著一些神秘的記號……

這是一個迷宮尋寶游戲，玩家的目的是找到寶藏，同時避開危險的動物，為了文章描述方便，迷宮的結(jié)構(gòu)設計得很簡單，如表1所示。

迷宮里有11個直接或間接連通的空間，有一些地方被巖石堵住無法通行，開始游戲時，玩家在迷宮的左下角，而寶藏在迷宮的右上角，危險的動物緊挨著寶藏，要是玩家能看到這張迷宮結(jié)構(gòu)圖，那游戲未免太簡單了，往上走兩步，再往右走三步就完成了任務。然而，這是一個第一視角游戲，玩家只能看到自己當前所處空間的狀況，而不知道上下左右其他空間的狀況，于是為了找到寶藏，就只有隨機四處行走來碰運氣。還有一個麻煩的問題是，玩家所控制的角色是個失憶癥重癥患者，每次進入到新的空間，他的記憶就會被清空，就算是最終獲得了寶藏或者撞上了危險動物，在回到初始位置重玩游戲時，剛才這種純粹碰運氣式的“努力”也都要全部再來一次。

但若玩家可以在空間與空間的交界處留下一些特殊的信息，情況就能有所改善，由于每完成一步移動就會失憶，所以玩家不能把整個迷宮的結(jié)構(gòu)圖畫出來，但至少可以記錄一下，自己來到當前空間的這一步行進動作是否劃算。

比如說，若新進入的空間里有寶藏，可以在進入的交界處留下“大膽往前走”的標志;如果新進入的空間里有危險的動物，就在交界處留下“小心有危險”的標志，如圖1所示。不過也有這樣的情況，新進入的某個空間，稱之為當前空間，這里并沒有什么東西，但卻能看到在當前空間通向下一個空間的交界處留下的標記是“大膽往前走”，那就可以在之前的空間與當前空間的交界處留下一個“值得往前走”的標記，如圖2所示。

以此類推，如果發(fā)現(xiàn)當前空間通往下一空間的交界處標記有“值得往前走”，那么還可以在之前空間通往當前空間的交界處留下“可以試著走”的標記?？墒?，為什么不全部標記“大膽往前走”呢？因為在一個復雜的迷宮里，通往寶藏的路徑可能不止一條，雖然說在某次探險中標記了一條可以通往寶藏的道路，但有可能這一條完全靠蒙的道路彎彎繞繞，兜了一個不必要的大圈子才到達目的地，所以，只要不是緊挨著寶藏，標記就不能寫得很絕對。通過上述這種方法，既可以把遠處的狀況信息，依靠臨近空間的標記逐漸擴散開來，又能提供給探險的玩家多種行進的可能性，這正是Q-learning強化學習的重要思路。那么，這種思路是如何真正落實到人工智能算法的實現(xiàn)中去的？對這個問題的解答，便成為開展教學的主要內(nèi)容。

1.給迷宮編碼

為了處理迷宮中的各種信息，需要將迷宮的結(jié)構(gòu)、迷宮里的東西、在迷宮中行走的動作以及特定動作執(zhí)行后在空間交界處所留下的標記，都編碼成數(shù)字或字母。

例如，把可以進入的空無一物的空間標記為0，無法進入的巖石墻體標記為2，有寶藏的空間標記為1，有危險動物的空間標記為-1，于是迷宮成為一個二維數(shù)組，如表2所示。

在游戲中，玩家的角色會變化位置，所以用x和y兩個變量來確定玩家當前的位置，整個數(shù)組（列表）從下往上數(shù)從第0行到第4行共5行，從左往右數(shù)從第0列到第5列共6列。因為玩家的角色并不會穿墻術，所以將x和y都設置為1，表示他在最左下角的空間里。將這個空間布局用Python的列表來表示，就如圖3所示的樣子。

然而還需要另外一張表，來記錄空間交界處為每個行進動作所做的策略標記，因為在每個空間中，可能有上下左右四個行進方向，所以就需要用一個三維的數(shù)組（列表）來記錄數(shù)據(jù)，如表3所示。

用Python代碼表示就如圖4所示。

可以將這個數(shù)組（列表）稱為Q表，初始狀態(tài)下，默認的策略標記都是0。[0，0，0，0]中用逗號隔開的四個部分，分別代表著向右、向下、向左和向上四種不同行進動作的策略值。值越大，就代表這個動作越劃算，反之則是不劃算。

接下來，是給上下左右每一步行進動作編碼，這里可以用四個字母代表上下左右四個方向，比如，“w”是上，“s”是下，“a”是左，“d”是右，這樣編碼有個好處，如果在鍵盤上控制角色的前進方向，也可以用“w”“s”“a”“d”這四個按鍵。用按鍵控制玩家的角色上下左右移動，并判定是否獲取寶藏或遭遇危險動物的代碼非常簡單，如圖5所示。

代碼中，將角色的y變量加1，等同于往右走;y變量減1，等同于往左走;x變量加1，等同于向上走;x變量減1，等同于向下走。限于篇幅本文沒有列出全部代碼，但補全代碼十分容易，讀者也可以自行設法利用函數(shù)，使得代碼更為簡潔。

到這里，玩家已經(jīng)可以控制角色在迷宮中自由探索了，不過到目前為止，還沒有解決先前所說的失憶癥問題。接下來的任務，是要使前一次通關的經(jīng)驗能夠為后一次通關提供幫助，將每一次行進動作的劃算程度記錄到Q表中。

2.充滿智慧的數(shù)學公式

相較于用一堆含混不清的文字來標記特定動作的劃算程度，直接用一個數(shù)字作為動作的策略值，明顯更有利于“無腦”的決策。比如，策略值數(shù)字大則推薦走，數(shù)字小則不推薦，因為游戲初始時，Q表中所有的策略值都是0，所以就需要根據(jù)特定行進動作的效果來更改值。

比如，在游戲初始時，玩家角色可以向上走，也可以向右走，但向左和向下的路是不通的，即便一定要頑固去走，結(jié)果只是無端撞墻后回到原地，這時候就可以在Q表中記錄一下策略值的變化：q[x][y][2]=q[x][y][2]-0.2。因為游戲初始時x和y是1，所以相當于是：q[1][1][2]=q[1][1][2]-0.2。

結(jié)果，q[1][1][2]的值是-0.2。因為值變小了，表示這個行進方向不太劃算?！癧1][1][2]”是列表q的三個下標，第一個下標表示角色所處的行，第二個下標表示所處列，第三個下標表示角色的行進動作，“0”“1”“2”“3”分別代表向右、向下、向左、向上四個方向。

如果角色向右走進入了藏有寶藏的空間，則公式是：q[x][y][0]=q[x][y][0]+0.5。

為了說明這個動作非常劃算，策略值變大了。類似地，如果進入到藏有危險動物的空間，策略值就會變小。

以上公式都十分容易理解，但在Q-learning強化學習，最有智慧的公式，出現(xiàn)在玩家角色進入到空無一物的空間后，對動作策略所進行的修改。下面的代碼是角色向上行進時，Q表中策略值發(fā)生的更改：q[x][y][3]=q[x][y][3]+0.1*（-0.1+0.9*max（q[x+1][y][0]，q[x+1][y][1]，q[x+1][y][2]，q[x+1][y][3]）-q[x][y][3]）。

將代碼分解如下：

max（q[x+1][y][0]，q[x+1][y][1]，q[x+1][y][2]，q[x+1][y][3]），目的是取得新進入的當前空間通往下一空間交界處各行進策略值中的最大值。

0.9*max（q[x+1][y][0]，q[x+1][y][1]，q[x+1][y][2]，q[x+1][y][3]），目的是要把這個策略值進行打折處理，0.9就是折扣率，比如說，在緊挨著寶藏的空間中，策略值是“百分百推薦這么走”，離開較遠一些，則應該是“比較推薦這么走”。這樣才能提供多條路徑選擇的可能。

-0.1+0.9*max（q[x+1][y][0]，q[x+1][y][1]，q[x+1][y][2]，q[x+1][y][3]），因為要避免兜圈子多走路，只要是走了一步，那么策略值就要減少一些，所以這里減去0.1。

0.1*（-0.1+0.9*max（q[x+1][y][0]，q[x+1][y][1]，q[x+1][y][2]，q[x+1][y][3]）-q[x][y][3]），把上述結(jié)果乘以學習率0.1，如果學習率設置得太高，結(jié)果可能是玩家會被框死在某條未必劃算的路徑上，如果設置得太低，那么行進動作策略的指示作用就難以體現(xiàn)出來。

折扣率和學習率的取值大小并沒有標準答案，需要不斷調(diào)整以使得算法獲得更優(yōu)效果，所以，可以在代碼起始時使用兩個變量代表折扣率和學習率，使得程序調(diào)試更為方便，上頁圖6是實現(xiàn)玩家動作及Q表策略值更新的部分代碼，限于篇幅，只提供向右行進并更改Q表策略值的代碼，其他幾個方向的行進代碼其實是類似的。

3.一邊玩，一邊學

寫到這里，筆者準備宣布一個稍微讓人沮喪的消息，本文雖然講了Q-learning強化學習算法的核心思想，也提供了部分實際可以運行的程序代碼，但要完整實現(xiàn)Q-learning的算法，還有許多事情要做。比如說，若要讓機器代替玩家自動分析數(shù)據(jù)并進行下一步動作的決策，就需要在代碼中增加條件判斷;為了讓機器能探索更廣闊的空間而不局限于先前行動的Q表的決策數(shù)據(jù)，就要引入隨機函數(shù)，并需要在純粹隨機的動作和Q表的決策數(shù)據(jù)之間進行平衡;為了讓代碼具有更多普適性，還要改造數(shù)據(jù)結(jié)構(gòu)，引入線性代數(shù)中“矩陣”的概念……筆者認為，如果人工智能教學面向的是基礎教育領域整體的學習者，在課時和學習者當前知識技能水平受到限制的情況下，教學的重點應該在于促成學習者對機器學習的根本思想方法的領悟，而不在于完整的機器學習算法的代碼的構(gòu)建。

本文提供的Q-learning強化學習算法的代碼雖然并不具有機器智能學習的完整功能，但卻提供了第一視角下親身體驗機器學習過程的可能，通俗來說，就是能夠很容易玩起來，一邊玩，一邊思考那些不斷變化的策略值的含義。在程序運行之初，界面中毫無有價值的信息，四個方向的空間交界處的數(shù)值都是0，玩家也只能隨便瞎走，如上頁圖7所示。但在多次行動后，通往四個方向的空間交界處的數(shù)據(jù)就有了提示作用，如上頁圖8所示。

比如，在最后一行的互動操作，應該選哪個方向行進呢？向右的“d”和向下的“s”所對應的數(shù)值都比較大且相差不多，所以可以隨便選一個動作試試，人是這樣判斷的，若是編程讓機器做出這樣的判斷，也并不是什么困難的事情。為了使得“失憶癥”效果更強烈，也就是說，讓玩家的行為更接近機器學習中機器的行為，還可以進行一些小變化，比如，將程序代碼中指示當前空間位置的代碼刪除掉，或者讓兩位學生交替輸入行進動作的方向，甚至兩兩組隊開展尋寶比賽，看哪一組學生可以在規(guī)定時間內(nèi)更多次獲取到寶藏。

在第一次乃至前幾次尋寶過程中，空間交界處的策略值數(shù)據(jù)差別不是很大，但多次尋寶成功，或者多次遭遇危險動物失敗后，這些數(shù)值的大小會逐步拉開差距，使得玩家的行進方向越來越明顯，這就體現(xiàn)了Q-learning算法延遲獲得回報的特征。只要多玩幾次游戲，就能領悟為什么延遲回報對類似迷宮探險這樣的游戲特別有用，這比多少單純的口敘筆述都更有效。假想一下，在基礎教育領域，面對全體學生講授Q-learning算法卻只有短短40分鐘課時，那該怎么安排教學內(nèi)容呢？筆者會拿出一半的課時來實施尋寶游戲的比賽，讀者們又怎么想呢？