Core Wars（月刊ASCII 1987年9月号6）

月刊ASCII 1987年7月号に続きCore Warsの特集があった。

扉にある写真をスクラップする。








以下本文記事をスクラップする。

はじめて読むREDCODEアセンブラ
　Core Warsは,現在のコンピュータシステムのほとんどが,それを基調とした思想の上に築いているvon Neumannのストアドプログラム方式を,もっとも具体的に示してくれるシステムにちがいない.
　ストアドプログラム方式では,プログラムとデータは主記憶装置に格納され,プログラムカウンタで示される命令が,主記憶より1つずつ取り出されて実行される.
　中央処理装置は,主記憶上に置かれた「買い物競争の命令カード」のようなものを順番に拾っては,その通りに実行していく。これは,結果的には,データや命令であるカードを置き換えたり,次に拾うカードの位置を変更することだけに限られている.
　それは、はなはだ簡単なルールであるが,簡単であるだけに、純粋に思考的な作業空間を育むのに適した環境を提供するものである。
　しかし,現実のコンピュータシステムでは,こうした実際の中央処理装置の活動を直接意識することは,あまりない.アセンブリ言語などで,それを指示することはあっても,命令を主記憶の中に配置するといった,もっともセンシティブな部分については、オペレーティングシステムや処理系が独占してしまっているのである.
　Core Warsは,いわばCore Viewerもいうべき性格を持っている.
　プログラムのどのステップが,実行され,どのようにメモリの中に作用するか?あるいは,自己増殖し,または,ちょっとしたデータの行き違いで,どのような突然変異種を生みだし,それが,具体的には,どのようなプログラムのステップの結果として発生するかを見て,考える場所を提供してくれる.
　これは,ストアドプログラム方式が提供しうる,もっとも知的でイマジネーションを刺激する部分に違いないのだ。
　Core Warsのプログラムは,REDCODEと呼ばれる専用のアセンブリ言語で書かれる.今回は,このREDCODEによるプログラミングについて,触れてみることにしよう.

アドレッシングモードについて
　REDCODEの言語仕様について,リストページに掲載した.DJN命令,CMP命令,SPL命令の少々分かり難い点についても説明しているので,参照してほしい.
　さて,アセンブリ言語の特徴は,機械命令の機能を直接操作できる点にあるが,プログラミングを行っていく上で,重要な意味を持っているものとしてアドレッシングモードがある.アドレッシングモードが理解いただければ,だいたいのプログラムは,読めるといっても過言ではない.
　REDCODEには,次の4つのアドレッシングモードがある.
1. イミディエイト(即値)
2. ダイレクト(直接)
3. インダイレクト(間接)
4. オートデクリメント・インダイレクト(自動減算・間接)
　イミディエイトは,数値(またはラベル)の前に"#"を付けたものであり,#3は,数値の3そのものを表す.また,#-5は,-5そのもの(8,000番地バージョンでは,7,995)を表す.
　ダイレクトは,数値(またはラベル)の前に"$"を付けるか,何も付けない形で表わしたものであり,「その命令のあるアドレス+指定された値」となる.たとえば,

1230		MOV		#4455,10

は,4,455という値を,1,230+10=1,240番地に格納することを意味している
　インダイレクトモードは,“@"を付加することで表し,ダイレクトに参照される番地の内容を、さらにダイレクトモードのアドレスとみなすことを意味する.たとえば,

1230		MOV		#2233,@10
	：			：
1240		DAT		700

のような状態で,1,230番地を実行すると,1,230+10=1,240,　1,240番地の内容は,700であるから,1,240+700=1,940番地に,2,233の値を格納することになる.
　また,オートデクリメント・インダイレクトは,“＜”を付けて表す.これは,インダイレクトとほぼ同じであるが,実効アドレスを計算するためのポインタの値(前の例では,700)を,命令を実行する前に1減算する.たとえば,

1230		MOV		#2233,<10
	：			：
1240		DAT		700

という場合,1,230+10=1,240,　1,240番地の内容は,700であり,1,240+7001=1,939番地に,2,233の値を格納する.この時,700番地の内容は,699に変化する.
　さて,REDCODEのアドレッシングについて,だいたい理解いただけただろう-か.では,次の練習問題をやってみてほしい。

		DAT		2
		DAT		10
		DAT		100
		[	?		]

　 　この[?]の部分に,以下の(1)～(5)のステートメントがあり,それを実行した場合,メモリの内容は,それぞれどのように変化するだろうか.ちょっとした頭の体操になる.答はリストページにある。

(1)		ADDT		-3,-3
(2)		ADDT		@-3,-3
(3)		ADDT		@-3,@-3
(4)		ADDT		@-3,<-3
(5)		ADDT		<-3,<-3

　

