今天,我們來教AI下西洋棋

2020-12-10 機器之心Pro

編輯：陳萍

西洋棋是一種在棋盤上玩的雙人戰略棋盤遊戲，棋盤格式為 64 格，排列在 8×8 網格中。有人無聊的時候會找電腦下西洋棋，但也有人無聊了會教電腦下棋。

西洋棋可以說是最棒的棋盤遊戲之一，它是戰略戰術和純技術的完美融合。每位玩家開局時各有 16 枚棋子：一王、一後、兩車、兩馬、兩象和八兵，各具不同功能與走法。真人對弈可以憑藉玩家的經驗，步步為營。那麼，對於一個機器——計算機，你該如何教會它下棋？近日，有人在 medium 上發表了一篇文章，詳細解釋了如何教計算機玩西洋棋。

本文將從 5 個方面進行介紹：

Board 表示；Board 評估；移動選擇；測試 AI；接口測試。在開始之前，你只需要提前安裝 Python3。

Board 表示

首先，你需要對棋子背後的邏輯進行編碼，即為每個棋子分配每一次可能的合法移動。

python-chess 庫為我們提供了棋子的移動生成和驗證，簡化了工作，安裝方式如下：

!pip install python-chess

python-chess 庫安裝好後，導入 chess 模塊並進行初始化：

importchessboard = chess.Board()board

在 notebook 中的輸出如下所示：

board 對象是一個完整的 board 表示，該對象為我們提供了一些重要的函數，例如，board.is_checkmate() 函數檢查是否存在將殺（checkmate），board.push() 函數附加一個移動，board.pop() 函數撤銷最後一次移動等。閱讀完整的文檔請參閱：https://python-chess.readthedocs.io/en/latest/

Board 評估

為了對 board 進行初步評估，必須考慮一位大師在各自比賽中的想法。

我們應該想到的一些要點是：

避免用一個小棋子換三個兵；象總是成對出現；避免用兩個小棋子換一輛車和一個兵。將上述要點以方程形式進行表達：

象 > 3 個兵 & 馬 > 3 個兵；象 > 馬；象 + 馬 > 車 + 兵。通過化簡上述方程，可以得到：象 > 馬 > 3 個兵。同樣，第三個方程可以改寫成：象 + 馬 = 車 + 1.5 個兵，因為兩個小棋子相當於一個車和兩個兵。

使用 piece square table 來評估棋子，在 8x8 的矩陣中設置值，例如在西洋棋中，在有利的位置設置較高的值，在不利的位置設置較低的值。

例如，白色國王越過中線的概率將小於 20%，因此我們將在該矩陣中將數值設置為負值。

再舉一個例子，假設皇后希望自己被放在中間位置，因為這樣可以控制更多的位置，因此我們將在中心設置更高的值，其他棋子也一樣，因為西洋棋都是為了保衛國王和控制中心。

理論就講這些，現在我們來初始化 piece square table：

pawntable=[0,0,0,0,0,0,0,0,5,10,10,-20,-20,10,10,5,5,-5,-10,0,0,-10,-5,5,0,0,0,20,20,0,0,0,5,5,10,25,25,10,5,5,10,10,20,30,30,20,10,10,50,50,50,50,50,50,50,50,0,0,0,0,0,0,0,0]knightstable=[-50,-40,-30,-30,-30,-30,-40,-50,-40,-20,0,5,5,0,-20,-40,-30,5,10,15,15,10,5,-30,-30,0,15,20,20,15,0,-30,-30,5,15,20,20,15,5,-30,-30,0,10,15,15,10,0,-30,-40,-20,0,0,0,0,-20,-40,-50,-40,-30,-30,-30,-30,-40,-50]bishopstable=[-20,-10,-10,-10,-10,-10,-10,-20,-10,5,0,0,0,0,5,-10,-10,10,10,10,10,10,10,-10,-10,0,10,10,10,10,0,-10,-10,5,5,10,10,5,5,-10,-10,0,5,10,10,5,0,-10,-10,0,0,0,0,0,0,-10,-20,-10,-10,-10,-10,-10,-10,-20]rookstable=[0,0,0,5,5,0,0,0,-5,0,0,0,0,0,0,-5,-5,0,0,0,0,0,0,-5,-5,0,0,0,0,0,0,-5,-5,0,0,0,0,0,0,-5,-5,0,0,0,0,0,0,-5,5,10,10,10,10,10,10,5,0,0,0,0,0,0,0,0]queenstable=[-20,-10,-10,-5,-5,-10,-10,-20,-10,0,0,0,0,0,0,-10,-10,5,5,5,5,5,0,-10,0,0,5,5,5,5,0,-5,-5,0,5,5,5,5,0,-5,-10,0,5,5,5,5,0,-10,-10,0,0,0,0,0,0,-10,-20,-10,-10,-5,-5,-10,-10,-20]kingstable=[20,30,10,0,0,10,30,20,20,20,0,0,0,0,20,20,-10,-20,-20,-20,-20,-20,-20,-10,-20,-30,-30,-40,-40,-30,-30,-20,-30,-40,-40,-50,-50,-40,-40,-30,-30,-40,-40,-50,-50,-40,-40,-30,-30,-40,-40,-50,-50,-40,-40,-30,-30,-40,-40,-50,-50,-40,-40,-30]

