マッチボックスの教育用三目並べエンジン
良い記事ですね。詳しくはこちらをクリックしてください。

MENACEレクリエーション
2015年に建造されたMENACEの再現

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

ミチーとチェンバースはコンピュータをすぐには利用できなかったため、マッチ箱を使ってエンジンを構築することでこの問題を解決した。[ 1 ]彼らが使用したマッチ箱はそれぞれ、○と×のグリッドの可能な配置を1つずつ表していた。コンピュータが最初にプレイする際、現在の配置に基づいてランダムに手順を選択する。ゲームを重ねるにつれて、強化ループによって、負けにつながる戦略は失格となり、勝ちにつながる戦略は補充されるようになった。ミチーは1961年にMENACEとのトーナメントを開催し、様々なオープニングを試した。

MENACEはMichieとの初対戦で、その戦略に人工知能が効果的に活用されていることを実証しました。MENACEの重み初期化とMENACEで使用されるBOXESアルゴリズムに関するMichieの論文は、コンピュータサイエンス研究の分野で高い評価を得ました。Michieは機械学習研究への貢献が認められ、実機コンピュータ上でMENACEのシミュレーションをプログラムする依頼を2度も受けました。

起源

1986年のドナルド・ミチー
ドナルド・ミチー、1986年

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

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

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

構成

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

それぞれのマッチ箱のトレイには、色とりどりのビーズがいくつか入っていました。[ 13 ]各色はゲームグリッド上のマス目の動きを表しており、グリッド上の位置が既に取られているマッチ箱には、その位置のビーズは入っていません。さらに、トレイの前面には「V」字型のカードが2枚追加されており、[ 10 ]「V」の先端はマッチ箱の前面を指しています。[ 11 ]ミチーと彼の人工知能チームは、MENACEのアルゴリズムを、このマシンに使用されている装置にちなんで「ボックス」と名付けました。 [ 7 ]最初の段階の「ボックス」は5つのフェーズで動作し、それぞれがゲームに関連するアルゴリズムのルールの定義と前例を設定しました。 [ 14 ]

手術

MENACE（O）と人間（X）がミッチーのオリジナルカラーのビーズを使ってプレイしたゲームの例。MENACEはこのゲームに負けたため、表示されているビーズはすべてそれぞれの箱から取り除かれています[ 15 ] [ 16 ]

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

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

実践結果

最適な戦略

最適な〇〇戦略
プレイヤーXがコーナーからスタートした場合の最適戦略。各グリッドにおいて、赤い網掛けのXは最適な動きを示し、Oの次の動きの位置は次に検討すべきサブグリッドを示します。

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

最適戦略を使うプレイヤーと対戦する場合、ドローの確率は100%にまで上昇する。1961年にドナルド・ミチーがMENACEと公式トーナメントを行った際[ 5 ]、彼は最適戦略を使い、20ゲーム後には彼とコンピュータはコンスタントにドローを始めた。ミチーのトーナメント[ 19 ]には以下の節目があった。ミチーは最初、コンスタントに「バリアント0」、つまり中央のマス目でオープニングを行った。15ゲーム目では、MENACEは角以外のオープニングを一切行わなくなった。20ゲーム目を少し過ぎた頃、ミチーはコンスタントに「バリアント1」、つまり右下のマス目でオープニングを行うようになった。60ゲーム目で再びバリアント0に戻った。80ゲーム目近くになると「バリアント2」、つまり上中に移った。110ゲーム目で「バリアント3」、つまり右上に移った。135ゲーム目で「バリアント4」、つまり右中に移った。 190 でバリアント 1 に戻り、210 でバリアント 0 に戻りました。

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

変異体試合番号「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

相関

ミッチーのトーナメントの散布図。
ドナルド・ミチーとメナスの試合結果を示す散布図

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

