三角棋的人工智慧

本文僅適合想使用 flash 設計益智遊戲的入門者
| 人工智慧概述 | 遊戲的模擬 | 結語 | 附件 |
人工智慧概述
  • 電腦其實只是一部快速的計算機器,它還備有一些記憶及儲存的裝置,可以儲存大量的資料,如此而已。 但是因為人工智慧的發展,不但作業系統改進了,各種應用程式也大幅演進;在棋類遊戲的 人工智慧發展上,電腦程式設計師設計出來的西洋棋電腦程式,更是已可和人類的世界棋王相抗衡。 不過本文只對電腦益智遊戲的簡易人工智慧做一簡介,讓有心了解電腦益智遊戲設計的人,尤其是 學校的師生們得以入門,使更多的人可以共同參與,並設計出更多、更吸引人的益智、數學遊戲來。
  • 益智遊戲的種類極多,但其趣味性和其數學理論的完整性是互相排斥的兩個部份。如果一種遊戲可 以完全被數學決定以後,玩的人只要曉得其中的理論,無不處於優勢。遊戲本身就成為數學的計算, 玩起來必索然無味;但如果將它視為數學問題處理,則蘊藏有甚多美妙的理論在其中。而富有挑戰 性的遊戲,則沒有固定的規律可尋,必須隨機應變,靠臨場的機智和經驗取勝,玩者有味,但在數 學理論上則沒有什麼可言。
  • 對於具有完整數學理論基礎的遊戲而言,其程式設計好像較為簡易,但是如何模擬真實遊戲的進行、 如何進行遊戲的檢查、如何記錄遊戲的流程、如何進行思考方式的模擬,仍是需程式設計者大費周章的。
  • 對於沒有完整獲勝法則、富有挑戰性的遊戲而言,一般人或許認為是智力上的一大考驗,所以程式設 計起來一定是十分困難;其實除了西洋棋、象棋、圍棋......等大型遊戲而言,因為其變化十分繁雜, 只使用簡易的人工智慧時,必須花費天文數字的時間才能完成一步棋的完整思考程序,所以必須應用 較多的技巧及規則來修剪不必要的枝節外,一般的遊戲其實只要應用最大最小法,再加上 αβ修剪法 即可輕易設計出一個高智力遊戲者表現的程式來了。所以如果你敵不過遊戲設計者設計出來的程式,不 必灰心,和他本人比比看,很可能你輕易就可擊敗他們哦!
  • 另一種程式設計的方式則充分利用了電腦快速運算及大量記憶的特性,將遊戲的所有可能狀況在遊戲前 全部計算出來,等到遊戲時才按圖索驥,依遊戲的實際狀況,找到最好的應手。
  • 以上提到的三種遊戲人工智慧方式,在數學戲谷中都有應用到。而三角棋所使用的方式是第三種,也是 以下要向大家介紹的!至於另外兩種人工智慧的介紹因篇幅的關係,將另文介紹。