通過以下四種方法得到評估函數：

第一步檢查遊戲是否還在繼續。

這個階段的背後編碼邏輯是：如果它在 checkmate 時返回 true，程序將會檢查輪到哪方移動。如果當前輪到白方移動，返回值為 - 9999，即上次一定是黑方移動，黑色獲勝；否則返回值為 + 9999，表示白色獲勝。對於僵局或比賽材料不足，返回值為 0 以表示平局。

代碼實現方式：

if board.is_checkmate(): if board.turn: return -9999else: return9999if board.is_stalemate(): return0if board.is_insufficient_material(): return0

第二步，計算總的棋子數，並把棋子總數傳遞給 material 函數。

wp = len(board.pieces(chess.PAWN, chess.WHITE))bp = len(board.pieces(chess.PAWN, chess.BLACK))wn = len(board.pieces(chess.KNIGHT, chess.WHITE))bn = len(board.pieces(chess.KNIGHT, chess.BLACK))wb = len(board.pieces(chess.BISHOP, chess.WHITE))bb = len(board.pieces(chess.BISHOP, chess.BLACK))wr = len(board.pieces(chess.ROOK, chess.WHITE))br = len(board.pieces(chess.ROOK, chess.BLACK))wq = len(board.pieces(chess.QUEEN, chess.WHITE))bq = len(board.pieces(chess.QUEEN, chess.BLACK))

第三步，計算得分。material 函數得分的計算方法是：用各種棋子的權重乘以該棋子黑白兩方個數之差，然後求這些結果之和。而每種棋子的得分計算方法是：該棋子在該遊戲實例中所處位置的 piece-square 值的總和。

material = 100 * (wp - bp) + 320 * (wn - bn) + 330 * (wb - bb) + 500 * (wr - br) + 900 * (wq - bq)pawnsq = sum([pawntable[i] for i in board.pieces(chess.PAWN, chess.WHITE)])pawnsq = pawnsq + sum([-pawntable[chess.square_mirror(i)]fori in board.pieces(chess.PAWN, chess.BLACK)])knightsq = sum([knightstable[i] for i in board.pieces(chess.KNIGHT, chess.WHITE)])knightsq = knightsq + sum([-knightstable[chess.square_mirror(i)]fori in board.pieces(chess.KNIGHT, chess.BLACK)])bishopsq = sum([bishopstable[i] for i in board.pieces(chess.BISHOP, chess.WHITE)])bishopsq = bishopsq + sum([-bishopstable[chess.square_mirror(i)]fori in board.pieces(chess.BISHOP, chess.BLACK)])rooksq = sum([rookstable[i] for i in board.pieces(chess.ROOK, chess.WHITE)])rooksq = rooksq + sum([-rookstable[chess.square_mirror(i)]fori in board.pieces(chess.ROOK, chess.BLACK)])queensq = sum([queenstable[i] for i in board.pieces(chess.QUEEN, chess.WHITE)])queensq = queensq + sum([-queenstable[chess.square_mirror(i)]fori in board.pieces(chess.QUEEN, chess.BLACK)])kingsq = sum([kingstable[i] for i in board.pieces(chess.KING, chess.WHITE)])kingsq = kingsq + sum([-kingstable[chess.square_mirror(i)]fori in board.pieces(chess.KING, chess.BLACK)])

第四步，計算評價函數，此時將會返回白棋的 material 得分和各棋子單獨得分之和。

eval = material + pawnsq + knightsq + bishopsq + rooksq + queensq + kingsqif board.turn: returnevalelse: return -eval

評價函數流程圖

移動選擇

