赫爾辛基大學AI基礎教程：搜索和遊戲

AiTechYun

編輯：yxy

在本節中，我們將研究一個經典的AI問題：遊戲。為了清晰起見，我們將重點關注的最簡單的場景是雙人遊戲，如井字棋和國際象棋等完全信息遊戲。

例如：玩井字棋

Maxine和Minnie是真正的遊戲愛好者。他們只是喜歡遊戲。特別是兩人完美的信息遊戲，例如井字棋或國際象棋。有一天他們在玩井字棋。Maxine或者簡稱為MAX使用X.。Minnie或者簡稱為Min使用O。Min剛打完O，棋盤如下：

Max正在看著棋盤，思考她的下一步行動，因為現在輪到她了，但這時她突然絕望地捂著臉，看起來就像1997年的加里·卡斯帕羅夫(Garry Kasparov)對戰深藍。

是的，Min在第一排即將獲得三個O，但Max可以輕鬆堵住它。那麼Max為什麼如此悲觀呢？

遊戲樹

為了使用AI來解決遊戲，我們將介紹遊戲樹的概念。遊戲的不同狀態由遊戲樹中的節點表示，與規劃問題非常相似。不同的是，在遊戲樹中，節點按照每個玩家在遊戲中的回合順序排列，以便樹的「根」節點（通常在圖的頂部）是遊戲中的開始位置。在井字棋中，是沒有X或O的空網格。接著根下的第二級，可能由第一個玩家的落子產生的狀態，無論是X還是O.我們稱這些節點為根節點的「子」節點。

第二級的每個節點將根據對手下一步的落子後的狀態發展下一個子節點。逐級繼續，直到達到遊戲結束的狀態。在井字棋中，這意味著其中一個玩家可以獲得三點一線並獲勝，或者棋盤已滿並且比賽以平局結束。

最小化值和最大化值

為了能夠創建想去贏得遊戲的AI，我們給每個可能的最終結果添加一個數值。對於棋盤上X有三點一線Max獲勝，我們附加值+1，同樣，對於Min連上三個O的情況，我們附加值-1。對於棋盤已滿並且雙方都沒有獲勝的職位，我們使用中性值0.（無論值是多少，只要按照這個順序，Max就會嘗試最大化該值，而Min會嘗試最小化該值。）

遊戲樹示例

例如，思考下面的遊戲樹，它不是從根開始，而是在遊戲的中盤（否則，樹太大了）。請注意，這與本節開頭插圖中顯示的那盤遊戲不同。我們用數字1，2，…，14對節點進行了編號。

遊戲繼續在根節點中顯示的棋盤位置，在頂部編號為（1），輪到Min將O放置在三個空白單元中的任何一個上。節點（2） – （4）分別顯示三種選擇各自產生的結果。在下一步中，每個節點有兩個可能的選擇讓Max畫X，於是樹再次分支。

當從上面的起始位置開始時，這個遊戲三步就結束了：在節點（7）和（9）中，獲勝者是使用X的Max，節點（11） – （14）中獲勝者是用O的Min。

請注意，由於玩家輪流交替，每一級標記了Max和Min用以表明輪到誰下了。

戰略性思維

思考到倒數第二層上的節點（5）到（10）。在節點（7）和（9）中，遊戲結束，Max贏得勝利。此時值+1。在剩下的節點（5），（6），（8）和（10）中，遊戲也等於結束了，因為Min只需要將她的O放在唯一剩下的單元格中就可以獲勝。換句話說，我們知道遊戲如何在倒數第二層每個節點處結束。因此，我們可以確定節點（5），（6），（8）和（10）的值是-1。

有趣的部分來了。讓我們思考節點（2） – （4）的值。由於我們觀察到（2）的兩個子節點，即節點（5）和（6）都會導致Min的勝利，我們可以毫不猶豫地將值-1附加到節點（2）。而對於節點（3），左邊的子節點（7）會讓Max的勝利+1，但是右邊的子節點（8）會讓Min的勝利-1。節點（3）的價應該是什麼？這時我們要思考，誰在節點（3）做出選擇。

既然輪到了Max，她當然會選擇左邊的子節點，節點（7）。因此，每當我們到達節點（3）中的棋盤位置，Max都可以確保勝利，並且我們可以將值+1附加到節點（3）。

節點（4）也與此相同：因為Max可以選擇將X放在哪裡，她總是可以確保勝利，並且我們將值+1附加到節點（4）。

確定誰贏了

本節中最重要的是如何應用上述的推理，從任何棋盤位置中提前確定遊戲結果。

到目前為止，我們已經確定節點（2）的值是-1，這意味著如果我們最終處於這樣一個棋盤位置，Min可以確保獲勝，而節點（3）和（4）的值是+1，這意味著如果Max做出正確的選擇，那麼他一定能贏。

最後，我們可以推斷出，由於Min是一位老玩家，她可能得出同樣的結論，因此她只有一個正確的選擇：在中間下O。

在下面的圖表中，我們包含了每個節點的值以及從根節點開始時最優的遊戲策略。

根節點的值=誰勝出

據說根節點的值是遊戲的值，告訴我們誰會贏（如果結果不只是純贏或輸，也會告訴我們勝率）：Max贏得如果遊戲+ 1,最小值為1,如果該值為0,那麼遊戲將以平局結束。在其他遊戲中，值也可能為其他（例如撲克中籌碼的貨幣價值）。

這一切都是基於這樣一種假設，即雙方的選擇對自己最好，但對另一方最差(這就是所謂的「零和博弈」)。