遊戲的模擬
  • 要製作一個電腦棋類遊戲,第一步就是要找到一個合適的資料結構以代表棋盤,棋子及棋局,因為電腦 的運作方式如前節所述,只能處理數值化的資料,所以棋賽中的實物及棋局狀況都必須被抽象化,合適的 資料結構有利於電腦的運作,並利於簡化演算法。但哪一種資料結構才是最好的?其實並無定論,往往 必須先依將使用的策略及演算法擬定初步的方案後,再於程式製作的過程中不斷的進行修正。
  • 數學戲谷中的三角棋程式是用 flash mx 製作的,其原始檔案「三角棋.fla」 在附件中,請自行下載參考。
  • 程式中棋子如圖 1 以 ABCDEFGHIJKLMNO 編碼,每一個棋子都用二進位中的一個位值 來表示,棋子 A 為第一個位元,棋子 B 為第 2 個位元,......;當某個棋子還在棋盤上沒被拿走時, 位元值為 1 ,如果已被取走了,位元值為 0 ,所以棋盤狀況只要用一個整數就可表示了。遊戲進行 的過程記錄在 backList 的陣列(堆疊)中,所以遊戲開始時 backList[0] 的值為 0x7FFF。
    編 碼ONMLKJIHGFEDCBA16進位值
    位元值111111111111111=0x7FFF
    ( 圖 1 ) 三角棋的編碼
  • 隨著遊戲的進行,某些棋子將被取走,代表棋局的整數值也會跟著變化,圖 2 中的棋形在 backList 中記錄的 就是 0x0FED。當然最後棋子取光而遊戲結束時的數值就是 0x0000 了。
    編 碼ONMLKJIHGFEDCBA16進位值
    位元值000111111101101=0x0FED
    ( 圖 2 ) 編碼示例二
  • 前節提過,數學戲谷中的三角棋遊戲是在遊戲開始前就將所有的棋形全部檢視過一遍了,所以遊戲進行中 的任何一個狀況全部都在電腦的資料庫中,並且已知其為勝型或輸型。三角棋一共有 15 個棋子,每個棋子 有存在( 即位元值為 1 )及被取走( 即位元值為 0 )兩種狀況,所以共有 0x7FFF= 32768 種不同的棋型, 尤怪在 DOS 時代設計三角棋程式時,因為記憶體有 640 K 的限制,所以還要使用一些技巧去節省記憶體的 用量,但是在 windows 作業系統中,記憶體的大小已不成問題了,所以只要用一個簡單的陣列 chessList 來儲存勝或輸的判定結果即可。每一種棋型的代表整數就是 chessList 陣列的索引編號,陣列的內容則 以 1 表示勝型,以 0 表示輸型。
  • 根據遊戲的規則,每次取子必須是相連成一直線的棋子。要怎麼判斷遊戲者的取子是合乎規定的呢? 如果先寫一個演算法去判斷是否相連,再寫一個演算法去判斷是否成一直線,當然也是方法之一。 但尤怪採用的方式是將所有可能的合法取法全部列成一表,要判斷遊戲者的取子時,只要到這 個列表( pickList )中去搜尋即可,如果取子的方式在列表中,就是合法的取子,如果取子的方式不在列 表中,就是不合法的取子。
    不過電腦要取子時可不能在列表中找了就用,因為列表中的取子雖然合法,但是棋盤中可不一定有指定的 棋子可取啊!那麼要怎麼判斷取法列表中的某一取法所取的棋子都在棋盤上呢?答案就是用邏輯「且」 運算,如果運算的結果等於取法的值,表示要取的子都在棋盤上;反之,若運算的結果不等於取法的值, 表示要取的子可能有部分不在棋盤上。以圖 2 的殘型 0x00FED 而言,如果電腦在取法列表中選擇了 0x03C0, 即要取去 GHIJ 四子,因 0x0FED & 0x03C0 = 0x03C0,運算的結果等於取法的值,所以這是正確合法的取子。
    編 碼 ONMLKJIHGFEDCBA16進位值
    目前殘型 000111111101101=0x0FED
    指定取法 000001111000000=0x03C0
    &(且)運算結果000001111000000=0x03C0
    如果電腦在取法列表中選擇了 0x1088, 即要取去 DHM 三子,因 0x0FED & 0x1088 = 0x0088,運算的結果不等於取法的值,所以這是不正確的取 子,因為想取的棋子 M 並不在棋盤上。
    編 碼 ONMLKJIHGFEDCBA16進位值
    目前殘型 000111111101101=0x0FED
    指定取法 001000010001000=0x1088
    &(且)運算結果000000010001000=0x0088
  • 解決了取子的合法性問題之後,就可以開始製作殘型勝負表了,尤怪使用的是倒推法。首先將儲存負表的 陣列值全部設定成 1,以假設所有的殘型都是勝型;然後因為取光棋子者勝,所以由 0x0000 的殘型開始 ( 即所有棋子已被取光的殘型 ) 開始檢視,只要發現殘型的設定值為 1,就將所有經合法取子會留下本殘型 的狀態全部設定為 0,因為當我們留下這些殘型時,對方可以找到至少一種取法搶佔到勝型;如果殘型的 設定值為 0,則表示該狀態為輸型,跳過即可;如此檢視完所有 0x7FFF 個可能的狀態後,三角棋起始時 是輸型( 先手必勝 ) 即已確認了。這項工作是由 setChessList2() 函數來負責完成的,各位讀者會發現 尤怪居然不一次完成所有 0x7FFF 個檢視,而是一次僅檢視 0x800 個狀態,分成 16 次才完成所有狀態的 檢視,這是因為 flash mx 的 AxtionScript 執行速度實在太慢了,在尤怪的電腦上,同樣的程式碼在 c 語言中不到 0.1 秒即可完成,但在 flash mx 中卻要 25 秒完成,所以如果想一次檢視完成,將會造成 flash 發出「有一個程序執行過慢」的錯誤訊息,對使用者造成困擾。
  • 剛才討論的是最後取光棋子者勝的勝負表製作法,如果遊戲改成最後取光棋子者輸,勝負表的製作有何不同呢? 答案是:只要將 0x000 設定為 0,然後由 0x001 開始檢視即可。好好的思考一下這其中的道理,你一定可以 明白的!
  • 準備好勝負表之後,就可以進入實戰階段了,當輪由玩家取子且經檢查是合法的取子時,應如何得到取子後 的殘型呢?方法就是應用邏輯「互斥或」運算。同樣的以圖 2 的殘型為例,如果玩者要取去 GHIJ 四子 , 因 0x0FED ^ 0x03C0 = 0x0C2D,恰為取子後的狀態沒錯。
    編 碼 ONMLKJIHGFEDCBA16進位值
    目前殘型 000111111101101=0x0FED
    指定取法 000001111000000=0x03C0
    ^(互斥或)運算結果000110000101101=0x0C2D
  • 當輪到電腦取子或需電腦提示時,電腦只要根據目前狀態值到勝負表一查,即可得知目前狀態是勝型或輸 型;若為勝型,表示對方已掌握了勝利之鑰,我方只能亂下了;如果對方留下的是輸型,表示我方一定可 以使用某些取法以搶佔勝型,此時只要一一檢視所有的合法取法,即可找到該取法了。
  • 程式還支援更改每次取子最大數的功能,這個部份又該如何達成呢?很簡單,只要將三角棋的 75 種合法 取子依一個棋子、二個棋子、......、五個棋子的順序排列,若每次取子最大數為 5,則合法取子當然為 所有的 75 手,但若每次取子最大數為 4,則合法取子只剩前面的 72 手,若每次取子最大數為 3,則合法取子 只剩前面的 63 手,.......。
結語
  • 三角棋.fla 的程式碼中,尤怪已加上了不少的註解,再加上前段的觀念解說,相信對 flash 已有基礎的讀者 應能了解本程式的設計方法。祝大家順利邁入遊戲設計的大道!
附件
 
 
 
本網頁建置日期:92.12.01 | 最近更新日期:92.12.01  | 回上頁 | 回首頁 |