マッチボックスの教育用ゼロ・クロスエンジン

マッチ箱教育可能ゼロクロスエンジン（機械教育可能ゼロクロスエンジンまたはMENACEと呼ばれることもある）は、1961年に人工知能研究者のドナルド・ミチーによって設計および構築された304個のマッチ箱で作られた機械式コンピュータです。任意のプレイ状態の動きを返すことでゼロとクロスのゲーム（三目並べ）で人間の相手と対戦し、強化学習によって戦略を改良するように設計されました。これは最初のタイプの人工知能の1つでした。

ミッチーはすぐに使えるコンピュータを持っていなかったため、マッチ箱でコンピュータを作ることでこの制約を回避しました。ミッチーが使用したマッチ箱は、それぞれがオッズとバツのグリッドの 1 つの可能なレイアウトを表しています。コンピュータが最初にプレイしたとき、現在のレイアウトに基づいて動きをランダムに選択します。ゲームを重ねるにつれて、強化ループによって、負けにつながる戦略は無効になり、勝ちにつながる戦略が補充されました。ミッチーは 1961 年に MENACE とのトーナメントを開催し、さまざまなオープニングを試しました。

MENACE が Michie と対戦した最初のトーナメントの後、その戦略に人工知能がうまく機能していることが実証されました。MENACE の重みの初期化と MENACE で使用される BOXES アルゴリズムに関する Michie のエッセイは、コンピューター サイエンスの研究分野で人気を博しました。Michie は機械学習研究への貢献を称えられ、実際のコンピューター上で MENACE シミュレーションをプログラムする依頼を 2 回受けました。

ドナルド・ミッチー（1923–2007）は、第二次世界大戦中にドイツのマグロ暗号を解読するチームに所属していた。^{[1] 15年後、彼は初期の}畳み込みニューラルネットワークで数学と計算の才能をさらに発揮したいと考えました。そのような用途にコンピュータ機器は入手できず、^[2]ミッチーはすぐに使えるコンピュータを持っていなかったため、^[2]彼は人工知能をより難解な形式で展示および実証することに決め、マッチ箱とビーズで機能的な機械式コンピュータを構築しました。 ^{[3] [4]}

MENACEは、そのようなマシンは不可能だと仮定したコンピュータサイエンスの同僚との賭けの結果として構築されました。 ^[5]ミッチーは、マッチ箱を収集して定義するという作業を「楽しいプロジェクト」として引き受け、後にデモンストレーションツールに変えました。^[6]ミッチーは1963年にMENACEに関するエッセイ^[4]「ゲーム学習の機械化に関する実験」と、RAチェンバースと共著したBOXESアルゴリズムに関するエッセイ^{[6]を完成させ、}スコットランドのエディンバラにあるホープパークスクエアにAI研究ユニットを設立しました。^[7]

MENACEは、オッズとクロスのマッチを増やして学習しました。毎回、人間のプレイヤーが各動きに対応するビーズを没収することで、負け戦略を排除しました。^[4]ビーズを追加することで動きの可能性を高め、勝利戦略を強化しました。^[8]これは、アルゴリズムをループさせ、失敗した戦略を削除して勝ち戦略のみを残すという図式的なアルゴリズムである強化ループの最も初期のバージョンの1つでした。 ^[4]このモデルは完全にランダムな状態から始まり、徐々に学習します。^[9]

MENACEは304個のマッチ箱を箪笥のような配置で接着して作られました。^[10]各箱にはコード番号があり、チャートに入力されました。このチャートには、X、O、空のマス目がさまざまな配置で描かれた三目並べのゲームグリッドがあり、 ^[4]ゲームが進行するにつれて起こり得るすべての可能な順列に対応していました。^[11]重複する配置（他の構成を単に回転または鏡像にした配置）を取り除いた後、MENACEはチャートで304個の順列を使用し、その数のマッチ箱を使用しました。^[12]

