コア戦争

『コア戦争』はプログラミングゲームのひとつである。専用に設計された仮想機械中で、互いに干渉しうるプログラム同士が戦うというもので、敵対するプログラムを終了させ、自分は生き残ってマシンを占領するのがゲームの目的である。仮想機械は『MARS』という名前で、戦闘プログラムは『戦士』"warriors" と呼ばれる。

ロボットバトルシミュレーションといった趣きのプログラミングゲームは他にもあるが、コンピュータの記憶装置そのものを戦場とし、プログラムが存在するメモリを上書きするなどして直接プログラム同士が戦う、という点がこの作品の特色である。なお「コア」は磁気コアメモリに由来する。

1. 概要
-----

初期化し無内容としたコアの上に複数のRedcodeプログラムを配置し動作させ、最後まで動作し生き残ったものを勝者とする。プログラムは自分の分身を作る、他者のコードを上書き破壊するなどして戦う。

MARSはコア上のプログラムを逐次実行する。コアは連続した番地を持つが、絶対番地を参照するコードは用意されていない。また、コアの番地の両端は連続している。初期のRedcodeはシングルプロセスであったが、現在ではMARSはタスク待ち行列  を持つようになり、SPL命令によって新規のプロセスを実行できるようになった。

2. 歴史
-----

//コア戦争//はCreeperと呼ばれるプログラムや、その後継で『死神』と呼ばれCreeper の複製を破壊するプログラムから着想を得ている。date=2010年5月}} パロアルト研究センターの Shoch と Hupp  らの説明によれば、Creaper は BBN のB. Thomas によって作られたという。Dewdney は　Creeper と Reaper の出自を知らず、Shoch と Hupp による Darwin ゲームとワーム実験に起源する噂としてこれに言及した。

また、発想の元としては、いずれもベル研究所所属の Victor A. Vyssotsky著者に名を連ねている), Robert Morris Sr. , ダグラス・マキロイ  らが1960年代に作ったDarwinというプログラミングゲームが挙げられることもある。1984年に A. K. Dewdney と D. G. Jones が「コア戦争ガイドライン」を発行し、同年DewdneyはScientific American誌の"Computer Recreations"でこのゲームを紹介した。日本でも同誌の日本版日経サイエンスの「コンピュータレクリエーション」コーナーなどで紹介され、一時はよく知られていた。

1984年、サイエンティフィック・アメリカン誌の『コア戦争』に関する記事がベル研究所の :en:Victor A. Vyssotsky、:en:Robert Morris Sr.、:en:M. Douglas McIlroy らによって 1960 年代に書かれた //Darwin// をそれにもかかわらず引用していた。

最初の Redcode 言語の記述は 1984 年の 3 月に :en:D. G. Jones と :en:A. K. Dewdney による『コア戦争ガイドライン』において発表された。このゲームはDewdneyによって書かれたサイエンティフィックアメリカン誌に 1984 年の 3 月に一般に紹介された。1985 年の 5 月、Dewdney は自身の "Computer Recreations" コラムにおいてコア戦争を再考し、また 1987 年 1 月にも取り上げた。

国際コア戦争協会  は Dewdney の記事の一年後、1985年に設立された。ICWSは1986年と1988年に Redcode 言語の新たな規格を出版し、新たな規格として非公式のセットを1994年に提案と更新を行った。にもかかわらず、1994年のドラフトは一般に採用、拡張され、今日のRedcodeのデファクトスタンダードへの基板を形成している。ICWS は Mark Clarkson 、William R. Buckley 、Jon Newman によって指揮されたが、現在は ICWS はもはや機能していない。

3. Redcode
----------

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

Redcode と MARS 環境は現実のコンピュータやプロセッサの複雑さなしに単純で抽象的なプラットフォームを提供するよう設計されている。Redcode は平凡なCISC アセンブリ言語に似せられているが、多くの点で実際のアセンブリ言語とは異なっている:

