コア戦争

コア戦争

pMARSシミュレータで実行
開発者	DG ジョーンズ & AK デュードニー
初回リリース	1984年3月
タイプ	プログラミングゲーム
Webサイト	コアウォーズ

Core War は、DG Jones とAK Dewdneyによって1984 年に作成されたプログラミング ゲームです。このゲームでは、2 つ以上の戦闘プログラム (「戦士」と呼ばれる) が仮想コンピューターの制御を競います。これらの戦闘プログラムは、 Redcodeと呼ばれる抽象アセンブリ言語で記述されています。言語と仮想マシンの標準は、当初は International Core Wars Society (ICWS) によって設定されましたが、その後、コミュニティの合意によって標準が決定されました。

ゲームの開始時に、各バトル プログラムがメモリ内のランダムな場所にロードされ、その後、各プログラムが順番に 1 つの命令を実行します。ゲームの目的は、対戦相手のプログラムのプロセスを終了させ (無効な命令を実行した場合に発生します)、勝利したプログラムがマシンを独占することです。

最初に公開されたバージョンの Redcode では、8 つの命令のみが定義されていました。ICWS-86 標準ではその数が 10 に増え、ICWS-88 標準では 11 に増えました。現在使用されている 1994 年ドラフト標準には 16 の命令があります。ただし、Redcode は、さまざまなアドレス指定モードと (1994 年ドラフト標準以降) 命令修飾子をサポートしており、実際に実行可能な操作の数は 7168 に増えています。Redcode 標準では、基礎となる命令表現が未定義のままになっており、プログラムがそれにアクセスする手段は提供されていません。算術演算は各命令に含まれる 2 つのアドレス フィールドで実行できますが、命令コード自体でサポートされている操作は、コピーと等価性の比較のみです。

一定の命令の長さと時間

各 Redcode 命令は 1 つのメモリ スロットを占有し、実行には 1 サイクルかかります。ただし、処理時間は均等に共有されるため、プロセスが命令を実行する速度はキュー内の他のプロセスの数によって異なります。

循環メモリ

メモリは、1 つの命令単位でアドレス指定されます。メモリ空間 (またはコア) のサイズは有限ですが、相対アドレス指定のみが使用されます。つまり、アドレス0 は常に現在実行中の命令を参照し、アドレス1はその次の命令を参照する、というようになります。最大アドレス値は、メモリ位置の数より 1 少ない値に設定され、必要に応じてラップアラウンドされます。その結果、アドレスとメモリ位置は 1 対 1 で対応しますが、Redcode プログラムが絶対アドレスを決定することは不可能です。無効命令やジャンプ命令に遭遇しないプロセスは、連続する命令を無限に実行し続け、最終的に開始した命令に戻ります。

低レベルマルチプロセッシング

Redcode シミュレーターには、単一の命令ポインターの代わりに、シミュレーターが循環する可変数の命令ポインターを含む各プログラムのプロセス キューSPLがあります。各プログラムは 1 つのプロセスのみで開始しますが、命令を使用して新しいプロセスをキューに追加できます。プロセスは、DAT命令を実行するか、ゼロ除算を実行すると終了します。プロセスが残っていない場合、プログラムは終了したとみなされます。

外部アクセス不可

Redcode と MARS アーキテクチャは、入力機能や出力機能を提供しません。シミュレータはクローズド システムであり、入力はメモリとプロセス キューの初期値のみで、出力は戦闘の結果、つまりどのプログラムに生き残ったプロセスがあったかのみです。もちろん、シミュレータでは、シミュレーションの実行中に外部からメモリを検査したり変更したりすることは可能です。

Redcode にはいくつかのバージョンが存在します。AK Dewdney ^[1]によって記述された最も初期のバージョンは、International Core War Society によって確立された後の標準とは多くの点で異なり、関連しているものの別の言語であると考えることができます。今日最も一般的に使用されている Redcode の形式は、1994 年に ICWS に提出された標準草案に基づいていますが、その頃に ICWS が事実上廃止されたため、正式に承認されることはありませんでした。ただし、Redcode の開発は、主にrec.games.corewar^[2] ニュースグループなどのオンライン フォーラムを通じて非公式に継続されています。

戦士は一般的にいくつかの広いカテゴリーに分類されますが、実際の戦士はこれらのうち2つ以上の行動を組み合わせることがよくあります。一般的な戦略のうちの3つ（レプリケーター、スキャナー、ボンバー）は、よく知られている遊び場のゲームでお互いのパフォーマンスが同名の戦略のパフォーマンスに似ているため、紙、はさみ、石とも呼ばれています。^[3]

紙（またはレプリケーター）

レプリケータは自身のコピーを繰り返し作成し、それらを並列に実行して、最終的にコア全体をそのコードのコピーで埋め尽くします。レプリケータを殺すのは困難ですが、敵を殺すのは困難な場合がよくあります。そのため、レプリケータは、特に他のレプリケータに対しては、同点になることが多い傾向があります。