1−DD−D（j+2）∑私＝0jD（j私+1）V私{\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番目のラウンドの乗数である。 [ 5 ]

結果 強化
勝利した Rn＝Mn−μ+1{\displaystyle R_{n}=M_{n}^{-\mu +1}}
描く Rn＝Mn−μ{\displaystyle R_{n}=M_{n}^{-\mu}}
失った Rn＝Mn−μ−1{\displaystyle R_{n}=M_{n}^{-\mu -1}}

遺産

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

MENACE が大反響を呼んだ後、ミチーはアメリカ海軍研究局に招かれ、スタンフォード大学で使用するIBMコンピュータ用の BOXES 実行プログラムの構築を委託された。[ 22 ]ミチーはD. マーティンの助けを借りて、ペガサス2 コンピュータ上で MENACE のシミュレーション プログラムを作成した。 [ 5 ]近年、元の物理的形式とコンピュータ プログラムの両方で、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の詳細な概要を記した架空の講義を掲載しています。

参照

参考文献

  1. ^ a b c Donald, Michie; Chambers, Roger (1968). E. Dale and D. Michie (ed.). BOXES: An experiment in adaptive control . Machine Intelligence. Vol. 2. University of Edinburgh. pp.  137– 152. CiteSeerX  10.1.1.474.2430 . 2020年6月26日時点のオリジナルよりアーカイブ。 2020年7月31日閲覧。
  2. ^ Boden, Margaret (2007年8月15日). 「ドナルド・ミチー (1923–2007)」 . Nature . 448 (7155): 765. doi : 10.1038/ 448765a . ISSN 1476-4687 . PMID 17700692. S2CID 5239830 .   
  3. ^ a b Wright, Matt (2020年3月31日). 「ドナルド・ミチー：マッチ箱とビーズでコンピュータープログラムをテストしたAIの先駆者」 . Scroll.in . 2020年10月20日時点のオリジナルよりアーカイブ。 2020年10月18日閲覧。
  4. ^ a b c d Child, Oliver (2016年3月13日). “Menace: the Machine Educable Noughts And Crosses Engine” . Chalkdust . 2020年5月12日時点のオリジナルよりアーカイブ。 2020年5月17日閲覧。
  5. ^ a b c d e f g h i j kミチー、ドナルド. 「ゲーム学習の機械化に関する実験 パート1. モデルとそのパラメータの特性評価」(PDF)。2019年11月21日時点のオリジナルよりアーカイブ(PDF) 。 2020年6月1日閲覧。
  6. ^ “Daily Telegraph obituary for Donald Michie” . The Daily Telegraph . 2007年7月9日. 2020年6月11日時点のオリジナルよりアーカイブ。 2021年5月25日閲覧。
  7. ^ a b Muggleton, Stephen (2007年7月10日). 「ドナルド・ミチーの訃報、2007年のガーディアン紙の記事」 .ガーディアン. 2020年10月1日時点のオリジナルよりアーカイブ。 2021年5月22日閲覧。
  8. ^ a bハーディングハム、サマンサ; フレイザー、ジョン; ジョーンズ、エマ・レティツィア (2012). 「ジョン・フレイザーとサマンサ・ハーディングハムの対談」 . AA Files (64): 69– 77. ISSN 0261-6823 . JSTOR 41762307 .  
  9. ^ Wylie, Caspar (2018年10月5日). 「300個のマッチ箱がMENACEを使って三目並べをプレイする方法」 . Open Data Science . 2021年5月15日時点のオリジナルよりアーカイブ。 2021年5月15日閲覧。
  10. ^ a b『サイエンスブック』第2版、ドーリング・キンダースリー社、2015年、288ページ
  11. ^ a b c dガードナー、マーティン (1962). 「数学ゲーム」. Scientific American . 206 (3): 138– 154. Bibcode : 1962SciAm.206c.138G . doi : 10.1038/scientificamerican0362-138 . JSTOR 24937263 . 
  12. ^ a b c d「Matchbox Educable Noughts And Crosses Engine In Empirical Modelling」（PDF） . ウォーリック大学. 2021年5月22日閲覧。
  13. ^ De Raedt, Luc. 「 AIにおける機械学習革命」。2020年6月12日時点のオリジナルよりアーカイブ。
  14. ^ラッセル、デイビッド (2012). 「BOXES方法論」より抜粋 (第2章 ゲームのメタファー) . ロンドン: Springer Professional. ISBN 978-1849965279。
  15. ^ 「Menace: 機械で教育可能なゼロとクロスのエンジン」 2016年3月13日。
  16. ^ミチー、ドナルド (1963年11月). 「ゲーム学習の機械化に関する実験 パートI：モデルとそのパラメータの特性評価」 .コンピュータジャーナル. 6 (3): 232– 236. doi : 10.1093/comjnl/6.3.232 . 2024年8月28日閲覧。
  17. ^ a b c「MENACE 2、木製の引き出しと色付きビーズで作られた人工知能」。2016年4月12日。2020年7月12日時点のオリジナルよりアーカイブ。 2021年5月22日閲覧。
  18. ^ a b Cappiell, Emily (2020年11月30日). 「三目並べで勝つ方法：マスターすべき戦略」 . Reader's Digest . 2021年1月22日時点のオリジナルよりアーカイブ。 2021年2月6日閲覧。
  19. ^ a b試行錯誤、ミチー・ドナルド、ペンギン科学調査1961年第2巻
  20. ^ Yam, Jim YF; Chow, Tommy WS (2000年1月1日). 「フィードフォワードニューラルネットワークの学習速度を向上させる重み初期化法」 . Neurocomputing . 30 (1): 219– 232. doi : 10.1016/S0925-2312(99)00127-7 . ISSN 0925-2312 . 
  21. ^サットン、リチャード・S.、バート、アンドリュー・G. (2018). 『強化学習：入門』 MIT Press. p. 753. ISBN 978-0262039246。
  22. ^ 「ドナルド・ミチー教授」デイリー​​・テレグラフ、2007年7月8日。ISSN 0307-1235。2020年6月11日時点のオリジナルよりアーカイブ。2020年6月11日閲覧。 
  23. ^スカルフィ、ピエロ (2014). 『知性は人工物ではない ―シンギュラリティがすぐに来ない理由と、ポストヒューマンの条件と知性の未来に関する考察』. オムニウェア. p. 27. ISBN 978-0976553199。
  24. ^ Zhao, Yibo (2013年12月1日). 「モデリング研究におけるゼロとクロスに関する機械教育可能なエンジン」 . ウォーリック大学. 2020年6月11日時点のオリジナルよりアーカイブ。 2021年5月22日閲覧。
  25. ^ 「AIトピックス.. 計算思考における三目並べ戦略、入門、MENACE」。2021年2月8日時点のオリジナルよりアーカイブ。 2021年5月22日閲覧。
  26. ^ Ute Schmid – 「相互説明によるインタラクティブ学習」（人間と機械学習システムが互いに利益を得る方法）– バンベルク大学、ドイツリンク
  27. ^スクロッグス、マシュー（2017年7月3日）。「MENACE マシンの構築」、Matthew Scroggs、University College London (YouTube)。
  28. ^ “Inspiring the Next Generation of Computer Scientists | King's Worcester” . King's Worcester . 2019年11月11日. 2020年6月12日時点のオリジナルよりアーカイブ。 2020年6月12日閲覧。
  29. ^ Scroggs, Matthew (2019年12月27日). 「Visualising MENACE's learning」 . mscroggs.co.uk . 2020年7月11日時点のオリジナルよりアーカイブ。2020年7月30日閲覧。
  30. ^ @rsi_science (2019年12月27日). 「メナス・マシンの製作者が304個のマッチ箱を持って現れ、製作過程を説明した」（ツイート） 。 2020年10月14日閲覧– Twitter経由。
  31. ^ 「QI XLシリーズT、税制上の問題に直面」 BBC 、 2023年1月6日。 2023年2月4日閲覧。
  32. ^ Scroggs, Matthew (2018年12月16日). 「MENACE in fiction」 . mscroggs.co.uk . 2020年7月11日時点のオリジナルよりアーカイブ。2020年3月18日閲覧。

出典

  • Michie, D.; Chambers, RA (1968)、「BOXES: An Experiment in Adaptive Control」、Machine Intelligence、エディンバラ、英国: Oliver and Boyd、S2CID  18229198 – Semantic Sc​​holar経由、Michie と R. A Chambers による BOXES と MENACE の AI への影響に関する論文。
  • ラッセル、デイビッド・W.（2012）、BOXES方法論：ブラックボックスダイナミックコントロール、シュプリンガーロンドン、ISBN 978-1849965286MENACE で採用されている「Boxes」アルゴリズムに関する本。
「 https://en.wikipedia.org/w/index.php?title=Matchbox_Educable_Noughts_and_Crosses_Engine&oldid=1322725239」より取得