自己増殖とMICEのアルゴリズム
　MICEは,1986年8月に行われた第1回国際Core Warsトーナメントの優勝プログラムである.
　Chip Wendellという作者によるこのプログラムは,ある明解な目的のもとに作られたプログラムであった.それは,できるだけ早く自分自身のコピーを作り,増殖するということである.この点で,MICEは,他のどの参加プログラムよりも「攻撃的」でなかったにもかかわらず,ほとんどのプログラムを生存不可能にした.
　MICEは,わずか8行のプログラムであり,Core Warsのゲームがスタートすると同時に,モニタの上に次々とコピーを作っていくのがうかがえる.まさに,MICEそのものであり,仮に相手のプログラムが,かなり強力なパワーを持っており,一時的に繁殖したMICEをかたっぱしから殺して2～3匹しか残らなかったとしても,ふと目を離している間に,ふたたび数十匹に増えていたりする!
　現在のところ,自己増殖の考え方が,かなり重要なテクニックであることは,確かなようである.
　自己増殖の方法論そのものは、けっして難しいものではない、自分のプログラム本体をデータとみなし,ある番地に転送する.そして,その番地にSPLしてやればよいのだ.一般的なプログラムで,データを連続して転送してやるように,カウンタを設けて,繰り返し処理をしながら,1wordずつ転送するわけである.
　つまり,問題は,具体的なコーディングとなるわけであるが,MICEのソースは,次のようなものとなっている.

SPTR		DAT		0
START		MOV		#12,SPTR
LOOP		MOV		@SPTR,<DPTR
		DJN		LOOP,SPTR
		SPL		@DPTR
		ADD		#653,DPTR
		JMZ		START,SPTR
DPTR		DAT		833

　これは,どのように動作するのだろうか.
　まず,STARTからプログラムは始まる.SPTRに12を入れているが,この数は,これから転送しようとしているword数に相当する.次に,SPTRで示される番地からDPTRで示される番地へ,MOVとDJN命令を使用して転送を行っている.転送先は,DPTRが833なので,仮にSTARTのあるアドレスが1番地であるとすると,STARTのコピーされる先は,828番地となる.無事転送処理が終ると,SPL命令を実行して,コピーに「命」を吹き込む.そして,DPTRに653を加えて転送先を変更し,ここまでの処理を繰り返すわけである.
　ここで,注目してほしいのは,転送をプログラムの後ろから順番に行っている点である.これは,REDCODEがオートデクリメントは持っているが,オートインクリメントは、持っていないことによる.また,ループカウンタと転送元アドレスを共用している点もキレイに処理されている.
　何でもないようで,これだけコンパクトな自己増殖のシーケンスは,なかなか書けるものではない.
　ところが,MICEは自己増殖プログラムとして洗練されたアルゴリズムで書かれているだけでなく,ちゃんとCore Warsのプログラム戦士としての性格も備えているのである!
　まず1つは,7行目のJMZについてのものである.4行目にDJNがあり,SPTRが0になっていなければ,そこから下へはプログラムの制御は降りてこないわけで,このJMZは,一見無意味なように思える.実は、これは,「乗っ取り防止用のわな」になっているのである.
　MICEの自己増殖の手続きは,プロセスの数が64個になったとたんSPLによるプロセスの増加は,行われなくなるが,本体のコピーは,続けられる.すると,この空き巣のMICEプログラムに,乗っ取り型のプログラムが飛び込んでくる可能性が,非常に高くなってしまう.これが,JMZによって,少なくともプログラムの後半に飛び込んだものについては,カバーできる.また,0爆弾などによって本体が破壊され始めている可能性があることを知り,自爆することによって,他の健康なMICEの増殖作用を早める働きをする.
　また,2行目の#126,なかなか深長な意味合いをもったコーディングのようである.MICEは,8wordのプログラムであり,また,最初のDAT文はコピーする必要がないとすると,これは、たかだか#7で済むように思える.つまり,余分な転送をしているわけである.
　これは,何を意味しているのかというと,一般的な0爆弾の発射ロジックよりも,はるかに簡単な方法で,0爆弾を落しているのと同じ効果をもたらしているのである.これは,MICEの占有している番地よりも後ろの4wordが,初期状態かDATに相当する内容であった場合,新しくMICEが増殖する時に,転送先でMICE本体よりも長い12wordを破壊できる.
　この12wordや,転送先番地の初期値である833(これは,子,孫となっていくにしたがって少ない値となる),そして,転送先番地の増加分である653が,どのようなバランスではじき出されたかは,現在のところ分からない.

MICEを倒すには?
そして,次の最強プログラムは?
　当面の目標をMICEに置いて,プログラムを考えるのも良いだろう.実際のところ,相手がMICEと分かっていても,このプログラムを倒すのは容易ではない.
　仮にMICEを駆逐するプログラムができたとしても,MICEとともに昨年のトーナメントで優勝を争ったCHANG1を抹殺できるかどうかは,保証の限りではない.
　しかし,Core Warsは,どうやら,プログラムがどのように動作するかを考え,それに対して,どのようなアルゴリズムを対応させるかを考えるゲームのようである.MICEに勝てるプログラムを,そして,さらに強力なCore Warsウォリアーを作ってほしい.

35年経っても面白い。頭の体操になる。誰かCore Warsを再現するプログラムを作ってはくれないだろうか。希望としては2つのプログラムを対戦させるのではなく3つ以上のプログラムを対戦させる戦国時代のようなゲームをしてみたい。