それぞれのマッチ箱のトレイには、色とりどりのビーズが詰め込まれていた。^[13]各色はゲームグリッド上のマス目の動きを表しており、グリッド上の位置がすでに取られている配置のマッチ箱には、その位置のビーズは入っていない。さらに、トレイの前面には「V」字型のカードが2枚余分にあって、^{[ 10]}「V」の先端はマッチ箱の前面を指していた。^[11]ミチーと彼の人工知能チームは、マシンに使われている装置にちなんで、MENACEのアルゴリズムを「ボックス」と呼んだ。第1段階の「ボックス」は5つのフェーズで動作し、それぞれがゲームに関連するアルゴリズムのルールの定義と前例を設定した。 ^[14]

MENACE は最初に O としてプレイしました。これは、すべてのマッチ箱が "X" プレイヤーにのみ関係する順列を表していたためです。^{[12] [17]} MENACE の動きの選択を取得するために、対戦相手またはオペレーターは、現在のゲーム状態、またはその回転または鏡像に一致するマッチ箱を探します。たとえば、ゲームの開始時に、これは空のグリッドのマッチ箱になります。トレイを取り外して軽く振って、ビーズを動かします。^[4]次に、トレイの前面の "V" 字型の先端に転がったビーズが、MENACE が選択した動きです。^[4]次に、その色がプレイする位置として使用され、選択したマッチ箱の構成と現在のグリッドの関係に基づいて必要な回転または反転が考慮された後、O がそのマスに配置されます。次に、プレーヤーが動きを実行し、新しい状態が見つかり、新しい動きが選択され、ゲームが終了するまでこれが続きます。^[12]

ゲームが終了すると、人間のプレイヤーはゲームの結果を観察しました。ゲームが進行するにつれ、MENACE のターンに使用された各マッチ箱のトレイは半開きで戻され、使用されたビーズは脇に置かれ、MENACE の動きの選択とそれらが属するゲーム状態が記録されました。ミッチーは強化システムを「報酬」と「罰」で説明しました。ゲームが終了したら、MENACE が勝った場合、勝利に対する「報酬」を受け取ります。取り除かれたビーズは、勝利した動きの順序を示していました。^[17]これらは、わずかに開いているため簡単に識別できるそれぞれのトレイに戻され、同じ色の 3 つのボーナスビーズも戻されました。^[11]このようにして、将来のゲームで MENACE はそれらの勝利の動きを繰り返す可能性が高くなり、勝利戦略が強化されます。負けた場合、取り除かれたビーズは戻されず、MENACE は「罰せられ」、将来的にその色のビーズがなくなった場合、負けを引き起こす動きを繰り返す可能性が低くなり、最終的にはできなくなることを意味します。^{[3] [8]}ゲームが引き分けになった場合、各ボックスにビーズが 1 つ追加されました。^[11]

ゼロとクロスにはよく知られた最適戦略があります。^[18]プレイヤーは、他のプレイヤーが列を作れないようにシンボルを配置し、同時に自分自身も列を作らなければなりません。しかし、両方のプレイヤーがこの戦略を使用した場合、ゲームは常に引き分けで終わります。^[18]人間のプレイヤーが最適戦略に精通していて、MENACE がそれをすぐに学習できれば、ゲームは最終的に引き分けで終わるでしょう。コンピューターがランダムにプレイする相手と対戦する場合、コンピューターが勝つ可能性は急速に高まります。^[3]

最適戦略を使用するプレイヤーと対戦する場合、ドローの確率は 100% にまで上昇します。1961 年にドナルド ミチーが MENACE と対戦した公式トーナメント^[4]では、最適戦略が使用され、20 ゲーム後には彼とコンピューターは一貫してドローになりました。ミチーのトーナメント^[19]には、次のようなマイルストーンがありました。ミチーは、中央のマスである「バリアント 0」で一貫してオープニングを開始しました。15 ゲームで、MENACE はコーナー以外のオープニングをすべて放棄しました。20 ゲームを少し超えた時点で、ミチーは右下のマスである「バリアント 1」を一貫して使用するように切り替えました。60 ゲームで、彼はバリアント 0 に戻りました。80 ゲームに近づくと、彼は上部中央の「バリアント 2」に移行しました。110 ゲームで、彼は上部右側の「バリアント 3」に切り替えました。135 ゲームで、彼は中央右側の「バリアント 4」に切り替えました。 190 でバリアント 1 に戻り、210 でバリアント 0 に戻りました。