Redcode はごく少ない命令を持つ。ICWS-88 では 10、ICWS-94 では 18。
いずれのアセンブルされた命令は命令コードと二つの数値フィールドに分割される。数値は命令コードには定義されない。コードは命令全体の一部としてコピーだけされ、同等に比較される。
opcode と二つの数値フィールドに加えて、ICWS-94はいずれの Redcode 命令はデータのサイズを定義する『修飾子』を持つことを　を可能にする。さらに、いずれの数値フィールドは関連するアドレッシングモード持っている。ICWS-88は4つのアドレッシングモードを定義しており、ICWS-94 ではこれは8にまで拡張されている。
どの Redcode命令も同じ長さと実行時間を持つ。メモリは一命令単位で配置される。
すべての数はメモリサイズより小さい符号なし 整数である。それゆえ数とメモリ位置には一対一の対応がある。すべての演算はメモリサイズを法としたモジュラ演算で行われる。
相対アドレッシングのみが使われる。これはアドレス“0”は常に現在実行中の命令を指していて、アドレス“1”はその後ろの命令となっている。メモリの境界を超えたアドレスは空間の最初からに丸められる。このため、プログラムはメモリ上の絶対位置を知ることは出来ない。いずれのプログラムも自身の命令ポインタを持ついくつかのアクティブなプロセスを持っている。いずれのプログラムも1プロセスから開始するが、他のプロセスはSPL命令によって作られる。それぞれのプログラムのプロセスは交互に実行され、それゆえどのプログラムもそのプログラムが持つアクティブなプロセスの数に反比例した実行スピードになる。プロセスはDAT命令を実行した時か、ゼロで除算したときに死ぬ。プログラムはひとつもプロセスが残っていないときに死んだとみなされる。

4. 戦略
-----

戦闘プログラムは通常いくつかのおおまかなカテゴリに分類されるが、実際の戦闘プログラムではしばしば2からそれ以上のプログラムの振る舞いが一体化することがある。3つの基本的な戦略は三すくみとなっていることも知られており、これらのお互いに対する振る舞いはよく知られたプレイグラウンドゲームにおいての同名のものに近似する。

bomber ) は通常の間隔でコア内に無差別に『爆弾』を複製し、敵に命中することを期待する。爆弾はたいていはDAT命令だが、他の命令や複数命令の爆弾が使われることもある。BOMBER はプログラムを小さく早くすることができ、爆弾は便利な障害物を供給することもできるので、敵を検索するよりさらなる有利に立つことができる。コア戦争の歴史において二度目に発表されたのは、:en:A. K. Dewdneyによるbomberである[1]である。
replicator )は自身のコピーと実行を並列に繰り返し、最終的にコア全体をそのコードのコピーで埋め尽くす。replicatorを殺すのが難しいが、その敵を殺すのもしばしば困難になる。それ故replicatorは相手と引き分けることが多く、相手がreplicatorであった場合はなおさらである。replicatorの初期の例は:en:Chip Wendellによる[2]がある。
silkは非常に高速なreplicatorの特殊なもので、名前は:en:Juha Pohjalainenの[3]にちなんでいる。最も現代的なreplicatorはこのタイプである。Silk はコード全体のコピーを一命令で並列実行し、それが完了する前にコピーの実行を開始する。
scanner) は主にメモリをSPL 0命令で爆撃することでreplicatorに勝つために設計された。これは敵に何もしないがさらなるプロセスを作成するような多数のプロセスを作成させる。これは有用なプロセスの減速を引き起こす。敵がまともなことをできなくなるまで十分に遅くなったとき、メモリはDAT命令で爆撃される。scannerは闇雲に攻撃するのではなく、狙った攻撃を開始する前にその敵の発見を試みる。このことにより、replicatorのような倒すのが厄介な敵に対してより効果的になるが、おとりに対する脆弱さを放置することにもなる。Scanner はまた、一般的に他のタイプの戦士より複雑であり、それゆえ巨大で壊れやすい。 :en:P. Klineによる[4] は強い Scanner の一例である。
Vampire は敵のプロセスを『落とし穴』という自身のコード片にジャンプさせる。Vampire は Bomber や Scanner から派生できる。自身のコードへのポインタをコア全体にばらまかなければならないので間接的に攻撃を受けやすいということは、弱点としてよく知られている。攻撃は遅く、敵のプロセスを穴に落とすのに多くのラウンドを費やす。:en:Paulsson による[5] はVampire の好例である。
one-shot  はターゲットを最初に見つけるまでコアを探索し、それから主にコアをクリアする攻撃戦略へと切り替えるだけの、ごく単純な Scanner である。:en:Roy van Rijn による [6] はシンプルだが効率的な oneshot である。
Imp  はその唯一の命令を自身の命令ポインタの直前に複製し続ける、ごく小さく機動的な単一命令の戦士である。Imp は殺しにくいが、攻撃面でもほとんど無力である。これはそれが多数生成するのが容易であり、たとえ元の戦士が死んでも生き残りやすいという事実により利用されるだけである。
Imp ring  はコアにそって等間隔で配置され、交互に実行される Imp で構成されている。リングの腕に配置されたこれらの Imp は次の腕にその命令を複製し、それは直ちに実行が繰り返される。リングは単純な Imp よりさらに殺しにくく、これらに対して防御していない戦士を殺すチャンスがある。Impリングの腕の数は、コアのサイズに対して互いに素でなければならない。
quickscanner は繰り返されない非常に高速な探索ループを使用して序盤で敵の捕獲を試みる。高速探索は序盤の戦略で、常にバックアップとしていくつかの他の戦略が必要になる。『高速探索』部分を戦士に追加すると、長い戦士、例えば他の quickscanner に対して戦績が向上する。しかしながら、繰り返されないスキャンは限られた数の場所しか対象にせず、小さな敵は捕捉するのは難しい。
core clearはコアにあるすべての命令を、しばしば自身を含め連続的に上書きする単純な戦士である。Core clear は単独の戦士としてはあまり見られないが、Bomber や Scanner の終盤の戦略としてしばしば使われる。
bomb-doder は対 Bomber に特化されている。これは bomb を発見するまでコアをスキャンし、bomber は同じ場所にはすぐには再び攻撃しないであろうことを予想して、それからそのコードをそこにコピーする。

