陳凱

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

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

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

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

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

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

1.給迷宮編碼

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

以上公式都十分容易理解，但在Q-learning強(qiáng)化學(xué)習(xí)，最有智慧的公式，出現(xiàn)在玩家角色進(jìn)入到空無一物的空間后，對動作策略所進(jìn)行的修改。下面的代碼是角色向上行進(jì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]），目的是取得新進(jìn)入的當(dāng)前空間通往下一空間交界處各行進(jìn)策略值中的最大值。

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

-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é)果乘以學(xué)習(xí)率0.1，如果學(xué)習(xí)率設(shè)置得太高，結(jié)果可能是玩家會被框死在某條未必劃算的路徑上，如果設(shè)置得太低，那么行進(jìn)動作策略的指示作用就難以體現(xiàn)出來。

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

3.一邊玩，一邊學(xué)

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

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

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

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