首頁 > 電腦如何下象棋
:::
電腦如何下象棋
機器與人對弈,近年來最著名的莫過於Alpha Go,但你知道除了圍棋,機器下象棋的能力,也已經超越人類的象棋特級大師了嗎?象棋的走步變化,單單一盤就有10的150次方種,機器如何學會下象棋、打敗人腦?
 
 
 

象棋盤面的平均合法走步大約有38個,而象棋每一局的平均手數是95手。因此可知一盤象棋共約有38的95次方種變化,相當於10的150次方種變化。相較於西洋棋,大約有10的120次方種變化,顯然象棋較為複雜。
▲象棋盤面的平均合法走步大約有38個,而象棋每一局的平均手數是95手。因此可知一盤象棋共約有38的95次方種變化,相當於10的150次方種變化。相較於西洋棋,大約有10的120次方種變化,顯然象棋較為複雜。

 

簡單的對局樹

電腦下棋,基本上像西洋棋、象棋或圍棋等是屬於「有限、雙人、完全資訊」的對局遊戲。早在1944 年范紐曼(Von Neumann)和摩根斯坦(Morgenstern)就提出電腦對局的基本原理:面對一個盤面狀態時,電腦可以模擬人類思考的方式,從當前的形勢推演各種可能的變化,從而形成一棵對局樹 (game tree)。
 

假設從盤面狀態A開始,可以有合法著手走到B、C、D三個盤面狀態,這時電腦可以對這三種盤面狀態各評定其優劣。若形勢對電腦方有利,則給予較高的分數,反之,則給予負分。

 

有了這些盤面狀態的評估分數之後,電腦就可以選擇對它最有利的著手,走向得分最高的B盤面。但是,如果再深入一層加以考慮,發現走向盤面B時,對方可以有走向E、F、G的三個合法著手;而走向盤面C時,對方可有走向H、I兩個合法著手;而走向盤面D時,對方可有走向J、K兩個合法著手。

 

這時如果電腦再對這些終端盤面狀態評定優劣,給予評估分數後,就要做最審慎的考慮了:假設對方會選擇走向對電腦最為不利的著手。向上一層歸納後,B盤面只得負67分,C盤面則得到負24分,而D盤面可得正33分。經分析歸納後,電腦就會選擇走向得分最高的D盤面。

 

像這種在輪到對方時選擇最審慎的極小值,而在輪到電腦自身時,選擇最有利的極大值的思考方式,就是電腦下棋最基本的演算原理,稱為極小極大步驟演算法。

 

先前所提的是敵對雙方各走一步的變化,假設電腦能夠不斷深入思考,直到分出勝負為止,便可以完全解答棋戲的理論值,也就是先下必勝、必敗或和的結論。

 
展開兩層的對局樹
▲展開兩層的對局樹

 

有限深度的極小極大演算法

對一些比較簡單的棋戲,像圈叉井字遊戲(Tic-Tac-Toe)或三角殺棋(Triangular Nim),雖然可以利用極小極大演算法完全解答,但是對於象棋、西洋棋或圍棋等這些變化較複雜的對局遊戲,如果反覆擴展對局樹,節點數目會呈現幾何級數的增加,最後無法避免地面臨組合爆滿的困境。為了解決這種困境,1950 年資訊界大師克勞德.夏農(Claude E. Shannon)就提出有限深度的極小極大演算法。在時間許可的情況下,思考有限深度的幾手後,就歸納回傳結果。如果思考層數越多,結果會更精確,棋力也就更強。

 

電腦程式的資料結構

有了基本思考的模式後,電腦程式必須選擇適當的資料結構記錄盤面上的各種資訊。象棋共有32個棋子,加上空白與邊界,共需34個不同的數值才能完全分辨。1988年臺灣大學資訊研究所學生曹國明所設計的〈象棋專家〉,就利用0到33來表示棋子,0 表空白,1~16表示紅子,17表示邊界,18~33表示黑子。

 

