今天，人工智能的應用已經滲入我們生活的方方面面，這是一個人工智能的時代。

而人工智能的核心是機器學習，或許你不知道的是，它誕生于一種跳棋游戲。

本文摘錄自中信出版集團出版的算法科普書《算法簡史：從美索不達米亞到人工智能時代》。

學習能力是人類智能的核心。相比之下，早期的計算機只能存儲和提取數據。

學習是完全不同的東西，學習是一種基于經驗改進行為的能力。孩子通過模仿大人和反復試錯來學習走路。一個嬰兒蹣跚學步，剛開始時步態不穩，但隨著協調和運動能力逐漸提升，最終能夠熟練地走路。

1956年2月24日，第一個用來展示學習能力的計算機程序在公共電視節目上公布。

這個程序是由IBM的亞瑟·塞繆爾（Arthur Samuel）編寫的。這是一個玩國際跳棋的程序，電視演示給人留下了深刻的印象，IBM的股價在第二天上漲了15個百分點。

塞繆爾1901年出生在美國堪薩斯州。在獲得了加州理工學院的電子工程碩士學位后，他加入了貝爾實驗室。第二次世界大戰后，他加入伊利諾伊大學擔任教授職位。盡管這所學校沒有計算機，塞繆爾還是開始研究玩國際跳棋的算法。3年后，他加入了IBM，終于弄到了一臺真正的計算機，可以開展更加深入的研究。

機器學習的發明者亞瑟·塞繆爾，1956年

1959年，塞繆爾終于發表了一篇論文，描述他的新國際跳棋程序。這篇論文的低調標題——《利用跳棋游戲進行機器學習的一些研究》——掩蓋了其思想的重要性。

塞繆爾的程序使用了一種巧妙的評分算法。算法對各種會用到的特征（feature）進行打分。特征是指任何表明一個棋局的長處或弱點的東西。

兩個對手棋盤上棋子數量的差異就是一種特征。

棋子的相對位置也是一種特征。戰略層面的元素也被認為是特征，比如移動的自由度或對棋盤中心區的掌控程度。

每個特征都有評分。給定特征的得分要乘以權重（weight）。將各個評分結果值加在一起，就得到了當下棋局的總得分。

權重決定了每個特征的相對重要性。權重可以是正的也可以是負的。正權重意味著該特征對計算機玩家有利。負權重意味著該特征降低了計算機獲勝的可能性。

權重越大，說明某一特征對總分的影響力越大。然而，低權重的多個特征可能結合在一起影響總體得分，從而影響最終決策。

綜上所述，塞繆爾的棋局評價方法的工作原理如下：

以一個棋局作為輸入。

將總分設置為零。

對每個特征重復以下步驟：

測量棋盤上的某個特征。

計算該特征的得分。

乘以特征的權重。

把計算結果加到總分中。

當所有特征都評分完成后，停止重復。

輸出總分。

這種評分機制對塞繆爾的算法至關重要。分數越能準確地反映出計算機獲勝的概率，程序做出的決策就越好。選擇用于分析的最優特征組合很重要。

除此之外，確定最佳權重分配也是必不可少的。然而，為權重找到最佳值是一個很棘手的任務。

塞繆爾設計了一個機器學習（machine learning）算法來確定最優權重。最開始，算法猜測權重是多少。然后，計算機與自己玩很多局游戲。

程序的一個副本下白棋，另一個下黑棋。隨著游戲的進行，算法會調整權重，以便計算出的分數能更準確地預測游戲的結局。

如果程序獲勝，對決策做出積極貢獻的權重會得到一點點提升。類似地，任何起到負面作用的權重都將降低。這強化（reinforce）了獲勝行為。

實際上，這是在鼓勵程序在未來以更貼近這樣的風格下棋。如果輸了游戲，就會發生相反的情況。這會阻止程序在接下來的游戲中以相同的方式下棋。在很多次游戲后，學習算法得以對程序的玩法做出精細的調整。

與人工選擇權重相比，塞繆爾的算法具有兩方面的優勢。

第一，計算機永遠不會忘記——每一步棋都會影響到權重。

第二，計算機可以與自己進行多次游戲，遠遠超過人類能玩的次數。因此，在學習過程當中可以獲得更多的信息。

塞繆爾對機器學習的開發是顛覆性的。以前，想改變程序的行為需要手動修改指令列表。相比之下，塞繆爾的程序所做的決策是由權重控制的，權重是簡單的數值。

因此，程序的行為可以通過改變權重來調整。程序代碼不需要修改。更改程序代碼很困難，但更改幾個權重數值是很容易的，該精妙的概念使學習過程的自動化成為可能。

此外，塞繆爾還加入了一個極小極大步驟（minimax）來選擇走法。該算法執行一個前瞻預測來生成一個包含所有可能的未來走法的樹。

在前瞻預測的結尾，計算出所有棋局的得分。我們假設雙方都能走出好棋。為了實現這一點，算法會回溯包含所有可能走法的樹。

程序從前瞻預測樹的葉子處開始回溯。輪到自己走棋時，回溯算法會選擇能夠獲得最高得分的走法。輪到對手走棋時，程序會選擇得分最低的一著。

在每個決策點上，與所選擇走法相關聯的分數會返回到上一節點。當這個回溯過程抵達樹的根部時，程序會使走法與最高回溯分數相關聯。

極小極大步驟的運行如下：

以可能走法的樹作為輸入。

從倒數第二個層級開始。

對每一層級重復以下步驟：

對該層級的每個節點重復如下操作：

如果輪到計算機走棋，

那么就選擇得分最高的走法，

否則選擇得分最低的走法。

將極小極大得分值復制到當前節點。

檢查完這一層級中的所有節點后，停止重復。

當到達樹的根部時停止重復。

輸出具有最大回溯分數的走法。

采用極小極大算法獲得回溯評分的前瞻預測樹

想象一個簡單的兩層級前瞻預測樹。這個樹包含計算機的潛在后續走法和其對手的可能應對走法。檢查樹的葉子（第2步棋層級）處的得分，以找到每個子樹上的最小值。

這反映了對手從自己的角度選擇的最佳走法。那些最低的分數被復制到上面一層的節點（第1步棋層級）。于是分數1、3、7、5、6被放置在第1步棋層級的各個節點上。

下一步，算法要選擇得分最高的走法。這意味著計算機站在自己的立場上選擇最好的走法。因此，最大值7被復制回樹的根部。如果對手是一名優秀的棋手，那么選擇走出7分的棋局是最好的選擇。這步走法迫使對手在得分為8、7和10的位置之間進行選擇。對手能做的最好的選擇就是接受7分的這個位置。

1962年，塞繆爾的國際跳棋程序與盲人跳棋大師羅伯特·尼利（Robert Nealey）進行了一場較量。

人們為計算機的獲勝而歡呼，但尼利甚至都不是一名州冠軍。30多年后的1994年，計算機程序才終于打敗國際跳棋世界冠軍。

-End-

2025.5.16

編輯：孫小悠 | 審核：醒醒