hackMD原稿
再麻煩將背景調為淺色,深色背景會看不太到圖。
看完了古人的操作,換我們來打造一個自動下棋AI了。
那除了把人塞進電腦裡之外,要怎麼讓電腦下棋呢?
以現今的科技要讓電腦下棋已經是稀鬆平常的事了,但是要怎麼讓電腦把棋下得好,甚至於遠超人類就是值得研究的問題了,不過這邊我們還是先從讓電腦可以下棋開始吧。
直覺能想到的應該就是先學習人類的思維,我們怎麼下棋就讓電腦怎麼下棋。
以五子棋為例,我們要阻止對方連成五個,就得在對方連成三個時去阻擋對方。
那可能就會有像是以下的策略:
if 對方有活三 or 死四:
擋住對方
else:
幫自己造活三 or 死四
接下來根據遊戲的特性跟你的經驗可以寫出更多的規則,然後你的「AI」可能就會長得像下圖這樣。
會有滿滿的if
else
但不管怎樣第一個會下棋的「AI」也算是完成了,又沒人說AI一定得用到什麼高深的演算法呢。
只是這麼做有個問題,那就是這樣的「AI」可能會有很多的「bug」,例如,自己可以連成活五,但對手有活三或死四,這個程式不會獲勝,而是去擋對方。不同的遊戲變化千變萬化,如果只判斷當前盤面,可能會產生無數種的例外情況。
而且AI的棋力會受到開發者棋力很大的影響,你寫的程式棋力最強就是跟你棋力相當而已,規則都是你寫的,你想不到的AI也下不出來,當然你也可以尋求棋力更強的玩家來幫助你寫規則,只是這樣終究有個上限。
既然寫規則有其極限,那我們乾脆暴力窮舉吧,不考慮效能的前提下,把所有可能的下法都試一遍總能找到最佳解的。
但現實是殘酷的,我們不可能不考慮效能,如果要窮舉完所有可能的下法需要100年的話,那我們按下執行後就可以開始寫遺囑了,只能拜託自己的孫子將運算結果還有獵人的完結篇一起燒給你,所以在我們使用暴力窮舉之前也得先做一些評估才行。
對局樹是一種用來表示遊戲中所有可能行動和結果的樹狀結構。
這邊以井字遊戲(Tic-Tac-Toe)為例:
我們只要生成一顆對局樹,就可以透過遍歷整個對局樹,找到最佳的下法。
下面的示意圖為從盤面已經有6手棋開始展開。
跟我們在學習演算法時分析的時間複雜度與空間複雜度類似,當我們分析遊戲的複雜度時,就叫做對局複雜度。
對局複雜度通常包含兩個主要部分:狀態空間複雜度和對局樹複雜度,用這兩個指標來衡量遊戲的策略空間和決策過程的複雜性。
狀態空間複雜度是指遊戲中所有可能的棋盤狀態的總數,下面三張圖都是其中一種棋盤狀態,或是我更習慣稱為盤面。
一樣以井字遊戲為例:
理論最大狀態數:
棋盤有 9 個格子,每個格子可能是空白、X 或 O,因此總共有 種可能的棋盤狀態,通常都會以此方式快速評估一個遊戲的狀態複雜度。
實際合法狀態數:
考慮到以下因素,實際的狀態數會更少。
最終真正有意義的井字遊戲合法狀態數約為 765 種。
對局樹複雜度是指遊戲中所有可能的對局(從開始到結束的完整行動序列)的總數。
以井字遊戲為例:
井字遊戲的棋盤一開始是空的,玩家 X 可以選擇任何一個地方,產生 9 種可能的局面。
第二步棋玩家 O 接著在剩下的 8 個空格中選擇一個位置下,所以共有 種可能的局面。
第三步棋玩家 X 接著在剩下的 7 個空格中選擇一個位置下子,有 7 種選擇。
所以共有 種可能的局面。
依此類推整個井字遊戲能產生的局面就是
對局樹通常都比狀態空間大得多,因為要產生同一個狀態可以有很多種方式,比如手順不同但結果卻相同。
比如下圖的盤面,X先下在A1再下B2跟先下B2再下A1會得到相同的盤面。
雖然狀態是相同的,但在遊戲樹展開的過程是完全不同的兩條路徑,如下圖。
如果將不合法、旋轉與鏡像等情況都刪除掉的話,那最終只有26830種對局順序。
當落子更多時就有更多機會造成相同的盤面,所以其實對局樹會有很多重複的盤面出現,造成效能的浪費,未來會介紹到Transposition Table就能夠來處理這個問題。
遊戲 | 狀態空間複雜度 | 對局樹複雜度 |
---|---|---|
井字遊戲 | 約 | 約 |
Connect 4 | 約 | 約 |
Othello (黑白棋) | 約 | 約 |
象棋 | 約 | 約 |
西洋棋 | 約 | 約 |
將棋 | 約 | 約 |
五子棋 | 約 | 約 |
圍棋 | 約 | 約 |
六子棋 | 約 | 約 |
狀態空間複雜度影響了需要存儲和處理的資料量,較低的狀態空間複雜度意味著遊戲可以被完全求解。
對局樹複雜度反映了完全遍歷所有可能對局所需的計算量,較高的對局樹複雜度意味著需要更深入的策略思考。
根據電腦對局導論中寫到,以2014年的電腦硬體,可以用窮舉法破解狀態空間在 ~ 之間的雙人對局,所以可以看到基本上是大多數的遊戲都沒有辦法直接暴力破解,就算是2024年的今天估計也是進步的有限,所以看到一個新的遊戲時,先別急著暴力窮舉,先評估看看這個遊戲的複雜度再來決定要使用什麼方法。
寫一堆規則的AI棋力受限於寫規則的人棋力,暴力窮舉雖然可以找到最佳解,但複雜度太高的遊戲可能有生之年都窮舉不完。