Core Wars（月刊ASCII 1987年7月号12）

Core Wars 面白かった。こいうのが好きだった。将来自分でもCore Warsの猿真似プログラムを作りたいのでスクラップする。

コア戦争を始めよう
　“Core"は,1950年代の初めにMITで実用化された主記憶用の記憶媒体である.小さなビーズ状の磁心の中にワイヤを通した仕掛けであり,高集積度の半導体メモリが一般化した今日も,主記憶装置を“Core"と呼ぶことがしばしばある.
　Core Warsは,すなわち,コンピュータの主メモリ空間を舞台にした戦争ゲームである。
　その基本的な考え方は、あっけないほどシンプルなものだ.
　メモリ空間にA,B2つのプログラムが存在するとしよう.Core Warsのシステムでは,2つのプログラムが同時に実行される.これらのプログラムは,互いに相手のプログラムの動作をストップさせることを目的にしている.つまり,2つのプログラムを戦わせて,最後まで生きていたプログラムが勝ちとなる.
　他のプログラムの動作を止めてしまう(殺す)のは簡単である.そのプログラムの本体を,破壊してしまえばよいのだ.
　たとえば,相手のプログラムの命令部分に数値0の爆弾を落す.MOV命令を使って,即値データの0を相手のプログラムの存在する番地に転送してやればよいのだ.プログラムが破壊されていることを知らずに,その番地を実行しようとしたプログラムは,命令例外のエラーとなり,動作をストップするだろう.
　数値0爆弾を使うもっとも簡単なプログラムとして,図1の一寸法師(DWARF)がよく知られている.
　たかだか4wordからなるこのプログラムは,メモリ空間全体にわたって,5wordおきに数値0爆弾を投下していくものである.CoreWarsのメモリ空間は,通常のコンピュータのそれと異なり,もつとも高い番地(たとえば,7999番地)は,もっとも低い番地(0番地)に,サイクリックに連続している.つまり,8000番地は,0番地と解釈される.
　一寸法師は,こうして自分自身のいる番地の付近にも数値0爆弾を投下することになる.ところが,わずか4word足らずの一寸法師の本体は、ちゃっかり爆弾と爆弾の投下間隔の間に入っているので自分自身の爆弾を浴びることはない.
　一寸法師は,小さくても強力なプログラムである.何の対処もしていない“善良”なプログラムは,例外なくこの爆弾の雨の洗礼を受けてエラー終了してしまうことになるだろう.
　Multiplanも,一太郎も,dBASEも,他のどんな優秀なアプリケーションソフトウェアも,この短いアルゴリズムの敵ではない.
　Core Warsで勝つためには,プログラムは,“Warriors"に変身しなければならないわけである.
　そこでは、プログラムは生き物のように自己の存在を主張し,猛然と他のプログラムに攻撃を仕掛け,あるいは,メモリ上で繁殖しようとするのである.
　さて,Core Warsがマニアの間に知られるようになったのは,その考案者であるA.K.Dewdneyが,3回にわたってScientific American誌の彼のコラムで,これを紹介してからのことである。
　その中で,彼は,Core Warsに似たことは,現実のシステムにおいてもありうるし,これに似たエピソードの中からこのゲームを思い付いたと述べている.また,主記憶容量48KbytesのAppleから,ゼロックス社パロアルト研究所のネットワークシステムまで、さまざまなシステムに見られた,プログラムの興味深い振舞いについても紹介している.
　すなわち,Core Warsの思想的な背景は,まとまったプログラムを書いたことのある人間なら1度はイメージするであろう,1つの可能性についてのものである.
　それは,プログラムとは,機械命令とデータからなる原生生物であり,それ自身のための挙動を示すことができるといった意味合いのものだろう.

