學會圈叉遊戲的火柴盒

<image>

學會圈叉遊戲的火柴盒（Matchbox Educable Noughts and Crosses Engine或Machine Educable Noughts and Crosses Engine，簡稱：MENACE），是人工智慧研究者唐納德·米基與同事羅傑·錢伯斯於1961年設計製造的機械計算機，由304個火柴盒組成。此物可與真人下井字棋，還可根據任意棋局給出下一步落子，並通過強化學習不斷改進策略，屬於最早出現的人工智慧系統。

米基和錢伯斯當時沒有電腦可用，便改用火柴盒搭建這台引擎。每個火柴盒對應井字棋棋盤的一種可能局面。系統初次對弈時，會根據當前局面隨機選擇落子。隨著對局增多，此物通過強化學習循環淘汰導致落敗的策略，並強化能夠取勝的策略。1961年，米基與MENACE舉行對抗賽，試驗了多種開局走法。

MENACE首次與米基對弈後，展現出人工智慧改進策略的能力。米基撰寫的MENACE權重初始化與BOXES算法論文在電腦科學界廣受關注，他因推動機器學習研究獲得表彰，並先後兩次受託在真正的電腦上編寫MENACE模擬程序。

## 起源

<image>

唐納德·米基曾在第二次世界大戰期間參與破譯德國陸軍的湯尼密碼。十五年後，他希望藉助早期卷積神經網絡進一步展示自己的數學和計算能力。由於當時無法取得可供此類用途使用的電腦設備，米基手邊也沒有電腦，他便另闢蹊徑，用火柴盒和珠子搭建出一台能夠實際運行的機械計算機，以此展示人工智慧。

MENACE源於米基與電腦科學業同行的一場打賭，對方認為這種機器不可能造出來。米基起初只把搜集火柴盒並逐一設定其對應局面當作消遣，後來才將MENACE用作演示工具。1963年，米基完成介紹MENACE的論文《遊戲學習機械化實驗》，後來又與 R·A·錢伯斯合著介紹BOXES演算法的論文。此外他還在蘇格蘭愛丁堡霍普公園廣場組建人工智慧研究團隊。

MENACE通過連續對弈井字棋的方式學習。每當它落敗，操作者便取走本局各步所對應的珠子，從而淘汰此類策略。若它獲勝，操作者則向相應火柴盒中添入珠子，提高此類走法再次被選中的機率，以強化取勝策略。這是最早的強化學習循環之一，即演算法反覆運行，不斷剔除失敗策略，直至只剩取勝策略。該模型起初完全隨機出招，隨後逐漸學會對弈。

## 組成

MENACE由304個火柴盒粘合而成，排列方式類似多屜櫃。每個火柴盒都有編號，並與一張圖表對應。圖表繪有不同局面的井字棋棋盤，格內標有不同組合的X、O或留空，涵蓋棋局進展中可能出現的各種排列。剔除僅由旋轉或鏡像形成的重複局面後，圖表共收錄304種排列，因此MENACE也使用304個火柴盒。

每個火柴盒內屜都裝有若干彩色珠子。每種顏色代表在棋盤某一格落子，因此若某個局面已有棋子占據該格，對應火柴盒內便不會放入代表該格的珠子。內屜前端另裝有兩片呈「V」字形的卡紙，「V」字尖端朝向火柴盒正面。

米基及其人工智慧研究團隊根據這套火柴盒裝置，將MENACE所用演算法命名為「BOXES」。BOXES的第一階段分為五個環節，分別規定與棋局有關的算法規則，並為後續操作確立依據。

## 運作

<image>

MENACE執O先行，因為所有火柴盒所表示的都是X方落子後可能出現的局面。對手或操作者先找到與當前棋局相符的火柴盒，若沒有完全相同的圖案，也可選用旋轉或鏡像後相同的局面。例如開局時，應取出代表空棋盤的火柴盒。隨後抽出內屜，輕輕搖晃，使珠子滾動。滾入內屜前端「V」字尖角的珠子，便代表MENACE選定的走法。操作者按珠子顏色確定落子位置，再根據火柴盒圖案與當前棋盤之間的旋轉或鏡像關係作相應變換，將O放入該格。人類玩家隨後落子，操作者再找出代表新局面的火柴盒並選取下一步，如此反覆，直至棋局結束。

