学会圈叉游戏的火柴盒

<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