プログラム戦士を作るには
　Core Warsでは,A.K.Dewdneyの考えた架空のマシンのアセンブリ言語によって,競技用のプログラムを記述する.それは,表1のような命令セットを持った簡単なアセンブリ言語であり,REDCODEと呼ばれる.
　作られたプログラムは,REDCODEアセンブラによって翻訳され,架空のマシンの上で実行される(図2).そのシミュレータは,MARSシステムと呼ばれる.
　MARSシステムは,同時に2つのプログラムの実行される環境,つまり,疑似的なマルチタスキング環境である.
　また,MARSシステムは,ゲームの進行状況をコンピュータのディスプレイでモニタリングできるばかりか,そこで,簡単なデバッギングも行える.
　本誌では,今回のCore Warsの紹介に続いて,実際にCore Warsを楽しむために,REDCODEアセンブラと,MARSシステムを,誌上で紹介していく予定である.
　このシステムは,ICWS(International Core Wars Society:「ICWS日本支部開設のお知らせ」参照のこと)で提供しているものを移植する.
　すなわち,プログラム戦士を作りたい場合には,REDCODEの文法に従ってプログラムを書けばよいことになる.
　対応機種としては,9月号でPC-9801シリーズ対応版を作成するほか,これと同時かそれ以降で8bitマシンにも移植していく予定である.
　Core Warsの特徴のひとつは,REDCODEのソースレベルでマシンに依存しない点だろう.基本的に,他機種のユーザーともゲームを行うことができる.Z80 CPUのマシンで開発したプログラムが,80286 CPUのマシンで開発したプログラムを破る可能性も十分にある.
　このゲームに参加するプログラマは,MARSシステムという,まったく共通のシステム環境の前にいるわけである.
　ただし,MARSシステムのメモリ空間は,従来,8000番地までであったのが,現在,16K番地,32K番地,および64K番地までの3種類のモデルに拡張されようとしている.その結果,実メモリの小さなマシンでは,大きなメモリ空間のMARSシステムが,簡単に実現できない可能性もある.
　これは,小さなメモリ空間のMARSシステムでは,小さなプログラムの方が有利であり,レーダーや自己修復機能を持つような,シャレたプログラムが作りにくいためのようである.つまり,よりエキサイティングなゲームを楽しむためのマイナーチェンジといったところだろう.IBMPC用の64K番地バージョンは,現在,ICWSでデバッグ中とのこことである.

キリングプログラムの戦略
　それでは,具体的なCore Warsプログラムの素顔を,少しだけ見ていくことにしよう.
　先に,非常に短くて強力なプログラム,一寸法師(DWARF)を紹介した.これよりもさらに短くて,場合によっては、さらに強力なプログラムに小鬼(IMP)がある。
　このプログラムの長さは,実に1命令しかない!それは,次のようなものである。

		MOV		0,1

　REDCODEの文法に従うと,この1命令は,相対番地0の内容を,1番地先に転送することになる.つまり,小鬼は,自分自身を1番地先にコピーし続けるプログラムということになる.
　小鬼は,最大限のスピードでメモリ空間を突っ走る,はなはだ乱暴なプログラムである.このプログラムの通ったあとには,そのコピーが延々と残るだけとなってしまう。やがて,そのスピードにものをいわせ,相手のプログラムを頭から塗りつぶしてしまうわけだ.
　この小鬼への対抗措置として,A.K.Dewdney氏は,小鬼地獄(IMP PIT)と呼ばれるプログラムがあるとしている.それは,次のようなものだ.

	loop	MOV		#0,-1
		JMP		loop

　このプログラムは,即値の0を,1番地前に書き続けるというものである.-すなわち,小鬼がちょうど小鬼地獄の1番地前に自分自身をコピーしたタイミングで,小鬼地獄が1行めの命令を実行すれば、みごと小鬼をやっつけてしまうことができるというわけだ.しかし,このプログラムは、完全とは言えないようである.タイミングが1つずれるとやっかいなことになる.
　小鬼地獄が,小鬼に変身してしまうのだその場合,敵と見方の2重身小鬼となってメモリの中を走りはじめる.小鬼対抗措置としては,Small-C版のMARSシステムの作者であるKvin Bjorke氏によると思われる小鬼返し(ANTI IMP)という,次のアルゴリズムもある.

	init	MOV		#0,-5
	loop	CMP		#0,-6
		JMP		loop
		MOV		#0,-5
		MOV		#0,-6
		MOV		#0,-7
		MOV		#0,-8
		JMP		init

　CMPという命令は,第1オペランドと第2オペランドを比較して,等しくない場合に,次の番地の命令をスキップするというものである.すなわち,このプログラムは次のような動きをする.
　まず,1行めが実行されると,それよりも5番地前を初期化する.これに続く2行で,この番地が書き換えられたかどうかを監視している.もし書き換えられていたら,小鬼,あるいはこれに類するものが来たとして,適当な位置に数値0爆弾を4発ほど食らわせるというわけだ.小鬼返しはCore Warsの考案者の考えた小鬼地獄よりも防御がかたく,ゲームをドローにする可能性が少ない.
　しかし,この小鬼返しに対抗する手段も考えられている.それは,小鬼返し返し(ANTIANTI IMP)と呼ばれる次のアルゴリズムである.

	loop	MOV		4,@leng
		ADD		#1,leng
		JMP		loop
	leng	DAT		5
		MOV		0,1