一般的程式通常利用二維或一維陣列表示棋盤,同時在棋盤的外側圍上邊界,以便檢查跳出棋盤外的走步。〈象棋專家〉的資料結構是利用一維陣列表示棋盤,並在棋盤周圍各加上3層邊界。除了記錄棋盤上的棋子之外,大部分的程式也會有一個棋子位置表,記錄各個棋子所在的位置。

 

有了棋盤資訊和棋子位置表後,程式師便可以根據棋子的走動規則,分別對每一兵種撰寫合法步產生的程式。根據統計的結果,象棋盤面的平均合法走步大約有38個,而象棋每一局的平均手數是95手。因此可知一盤象棋共約有38的95次方種變化,相當於10的150次方種變化。相較於西洋棋,大約有10的120次方種變化,顯然象棋較為複雜。

 

如何評估局勢 

電腦能正確產生合法走步後,便可利用有限深度的極小極大演算法展開對局樹,並在適當的終端節點評估局勢的利弊得失而加以數值化。常見的考慮因素包括棋子的多寡、棋子的靈活度、位置的重要性,以及棋子之間互相威脅與保護的情形。

 

棋子的多寡是評估局勢優劣最簡單的方法,棋子多是優,棋子少則劣。不同的棋子有不同的攻擊和防禦能力,價值自然不同。而將與帥是棋局中最重要的,因此它的價值設定必須遠大於其他各棋子的總和。至於其他棋子的價值,則取決於它們之間相對的重要性。例如:車大約相當於一馬和一包的威力;而一馬大約可換取雙象。基於這些考慮,〈象棋專家〉給於每一兵種基本分數。

 

除了棋子的多寡之外,棋子所占的位置也是評估局勢的重要因素。如果車控肋道,馬占臥槽,飛砲沉底,或兵臨城下,都會對將帥構成相當大的威脅。因此,對應每一兵種,電腦程式都有一個位置評估表,用來引導各個棋子去搶占要津。一般而言,兵種的位置若可使其火力威脅到對方主帥,那就是該棋子最佳的戰鬥位置。

 

馬路疏通,砲貴機動。棋子在盤面上如果不能靈活走動,就無法發揮戰鬥力,因此棋子靈活度也是評估局勢優劣的另一個因素。而除了砲以外,其他棋子可以到達的位置就是它的火力範圍。因此,棋子愈靈活,愈能顯示它的戰鬥優越性。

 

此外,棋子在盤面上是否安全,和它所受到的威脅與保護的棋子、兵種也息息相關。通常電腦程式會在終端節點嘗試互攻兌子,直到某一靜止狀態,然後再引用審局函數評估局勢。而在延伸攻殺時,不能忽略解將的棋步。

 

程式設計師把以上考慮的因素,按照適當的比例加以彙總之後,就可以對終端盤面給予評估。利用極小極大演算法,倒推歸納到樹根起始盤面,電腦就可以下出一步合理的著手了。如果時間許可,電腦可以再深入思考,歸納回傳的結果會更精確,棋力也會更強。以目前機器的速度,電腦在十幾秒內應當可以完全評估六個著手內的所有變化,其棋力接近初段的程度。

 
面對一個盤面狀態時,電腦可以模擬人類思考的方式。(圖片來源:種子發)
▲面對一個盤面狀態時,電腦可以模擬人類思考的方式。(圖片來源:種子發)

 

進階的人工智慧演算法

雖然有限深度的極小極大演算法已經可以讓電腦下出不錯的著手,但是人工智慧的研究人員並不以此為滿足,數十年來仍不斷地推陳出新,開發出更有效率的對局樹搜尋演算法。其中包括了一些重要的技巧:平靜搜尋、深度αβ切捨、主要變化搜尋、逐層加深、殺手經驗法則和同型表等技巧。

 
隨著更進階的切捨演算法,以及半導體速度不斷的成長,電腦的思考更加深入。在十幾年前,約2000年前後,電腦已可深入推算十幾步了,棋力達到人類高手的程度。如今再利用平行演算法讓多台電腦分工合作協同思考,其最強的有效思考深度更可以推進到四十多手,這一棋力已超越人類的象棋特級大師,就連棋王也會自嘆不如了。
推薦文章

TOP