Waits: アーサー・サミュエルのチェッカー

WAITS: アーサー・サミュエルのチェッカー 2026年8月9日 (日) DEC PDP-10 WAITS チェスは人気のターゲットでしたが、ゲームをプレイするための古典的なプリLLM人工知能の初期の例の1つは、チェッカー/ドラフツでした。アーサー・サミュエルは1950年代初頭にそのようなプログラムの最初の1つを書き、SAILに移ったときにPDP-10に移植し、1970年代後半にはホームコンピュータ用のバージョンも作成しました。この記事では、サミュエルのチェッカーに関する仕事を見て、彼がWAITSで作成した1972年版を実行します。 歴史 IBM 7090と対戦するサミュエル。出典: IBM アーサー・サミュエルは、1930年代にベル研究所で真空管の仕事からキャリアをスタートさせました。1946年にイリノイ大学の教授になりました。大学にコンピュータを導入したいと考え、コンピュータを構築し、チェッカーをプレイできるプログラムを実行する提案を思いつきました。彼は紙の上で計画を立て始めましたが、彼が1949年にIBMに転職するまでに、コンピュータもプログラムも完成しませんでした。そこで彼の主な役割は真空管や後のトランジスタでしたが、チェッカーの問題は依然として彼を魅了していました。彼はIBM 70xシリーズのマシンを使用してこの問題に取り組みました。1979年のコンピュータ雑誌のジャーナリストへの手紙によると、IBMマシンにはアセンブラさえ利用できなかったため、当初は生の機械語で書かれていました。 最初のバージョンは1952年に完成しましたが、「1954年にIBM 704が登場して初めて、私のプログラムは興味深いゲームをプレイできるようになりました。私の貢献はプログラムに学習を追加することでした。そして、私はこれを最初のものだと主張できると信じています。」と述べています。1956年には、このプログラムがテレビで紹介され、大衆の想像力を掻き立てました。最終的には、マスタープレイヤーに時折挑戦できるレベルでゲームをプレイできるようになりました。ミニマックス、アルファベータ枝刈り、ルーチン学習などの技術を使用して、彼の仕事はAIの初期において影響力がありました。サミュエルは1956年のジョン・マッカーシーのダートマス会議に出席し、彼の仕事は1960年代のAIに関する画期的な概説書である『Computers and Thought』に収録されました。 彼は1966年にIBMを退職し、SAILの上級スタッフとして参加しました。ここでは、研究所の多くのプロジェクトを支援し、IBM 7090のアセンブリプログラムをPDP-10のアセンブリ言語に移植しました。今日実行されているバージョンは1972年のものです。 WAITSでチェッカーを実行中。出典: Rupert Lane. ライセンス: CC0. 彼は1976年に他の研究者の関心から再びこの問題に取り組み、IBM System/360で新しいプログラムを実行していたデューク大学のチームと対戦しました。2つのゲームが行われましたが、CPU時間の必要性から完了しませんでした。サミュエルの説明によると、「デューク大学のプログラムは両方のゲームで勝利の可能性があったと信じられていた。その後の分析では、これらのゲームの1つは引き分けにつながる可能性があったことが明らかになった。」また、1977年には、初期のホームコンピュータ向けのチェッカーのバージョンを開発するために、VideoBrain Family Consoleのメーカーと協力しました。システムは1KBのRAMしかありませんでしたが、4つの異なる難易度レベルを提供したため、これは機能が削減されたバージョンでした。彼はまた、VideoBrain版のReversi/OthelloであるVice VersaのAIにも協力しました。 VideoBrainチェッカープログラムとマニュアル。出典 (左) atariprotos.com (右) archive.org WAITSでチェッカーをプレイする プログラムは、R CHECKEと入力することで、任意の端末タイプで実行できます。コマンドのリストを表示するには、HELP（大文字である必要があります）と入力してください。初期ボード設定を入力したり、プレイパラメータを調整したり、PSコマンドでコンピュータ同士でプレイさせることさえできます。デフォルトでは、プレイヤーが先に（黒/赤として）プレイし、コンピュータが後に（白/青として）プレイします。移動は、1が右下の位置、32が左上の標準表記を使用して、ソースとデスティネーションのマスを入力します。ここでプログラムを開始し、マス9からマス13に移動します。 .R CHECKE 26 JUL 74 1* 9 13 プログラムは最適な手を見つけようとし、検索した位置の数、評価関数の最良値、およびミリ秒単位でかかった時間（ここでは約13秒、実際のハードウェアでははるかに遅かったでしょう）の統計情報とともに表示します。 MOVE # OF BDS PIECE EVAL TIME 2 23-19 219956. 0 35 13567 したがって、23-19に移動しました。ASCIIでボードを表示するには、BD命令を入力できます。 3* BD * * * * * * * * * * * + W + W + W + W * * W + W + W + W + * * + W + + W + W * * + W + + + * * + + + + B * * B + B + B + + * * + B + B + B + B * * B + B + B + B + * * * * * * * * * * * しかし、生活を楽にするために、ゲームテーブルのようなものを使用して2プレイヤーモードで移動を記録することもできます。ボードは次のようになります。 CHECKEとチェッカーをプレイ中。出典: Rupert Lane. ライセンス: CC0. 無意味な移動を入力すると、次のようになります。 3* 99 66 SORRY CHARLIE! ゲームの全記録は提供しませんが、44手目でプログラムは次のように発表しました。 THE PDP-10 EXPECTS TO WIN IN 11 MOVES. 44 26-22 15171. 11 MOVE WIN. 1017 しかし、私の破滅はわずか3手後に起こりました。ここでは、FORCEDと表示されています。これは、ゲームのルールにより、相手の駒を取ることができる場合は取らなければならないためです。 45* 10 15 46 17-1 3. FORCED 0 47* 15 18 26 JUL 74 1* ソースコード 私が知る限り、オリジナルのIBM 7090コードは公開されていません。WAITSシステム上のサミュエルのディレクトリは、saildart.orgで見つけることができます。1972年のCHECKEバイナリに一致するコードがどれであるかを判断するのは難しいですが、CKP2.MAC[2,ALS]が最も古いファイルで、1971年にさかのぼります。1977年までのさらなる拡張機能は、[CH2,ALS]で見つけることができ、サンプルゲームデータは[CH3,ALS]、[CH4,ALS]、[3,ALS]にあります。コードは、PDP-10に同等の命令がなかった一部の命令をサブルーチンに翻訳するなど、IBM 7090バージョンの移植であることが示されています。例えばCAQなどです。VideoBrain開発ディレクトリはF8と呼ばれています。これには、チェッカーのソースコードのいくつかのバージョンと、おそらくFairchild（VideoBrainのCPUを製造した会社）によって書かれたFortranのクロスアセンブラが含まれています。サミュエルが書いた量と、VideoBrainの協力者が書いた量がどれくらいかは不明です。サミュエルとVideoBrainのメーカーとの間のいくつかのやり取りもあり、サミュエルは他のゲームの制作を提案し、開発ハードウェアの信頼性の低さについて苦情を述べています。 さらなる情報 IBMの記事「The games that helped AI evolve」は、チェッカーに関するサミュエルの同社での仕事の最初の紹介であり、TesauroのTD-Gammonプログラムについても論じています。サミュエルのオリジナルの1959年7月の論文「Some Studies in Machine Learning Using the Game of Checkers」は、IBM Journal of Research and Development、vol. 3、no. 3、pp. 210-229に掲載されており、IEEExploreでダウンロード可能です。IEEEはサミュエルの仕事に関する追悼記事も掲載しています。Richard SuttonとAndrew Bartoの著書「Reinforcement Learning: An Introduction」はオンラインで全文公開されており、サミュエルのチェッカーに関するケーススタディが含まれています。MAMEはVideoBrainのエミュレータを持っており、ゲームカートリッジROMのコピーはオンラインで見つけることができます。別の初期のチェッカープログラムは、1950年代初頭にChristopher StracheyがFerranti Mark 1用に書いたもので、これを実行できるエミュレータがあります。 質問、修正、コメント ご質問やコメントを歓迎します。もし私が何か間違っている場合は、特に修正を歓迎します。rupert@timereshared.comまでメールしてください。ここに追記し、本文を更新します。