5. 『コア戦争』のプログラミング
-----------------

『コア戦争』戦略の理解に基づいて、プログラマはある目的を達成する戦士を作ることができる。戦士は『.red』拡張子をつけた ASCII 形式で保存される。たまに革新的なアイデアが舞い降りる……が、ほとんどの場合はプログラマはアイデアを得るためにすでに公開された戦士を利用する。OptiMax や core-step optimizer toolsのような最適化システムを使うと、よりコンパクトで効率的な戦士を作ることもできる。

戦士は遺伝的アルゴリズムもしくは遺伝的プログラミングにより生成することもできる。この進化技術を統合するプログラムは Core War Evolvers としても知られている。いくつかの小さく高速な evolver は『コア戦争』コミュニティで紹介されているが、より小さい『コア戦争』設定に焦点を当てている。大きな成功をした最新の evolver は、極小の KOTHs を生成した [8] である。とはいえ、進化戦略はより大きな丘でその効率の検証を未だ必要としている。

6. 派生形
------

CoreWars 8086 はオリジナルのコア戦争とよく似たゲームを実装している。Redcode のカスタマイズされた命令セットを使う代わりに、CoreWars 8086 戦士プログラムは 8086 アセンブリ言語によって書かれている。
Tierraはトマス・S・レイによって書かれたコア戦争の翻案で、生命システムのモデリングを利用する。
Avida は Tierra を足がかりにコア戦争を大きく派生させたもので、進化の過程を抽象化する。Christoph Adami, Charles Ofria, and Titus Brown によって作られた Avida は、進化についての科学研究に使われている。

7. 脚注
-----

8. 関連事項
-------

Crobots

9. 外部リンク
--------

[9]
[10]
[11]
[12]

9.1. ドキュメント
-----------

[13] プログラマおよび非プログラマに Redcode のイントロダクションを提供する。provides an introduction to Redcode for programmers and non-programmers alike.
[14]
[15]
[16]
The [17] コア戦争新人へのトップ10リンク

9.2. プログラム
----------

[18] はそのニューズグループの公式シミュレータ。is the official simulator of the newsgroup [19]. [20] は SDL ベースのpMARS の Window ポートで、ICWS-94 ドラフト規格と互換性がある。
[21] は GUIベースの Windows 用コア戦争シミュレータで、拡張 ICWS-94 と互換性がある。
[22] - 対話的なチュートリアルを含むコア戦争の Windows 用シミュレータとデバッガ。拡張 ICWS-94 と互換性がある。
[23] - Core War MARS for .NET。拡張 ICWS-94 と互換性がある。
[24] - アセンブラ、ディスアセンブラ、シミュレータ、トーナメントのイタリア製キット。ICWS-86 規格。
[25] - Javaで書かれた CoreWars 8086 ゲームエンジン。

9.3. 大会
-------

[26] "King of the Hill" コア戦争大会をホストし、情報とソフトウェアを提供している。
[27] 他の数多くの Core War hills を主催している。
[28] いくつかの infinite Core War hills を主催している。
[29] Sumo 大会ランキングを実装する。