算法的最後一步是用 Minimax 算法中的 Negamax 實現進行移動選擇，Minimax 算法是雙人遊戲（如跳棋等）中的常用算法。之後使用 Alpha-Beta 剪枝進行優化，這樣可以減少執行的時間。

現在讓我們深入研究一下 minimax 算法。該算法被廣泛應用在棋類遊戲中，用來找出失敗的最大可能性中的最小值。該算法廣泛應用於人工智慧、決策論、博弈論、統計和哲學，力圖在最壞的情況下將損失降到最低。簡單來說，在遊戲的每一步，假設玩家 A 試圖最大化獲勝機率，而在下一步中，玩家 B 試圖最小化玩家 A 獲勝的機率。

為了更好地理解 minimax 算法，請看下圖：

維基百科中 minimax 樹舉例

為了得到更好的結果，使用 minimax 變體 negamax，因為我們只需要一個最大化兩位玩家效用的函數。不同點在於，一個玩家的損失等於另一個玩家的收穫，反之亦然。

就遊戲而言，給第一個玩家的位置值和給第二個玩家的位置值符號是相反的。

negamax 示例

首先，我們將 alpha 設為負無窮大，beta 設為正無窮大，這樣兩位玩家都能以儘可能差的分數開始比賽，代碼如下：

except:bestMove = chess.Move.null()bestValue = -99999alpha = -100000beta = 100000formove in board.legal_moves:board.push(move)boardValue = -alphabeta(-beta, -alpha, depth - 1)ifboardValue > bestValue:bestValue = boardValuebestMove = moveif(boardValue > alpha):alpha = boardValueboard.pop()returnbestMove

下面讓我們以流程圖的方式來解釋：

search 函數的流程圖

下一步是進行 alpha-beta 的剪枝來優化執行速度。

來自維基百科的 alpha-beta 剪枝說明

代碼如下：

def alphabeta(alpha, beta, depthleft): bestscore = -9999if (depthleft == 0): return quiesce(alpha, beta) for move in board.legal_moves: board.push(move) score = -alphabeta(-beta, -alpha, depthleft - 1) board.pop() if (score >= beta): returnscore if (score > bestscore): bestscore = score if (score > alpha): alpha = score return bestscore

現在，讓我們用下面給出的流程圖來調整 alphabeta 函數：

現在是靜態搜索，這種搜索旨在僅評估靜態位置，即不存在致勝戰術移動的位置。該搜索需要避免由搜索算法的深度限制所引起的水平線效應（horizon effect）。

代碼如下：

defquiesce(alpha, beta):stand_pat = evaluate_board()if(stand_pat >= beta):returnbetaif(alpha < stand_pat):alpha = stand_patformove in board.legal_moves:ifboard.is_capture(move):board.push(move)score = -quiesce(-beta, -alpha)board.pop()if(score >= beta):returnbetaif(score > alpha):alpha = scorereturnalpha

簡單總結一下 quiesce 函數：

quiesce 函數流程圖。

測試 AI

開始測試前，需要導入一些庫：

測試有 3 項：

AI 對弈人類；AI 對弈 AI；AI 對弈 Stockfish。1. AI 對弈人類：

AI 選擇從 g1 到 f3，這是一個很明智的選擇。

2. AI 對弈 AI：

3. AI 對弈 Stockfish：

可以得出：AI 還不夠智能，不足以打敗 stockfish 12，但仍然堅持走了 20 步。

接口測試

上述測試方式看起來代碼很多，你也可以寫一個接口測試 AI。

然後執行：

最終輸出