　何のことはない、これはニセの小鬼で,その素性は一寸法師と同じものである.
　一寸法師といえば,こいつにはどう対処したら良いのであろうか?
　相手が,一寸法師と分かっていれば,一寸法師の数値0爆弾の隙間に入ってしまうか,あるいは,爆弾の落下位置の移動速度と同じスピードで自分自身を複写し,制御を移して行くといった類の手法をとれる.そうするうちに,一寸法師の本体を破壊してしまえば良い.
　しかし,このようなアプローチでは,それほど面白い変化は望めないだろう.
　実のところ,ここに現在のCore Warsの仕様の中で,もっとも興味深い部分が隠されている。

　それは,SPL命令による兄弟プロセスの生成だ
　SPL命令は,そのオペランドで指定した番地に兄弟のプロセスを発生させ,自分自身は,SPLに続く命令を実行し続ける.すなわち,1つのプログラムが,協力しあう2つのプロセスを持つことができるようになるわけである(図3).
　プロセスの数は、1プログラムあたり,最大64個を持つことができる.ただし,プロセスの増加に比例して、プロセスごとの実行速度は低下していくことになるので注意する必要がある.
　兄弟プロセスと実行サイクルの関係によっては,先ほどの小鬼返しも,小鬼に対して完璧な防御力を持つとは限らなくなってくるだろう.
　第1回CoreWarsトーナメントで上位にランキングされたプログラムは,いずれも,このSPL命令を巧妙に使ったものとなっている.
　たとえば,優勝を争った2つのプログラム,CHANG 1とMICEは,それぞれ異なるストーリーのもとに作られたプログラムである.
　CHANG 1は,典型的な戦闘型のプログラムと言えるだろう.それは,3つの兄弟プロセスによるエンジンを持っている.まず,小鬼地獄を本体の前面に防御用のシールドとしており,自分自身も後方に小鬼送出装置を用意している.そして,本体中央から数値0爆弾を効率よく発射するというものだ.
　これに対して,MICEは,わずか7ステップからなる非常に繁殖力のすぐれた,自己増殖型のプログラムであった.SPL命令によって,Core Warsプログラムは,生命力のようなものが,かなり重要となってきたようである.トーナメントの優勝は、次のようなちっぽけなプログラムがさらってしまったわけである(＜は,オートデクリメントのアドレッシングを意味する).

	go	MOV		#12,6
	loop	MOV		@-2,<5
		DJN		loop,-3
		SPL		@3
		ADD		#653,2
		JMZ		+5,-6
		DAT		833

　繁殖力とは逆の意味で,面白い動きをしたのが,次のPARASITEである.このプログラムは,メモリを検索して敵を探すように作られているが,いざ敵を見つけてからの動作は,なかなかユニークである.これは,言ってみればウイルスのようなプログラムである.どのような活動をするか追って見ていただきたい。

		DAT		#11
		DAT		#-2
	go	SPL		5
		JMZ		2,@-3
		SPL		@-4
		ADD		#1,-5
		JMP		-3
		JMZ		2,@-6
		SPL		@-7
		SUB		#1,-8
		JMP		-3

　A.K.DewdneyによるとCore Warsプログラムの次の世代は,環境を感じ取って、具体的な番地を直接攻撃するものであり,破損部分に対する自己修復を行うプログラムでなければならないという
　こうした趣向のプログラムも作られているが,Core Warsのプログラミングは,まだ,スタイルとして確立されておらず,MICEのようなシンプルなプログラムを有利にさせているようである.
　コーディングそのものは,積極的なコメントとラベル付けをすれば,普通のアセンブリ言語程度には書けるようになる.問題は,イマジネーションなのだろう.
　また,実際にREDCODEアセンブリ言語でプログラムを書き,実行してみると,このゲームの魅力の50%以上は,ゲームとしてどちらのプログラムが勝つかといった点ではなく,メモリ空間の上で,アルゴリズムがどのように振舞うかをモニタから観察する点にあることが分かる.
　Core Warsは,文字どおり「コア戦争」として,プログラム同士で熾烈な戦いを行うというベースを持っているものの,「コアの中でたわむれる」という要素も少なからず持っている.そのあたりに,Core Warsというゲームの課題があると同時に,他のどのようなゲームでも期待できない可能性があるのは間違いないだろう.
　より,戦闘的な,あるいは戦略的な,そして美しく、最後まで生き残るだけの柔軟性をそなえたプログラムは,どのようにして作られるだろうか.