シルクは、ユハ・ポハライネンによるシルク・ウォリアー^[4]にちなんで名付けられた、非常に高速なレプリケータの特殊なタイプです。現代のレプリケータのほとんどはこのタイプです。シルク・レプリケータは並列実行を使用して、1つの命令でコード全体をコピーし、コピーが完了する前に実行を開始します。^[5]

はさみ（またはスキャナー）

スキャナーはレプリケーターを倒すために設計されている。スキャナーはやみくもに攻撃するのではなく、標的を定めて攻撃する前に敵の位置を特定しようとする。これにより、レプリケーターのような倒しにくい敵に対してはより効果的になるが、デコイに対しても脆弱になる。スキャナーは通常、SPL 0命令でメモリを爆撃する。これにより、敵は大量のプロセスを作成するが、それらはさらに多くのプロセスを作成するだけで、有用なプロセスを遅くする。敵が遅くなりすぎて有用なことを何もできなくなると、メモリはDAT命令で爆撃される。スキャナーは一般に他のタイプの戦士よりも複雑であるため、より大きく脆弱である。^[6]

ワンショットは、最初のターゲットが見つかるまでコアをスキャンし、その後は攻撃戦略（通常はコアクリア）に永続的に切り替わる非常に単純なスキャナーです。ロイ・ファン・ラインのミュルミドン^[7]はワンショットの例です。

ストーン（または爆撃機）

爆撃機は、敵を攻撃しようと、コア内で一定間隔で「爆弾」を盲目的にコピーします。爆弾はDAT命令であることが多いですが、他の命令や複数命令爆弾が使用されることもあります。爆撃機は小型で高速であり、爆弾は便利な注意散漫の役目も果たすため、敵をスキャンする際に有利になります。爆撃機は、レプリケーターに対する耐性を高めるために、インプ スパイラルと組み合わせられることがよくあります。

吸血鬼（または罠猟師）

ヴァンパイアは、相手のプロセスを「ピット」と呼ばれる自身のコードの一部にジャンプさせようとします。ヴァンパイアは、ボンバーまたはスキャナーのいずれかをベースにすることができます。ヴァンパイアの主な弱点は、必然的にコードへのポインタをコア全体に散らばらせる必要があるため、間接的に簡単に攻撃できることです。また、プロセスがピットに到達するまでに余分なラウンドが必要なため、攻撃は遅くなります。PaulssonによるmyVamp ^[8]は、ヴァンパイアの例です。

インプ

インプは、 AKデュードニーによる史上初の戦士、インプ^{[9]にちなんで名付けられました。インプは、}命令ポインタの直前の唯一の命令を継続的にコピーする、単純な1命令の移動戦士です。インプは殺すのが難しいですが、攻撃にはほとんど役に立ちません。インプの用途は、簡単に大量に生成でき、他の戦士が殺されても生き残る可能性があるという事実にあります。

インプリング(またはインプ スパイラル) は、コアの周りに等間隔で配置され、交互に実行するインプで構成されています。リング/スパイラルの各アームのインプは、次のアームに指示をコピーし、次のアームですぐに再度実行されます。リングとスパイラルは、単純なインプよりも殺すのがさらに難しく、それらに対して保護されていない戦士を殺す可能性も (わずかですが) あります。インプ リングまたはスパイラルのアームの数は、コアのサイズと互いに素でなければなりません。

クイックスキャナー（またはq-scan）

クイックスキャナーは、非常に高速なアンロール スキャン ループを使用して、敵を早期に捕らえようとします。クイックスキャンはゲーム序盤の戦略であり、常にバックアップとして他の戦略が必要です。戦士にクイックスキャン コンポーネントを追加すると、他のクイックスキャナーなどの長い戦士に対するスコアが向上します。ただし、アンロール スキャンは限られた数の場所しかターゲットにできず、小さな敵を捕らえる可能性は低くなります。

コアクリア

コア クリアは、コア内のすべての命令を順番に上書きします。場合によっては、コア自体も上書きされます。コア クリアは、スタンドアロンの戦士としてはあまり一般的ではありませんが、爆撃機やスキャナーによる終盤戦略としてよく使用されます。

コア戦争戦略を理解することで、プログラマーは特定の目標を達成するための戦士を作成できます。革命的なアイデアは時々生まれますが、ほとんどの場合、プログラマーは既に公開されている戦士に基づいてプログラムを作成します。OptiMax などの最適化ツールやコアステップ最適化ツールを使用すると、より効果的な戦士を作成できます。

戦士は遺伝的アルゴリズムや遺伝的プログラミングによっても生成できる。この進化的手法を統合したプログラムはエボルバーと呼ばれる。Core Warコミュニティによっていくつかのエボルバーが導入され、小規模なコア設定の戦士の生成に重点を置く傾向がある。大きな成功を収めた最新のエボルバーはμGP ^{[10] [11]}で、最も成功したナノ戦士や極小戦士を生み出した。しかし、進化戦略は、より大きなコア設定での有効性をまだ証明する必要がある。^[12]

