コア戦争

『コア戦争』（コアせんそう、英：Core War または Core Wars）はプログラミングゲームのひとつである。専用に設計された仮想機械中で、互いに干渉しうるプログラム同士が戦うというもので、敵対するプログラムを終了させ、自分は生き残ってマシンを占領するのがゲームの目的である。仮想機械は『MARS』（火星にも掛けているが、Memory Array Redcode Simulatorの頭字語）という名前で、戦闘プログラムは『戦士』"warriors" と呼ばれる。

pMARS シミュレータ上で実行されているコア戦争の試合。見ての通りコアをグラフィカルに表示している。

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

概要

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

MARSはコア上のプログラムを逐次実行する（複数のプログラムが存在する場合は、それぞれのコードを同時に動作させる）。コアは連続した番地を持つが、絶対番地を参照するコードは用意されていない。また、コアの番地の両端は連続している（コアの大きさはCORESIZEで定義されるが、CORESIZE番地は0番地と同一である）。初期のRedcodeはシングルプロセスであったが、現在ではMARSはタスク待ち行列 (task queue) を持つようになり、SPL命令によって新規のプロセスを実行できるようになった（待ち行列には各プロセスの命令ポインタに当たるtask pointerが登録される）。

歴史

コア戦争はCreeperと呼ばれるプログラムや、その後継で『死神』(Reaper)と呼ばれCreeper の複製を破壊するプログラムから着想を得ている。^[要出典] パロアルト研究センターの Shoch と Hupp (CACM, vol. 25, no. 3, 1982) らの説明によれば、Creaper は BBN のB. Thomas によって作られたという。Dewdney は　Creeper と Reaper の出自を知らず、Shoch と Hupp による Darwin ゲームとワーム実験に起源する噂としてこれに言及した。

また、発想の元としては、いずれもベル研究所所属の Victor A. Vyssotsky^[1](Multics計画のベル研側の責任者であり、Introduction and Overview of the Multics SystemなどといったMulticsの重要な文献の(共)著者に名を連ねている), Robert Morris Sr. (ロバート・T・モリスの父), ダグラス・マキロイ (パイプの提案者で、Unix用のユーティリティも多く書いている) らが1960年代に作ったDarwin（en:Darwin (programming game)）というプログラミングゲームが挙げられることもある^[2]。1984年に A. K. Dewdney と D. G. Jones が「コア戦争ガイドライン」を発行し、同年DewdneyはScientific American誌の"Computer Recreations"でこのゲームを紹介した。日本でも同誌の日本版日経サイエンスの「コンピュータレクリエーション」コーナーなどで紹介され、一時はよく知られていた。

1984年、サイエンティフィック・アメリカン誌の『コア戦争』に関する記事^[3]がベル研究所の 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 による『コア戦争ガイドライン』(Core War Guidelines)^[4]において発表された。このゲームはDewdneyによって書かれたサイエンティフィックアメリカン誌に 1984 年の 3 月に一般に紹介された。1985 年の 5 月、Dewdney は自身の "Computer Recreations" コラムにおいてコア戦争を再考^[5]し、また 1987 年 1 月にも取り上げた。^[6]

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

Redcode

→詳細は「en:Redcode」を参照

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

ICWS-94 スタイルの Redcodeでアセンブルされる。
Assembled ICWS-94 style Redcode

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

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

いずれのプログラムも自身の命令ポインタを持ついくつかのアクティブなプロセスを持っている。いずれのプログラムも1プロセスから開始するが、他のプロセスはSPL命令によって作られる。それぞれのプログラムのプロセスは交互に実行され、それゆえどのプログラムもそのプログラムが持つアクティブなプロセスの数に反比例した実行スピードになる。プロセスはDAT命令を実行した時か、ゼロで除算したときに死ぬ。プログラムはひとつもプロセスが残っていないときに死んだとみなされる。

戦略

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

• bomber (『爆弾魔』もしくは 『岩』(rock、ジャンケンの『グー』の意)) は通常の間隔でコア内に無差別に『爆弾』を複製し、敵に命中することを期待する。爆弾はたいていはDAT命令だが、他の命令や複数命令の爆弾が使われることもある。BOMBER はプログラムを小さく早くすることができ、爆弾は便利な障害物を供給することもできるので、敵を検索するよりさらなる有利に立つことができる。コア戦争の歴史において二度目に発表されたのは、en:A. K. DewdneyによるbomberであるDwarfである。