相關焦點

  • 今天我們學習西洋棋的坐標和記錄方法!
    西洋棋中有很多數學的原理。在西洋棋有2500年的歷史中，湧出來無數的數學知識，這些數學知識就想好像宙中的點點繁星。閃耀在西洋棋乃至人類的歷史的長河中。今天我們就學習西洋棋中的坐標和記錄方法。西洋棋棋盤豎排有1-8，八數字，橫排有a-h，八個字母，有64個小方格，每個格子的組成是字母和數字的組合，比如a1格是字母a和1的組合，稱為a1格。我們看一下棋盤中的斜線：棋盤上可以劃出從2格到8格長短不一的26條斜線。
  • 小學生下西洋棋
    就在那一天，我把我的一個好朋友約到家裡，我要與他一決高下，我們在「戰場」殺得天昏地暗，伯仲難分。這就是那西洋棋。 我記得我以前到他家中玩，那時的我對西洋棋一竅不通，甚至連規則都不大懂，更不知道如何下西洋棋了，我是在他的帶領下，學會西洋棋，並慢慢成長的。 隨後，我便與他下了一局又一局，一共下了十局，才用了十分鐘，每次下完全是黑色的主場，一敗塗地，所以，我渴望有一天能「一報雪恥」。
  • 今天我們來學習西洋棋中象的走法!
    象的走法和吃子象（英文：Bishop）是西洋棋中底線左起第三和第六個棋子。象的走法只可斜走，格數不限，但不可轉向。吃子與走法相同。象的吃子方法西洋棋中的象是斜著吃子的，我們看上面這幅圖，象可以吃掉b4的馬、d2的兵、a1的車。但是想該如何選擇呢？我們看象如果吃掉d2的兵，那麼在c3的兵就會吃掉象，所以我們選擇吃掉b2的馬。如下圖：
  • 聚焦影視大明星下西洋棋
    格利高裡·派克和波莉·伯根（Polly Bergen）下西洋棋英國電視明星休·勞瑞（Hugh Laurie）史蒂芬·弗萊（Stephen Fry）在劍橋弗萊家中下西洋棋。喜劇大師卓別森（Charlie Chaplin）和西洋棋神童雷舍夫斯基（Samuel Reshevsky）下西洋棋
  • 聶衛平下西洋棋的故事
    聶衛平聶衛平還愛用的一句評棋用語是：這兩位棋手一個下的是跳棋，一個下的是西洋棋。實際上聶衛平的西洋棋下得也湊合，那是1974年他輸給陳祖德的前夕，聶衛平從黑龍江赴成都參加全國比賽，他先坐火車到上海，再改乘船去重慶，這樣可以順便遊覽一下三峽，最後的目的地是成都賽場。
  • 快速下好西洋棋的十個步驟
    想必每個人都想獲得一套秘籍來幫助自己快速下好西洋棋吧。那如何才能成為一名厲害的西洋棋棋手呢？我們需要研究戰術嗎？應該在殘局上花費多少時間呢？必須要有線下對弈經驗嗎？對於諸如此類的種種問題，我們將通過這篇文章為你逐一解答，為你提供一套包含十個重要步驟的簡單計劃。讓我們開始吧！提高棋力最重要的步驟之一或許就是解答戰術題目了。
  • 談談對於下西洋棋的那些疑惑
    這可能是因為我們看到確實有很多小孩子在學棋、下棋，之後到了成年就很少看到他們下棋。如果你從事其它運動，例如籃球，你就隨處可見年輕人在公園裡打籃球，或在電視上看NBA。西洋棋也一樣，只不過電視轉播並不多，這讓很多人認為西洋棋僅是一種兒童遊戲，而並沒有更廣泛的成人群體。
  • 如何下一盤西洋棋
    這一篇文章裡，我們主要講一下西洋棋的規則（只講規則）。在西洋棋裡面，每方有六種兵種。它們分別是王（King），後（Queen），車（Rook），象（Bishop），馬（Knight）和兵（Pawn）。
  • 數字西洋棋平臺如何通過Twitch錦標賽使西洋棋走下棋盤
    該平臺過去曾舉辦過許多類似於電子競技的賽事，讓精英西洋棋專業人士在遊戲中處於頂尖地位，但PogChamps有點不同——所有參與者都不擅長西洋棋。「長期以來，我們一直認為西洋棋會成為一種優秀的電競遊戲，而且在某個時候它會流行起來。我們在各地都取得了成功，但PogChamps遙遙領先，是我們迄今為止舉辦效果最好的比賽。」
  • 數字西洋棋平臺如何通過Twitch錦標賽,使西洋棋走下「棋盤」
    前幾天，數字西洋棋平臺Chess.com宣布了其價值5萬美元的Twitch streamer錦標賽PogChamps第二賽季結束。該平臺過去曾舉辦過許多類似於電子競技的賽事，讓精英西洋棋專業人士在遊戲中處於頂尖地位，但PogChamps有點不同——所有參與者都不擅長西洋棋。
  • 「歷史上的今天」西洋棋界的人機大戰，震驚世界
    【歷史上的今天】西洋棋界的人機大戰，震驚世界！welcome1997年5月11日西洋棋世界冠軍與電腦「深藍」較量1997年5月11日，一場別開生面的西洋棋比賽落下帷幕1988年，它的上一代「深思」是第一個贏過西洋棋特級大師的電腦；1997年，它又成為第一個在多局賽中戰勝西洋棋世界冠軍的電腦。卡斯帕羅夫曾經說過，電腦要想戰勝世界冠軍，得等到2010年，「深藍」把這個日子提前了13年。我們也將不得不認真地思考下人與電腦的關係了。打開看點快報，查看高清大圖
  • 名人國象:羅伯斯比爾下西洋棋的故事
    24年來，培養出的國家運動健將、一級運動員及各級別「西洋棋大師」稱號的學員225人次居中國北方地區前列，是名副其實的「西洋棋高水平」後備人才培訓基地。2018年全年共榮獲27人次「西洋棋大師」稱號學員，2019年1月1日-8月23日期間有14人榮獲「西洋棋大師」稱號。所有教練均有「西洋棋大師稱號」和中國西洋棋協會認證的教練員證，專業教練團隊。
  • 成人、兒童、作弊與在線西洋棋(下)
    然而，阿什頓相信，大多數學校西洋棋選手都明白什麼是公平的，什麼是不公平的。阿什頓建議父母問問孩子發生了什麼事。        記住，許多孩子在下棋時作弊。父母可能會覺得他們和他們的孩子不應該承認犯錯，好像西洋棋作弊是一個法律錯誤。然而，在西洋棋中，（如果作弊了）最好是說聲抱歉，然後繼續前進。
  • 下西洋棋的三個技巧
    下西洋棋的三個技巧 西洋棋歷史悠久，是世界上最古老的智力遊戲之一，更是是全世界幾千年的文化瑰寶
  • 下西洋棋容易犯的11種失誤
    有些人喜歡西洋棋，是因為它具有很強的競爭性。還有些人喜歡西洋棋，是因為多數情況下是技巧而非運氣決定最終的結果。但是，想下好西洋棋，要注意避免11種失誤。 失誤之十一：靠下西洋棋掙錢 有些人不願花時間研究研究西洋棋，
  • 西洋棋與教育
    1900年，許多報紙發表了一則轟動一時的消息，西洋棋世界冠軍拉斯克，在數學系只念了四個學期，就在厄蘭根大學出色地通過了數學和哲學的博士論文答辯，獲得雙博士學位。卓越數學家格哈爾基在其論文《數學家的自白》中寫道：「拆解西洋棋的棋題正像解數學題一樣，而下西洋棋就仿佛是在進行數學運算。」
  • 注意以下幾點,避免成為一個「僅僅會下西洋棋」的人
    小朋友們可能不知道，全球約有7億人會下西洋棋，接近世界總人口的10分之一！可見西洋棋是多麼受人歡迎的一項智力運動！不過，絕大多數人僅僅是會下西洋棋而已，等級分可能都不到1000分，哪怕對於我們學過幾年棋的小朋友來說，他們也都只不過是初學者。
  • 西洋棋拳擊賽
    這裡是小管賽事介紹處~ 今天我想給各位介紹的運動賽事是一個國外流行起來的運動項目——西洋棋拳擊賽。    顧名思義，西洋棋拳擊賽，就是西洋棋和拳擊的結合賽事。  前4分鐘還很紳士地坐在棋盤邊，下著西洋棋；後3分鐘卻赤裸上身，用盡全力打起了拳擊。這不僅是項正兒八經的運動，而且已經有相應的世界錦標賽了。
  • 美國總統44位總統下西洋棋者25位
    華盛頓曾告訴夫人，他喜歡的消遣方式是閱讀、寫作和下西洋棋。據說，華盛頓贏得獨立戰爭中的一場重要戰役，西洋棋幫了他大忙。當時他進攻英國人的作戰計劃被一名間諜竊取了，當間諜把這份重要情報送到對手英國上校拉爾手中時，拉爾正同手下軍官忙著下西洋棋，他隨手把這份重要情報塞進了口袋，直到他在戰役中戰死，這份作戰計劃還原封不動地留在他的口袋裡，拉爾上校糊裡糊塗地當了西洋棋的怨死鬼。
  • 為什麼我們要加強學習西洋棋經典歷史對局?
    由此，我們從以下幾點來闡述學習經典對局的重要性：01更好地理解西洋棋學習經典棋局將幫助你得到一種整體的改善。它們就像一門清晰的西洋棋延伸課程。你可以學習很多西洋棋的策略，還可以看到漂亮的進攻和出色的殘局技巧。重要的是，你要理解他們的著法背後的想法，並在這種局面下找到合適的計劃。經典棋局中的精彩部分通常非常清晰，並且確實接近完美。