棋局結束後，人類玩家根據結果調整珠子。對弈過程中，每逢MENACE落子，所用火柴盒的內屜都會留一條縫插回盒中，並將選中的珠子另行放置，以記錄MENACE在各個局面作出的選擇。米基將這套強化機制稱為「獎勵」與「懲罰」。MENACE若獲勝，便會得到「獎勵」。取出的珠子記錄了整套取勝走法，操作者將這些珠子放回半開的對應內屜，並各添三顆同色珠子。這樣一來，MENACE日後更可能重複此類走法，從而強化取勝策略。MENACE若落敗，取出的珠子則不再放回，以示「懲罰」。此後其選擇此類敗著的機率便會降低，某種顏色的珠子全部取盡後，更無法在相應局面重走該步。若雙方戰平，則在各個火柴盒中添入一顆相應顏色的珠子。

## 實際表現

### 最優策略

<image>

井字棋有一套廣為人知的最優策略。玩家既要阻止對手連成一線，也要設法使自己的棋子連成一線。然而，雙方若都採用最優策略，棋局必然以平局告終。若人類玩家熟悉最優策略，MENACE又能迅速學會，雙方最終便只會戰平。與隨機落子的人類對手交鋒時，電腦的勝率則會迅速提高。

對手採用最優策略時，MENACE戰平的機率會逐漸升至100%。1961年，唐納德·米基與MENACE舉行正式對抗賽，米基採用最優策略，雙方在約二十局後開始連續戰平。米基的對抗賽經歷了以下階段：起初，他始終採用「變式0」，即在中央格開局。第15局時，MENACE已放棄所有不從角格開局的走法。二十餘局後，米基改用「變式1」，固定從右下角開局；第60局恢復變式0；接近第80局時改用「變式2」，從上方中央格開局；第110局改用「變式3」，從右上角開局；第135局改用「變式4」，從右側中央格開局；第190局恢復變式1，第210局又恢復變式0。

「2號」火柴盒內珠子數量的變化如下：

變式｜局數｜「2號」火柴盒內珠子數量變化

變式0｜0｜0

變式1｜20｜-5

變式0｜60｜5

變式2｜70｜10

變式3｜110｜20

變式4｜135｜25

變式1｜190｜100

變式0｜210｜120

### 相關性

<image>

人類玩家採用的策略不同，MENACE勝局在散點圖中呈現的變化趨勢也不同。人類隨機落子時，圖中幾乎呈完全正相關，而採用最優策略時，增長速度則略慢。這種強化機制並不能保證每局獲勝，演算法每次仍會隨機得出不確定結果。第j輪後，接近完美對弈的相關值為：

$${1-D \over D-D^{(j+2)}}\sum_{i=0}^j D^{(ji+1)} V_i$$

其中，Vi表示對局結果，勝為+1，平為0，負為−1；D為衰減因子，即以往勝負值的平均衰減程度。下式中，Mn表示一局中第n輪的乘數。

結果｜強化值

獲勝｜$R_n=M_n^{-\mu+1}$

戰平｜$R_n=M_n^{-\mu}$

落敗｜$R_n=M_n^{-\mu-1}$

## 影響

唐納德·米基的MENACE證明，電腦能夠從成敗中學習，逐漸掌握特定任務。它在相關理論尚未成熟前，便已運用後來成為機器學習核心的若干原理。例如，MENACE最初在各火柴盒中放入等量的不同顏色珠子，再從中隨機抽取，這種學習機制與現代人工神經網絡的權重初始化相似。1968年，唐納德·米基與R·A·錢伯斯又以BOXES為基礎開發GLEE（Game Learning Expectimaxing Engine，遊戲學習期望極大化引擎）演算法，使其學習如何保持小車上的杆子平衡。

MENACE引起熱烈反響後，米基獲邀前往美國海軍研究辦公室，受託為史丹福大學使用的IBM電腦編寫運行BOXES的程序。米基還在 D·馬丁協助下，為費蘭蒂飛馬座電腦編寫MENACE模擬程序。此後，人們多次以實體裝置或電腦程式復原MENACE。其演算法後來演化為克里斯多福·沃特金斯的Q學習演算法。

MENACE雖不再作為實用電腦使用，卻成為多門神經網路課程的教學演示工具，倫敦大學學院研究員馬修·斯克羅格斯也曾公開演示這套裝置。斯克羅格斯製作的MENACE復原品曾亮相2019年英國皇家科學院聖誕講座以及2023年播出的一期《QI》。

MENACE還見於弗雷德·薩伯哈根1963年的短篇小說《不假思索 (小說集)》，以及托馬斯·J·瑞安1977年的小說《P-1的青春期》。

## 來源

- , Michie and R. A Chambers' paper on the AI implications of BOXES and MENACE.
- , a book on the "Boxes" algorithm employed by MENACE.

## 外部連結

- Online simulation of MENACE