搶 30 的人工智慧

本文僅適合想使用 flash 設計益智遊戲的入門者
| 概述 | 遊戲的模擬 | 最大最小法及其修剪 | 結語 | 附件 |
人工智慧概述
  • 電腦其實只是一部快速的計算機器,它還備有一些記憶及儲存的裝置,可以儲存大量的資料,如此而已。 但是因為人工智慧的發展,不但作業系統改進了,各種應用程式也大幅演進;在棋類遊戲的 人工智慧發展上,電腦程式設計師設計出來的西洋棋電腦程式,更是已可和人類的世界棋王相抗衡。 不過本文只對電腦益智遊戲的簡易人工智慧做一簡介,讓有心了解電腦益智遊戲設計的人,尤其是 學校的師生們得以入門,使更多的人可以共同參與,並設計出更多、更吸引人的益智、數學遊戲來。
  • 益智遊戲的種類極多,但其趣味性和其數學理論的完整性是互相排斥的兩個部份。如果一種遊戲可 以完全被數學決定以後,玩的人只要曉得其中的理論,無不處於優勢。遊戲本身就成為數學的計算, 玩起來必索然無味;但如果將它視為數學問題處理,則蘊藏有甚多美妙的理論在其中。而富有挑戰 性的遊戲,則沒有固定的規律可尋,必須隨機應變,靠臨場的機智和經驗取勝,玩者有味,但在數 學理論上則沒有什麼可言。
  • 對於具有完整數學理論基礎的遊戲而言,其程式設計好像較為簡易,但是如何模擬真實遊戲的進行、 如何進行遊戲的檢查、如何記錄遊戲的流程、如何進行思考方式的模擬,仍是需程式設計者大費周章的。
  • 對於沒有完整獲勝法則、富有挑戰性的遊戲而言,一般人或許認為是智力上的一大考驗,所以程式設 計起來一定是十分困難;其實除了西洋棋、象棋、圍棋......等大型遊戲而言,因為其變化十分繁雜, 只使用簡易的人工智慧時,必須花費天文數字的時間才能完成一步棋的完整思考程序,所以必須應用 較多的技巧及規則來修剪不必要的枝節外,一般的遊戲其實只要應用最大最小法,再加上 αβ修剪法 即可輕易設計出一個高智力遊戲者表現的程式來了。所以如果你敵不過遊戲設計者設計出來的程式,不 必灰心,和他本人比比看,很可能你輕易就可擊敗他們哦!
  • 另一種程式設計的方式則充分利用了電腦快速運算及大量記憶的特性,將遊戲的所有可能狀況在遊戲前 全部計算出來,等到遊戲時才按圖索驥,依遊戲的實際狀況,找到最好的應手。
  • 以上提到的三種遊戲人工智慧方式,在數學戲谷中都有應用到。而搶 30 所使用的方式是第二種:可能是 因為尤怪的能力問題,到目前為止尚無法歸納出完整獲勝法則,例如:
    1. 對於可用的數字牌 ( 牌面數字為 1∼n )及奪標數 sum,那一種組合是先手勝?那一種組合是先手敗? 它們之間有什麼關聯?
    2. 如果是先手勝,先手者可取用的是哪一些牌?隨著遊戲的進行,遊戲中的取牌策略又如何?
    3. 當可用的牌組數不同時,對於可用數字牌及奪標數 sum 的組合有何影響?
    在程式設計者無法掌握完整獲勝法則的情形下,使用最大最小法再加上 αβ修剪的人工智慧方式, 是賦予電腦智力的最通用方式,本程式即是一例,而由於遊戲並不複雜,所以雖然 flash mx 的程式執行速度 不快,但是電腦的智力表現仍能有相當的水準。