「2」のボックス内のビーズの変化の傾向は次のとおりです。^[19]

MENACEは、人間のプレイヤーが採用した戦略に応じて、勝利の散布図に異なる傾向を生み出します。 ^[4]人間のプレイヤーからのランダムなターンを使用すると、ほぼ完璧なプラスの傾向が得られます。最適な戦略をプレイすると、わずかにゆっくりとした増加が返されます。^[3]強化は勝利の完璧な基準を作成するわけではありません。アルゴリズムは毎回ランダムで不確実な結論を導きます。j番目のラウンドの後、ほぼ完璧なプレイの相関は次のようになります。

${\displaystyle {1-D \over DD^{(j+2)}}\sum _{i=0}^{j}D^{(ji+1)}V_{i}}$

ここで、V _iは結果（+1は勝ち、0は引き分け、-1は負け）、Dは減衰係数（過去の勝ち負けの値の平均）です。以下、M _{n は}ゲームの第 nラウンドの乗数です。 ^[4]

ドナルド・ミチーのMENACEは、コンピュータが失敗と成功から学び、タスクをうまくこなせることを証明した。^[17]これは、機械学習の分野で適切に理論化される前の中核原理を使用した。たとえば、MENACEが各マッチ箱に同数の種類のビーズを入れて開始し、その後これらをランダムに選択する方法の組み合わせは、現代の人工ニューラルネットワークの重みの初期化に似た学習動作を生み出す。^[20] 1968年、ドナルド・ミチーとRAチェンバースは、カートの上で棒のバランスをとる方法を学習するGLEE（Game Learning Expectimaxing Engine）と呼ばれる別のBOXESベースのアルゴリズムを作成した。^[21]

MENACEが大好評を博した後、ミッチーは米国海軍研究局に招かれ、スタンフォード大学で使用するIBMコンピュータ用のBOXES実行プログラムの構築を委託された。^[22]ミッチーはD.マーティンの助けを借りてペガサス2コンピュータ上でMENACEのシミュレーションプログラムを作成した。 ^[4]近年、元の物理的形式とコンピュータプログラムの両方でMENACEが何度も再現されている。^[12]そのアルゴリズムは後にクリストファー・ワトキンのQ学習アルゴリズムに収束した。^[23]機能的なコンピュータとしてではないが、デモンストレーションの例ではMENACEは様々なニューラルネットワークの授業で教材として使われており、^{[24] [25] [26]}ユニバーシティ・カレッジ・ロンドンの研究者マシュー・スクロッグスによる公開デモンストレーションもその一つである。^{[27] [28]}スクログスが製作したMENACEのコピーは、 2019年の王立研究所クリスマス講演会で紹介されました。 ^{[29] [30]また、2023年の}QI XLのエピソードでも紹介されました。^[31]

MENACEは、フレッド・セイバーヘイゲンの1963年の短編小説『Without A Thought』やトーマス・J・ライアンの1977年の小説『The Adolescence of P-1』で言及されています。^[32]作家ナオミ・アルダーマンは2023年の著書『The Future』の中で、 MENACEの詳細な概要を説明した架空の講義を収録しています。

• ヘキサポーン

• Michie, D.; Chambers, RA (1968)、「BOXES: 適応制御の実験」、Machine Intelligence、エディンバラ、イギリス: Oliver and Boyd、S2CID  18229198 – Semantic Sc​​holar 経由、Michie と R. A Chambers による BOXES と MENACE の AI への影響に関する論文。
• ラッセル、デビッド・W（2012）、BOXES方法論：ブラックボックスダイナミックコントロール、シュプリンガーロンドン、ISBN 978-1849965286MENACE で採用されている「Boxes」アルゴリズムに関する本。

• MENACEのオンラインシミュレーション