コア戦争は、自己複製プログラムであるクリーパーと、クリーパーのコピーを破壊する後続のプログラムであるリーパーに触発された。 ^{[13]クリーパーは}BBNのボブ・トーマスによって作成された。^[14]デュードニーはクリーパーとリーパーの起源を知らず、ダーウィンとショックとハップのワーム実験に由来する噂であると述べた。1984年のサイエンティフィック・アメリカン誌のコア戦争に関する記事^{[13]では、1961年に}ビクター・A・ヴィソツキー、ロバート・モリス、ダグラス・マキロイがベル研究所でプレイしたゲーム「ダーウィン」に言及している。

名前の「コア」という単語は、磁気コア メモリに由来しています。これは、廃止されたランダム アクセス メモリテクノロジです。この用語は当時も現在も、 Unix およびほとんどの Unix 系システムで、コア ダンプと呼ばれるワーキング メモリ ダンプ内のワーキング メモリを表す用語として一般的に使用されています。また、このようなシステムでコア ダンプに使用されるデフォルトのファイル名は、通常「コア」であるか、コアという単語を含んでいます。

レッドコード言語の最初の説明は、1984年3月にDGジョーンズとAKデュードニーによるコアウォーガイドラインで発表されました。^{[1]このゲームは、1984年5月にデュードニーが}サイエンティフィックアメリカンに書いた記事で一般に紹介されました。デュードニーは、1985年3月の「コンピュータレクリエーション」コラムでコアウォーを再検討し、^[15] 1987年1月に再び取り上げました。 ^[16]

国際コア戦争協会 (ICWS) は、デュードニーの最初の論文の 1 年後の 1985 年に設立されました。ICWS は 1986 年と 1988 年にレッドコード言語の新しい標準を公開し、1994 年に更新を提案しましたが、正式には新しい標準として設定されませんでした。^[17]とはいえ、1994 年の草案は広く採用され、拡張され、今日のレッドコードの事実上の標準の基礎となっています。ICWS は、マーク クラークソン (1985–1987)、ウィリアム R. バックリー (1987–1992)、ジョン ニューマン (1992–) によって指揮されましたが、現在^{[いつ? ]} ICWS は廃止されています。^[18]

0000 : ADD . AB # 4 , $ 3 0001 : MOV . F $ 2 , @ 2 0002 : JMP . B $ - 2 , $ 0 0003 : DAT . F # 0 , # 0           
            
           
            

Redcode はCore Warで使用されるプログラミング言語です。これは、Memory Array Redcode Simulator ( MARS)と呼ばれる仮想マシンによって実行されます。Redcode の設計は、1980 年代初期の実際のCISCアセンブリ言語に基づいていますが、実際のコンピュータ システムには通常見られない機能^{[あいまい]}がいくつか含まれています。

Redcode と MARS 環境はどちらも、実際のコンピュータやプロセッサの複雑さを排除した、シンプルで抽象的なプラットフォームを提供するように設計されています。Redcode は通常の CISC アセンブリ言語に似ていますが、「実際の」アセンブリに比べてかなり単純化されており、絶対的なメモリ アドレス指定はありません。

オリジナルの8つの命令は以下のように記述されます。後のバージョンではNOP、乗算、より複雑な比較が追加されました。^[19]

オペコードニーモニック引数アクション------- --------- ----- ----- ---------------------------------- 0 DAT B位置を値Bに初期化します。1 MOV A B Aを位置Bに移動する。2 ADD A BオペランドAを位置Bの内容に追加し、結果を位置Bに格納する。3 SUB A BオペランドAを位置Bの内容から減算し、結果を位置Bに格納する。4 JMP B位置Bにジャンプする。5 JMZ A BオペランドAが0の場合は位置Bにジャンプし、それ以外の場合は次の命令に進む。6 DJZ A B位置Aの内容を1減らす。位置Aに現在0が入っている場合は位置Bにジャンプする。それ以外の場合は次の命令に進む。7 CMP A BオペランドAとオペランドBを比較する。等しくない場合は次の命令をスキップする。等しい場合は次の命令を実行する。                      
    
                            
                           
                                    
                                    
                           
                               
                                      
                                       
                                       
                                    
                                     

ICWS '94 標準ドラフトでは、主に A フィールド間接参照を扱うためのアドレッシング モードが追加され、合計 8 つのアドレス モードになりました。

    # —即時$ —直接( $は省略可能) * — A -フィールド間接@ — B -フィールド間接{ — A -プリデクリメント付きフィールド間接< — B -プリデクリメント付きフィールド間接} — A -ポストインクリメント付きフィールド間接> — B -ポストインクリメント付きフィールド間接   
           
       
       
         
         
         
         

ゲームの実装の開発は、何年にもわたって複数の作者によって続けられてきました。このゲームには複数のバージョンがあり、^{[20]複数のプラットフォームに} 移植されています。たとえば、 SourceForgeにソースコードがあるオープンソースソフトウェアのpMARS、^[21]や、 Windows用のSDLベースのSDL pMARSなどがあります。^[22]

共通実装pMarsは、2000年から2021年の間にSourceForgeから35,000回以上ダウンロードされました。^[23]

• Core War ⚡ 究極のプログラミング ゲーム
• コア戦争情報ページ
• Redcode初心者ガイド
• 1994 年中核戦争標準案の注釈付き草案
• コアウォー書誌