• replicator (『複製者』もしくは『紙』(paper、ジャンケンの『パー』の意))は自身のコピーと実行を並列に繰り返し、最終的にコア全体をそのコードのコピーで埋め尽くす。replicatorを殺すのが難しいが、その敵を殺すのもしばしば困難になる。それ故replicatorは相手と引き分けることが多く、相手がreplicatorであった場合はなおさらである。replicatorの初期の例はen:Chip WendellによるMiceがある。^[10]
  • silkは非常に高速なreplicatorの特殊なもので、名前はen:Juha PohjalainenのSilk Warriorにちなんでいる。最も現代的なreplicatorはこのタイプである。Silk はコード全体のコピーを一命令で並列実行し、それが完了する前にコピーの実行を開始する。^[11]

• scanner(『監視者』もしくは『はさみ』(scissor、ジャンケンの『チョキ』の意)) は主にメモリをSPL 0命令で爆撃することでreplicatorに勝つために設計された。これは敵に何もしないがさらなるプロセスを作成するような多数のプロセスを作成させる。これは有用なプロセスの減速を引き起こす。敵がまともなことをできなくなるまで十分に遅くなったとき、メモリはDAT命令で爆撃される。scannerは闇雲に攻撃するのではなく、狙った攻撃を開始する前にその敵の発見を試みる。このことにより、replicatorのような倒すのが厄介な敵に対してより効果的になるが、おとりに対する脆弱さを放置することにもなる。Scanner はまた、一般的に他のタイプの戦士より複雑であり、それゆえ巨大で壊れやすい。^[12] en:P. KlineによるHe Scans Alone は強い Scanner の一例である。

• Vampire (吸血鬼、pit-trapper)は敵のプロセスを『落とし穴』という自身のコード片にジャンプさせる。Vampire は Bomber や Scanner から派生できる。自身のコードへのポインタをコア全体にばらまかなければならないので間接的に攻撃を受けやすいということは、弱点としてよく知られている。攻撃は遅く、敵のプロセスを穴に落とすのに多くのラウンドを費やす。en:Paulsson によるmyVamp5.4 はVampire の好例である。

• one-shot (一撃) はターゲットを最初に見つけるまでコアを探索し、それから主にコアをクリアする攻撃戦略へと切り替えるだけの、ごく単純な Scanner である。en:Roy van Rijn による Myrmidon はシンプルだが効率的な oneshot である。

• Imp (小鬼。en:A. K. Dewdney によって最初に発表された戦士、Imp に由来する) はその唯一の命令を自身の命令ポインタの直前に複製し続ける、ごく小さく機動的な単一命令の戦士である。Imp は殺しにくいが、攻撃面でもほとんど無力である。これはそれが多数生成するのが容易であり、たとえ元の戦士が死んでも生き残りやすいという事実により利用されるだけである。
  • Imp ring (『小鬼の輪』、Imp spiral) はコアにそって等間隔で配置され、交互に実行される Imp で構成されている。リングの腕に配置されたこれらの Imp は次の腕にその命令を複製し、それは直ちに実行が繰り返される。リングは単純な Imp よりさらに殺しにくく、これらに対して防御していない戦士を殺す(ささいな)チャンスがある。Impリングの腕の数は、コアのサイズに対して互いに素でなければならない。

• quickscanner (『高速な探索者』)は繰り返されない非常に高速な探索ループを使用して序盤で敵の捕獲を試みる。高速探索は序盤の戦略で、常にバックアップとしていくつかの他の戦略が必要になる。『高速探索』部分を戦士に追加すると、長い戦士、例えば他の quickscanner に対して戦績が向上する。しかしながら、繰り返されないスキャンは限られた数の場所しか対象にせず、小さな敵は捕捉するのは難しい。

• core clear(『コア抹消』)はコアにあるすべての命令を、しばしば自身を含め連続的に上書きする単純な戦士である。Core clear は単独の戦士としてはあまり見られないが、Bomber や Scanner の終盤の戦略としてしばしば使われる。