遊戲的模擬
  • 要製作一個電腦益智遊戲,第一步就是要找到一個合適的資料結構來模擬遊戲的狀況,因為電腦 的運作方式如前節所述,只能處理數值化的資料,所以遊戲中的實物及遊戲狀況都必須被抽象化,合適的 資料結構有利於電腦的運作,並利於簡化演算法。但哪一種資料結構才是最好的?其實並無定論,往往 必須先依將使用的策略及演算法擬定初步的方案後,再於程式製作的過程中不斷的進行修正。
  • 數學戲谷中的搶 30 程式是用 flash mx 製作的,其原始檔案「搶30.fla」 在附件中,請自行下載參考。
  • 由於本程式所使用的道具是撲克牌,所以尤怪非常自然的以撲克牌上的數字做為撲克牌元件的編號,但是 遊戲中可使用的撲克牌不只一組,所以要再加上組別序號,才能正確的控制遊戲中的每一張牌,例如 p10 表示 1 號牌的第一張牌,p32 表示 3 號牌的第 3 張牌,p81 表示 8 號牌的第 2 張牌......。撲克牌元件 共有 10 個影格,第一個影格的牌面為 1 ,第二個影格牌面為 2 ,第三個影格牌面為 3 .......,要顯示 某一數字的撲克牌,只要將影格停在該數字即可。
  • 程式以一個整數陣列 used[] 來代表撲克牌在遊戲中的取用狀態。 遊戲開始時陣列 used[] 的值全部會被設定成目前的牌組數,隨著遊戲的進行,某些撲克牌將被取用, 陣列中相對節點的值也將被更改,如果陣列中某一節點的值為 0 ,表示該號碼的牌已被取光,就不能再 被取用了。
  • 程式以 nowsum 來記錄到目前為止,遊戲者已取用的撲克牌數字之和。遊戲剛開始時 nowsum 的值將歸 0 , 隨著遊戲的進行,某些撲克牌將被取用,牌面上的數字也將隨著加入 nowsum ,當 nowsum 的值大於 奪標數時,將依勝負判定的規定找出勝利者,並結束遊戲。
  • 遊戲進行的過程記錄在 backList[] 的陣列(堆疊)中。因為已被取用的牌需要依取用的順序排列在遊戲盤的下方, 以供遊戲者參考,所以尤怪針對每一手在 backList[] 的記錄中包含牌面的數字及牌組序號兩個數值,然後 依照該二值鎖定指定的撲克牌元件來顯示。每取用一張牌要記錄的這兩個數值,如果使用陣列的兩個節點來儲存雖可, 但是尤怪所使用的方式是:將該二值合併成一個數值,十位數是牌組序號、個位數則是牌面數值,如此就能只用 一個節點來記錄一次的取用了。
