iT邦幫忙

2024 iThome 鐵人賽

DAY 4
1

hackMD原稿
再麻煩將背景調為淺色,深色背景會看不太到圖。

看完了古人的操作,換我們來打造一個自動下棋AI了。
那除了把人塞進電腦裡之外,要怎麼讓電腦下棋呢?
以現今的科技要讓電腦下棋已經是稀鬆平常的事了,但是要怎麼讓電腦把棋下得好,甚至於遠超人類就是值得研究的問題了,不過這邊我們還是先從讓電腦可以下棋開始吧。

如何讓電腦下棋

工人智慧

直覺能想到的應該就是先學習人類的思維,我們怎麼下棋就讓電腦怎麼下棋。
以五子棋為例,我們要阻止對方連成五個,就得在對方連成三個時去阻擋對方。
那可能就會有像是以下的策略:

if 對方有活三 or 死四:
    擋住對方
else:
    幫自己造活三 or 死四

接下來根據遊戲的特性跟你的經驗可以寫出更多的規則,然後你的「AI」可能就會長得像下圖這樣。

image

會有滿滿的if else
但不管怎樣第一個會下棋的「AI」也算是完成了,又沒人說AI一定得用到什麼高深的演算法呢。
只是這麼做有個問題,那就是這樣的「AI」可能會有很多的「bug」,例如,自己可以連成活五,但對手有活三或死四,這個程式不會獲勝,而是去擋對方。不同的遊戲變化千變萬化,如果只判斷當前盤面,可能會產生無數種的例外情況。
而且AI的棋力會受到開發者棋力很大的影響,你寫的程式棋力最強就是跟你棋力相當而已,規則都是你寫的,你想不到的AI也下不出來,當然你也可以尋求棋力更強的玩家來幫助你寫規則,只是這樣終究有個上限。

暴力窮舉

既然寫規則有其極限,那我們乾脆暴力窮舉吧,不考慮效能的前提下,把所有可能的下法都試一遍總能找到最佳解的。
但現實是殘酷的,我們不可能不考慮效能,如果要窮舉完所有可能的下法需要100年的話,那我們按下執行後就可以開始寫遺囑了,只能拜託自己的孫子將運算結果還有獵人的完結篇一起燒給你,所以在我們使用暴力窮舉之前也得先做一些評估才行。

對局樹 (Game Tree)

對局樹是一種用來表示遊戲中所有可能行動和結果的樹狀結構。
這邊以井字遊戲(Tic-Tac-Toe)為例:

  • 根節點 (root node):代表初始的棋盤狀態,可以是空白棋盤或是下到一半的棋盤。
  • 節點 (node):每個節點代表一個特定的棋盤狀態。
  • 邊 (edge):從一個節點到下一個節點的邊代表玩家的一次行動(在棋盤上下一個子)。
  • 層級 (level/depth):樹的層級表示遊戲的進展,奇數層通常是玩家 X 的回合,偶數層是玩家 O 的回合。
  • 葉節點 (leaf node):代表遊戲結束的狀態,可能是 X 勝、O 勝或平局。

我們只要生成一顆對局樹,就可以透過遍歷整個對局樹,找到最佳的下法。
下面的示意圖為從盤面已經有6手棋開始展開。

100大路徑圖去背

對局複雜度 (Game Complexity)

跟我們在學習演算法時分析的時間複雜度與空間複雜度類似,當我們分析遊戲的複雜度時,就叫做對局複雜度。
對局複雜度通常包含兩個主要部分:狀態空間複雜度對局樹複雜度,用這兩個指標來衡量遊戲的策略空間和決策過程的複雜性。

狀態空間複雜度 (State-space Complexity)

狀態空間複雜度是指遊戲中所有可能的棋盤狀態的總數,下面三張圖都是其中一種棋盤狀態,或是我更習慣稱為盤面。

重複路徑去背

一樣以井字遊戲為例:

  • 理論最大狀態數
    棋盤有 9 個格子,每個格子可能是空白、X 或 O,因此總共有 種可能的棋盤狀態,通常都會以此方式快速評估一個遊戲的狀態複雜度。

  • 實際合法狀態數
    考慮到以下因素,實際的狀態數會更少。

    • 玩家次序:X 和 O 的數量差不能超過 1。
    • 勝負條件:一旦有玩家獲勝,遊戲即結束,後續的行動不再合法。
    • 對稱性:旋轉和鏡像對稱的棋盤狀態被重複計算,下圖三種情況可以視為同個狀態。

    最終真正有意義的井字遊戲合法狀態數約為 765 種。

對局樹複雜度 (Game-tree Complexity)

對局樹複雜度是指遊戲中所有可能的對局(從開始到結束的完整行動序列)的總數。

以井字遊戲為例:
井字遊戲的棋盤一開始是空的,玩家 X 可以選擇任何一個地方,產生 9 種可能的局面。
第二步棋玩家 O 接著在剩下的 8 個空格中選擇一個位置下,所以共有 種可能的局面。
第三步棋玩家 X 接著在剩下的 7 個空格中選擇一個位置下子,有 7 種選擇。
所以共有 種可能的局面。
依此類推整個井字遊戲能產生的局面就是

對局樹通常都比狀態空間大得多,因為要產生同一個狀態可以有很多種方式,比如手順不同但結果卻相同。
比如下圖的盤面,X先下在A1再下B2跟先下B2再下A1會得到相同的盤面。

重複路徑去背

雖然狀態是相同的,但在遊戲樹展開的過程是完全不同的兩條路徑,如下圖。

路徑圖2去背

如果將不合法、旋轉與鏡像等情況都刪除掉的話,那最終只有26830種對局順序
當落子更多時就有更多機會造成相同的盤面,所以其實對局樹會有很多重複的盤面出現,造成效能的浪費,未來會介紹到Transposition Table就能夠來處理這個問題。

常見遊戲的複雜度

遊戲 狀態空間複雜度 對局樹複雜度
井字遊戲
Connect 4
Othello (黑白棋)
象棋
西洋棋
將棋
五子棋
圍棋
六子棋

狀態空間複雜度影響了需要存儲和處理的資料量,較低的狀態空間複雜度意味著遊戲可以被完全求解。
對局樹複雜度反映了完全遍歷所有可能對局所需的計算量,較高的對局樹複雜度意味著需要更深入的策略思考。
根據電腦對局導論中寫到,以2014年的電腦硬體,可以用窮舉法破解狀態空間在 ~ 之間的雙人對局,所以可以看到基本上是大多數的遊戲都沒有辦法直接暴力破解,就算是2024年的今天估計也是進步的有限,所以看到一個新的遊戲時,先別急著暴力窮舉,先評估看看這個遊戲的複雜度再來決定要使用什麼方法。

結論

寫一堆規則的AI棋力受限於寫規則的人棋力,暴力窮舉雖然可以找到最佳解,但複雜度太高的遊戲可能有生之年都窮舉不完。

Reference


上一篇
Day3 自動下棋機器人
下一篇
Day5 Minimax Algorithm
系列文
猴子也能懂的電腦對局 : 30天打造自己的對局AI30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言