• bomb-doder は対 Bomber に特化されている。これは bomb を発見するまでコアをスキャンし、bomber は同じ場所にはすぐには再び攻撃しないであろうことを予想して、それからそのコードをそこにコピーする。

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

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

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

派生形

• CoreWars 8086 はオリジナルのコア戦争とよく似たゲームを実装している。Redcode のカスタマイズされた命令セットを使う代わりに、CoreWars 8086 戦士プログラムは 8086 アセンブリ言語によって書かれている。

• Tierraはトマス・S・レイ(ICWS の初期メンバー)によって書かれたコア戦争の翻案で、生命システムのモデリングを利用する。

• Avida は Tierra を足がかりにコア戦争を大きく派生させたもので、進化の過程を抽象化する。Christoph Adami, Charles Ofria, and Titus Brown によって作られた Avida は、進化についての科学研究に使われている。

脚注

[脚注の使い方]

1. Victor Alexander Vyssotsky
2. 英語版Wikipediaの当該記事によれば、さらにデニス・リッチーの名が挙げられることもあるが関わっていない、とのことである。
3. Dewdney, A. K. (May 1984). “In the game called Core War hostile programs engage in a battle of bits.”. Scientific American. https://corewar.co.uk/dewdney/first.htm 2008年11月18日閲覧。.
4. Jones, D. G.; Dewdney, A. K. (1984年3月). “Core War Guidelines”. 19 November 2008閲覧。
5. Dewdney, A. K. (March 1985). “A Core War bestiary of viruses, worms and other threats to computer memories.”. Scientific American. https://corewar.co.uk/dewdney/second.htm 2008年11月18日閲覧。.
6. Dewdney, A. K. (January 1987). “A program called MICE nibbles its way to victory at the first Core War tournament.”. Scientific American. http://corewar.co.uk/dewdney/third.htm 2008年11月18日閲覧。.
7. Doligez, Damien; Durham, Mark (8 November 1995). “Annotated Draft of the Proposed 1994 Core War Standard”. 19 November 2008閲覧。
8. Metcalf, J. A.. “A Brief History of Corewar”. 19 November 2008閲覧。
9. Mintarjo, W. "Intro to Art in '88: Paper - Stone - Scissors Trilogy."
10. The First International Core War Tournament
11. replicators? - Phoenix & TimeScape source
12. Metcalf, J. A. "Anatomy of the Scanner, A Basic Introduction."
13. Bvowk, Sasha & Fizmo: An Evolutionary Approach Generates Human Competitive Corewar Programs

関連事項

• Crobots

外部リンク

• Core War - the war of the programmers
• The Core War Info page
• Core War Frequently Asked Questions
• Annotated Draft of the Proposed 1994 Core War Standard

ドキュメント

• The Beginner's Guide to Redcode プログラマおよび非プログラマに Redcode のイントロダクションを提供する。provides an introduction to Redcode for programmers and non-programmers alike.
• Annotated Draft of the Proposed 1994 Core War Standard
• The Core War FAQ
• The Core War Bibliography
• The Top 10 links for Corewar Newbies コア戦争新人へのトップ10リンク

プログラム

• pMARS はそのニューズグループの公式シミュレータ。is the official simulator of the newsgroup rec.games.corewar. SDL-pMARS は SDL ベースのpMARS の Window ポートで、ICWS-94 ドラフト規格と互換性がある。
• CoreWin は GUIベースの Windows 用コア戦争シミュレータで、拡張 ICWS-94 と互換性がある。
• ARES - 対話的なチュートリアルを含むコア戦争の Windows 用シミュレータとデバッガ。拡張 ICWS-94 と互換性がある。
• nMars - Core War MARS for .NET。拡張 ICWS-94 と互換性がある。
• XRK - アセンブラ、ディスアセンブラ、シミュレータ、トーナメント（ネットワークをサポート）のイタリア製キット。ICWS-86 規格。
• corewars8086 - Javaで書かれた CoreWars 8086 ゲームエンジン。

大会

• KOTH.org "King of the Hill" コア戦争大会をホストし、情報とソフトウェアを提供している。
• KOTH@SAL 他の数多くの Core War hills を主催している。
• Koenigstuhl いくつかの infinite Core War hills を主催している。
• The Corewar DynaHill Sumo 大会ランキングを実装する。