最大最小法及其修剪
  • 對局遊戲必定有勝有負,遊戲者莫不希望自己的每一手使得局勢變成對自己有利,也就是使自己愈接近勝利, 但是什麼樣的局勢才是對自己有利的呢?在搶 30 的遊戲中,這不是一個容易回答的問題,至少很難精確的 說出來;因為經過一段時間的遊戲之後,每一個遊戲者雖然一定都能歸納出一些勝負的法則,例如( 假設奪標數 和累計值之差稱為剩餘值 ):
    1. 法則一:當目前可用的最大牌值大於剩餘值時,輪到取牌者勝。
      例如:目前可用的牌是 2、3、6、9,奪標數是 30,累計值為 25,輪到取牌者只要取用最大牌值 的那一張牌,就可以使累計值大於奪標數而得勝了。
    2. 法則二:當目前可用的最大牌值不大於剩餘值,且最大牌值及最小牌 值之和大於剩餘值時,輪到取牌者輸。
      例如:目前可用的牌是 2、3、5、6、9,奪標數是 30,累計值為 20,輪到取牌者不論取哪一張牌, 都無法使累計值大於 30,但輪到對手後,對手只要取用最大牌值的那一張牌,就可以使累計值 大於奪標數而得勝了。
    3. 法則三:若存在一張牌使得輪到取牌者可造成法則二的情勢,則輪到 取牌者勝。
      例如:目前可用的牌是 1、2、3、4、5、6、7,奪標數是 30,累計值為 17,輪到取牌者只要取用 牌面為 7 的那張牌,就可以使累計值達 24、而剩餘值為 6,此時最大牌值 6 不大於剩餘值、 但是最大牌值 6 及最小牌值 1 之和 7 大於剩餘值 6,符合法則二,所以輪到取牌者勝。
    4. ......
    但是這些獲勝的法則並無法涵蓋所有的可能情況,而且要用程式一一檢視這些法則後,再找出一個最佳的應手, 有時是十分耗費程式設計者之時間及心力的,所以要另闢蹊徑才行。
  • 在沒有完整的獲勝法則下,什麼是程式設計師的最後秘密武器呢?答案就是最大最小法再加上 αβ修剪。 如果運用得當,而且遊戲並非十分複雜,通常使用這類的人工智慧方式來設計程式後,其智力表現保証 叫常人自嘆不如的。但什麼是最大最小法及 αβ修剪呢?且看以下分解!
  • 為了解說的方便,降低遊戲的複雜度,我們且先把遊戲簡化成「只能使用一組 1∼4 的撲克牌,當累計值 大於 7 者得勝」的模式 ( 以下簡稱搶 7 遊戲 )。針對遊戲的某一個狀況 ( 殘型 ) ,輪到先取牌者稱 為先手者,另一個遊戲者稱為後手者。
  • 考慮遊戲的所有可能狀況,例如在搶 7 的遊戲中,先手者的第一步取牌值有四種可能:1、2、3、4。 後手者第二步的應手因為已少了一張牌,所以只剩下相對的三種可能,再輪回先手的第三步時剩 下兩種可能,後手的第四步應手就只剩下唯一的一種取法了。所以所有的情況 只有 4×3×2×1 = 24 種不同的可能性。把這些可能的取法及其可能應手以圖形表示時, 就成了一棵樹的樣子,這叫做遊戲樹。
    ( 圖 1 ) 搶 7 遊戲的遊戲樹
  • 在圖 1 的遊戲樹中,先手者的位置在偶數層,此時應選擇評估值最小的子節點,做為自己的評估值 ( 因為對先手者最不利的棋步,對後手者而言卻是最有利的,所以如果先手者選擇了這個節點做為他的 棋步,後手者一定會選取評估值最小的那一個節點當做應手 );同理,後手者的位置在偶數層( 根節 點除外 ),此時則應選擇評估值最大的子節點,做為自己的評估值 ( 因為如果後手者選擇了這個 節點做為他的棋步,我們一定會選取評估值最大的那一個節點當做應手 )。在奇數層上的節點通稱 為 max 節點,在偶數層上的節點則通稱為 min 節點,最大最小法的名稱即由此而來。
  • 雖然遊戲起始時勝負情勢通常不容易判定,但是隨著遊戲的進行,遊戲的情勢對誰有利是愈來愈容易評估的。 有時甚至根本不必進行評估,因為勝負已經揭曉了。例如圖 1 中搶 7 遊戲的遊戲樹,到了第四層時, 累計值一定會大於奪標值,所以此時可以使用勝負判定函數來代替評估函數。
  • 像搶 7 遊戲這麼簡單的遊戲,大概一下子就會被破解強記了的,一般的遊戲都要複雜多了,不太可能在 決定一步應手前,先把往後的所有可能性全部都檢視過一遍,再從中挑一個最佳應手來;但是儘可能的 深入愈多層,對遊戲的掌握就愈精準,則是不變的法則了。
  • 但是考慮愈多層,遊戲樹的節點就愈多,以搶 30 的遊戲為例:遊戲起始時的第一層可能取法共有 9 種, 第二層的相對應手各有 8 種可能,第三層的相對應手又各有 7 種可能,......所以共有
    9!= 9×8×7×6×5×4×3×2×1= 362880
    種可能。這個數字說大不大,但是只要假設電腦處理每一個節點的相關程序,然後再加以評估, 僅需 0.001 秒吧,362880 種可能共需 362880×0.001= 362 秒。當然電腦可能更快,但這 告訴了我們一件事:好的資料結構、簡單的節點處理、簡明的評估函數是十分重要的。
  • 既然增加遊戲層數的檢視代價驚人,於是就有各種的改進策略被提出來應用了,其中又以 αβ修剪 最為通用。這主要是從減少遊戲樹中所要檢視的節點來著手的,對遊戲樹中的任何一個節點而言, 只要能夠省去一個節點,就可以省去一個後代子樹的檢視;另外遊戲樹的節點不一定全部都可達 到某一層,所以遊戲終止時的處理也是十分重要的。
  • 所謂的 αβ修剪其實是由兩種截止所混合而成的:
    1. min 節點的 α截止:max 節點將選擇評估值最大的子節點做為自己的評估值,而在未檢視所有 的子樹前,它的暫時評估值為己尋訪過之子節點之最大值,所以此值可作為未檢視之子節點的 下限值( 稱做 α值 ),因為 max 節點的子節點為 min 節點,一旦 min 節點的暫時評估值不 大於此下限值時,它的最終評估值必然也不大於 α值,如此一來 min 子節點必然不會 被 max 父節點所選取,所以 min 節點的其餘子樹也不用再檢視了;這就是 α截止了。
    2. max 節點的 β截止:min 節點將選擇評估值最小的子節點做為自己的評估值,而在未檢視所有 的子樹前,它的暫時評估值為己尋訪過之子節點之最小值,所以此值可作為未檢視之子節點的 上限值( 稱做 β值 ),因為 min 節點的子節點為 max 節點,一旦 max 節點的暫時評估值不 小於此下限值時,它的最終評估值必然也不小於 β值,如此一來 max 子節點必然不會 被 min 父節點所選取,所以 max 節點的其餘子樹也不用再檢視了;這就是 β截止了。
  • 如果程式有辦法檢視完所有的遊戲樹,例如圖 1 的搶 7 遊戲,則可使用修剪得更徹底的方法,因為 我們可以直接以勝負判定函數來代替評估函數,所以評估值只有兩種:不是勝,就一定是輸。
    1. max 節點在檢視子樹時,如果發現某一個子節點的評估值為勝,因為其他子節點的評估值 不可能得到比勝利更好的狀況了, 所以其他子節點必然不會被 max 父節點所選取, 所以其餘的子樹也不用再檢視了。
    2. min 節點在檢視子樹時,如果發現某一個子節點的評估值為輸,因為其他子節點的評估值 不可能得到比失敗更差的狀況了, 所以其他子節點必然不會被 min 父節點所選取, 所以其餘的子樹也不用再檢視了。
    在這樣的修剪(姑且稱為勝負修剪吧)下,圖 1 的搶 7 遊戲樹將被修剪成圖 2 的樣子:
    ( 圖 2 ) 搶 7 遊戲的遊戲樹修剪
  • 搶 30 遊戲雖然簡單,但是因為 flash mx 的 AxtionScript 執行起來,和其他的程式語言相比, 相對的慢了許多,所以如果要採用勝負修剪的方法,去檢視完所有的遊戲樹,將會造成 flash 發出「有一個程序執行過慢」的錯誤訊息,所以必須分成多次來檢視,其程式碼在 PCThink() 函數,尤怪已加上許多註解,如果已有其運作方式的概念,應該可以自行參閱了。
  • 一般遊戲程式設定電腦智力的方式是智力等級愈高,檢視的層數愈多,但是本程式因為省去了 評估函數,所以無法對未達遊戲底層的殘局給出評估值,並不適用該方法來設定。因為除非 遊戲者對本遊戲已具有相當深入的研究,並已能根據不同的殘局給出適當的應手,否則遊戲 之初的取牌對最後的勝負並沒有任何影響力,所以程式中設定棋力的方式是:對於不同的智力 等級,程式會從指定的剩餘值開始運作,當剩餘值大於該智力等級時,程式採取亂數取牌;當 剩餘值小於該智力等級時才進行思考。
結語
  • 搶30.fla 的程式碼中,尤怪已加上了不少的註解,再加上前段的觀念解說,相信對 flash 已有基礎的讀者 應能了解本程式的設計方法。祝大家順利邁入遊戲設計的大道!
  • 常有人問尤怪:「你怎麼會那麼厲害!對那麼多種遊戲都有相當的研究?」尤怪只能笑笑, 也曾多次否認,但大家都不相信,認為尤怪只是謙虛罷了。其實,尤怪對各種數學益智遊戲 雖有興趣,但卻真的不曾深入研究過,所以在設計數學戲谷的遊戲時,大多先採最大最小法 並加上適當的修剪,等到程式初稿設計出來之後,才在試玩中尋找規律,若能找到最好, 只要將電腦思考的部分更改成固定法則即可,如果真的歸納不出結果,只好保留最大最小法 了。所以說:最大最小法是程式設計者的最重要武器,並不為過!有志於設計遊戲者一定要 好好研究此法。
附件
 
 
 
本網頁建置日期:92.12.09 | 最近更新日期:92.12.09  | 回上頁 | 回首頁 |