註：

找到最佳的辦法

在確定了遊戲樹中所有節點的值之後，可以推導出最優移動：在任何Min節點處（輪到Min下的地方），最優選擇由其值最小的子節點給出，相反，在任何最大節點（輪到Max的地方），最優選擇由其值最大的子節點給出。有時候，也會有不管選擇哪一個結果都一樣的選擇。

Minimax演算法

我們可以利用上述遊戲價值的概念來理解Minimax演算法。它在理論上保證了任何確定性的、雙人的、完全信息的零和博弈的最佳遊戲玩法。在給定遊戲狀態的情況下，該演算法簡單地計算給定狀態的子節點的值，並且如果輪到Max則選擇具有最大值的那個值，並且如果輪到Min則選擇具有最小值的那個值。

該演算法使用很少的代碼就可以實現。但在這裡，掌握主要思路就可以了。如果有興趣查看實際演算法（警告：需要編程），請查看（https://en.wikipedia.org/wiki/Minimax）。

聽起來不錯，但這就結束了嗎？

如上所述，Minimax演算法可用於在任何確定性的、雙人的、完全信息的零和博弈中實現最佳遊戲玩法。這類遊戲包括井字棋，四子連珠，國際象棋，圍棋等等（猜拳不屬於這類遊戲，因為它涉及隱藏於其他玩家的信息; 大富翁或西洋雙陸棋也不是確定性的）那麼，但這個主題已經結束了嗎？答案是，在理論上，是的，但在實際中，沒有。

註：

較大遊戲樹的問題

在許多遊戲中，遊戲樹太大而無法完全遍歷。例如，在國際象棋中，平均分支因子（即每個節點的平均子節點數量，不計不可移動的）大約為35.這意味著只要探索前進兩步的所有可能場景，我們就需要訪問大約35 x 35 = 1225個節點 ……三步則需要訪問42875個節點; 四步1500625; 10步驟需要2758547353515625（即大約2700萬億）節點。在圍棋中，平均分支因子估計大約為250，Minimax不可用。

更多技巧：管理大的遊戲樹

管理大量遊戲樹需要很多的技巧。其中許多是IBM深藍計算機在1997年擊敗國際象棋世界冠軍卡斯帕羅夫的關鍵因素。

如果我們只能探索遊戲樹的一小部分，我們需要一種方法來在到達終端節點（比如，遊戲結束並且勝利者已知的節點）之前停止minimax遞歸。這是通過使用一個所謂的啟發式評估函數來實現的，該函數以一個棋盤位置作為輸入（同時包含下一個該輪到誰的信息），並返回一個分數，該分數應該是從給定棋盤位置繼續進行的遊戲的可能結果的估計。

註：

好的啟發式評估

例如，良好的國際象棋啟發式演算法通常會計算按其類型加權的材料（棋子）總數：女王通常被認為價值是車的兩倍，馬或象的三倍，兵的九倍。國王當然比其他所有東西的價值都要高，因為輸掉它就等於輸了比賽。此外，佔據戰略要地被認為是一種優勢，啟發式為這些位置賦予更高的價。

上面提出的minimax演算法需要最小的變化來獲得深度受限的版本，在給定深度受限法的所有節點上返回啟發式搜索：深度時指的是在應用啟發式評估函數之前遊戲樹被展開的步數。

練習7：Max為何悲觀？

讓我們回到本節開頭描述的井字棋。為了縮小可能的最終遊戲空間，我們可以觀察到，Max必須明確地將X放在第一排以避免即將到來的失敗：

現在輪到Min畫O。使用Minimax演算法以此為根，評估在這種遊戲狀態下的值以及遊戲樹中的其他狀態。

你的任務：

看看從下面棋盤位置開始的遊戲樹。用筆和紙填寫遊戲結束時底層節點的值。請注意，這次有些遊戲以平局結束，這意味著節點的值是0。

接下來繼續填充倒數第二級節點的值。由於這級沒有分支，與底層的值相同。

在倒數第三級，通過為每個節點選擇子節點的最大值來填充值 – 如你所見，這是一個MAX級。最後，通過選擇根節點的子節點值的最小值來填充根節點的值。這就是遊戲的值。

輸入遊戲的值作為答案。

註：

簡單搜索的局限性

可能看起來像我們有一種方法可以通過指定它們之間的狀態和轉換，並找到從當前狀態到目標的路徑來解決任何問題。可惜，當我們想在實際問題中應用AI時，情況會變得更加複雜。基本上，即使是一個中等複雜的現實世界情景中的狀態數量無法控制，我們無法通過窮舉搜索（「蠻力」）甚至巧妙的啟發式方法找到解決方案。

而且，當我們選擇一個行動時，將我們從一個狀態轉換到另一個狀態的轉換不具有確定性。這意味著，無論我們選擇做什麼都不會總是完全確定結果，因為有些因素是我們無法控制的，而這些因素往往不為我們所知。

我們上面討論的演算法可以適用於處理一些隨機性，例如在從洗牌平台選擇牌時的隨機性或擲骰子。這意味著我們需要引入不確定性和概率的概念。只有這樣我們才能開始接近現實世界的AI而不是簡單的謎題和遊戲。這是會是我們第3章的主題。

完成第2章後，你應該能夠：

規劃一個真實世界的問題為一個搜索問題

為簡單的遊戲（如井字棋）做遊戲樹

使用minimax原則在小的遊戲樹中找到最佳移動

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！