Hatena::ブログ(Diary)

やねうらお−ノーゲーム・ノーライフ このページをアンテナに追加 RSSフィード

GT-Rの買取ならここですわ。どこよりも高く買取ってもらえるはず。お勧め!GT-R 買取
電王戦出場記念! 書籍化されたで! 監修したで!(`ω´) 絶版なってしもた Kindle版で復活!! 記事書いたで!
解析魔法少女美咲ちゃん マジカル・オープン!

YaneuLabs / やねうら王公式 / やねうらおにメール / twitter / プロフィール

 

2013-09-04 CodeIQで結城先生が出題されたCrossingが神がかっていた件

[] CodeIQ結城先生が出題されたCrossingが神がかっていた件  CodeIQで結城先生が出題されたCrossingが神がかっていた件 - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  CodeIQで結城先生が出題されたCrossingが神がかっていた件 - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


CodeIQ挑戦者数が400人超えという異例の事態になったCrossingとはどんな問題だったのか。twitterでも恐ろしい勢いで拡散され、最終日に100人を超えるチャレンジがあった、この問題。一体どこにそんな魅力があったのかについて考えてみる。


まず、このように注目されるためには満たすべき条件が二つある。


繁盛する飲食店を考えてもわかるように、まず美味しくなければならない。CodeIQで言うと、問題として良問でなければならない。解答後の達成感がなくてはならない。


次に、飲食店なら、その店に入ってみようという気にさせなければならない。入りにくそうなお店でも、料理さえ美味しければその後口コミで広がることもあるだろうが、それだと繁盛するまでに時間がかかりすぎる。だからCodeIQで言うと、まず問題を解いてみようという気にさせなければならない。


このどちらが欠けても駄目である。この問題はこの二つの条件を見事に満たしているのである。言うのは簡単だが、実際、この二つの条件を同時に満たすのは極めて難しい。


結城先生の問題は、まず、やってみようという気にさせる。「あれ?これなら俺なんかでもチョチョイのチョイで解けるぞ」と思わせる。そういう入りやすさ、取っ付きやすさにかけては天下一品である


問題「交差点をすばやく数えよう!」


f:id:yaneurao:20130904144718p:image


絵も凄くわかりやすい。絵を見ただけで問題が想像できる。上段に1,2,3,4,5,6,7,8,9と数字が書いてあって、それを適当並べ替えものが、下段にある。同じ数字同士を線でつないだときにできる交点の数を数えるんだなと。それって、下段のそれぞれの数字について、その数字の左側にある自分数字より大きい数字の個数を合計したものなんじゃ…。

絵を見ただけで解法までわかってしまう。「おお、これなら俺でも1分でできるぜ!」そう思わせるだけの大きな釣り針が垂らされている。


そしてCodeIQログインして挑戦ボタンを押してしまうのであるが、それが罠なのである。これが実際にやってみるととんでもない問題で、与えられる頂点数は314159個もある。314159にどんな意味があるのかは知らないが、たぶん、3.14159(円周率の一部)であり、かつ、素数ということなんだろう。


そして3秒未満で計算できないと評価5はあげませんと書いてある。314159個もあると、O(n^2)なアルゴリズムだと3秒未満に収めるのは困難を極める。(OpenMP+OpenCLで2982msで解くプログラムを書いた強者がいるようだが)


そこで、何らかの工夫をしないといけない。交差点の数は逆転数(inversion)に等しいので、逆転数の数え上げ(「counting inversions」で検索すると出てくる)に帰着する。


方法1) マージソートを使う。ソート済みの部分数列a,bがあったとして、それをマージするときに逆転数がどう増えるのか考えてみるとわかる。O(n * log(n))


方法2) 逆転表を使う。これは、自分よりも左の方に、自分よりも大きい要素が何個いるかが書かれている表である。表は普通に考えると作成にO(n^2)の時間がかかるが、うまくするとO(n * log(n))で済む。(Knuth, "The Art of Computer Programming, Vol.3", 5.1.1. Exercise 6.を参考に)


方法3) Binary Indexed Tree (Fenwick Tree)を使う。O(n * log(n))で求まる。


私は「この逆転数を求める問題、20年ぐらい前に見たことあるなぁ…」と思いながらも、アルゴリズム教科書を開くのはルール違反かと思って、初心にかえったつもりで自力で求めるコードを書いた。上の方法1)〜3)のいずれとも違う方法だ。たぶん、名もないアルゴリズムである。(力技とも言う)


以下にそのコードを貼り付けておく。今回の問題に対しては優れた解答とは言いがたいが、この考え方はこの考えかたで汎用性があるので他のことに応用できそうである


もちろん、これ以外にもいろいろ方法はあると思う。いずれにせよ、この問題に対しては、このように複数の解法が考えられること、そして、どのような解法で解答したとしても、ナイーブな実装では3分以上かかる処理を3秒未満で処理が完了するようになったという改善効果に対する驚き、そして、得られる達成感のようなものがある。


この意味においても、たいへん素晴らしい問題で、解いたあとに思わずツイートしたくなる。「俺はやったぞ!お前もやってみろよ!」と。


結果的に見ても、挑戦者430人中198人もの人が評価5であった。この意味において、多くの人が達成感を味わい、そして、それをまたツイートしていたことが伺える。これが、このCrossingという問題に400人以上が挑戦した理由であると思う。


※ おまけ。以下、私の書いたコード

	// 配列を256要素ごとにスライスし、そのスライスされた部分において、
	// そこより左側(配列の添字の小さいほう)にX/256以上の値の個数がいくつあるのか(簡略化された逆転表)を
	// 事前計算しておき、これを利用してカウントを高速化している。
	// (C#で書いたところ、1秒未満に収まっている。)

	var sw = new Stopwatch();
	sw.Start();

	// 配列aに値を格納。
	var a = new List<int>();
	using (var sr = new StreamReader("crossing.txt"))
	{
		while (!sr.EndOfStream)
			a.Add(int.Parse(sr.ReadLine()) - 1);
			// 0オリジンでないと気持ち悪いので0引いておく。
	}

	// aのなかで、ある数xがどの位置にあるかを与える配列を用意。
	var b = new int[a.Count];
	for (int i = 0; i < a.Count; ++i)
	{
		b[a[i]] = i;
	}

	// cはlen×lenの正方行列。部分計算した配列。
	// a[ p/256 ]より左側にある、X/256より大きな値の個数が c[ ((p>>8)+1)*len + X/256 ]に格納されているものとする。
	var len = (a.Count >> 8) + 2;
	var c = new int[len * len];

	for (int i = 0; i < a.Count; ++i)
	{
		var p = (i >> 8) + 1;
		var y = a[i] >> 8;
		c[p*len + y] ++;
	}
	// ↑で求まったのは、単に(p,y)の個数だから、これを縦方向と横方向に重層する必要がある。
	// 縦方向の重層
	for (int p = 1; p < len; ++p)
		for (int y = len -2; y >= 0; --y)
			c[p*len + y] += c[p*len + ( y + 1 )];
	// 横方向の重層
	for (int y = len - 2; y >= 0; --y)
		for (int p = 1; p < len; ++p)
			c[p * len + y] += c[(p - 1) * len + y];

	long sum = 0;
	for (int i = 0; i < a.Count; ++i)
	{
		// そこの数Xより配列の左側にあるXより大きな数の個数をカウントする。

		// step 1)  p(iを切り捨てた値)より左側にある、y(xを繰り上げた値)以上の数の個数を加算
		var x = a[i];
		var p = i >> 8;
		var y = (x >> 8)+1;

		sum += c[p*len + y];
		y <<= 8;
		p <<= 8;

		// step 2) iより左にあるx 〜 y未満の数の個数を加算
		for (int j = x + 1; j < y && j < a.Count; ++j)
			if (b[j] < i) sum++;

		// step 3) a[p]以降にある、y以上の数の個数の加算
		for (int j = p ; j < i ; ++j)
			if (a[j] >= y) sum++;
	}

	Console.WriteLine(sum + "," + sw.ElapsedMilliseconds/1000);

yaneuraoyaneurao 2013/09/04 15:54 修正。評価5は1秒未満ではなく3秒未満でした。twitterのほうで結城先生から直々にご指摘をいただきました。

解答の出力が秒単位で、1秒未満切り捨てだったので、「0」が出力されるようにしなきゃ!と考えていたので勘違いしました。謹んでお詫び&訂正させていただきます。

   2013/09/09 18:41 挑戦したけどそもそものトータルが間違えてて評価1でしたorz

解く手順などは近しい手順だったのですが、phpで処理したら単純解では3分経っても終わらなかったので、別の解法に挑戦してみて、何か解けたっぽい!と思って提出。

勤務時間が近づいていたので、確認も取らずに出したのが間違いでした…恥ずかしくて名前が書き込めない…ッ

yaneuraoyaneurao 2013/09/17 08:42 競技プログラミングの神様からコメントがあったので引用。

> Hideyuki Tanaka ‏@tanakh
> こんだけでいい気がする。
> solve xs = sum $ zipWith (\i x -> max 0 $ x - i) [1..] xs
https://twitter.com/tanakh/status/379736079751847936

> Hideyuki Tanaka ‏@tanakh
> 競技プログラミング的にはわりと頻出系じゃまかろうか(´・_・`)
https://twitter.com/tanakh/status/379736582669889537

2013-06-28 CODE VS 2.1が大変なことになっている件

[] CODE VS 2.1が大変なことになっている件  CODE VS 2.1が大変なことになっている件 - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  CODE VS 2.1が大変なことになっている件 - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


「CODE VS 2.1予選問題は悪問ではないか」(→ http://d.hatena.ne.jp/yaneurao/20130625 )において、「せめて決勝に進んだら交通費宿泊代ぐらい出して欲しい。」とぼやき半分で書いたのだが、中の人が真夜中のテンションで突然こんなことを言い出した。


f:id:yaneurao:20130628034705p:image


なんとSILVERまで交通費を出すとか…!SILVERまでって30人もいるんですけど…。参加者ほとんど全員じゃないですか…。


交通費が出るなら、1位〜3位の賞金、いまの半分でも良かったんじゃないですかね。交通費出してもらえて同じ問題にチャレンジしてた仲間が2〜30人ぐらい集まるなら、これすごく楽しいイベントだよ!



こりゃ、私も参加すればよかったなー。

予選3位でOzyさんにはパワーを送っておいたので、どうか私の代わりに優勝してきていただきたく。



でも、そのあと、CodeVSの中の人が青ざめている件。


f:id:yaneurao:20130628034704j:image



ともかく、来年は要チェックですな。


CODE VS 2.1公式

http://codevswc.jp/jpn/

2013-06-25 CODE VS 2.1予選問題は悪問ではないか

[] CODE VS 2.1予選問題は悪問ではないか  CODE VS 2.1予選問題は悪問ではないか - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  CODE VS 2.1予選問題は悪問ではないか - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


プログラム系のサイトを巡回している人ならばうざいぐらいにバナー広告が出てきていて、当然ご存知だとは思うのだけども、いまCODE VS 2.1というプログラマ世界一決定戦というプログラミング競技が開催されている。


CODE VS 2.1公式

http://codevswc.jp/jpn/


予選は2013年6月27日まで。予選ランキングの上位8名が決勝に進め、決勝は1位の賞金が50万円、2位が30万円、3位が20万円である


問題をパッと見た限り、私なら予選通過は余裕なので、時間があればやろうと思っていたのだけど、問題の作りがいまひとつよろしくない。これについては長くなるので後述する。


そもそも決勝に進出しても私には3位に100%入る自信はない。まあ、たぶん問題の性質から言って3位ぐらいなら入れるとは思うが、1日勝負だとその日の閃きとか体調にも左右されるので過信は禁物である。3位に入れなければ交通費宿泊代とマシン代で大赤字である。そもそも優勝賞金少な過ぎない?どう見ても広告費のほうがお金かかってるよね。せめて決勝に進んだら交通費宿泊代ぐらい出して欲しい。


Short Coding ~職人達の技法~

Short Coding ~職人達の技法~


そんなことを思っていたら、ショートコーディング本のOzyさんがチャレンジ開始。(今月の5日ごろの話)


Ozy「いま私の使っている最高性能のPCが、Let's noteなのでもっと速いマシンを買いたいんですが、XeonとCorei7ならXeon買ったほうがいいですか?」

私「Xeonはdualに出来るのが特長で、singleで使うならそれと同じアーキテクチャCore i7シリーズとほぼ同等の性能しか出ません。並列度の高いプログラムを動かすのであれば、Core i7搭載のPCを2台用意するほうがコスパに優れています。」


Ozy「そうですか、じゃあCore i7-3970Xにしときます。」

私「えっ。いまならHaswell搭載PC×2のほうがコスパ(電気代も含めて)が良かったりしませんか…」


Ozy「もうポチっちゃいました^^;」

私「…」


その3,4日後にそのマシンが到着したようで、Ozyさんが予選ランキング1位に!(現在3位)


これくらいで1位になれるなら私も挑戦しようかと思ったのだが(Ozyさんのプログラムについて詳しくは知らないが、XXXとかXXXとかをやっていないということはわかっている)、どうせならGPGPUで並列化したい。だけど、Tesla K20X、まだ90万円ぐらいするんだよね。もう少し下がったら買おうと思っていたのだが…。



CUDA 5.5になってからDynamic Parallelismという機能が搭載された。この機能自体、あまり取り沙汰されていなくて知らない人がほとんどだと思うけど、この機能ホント凄くて、従来、GPUでの計算結果をCPU側にいったん戻していたような処理が、GPUからGPUスレッドを直接実行できることが出来るようになって、CPU側に処理を戻さなくて済む(場合がある)。


今回の問題のような探索処理をGPUで処理しようとするとき、このDynamic Parallelismが驚異的な威力を発揮する(と私は思う)わけだが…手元に実験できる環境がないので知らん。だもんで、この件は、話半分に聞いておいて欲しい。


まあ、いまTesla K20Xを買ってまでチャレンジしたくはないという私の個人的な事情はさておき、今回の問題が悪問だと言う根拠は、以下の通り。(他の解答者へのヒントになるといけないのでアルゴリズムに関する部分はぼかして書く)


ブロック(パック)の配置も左2升が空白のときにx=-2とかに置けるだとか、プログラムをいたずらに複雑化するだけなのでないほうがいい。


ブロックサイズも1×2固定とかにして回転をなくし、かつサイズを固定しても競技性は変わらなかったと思う。


ブロックが消える条件が結構ややこしい。縦横斜方向の2升の合計とかで良かったのではないか


・点数計算がややこしすぎる。お邪魔ブロックとか、発火数カウントとか要らない。単にチェイン数だけの勝負でも競技性は変わらなかったと思う。


・フィールドが3種類も要らない。1種類だけで十分。


・1回の制限時間が長すぎる。フィールドsmallのみで、15分ぐらいで十分。3時間かけて生成された解答に対抗するにはこちらも(同じ程度のプログラムであれば)3時間PCをフル稼働させないといけない。


アルゴリズムにも工夫の余地がほとんどない。(まだ競技が終わっていないので詳しいことは書かないが)


・公平性を期すなら、他の競技プログラミングのようにサーバーサイドでユーザーのプログラムをコンパイルして実行してくれるほうが望ましい


など、競技性を損なわない形でもう少しとっつきやすく、かつ、公平な形に出来たんじゃないのかなぁというのが正直な感想


予選スコアを見ると上15人ぐらいだけが本気で、あとの人は形にすらなってない感がある。まともなスコアをサブミットしている参加人数も30人ぐらいしか居ないし、仕様が複雑すぎて手をつける気にもならないのが現状ではなかろうか。


もう少しとっつきやすくして、参加者を増やさないと競技にならない。いまの仕様なら自動ぷよぷよのほうがまだとっつきやすいだろう。


逆に言えば、まだ参加者は少ないので明日明後日で頑張れば予選突破ぐらいは出来るんじゃないだろうか。みんな、いまからがんがれ!すごくがんがれ!

2013-01-25 古くて新しい自動迷路生成アルゴリズム

[][] 古くて新しい自動迷路生成アルゴリズム  古くて新しい自動迷路生成アルゴリズム - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  古くて新しい自動迷路生成アルゴリズム - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


最近、ゲーム界隈ではプロシージャルテクスチャー生成だとか、プロシージャルマップ生成だとか、手続き的にゲーム上で必要なデータを生成してしまおうというのが流行りであるが、その起源はどこにあるのだろうか。


メガデモでは初期のころから少ないデータでなるべくど派手な演出をするためにプロシージャルな生成は活用されてきたが、ゲームの世界でプロシージャル生成が初めて導入されたのは、もしかするとドルアーガの塔(1984年/ナムコ)の迷路の自動生成かも知れない。


なぜ私が迷路のことを突然思い出したのかと言うと、最近、Twitterで「30年前、父が7年と数ヶ月の歳月をかけて描いたA1サイズの迷路を、誰かゴールさせませんか。」というツイートが話題になっていたからである


f:id:yaneurao:20130125090434j:image



f:id:yaneurao:20130125090418j:image:w400


f:id:yaneurao:20130125090426j:image:w400


f:id:yaneurao:20130125090427j:image:w400


この迷路を見て「ああ、俺様も迷路のことを書かねば!俺様しか知らない(?)自動迷路生成のことを後世に書き残さねば!」と誰も求めちゃいない使命感がふつふつと湧いてきて、明日は大事なプレゼンがあるというのにかなりの長文になるであろうこの記事を書きだしたわけである。読者諸氏におかれましては「ああ、またいつもの病気か」とぐらいに思っておいていただきたい。


余談ではあるが大事なことなのでいま書いておくとだな、年が明けてからと言うもの、私が書く記事、書く記事にたくさんはてブをしていただき、たくさんのPVがあったのは本当にブロガー冥利に尽きるというものなのだが、アマゾンの商品の紹介をほとんどしていないものでアマゾンのアフィリ料はほとんど入ってこない。昨年のアフィリ収入は数年前と比較すると1/10のすらない。



f:id:yaneurao:20130124004101j:image

写真提供 : 女装する人がひたすら脱毛について語るブログ ゆきにゃん( http://yukinyan.info/ )


「うわっ…私のアフィリ料、低すぎ…?」



ほれ見ろ!鹿目まどかさんもアフィリ料があまりに少なすぎておもわずオシッコちびってしまったではないか!(えっ。これオシッコじゃないの?)



お前たち、わかったら、下のまどかさんでも、このブログの上に貼りつけてある右端の本でもいいから、クリックしてアマゾンに飛んで、10万円ほど無駄遣いしてくるんだぞ!






冗談はさておき。




ドルアーガの塔で迷路を自動生成しているのは「プロシージャルに生成して、遊ぶたびにライブ感を!」という試みではなく、単にROM容量が少なく、マップのための容量が惜しかったからである。(生成されるマップは毎回同じである。)


「容量が惜しい」とは言っても、下図のように柱と柱の間の壁の有無だけなので1フロアにつき垂直方向の壁17*9 + 水平方向の壁18*8 = 153 + 144 = 297ビット。これが60フロア分で17820ビットすなわち2223バイトあれば収まる。


ドルアーガの塔 アーケード Floor1

f:id:yaneurao:20130125090416p:image


ドルアーガの塔のROMは32KB×2だったように思う。これはマッピーの基板が2000枚ほど余っていて、それを流用するためにドルアーガの塔を作ったので、マッピーのとき仕様を引きずっているのだと思われる。2223バイトが本当に惜しかったのかどうかは私にはよくわからない。


そもそもマップをよーく見ると、柱から上下左右のいずれか一方向に柱が倒れたかのように壁が存在するので倒れた方向2ビット×柱の数でよく、上記の半分ぐらいで収まる。そう考えると本当に1KB強のメモリが惜しかったのだろうか…という疑問がなくはないのだが。


f:id:yaneurao:20130125090417p:image



さて、ドルアーガの塔のようなゲームの迷路を自動生成する場合、良い迷路とはどのような迷路だろうか?


「良い迷路」を言葉で定義するのは難しいが、明らかにまずい例を一つ挙げることは出来る。


壁の閉ループ(袋小路)はまずい。ダメ絶対!


ドルアーガの塔では壁を壊すためのアイテム(マトック)をゲーム開始時には主人公が持っていないので、袋小路に主人公が出現すると詰んでしまう。


あと、迷路はある程度入り組んでいないといけない。鍵と扉の出現位置はランダム(だと思う)が、宝箱は主人公の開始位置に出現する。宝箱の出現条件を満たし、宝箱を回収して、鍵を取って扉に入るわけだが、これらの移動距離があまりに短いとゲームとしてつまらない。


この入り組み加減を実現するために、通路がループになっているものを禁止する。ここではそのようなループのことを「開ループ」と呼ぶことにしよう。開ループがあると、ある地点からある地点への経路が複数できてしまうので入り組み度が下がる。開ループを禁止すれば、ある地点からある地点への最短経路は一意に定まる。ゆえに、解(開始位置から扉への経路)の唯一性も保証される。


入り組み度を上げるための方法は他にもいろいろあるが、専門的になりすぎるので割愛する。


あと、迷路がワンパターンではないこと。これも重要なファクターである。左上が入り口で右下が出口であるとき、どの迷路も真ん中あたりを通過する経路を選べばゴールできるだとか、特徴が似通っているのはよろしくない。


ともかく、そのような視点で見たときに、上図のマップは非常によく出来ている。入り組み方とかが芸術的とも言える。


ドルアーガの塔の画面はマッピーと同じく横スクロール型なのでマップ全体がプレイヤーに見えているわけではない。ある程度スクロールさせないと鍵や扉の位置がわからず、鍵を拾ってから扉に移動するまでに壁を壊せないなら、かなり回りこまないといけないことも多い。このへん、ゲームとしてうまく出来ている。


このようなマップはどのようにすれば生成できるだろうか?というのを考える前段階として、迷路の自動生成に関する一般的な手法をいくつか紹介する。


私の記憶によると、創刊号付近のマイコンBASICマガジン(30年前か…)にBASICで書かれたPC-8001用の迷路自動作成プログラムが載っていたと思う。小学生だった私はそれをせっせとPC-6001用に移植して走らせたのを覚えている。


そのアルゴリズムは確か、いわゆる穴掘り法と呼ばれるもので、画面上のランダムな位置から開始して、適当に掘り進み(2コ先が通路でないなら掘る)、現在地点の四方向とも掘り進めなくなれば(2コ先×4方向がすべて通路なら)、いままで掘ってきたところを一つずつ戻っていき(掘った経路は覚えている)、そこからまた掘っていくというアルゴリズムである


迷路自動生成アルゴリズム

http://www5d.biglobe.ne.jp/%257estssk/maze/make.html



f:id:yaneurao:20130125090433j:image



穴掘り法は入り組んだ迷路が生成されるのだが、開始点から放射状の迷路が出来るので、大きな迷路だとあまり評判はよろしくない。


穴掘り法以外のアルゴリズムとして棒倒し法、壁のばし法などがある。(上のURLを参考に)

それらは出来がいまひとつなのでここでは紹介しない。


それらとは一線を画すアルゴリズムとしてクラスタリングアルゴリズムというのがある。


クラスタリングによる迷路作成

http://apollon.issp.u-tokyo.ac.jp/~watanabe/tips/maze.html


f:id:yaneurao:20130125090430j:image


f:id:yaneurao:20130125090431j:image


f:id:yaneurao:20130125090432j:image



クラスタリングと言ってもPCを複数台用意して…みたいな話とは全く違って、単に部屋に番号をつけておき、壁を壊すときに同じ番号(同じ仲間)にするというアルゴリズムである



このアルゴリズムは実に明快で、実装しやすい。また、開ループ・閉ループが作られないということの証明が容易で、教育的にも好ましい。


ただ、それぞれの壁に対して乱数によって一定確率で壊していいか(その壁に隣り合うのは異なる部屋番号か)を判定することを繰り返すようなアルゴリズムになっているので、大きな迷路だとなかなか最後のほうの壁が壊れなくて時間がかかるかも知れない。(まだ壊していない壁だけを配列に持っておき、そこだけを調べればもう少し効率的だが…。)


あと、迷路の入り組み加減はどうなんでしょう…。壊していい壁がランダムに壊されていくようなモデルなので、比較的癖のない迷路になるんですかね。


以上のことを踏まえた上で、ドルアーガの塔の迷路生成アルゴリズムに踏み込んでいく。


『ドルアーガの塔』編(『ドルアーガの塔』研究室)

http://www.druaga.to/qanda_tod.html


f:id:yaneurao:20130125090435j:image


上の書き方はアルゴリズムとして少しわかりにくいので私が以下に書きなおす。


【定義】

「壁つきの柱」とはその柱の上下左右のうち1箇所以上すでに壁がつけてある柱のこと。

「壁なしの柱」とはその柱の上下左右のうち壁がまだつけてない柱のこと。


1. 画面左上の柱から順番に調べていく。壁付きでない柱に対してだけ以下の2.〜4.の処理をして壁を伸ばす。

2. いま注目している柱から壁を伸ばす。0〜3の乱数により、それに相当する方向(0:上,1:右,2:下,3:左)に壁を作る。

3. 伸ばした壁が外壁か、壁つきの柱に到達したなら終了。

4. 0〜2の乱数(0:進行方向左、1:まっすぐ、2:進行方向右)により、いま注目している柱から壁をさらに伸ばす。3.に戻り繰り返す。


参考動画として次の動画を挙げておく。


FC版 ドルアーガの塔 FLOOR1 マップ生成手順

D

ただし、3.で伸ばすとき自分自身(上記2.〜4.で処理中の柱)にはぶつからないようにという条件が必要のようだ。(ぶつかると閉ループが出来てしまう)


また「(3方向とも処理中の柱であったなら)一つ前の柱に戻ってやりなおしたような気がします」と遠藤さんはおっしゃっているのだが、一つ前の柱に戻っても下図のようになっていると何度やっても行き止まりになってしまう。


f:id:yaneurao:20130125090419p:image


まり、一つ前の柱に戻ってやりなおすという処理だとまずく、そういう処理はしていないと私は思うのだが、もしかするとたまたまそういう形の乱数は発生せず、うまく迷路生成が出来ているのかも知れない。


ただ、自分自身にぶつかった場合はその壁は作らずに処理を終了させる場合、その周囲に次図のように開ループが出来てしまうことがある。(緑の線で書いた経路)


f:id:yaneurao:20130125090420p:image


今回生成した壁すべてをキャンセルして、再度元の柱からやりなおすような処理にすれば良いのだが、生成しなおすのが馬鹿らしいので、生成中の柱による袋小路に突っ込んでしまった場合は、生成した壁は消さずにひとつ戻る。その柱の3方向が生成中の柱ならばさらにひとつ戻る。(以下繰り返し)


というように、生成した壁は消さずに柱をいくらでも戻っていくようなアルゴリズムになっている必要があると思う。


さて、このアルゴリズムで生成した迷路に開ループと閉ループが存在しないことを証明しなければならないが、この証明が結構やっかいなので簡単な説明だけをする。


それぞれの柱に着目した場合、その柱から伸びいている壁は1つに定まる。つまりこのアルゴリズムで迷路を生成した場合、柱の本数だけ壁が存在する。


f:id:yaneurao:20130125090417p:image


なぜなら、上記1.で壁なしの柱から壁を伸ばしていき、どこかに当たった時点で停止するので棒倒しのように、壁にはそれに帰属する柱が定まるというわけだ。


また伸ばしていくとき自分自身には衝突しない(閉ループができない)ようにしている。


いま下図の赤い矢印が壁だとして、ここに緑の破線のような壁を作って閉ループが作れるかどうかを考えてみる。


f:id:yaneurao:20130125090421p:image


緑の破線の壁は3つであるが、棒倒しのように倒せる柱は2つしかない。つまり、閉ループになっていない柱と壁のつらなりに対して、このアルゴリズムでは閉ループが追加されることはない(倒せる柱の数が1つ足りないから)ことが保証されている。ゆえに閉ループは出来ない。


次に、開ループが出来ないことを証明しよう。たとえば1本の柱のまわりに開ループをつくるとする。以下図のようになるが、この中央の柱をどちらかに倒さなければならないので開ループにならない。(赤い矢印は壁で、ここが閉ループに見えますが、実際はどこかの壁が開いていると考えてください。この赤い壁による閉ループの内側では、ある二点に対して経路が複数あるのでこれは開ループになっていると言えます。)


f:id:yaneurao:20130125090422p:image


同様に下図の場合もまんなかの2本の柱をどのような組み合わせで倒しても開ループが壊れてしまう。


f:id:yaneurao:20130125090423p:image


下図も同様。中央の4本で閉ループを作っていいのなら開ループが出来るのだが、閉ループを作れないことは証明済み。


f:id:yaneurao:20130125090424p:image


このように開ループを作ってもその内側にある柱から絶対に1つは壁が伸びてくるので開ループは出来ない。


迷路作成アルゴリズムには棒倒し法というのがあって(あまり質のいい迷路が出来るわけではないので取り上げなかった)、棒倒し法で閉ループ・開ループが作られないという証明は上記と同様にして出来るのではないかと思う。



ドルアーガの塔の迷路生成アルゴリズムで閉ループ・開ループが作られない証明が得られたので、次にドルアーガの塔のフロア60の話に移ろう。


遠藤さんの話を思い出そう。

・フロア番号(1〜60)を乱数のseedとして生成していた。

・乱数のseedを255にすると「整然とした迷路になった」。これをフロア60に使うことにした。


あと、

・乱数は線形合同法で生成している。

これは別のところで遠藤さんがおっしゃっていたと思う。


ドルアーガの塔 アーケード Floor 60

f:id:yaneurao:20130125090425p:image


上図がフロア60である。もう棒がどちらに倒れているかは図示しなくてもおわかりだろう。すべて左に倒れている。すなわち、「0〜3の乱数により、それに相当する方向(0:上,1:右,2:下,3:左)に壁を作る」ときに、3が出続けたというわけだ。


0〜3の乱数なので発生させた乱数を4で割った余りだろう。


線形合同法は下位ビットの乱数としての精度が悪いことが多いのでビットシフトをしてまんなか付近のビットを取り出すこともあるが、たぶんそれはやってなくて、255をseedにして乱数を発生させ、下位2ビットを取り出すと3ばかりが出てきたのだろう。


線形合同法はもともと下位ビットの乱数としての精度は悪いのだが、当時の事情を考えると、それだけではない気がする。


ドルアーガの塔ではCPUはMotorola社のMC6809で動いていたからMUL(乗算)はあっても除算はなく、除算のルーチンは結構面倒なので除算せずにビットマスクで済ましてあったのではなかろうか。


すなわち、線形合同法の次式に対して、

f:id:yaneurao:20130125090436j:image


Mを2のN乗にする。(こうすればビットマスクで済む)


MC6809のMULは8ビット×8ビットが16ビットで結果が得られる。(Aレジスタ×Bレジスタ = Dレジスタ)


MUL一回で求めようとすれば、上式のAは8ビット、Xnは前回の乱数(8ビット)になってしまい、乱数の周期が極めて短くなってしまう。さすがにこれは無いと思うのだが、ともかく、Xnの初期値がseedで、これが255だと、0〜3の乱数を発生させたときに3ばかりが出続けたということのようだ。


あと、剰余を求めるコストが馬鹿にならなかったということで思い出したが、「0〜2の乱数(0:進行方向左、1:まっすぐ、2:進行方向右)により、いま注目している柱から壁をさらに伸ばす。」という処理をするために0〜2の乱数を発生させなければならないが、発生させた乱数を3で割った余りを求めるのは嫌なので、4で割った余り(これならビットマスクで得られる)を求め、それが3だったなら乱数発生からやりなおす、というような手法が取られることがある。


このとき、やりなおすのではなく、得られた数値が3だったなら1とみなすようにすれば、0と2が出る確率がそれぞれ25%で、1が出る確率が50%の乱数になる。ドルアーガの塔では、直進方向の壁を確率高めに生成したほうが迷路っぽくなると思うので、もしかしたらそういう処理になっているかも知れない。[要検証]


ともかく、ドルアーガの塔の迷路生成についての解説が一通り終わった。


上記のアルゴリズムは遠藤さんのオリジナルのようなのだが、現代でも十分通用する手法だと思う。

このアルゴリズムの優秀さに私は感心すると同時に、現在にこういった手法が受け継がれていないことを残念に思う。


迷路の自動作成の話題としては最近ではイラストを与えて、それを迷路化するのが流行っているようなのだが、これについて書こうと思っていたらすっかり出かける時間になってしまった。以下のサイトを紹介してこの記事を終わる。


Maze Design

http://www.cgl.uwaterloo.ca/~csk/projects/mazes/


f:id:yaneurao:20130125090428p:image

yaneuraoyaneurao 2014/09/11 02:53 以下の記事でドルアーガの塔の迷路生成〜乱数生成の話題が少し出てきていたのでご紹介。

[CEDEC 2014]ナムコ作品で見る乱数の歴史。「ゲーム世界を動かすサイコロの正体 〜 往年のナムコタイトルから学ぶ乱数の進化と応用」レポート
http://www.4gamer.net/games/042/G004287/20140905040/

yaneuraoyaneurao 2014/09/14 05:34 ドルアーガの塔の迷路でジグザグが多いのは以下のような理由らしい。

せっき〜のゲーム屋さん ドルアーガの塔 乱数の工夫の正体
http://sekigames.gg-blog.com/Entry/291/

2013-01-11 ピアノの運指を自動生成するには?

[][] ピアノの運指を自動生成するには?  ピアノの運指を自動生成するには? - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  ピアノの運指を自動生成するには? - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


一般的に言ってピアノの初見能力は訓練次第でかなりのスピードにまで向上する。一つの音符を1つの文字だと考えてみると想像やすい。文字を読む速度は子供のころは遅いが、大人になるころには1分間に1000文字ぐらい読めるようになっているはずで、ピアノを10年か20年ぐらいやっていれば、1分間に1000音符ぐらい読めるようになっていても不思議ではない。


しかし、どれほど初見能力があってもミスタッチなしに正確に演奏できるか、そして、リアルタイムに運指を導き出せるかと言うと話は別である


例えば、フランツ・リストは「どんな難曲でも初見で弾ける」と豪語していたが、ショパンのエチュードに至っては初見では弾けなかったと言われている。私が思うに、ショパンのエチュードは運指がすこぶる嫌らしいのだ。


知らない人のために説明すると「運指」というのはどの音符をどの指で押すのかということなのだが、運指は無数に考えられ、数学的に言うと組み合わせ爆発をしている。


組み合わせ爆発しているものを人間は瞬時に解答できないので(例:ナップサック問題)、どれだけ初見能力があり、超高速で正確に指を動かす能力があったとしても、運指を瞬時に決められない以上、そこに人間の限界があるのだろう。




―――とまあ、そんなありきたりな説明には飽き飽きしている人のために、もう少し突っ込んだ話をしようというのが今回の趣旨である。上の説明ですでにお腹いっぱいになった人はブラウザを閉じてすみやかにお戻りください。




ピアノの場合、好ましい運指の条件として次のようなものが考えられる。

・あまり特定の2指か3指での動きが続くとそれらの指が疲れてくるのでなるべく指は満遍なく使いたい。

・同じ指で次の違う鍵を押すのはあまり良くない(前の音が切れてしまうため)

・2の指(人差し指)から3の指(中指)のような隣合う指を使っていく場合、前の音からなるべく跳躍がないほうがいい(そんなに指が開かないし、またミスタッチもしやすくなるため)

・1の指(親指)と2の指(人差し指)はそこそこ開くが、2の指(人差し指)と3の指(中指)はさほど開かないというような指ごとの特性がある。1と2の間は多少開いてもいいが、2と3の指の間が開くと無理な動きになるので音が途切れてはならないときは、前者のほうが好ましい。

・トリル、モルデント、プラルトリラー等の交互連打は2,3(or 3,4)の指でやるのが好ましく、4,5の指はそこまで速く交互に動かないので出来れば避けたい。


そこで、最適な運指を探すアルゴリズムは、良くないとされるような運指に高い点数をつければ、その点数を最小化するような経路を探すという有向グラフの最短路問題に帰着する。動的計画法を用いればこれはO(N)で解ける。


フルートで同じような議論をしてある論文があるので参考のため紹介しておく。


フルートの運指のモデル化とその最適化に関する研究

http://ci.nii.ac.jp/naid/110006164752


このような最短経路問題を人間は瞬時に解くことは不可能であり(人間の計算能力的なものを超えていると思われる)、いくら初見能力が高かろうと、複雑な譜面に対して最適な運指を実時間で求めることは出来ないと考えるべきだと思う。


まり、ショパンのエチュードレベルの曲を初見で弾ける人間は多分この世にいないのだと思う。

(演奏前に楽譜を見て運指を考えていいなら可能なのかも知れない。私には未知の領域すぎてわからない。)


さて、話を少し戻ろう。


動的計画法でO(N)で解けるのだから本当に人間に不可能なのかどうかは議論の余地がある。

まり、これがどれくらいの計算コストなのか、もう少し突っ込んで考えてみる。


旋律がすべて単音であるとして、かつ、右手だけをいまは問題として扱う。


また、現在鍵を押さえている指だけに着目し、それより過去の時間においてどの鍵をどの指で押さえていたかは問わないものとする。(たとえば3の指で鍵盤中央のドの音を押さえているとき、自ずと手首がどのへんにあるか、他の指がどのへんにあるのかは確定するだろうという仮定をする。)


そうすると、現在、鍵を押さえている指は5通り(片手には指が5本あるから)で、そこまでの最小の経路のスコアが既知である。これをそれぞれ、S(1)〜S(5)とする。つまり、例えばS(1)ならば現在の鍵を1の指(親指)で押している場合の最小のスコア。(そこまでの経路のうち、最小のスコアをつける経路のスコア)


次に押さえるべき鍵をたとえばaの指で押さえるときのことを考える。ひとつ前の鍵を押さえていた指がbだとしたら

今回のS(a) = 前回のS(b) + 今回のコスト(=前の鍵をbで押さえて今回の鍵をaで押さえるときのコスト関数)

である


S(a)は最小化しないといけないから、結局、

・前回のS(1) + 今回のコスト(前の鍵を1で押さえて今回の鍵をaで押さえるときのコスト)

・前回のS(2) + 今回のコスト(前の鍵を2で押さえて今回の鍵をaで押さえるときのコスト)

・前回のS(3) + 今回のコスト(前の鍵を3で押さえて今回の鍵をaで押さえるときのコスト)

・前回のS(4) + 今回のコスト(前の鍵を4で押さえて今回の鍵をaで押さえるときのコスト)

・前回のS(5) + 今回のコスト(前の鍵を5で押さえて今回の鍵をaで押さえるときのコスト)

のうち最小のものを選択することになる。


今回のS(1)〜S(5)に対して上記のように最小のコストのものを選んでやる必要があるので、コスト関数を25個それぞれ計算して、上記のようにS(1)〜S(5)を更新してやる必要があるので、S(1)〜S(5)を記憶するための5つの記憶域と、1音符に対して25回のコスト関数の計算、およびその加算と最小値を探すための比較が必要になる。


「暗算日本一の人とかなら可能なんじゃないか」と言う人がいるかと思うが、しかし暗算日本一の人も数字を文字を読むように認識しているだけだろうから、人間の文字を読む速度(1分に1000文字程度)を超えた計算は不可能ではないかと私は思う。


ピアノ曲でテンポの速い曲はBPM200程度であり、つまり1分間に4分音符が200個、16分音符なら800個、両手ならその倍の1600個。その1600個の音符それぞれに対して上記のように25回のコスト関数の計算、25回の加算、5回の最小値の選出が必要になる。これは間違いなく人間の処理能力を越えていると思う。


ゆえに、そのような譜面に対してピアノの運指をリアルタイムに人間が求めることは出来ないという結論になる。


一方、コンピューターで計算させて良いのであれば、上記アルゴリズムはこれは極めて簡単なプログラムで実現できる。実際は単音ではなく和音であったり、あと右手と左手が交差するようなこともあるし、鍵を押したまま他の指を動かす場合もあるのでもう少しややこしいが考え方自体はここに書いた方法で良い。


また、直前に押した指だけではなく、その一つ前とか二つ前の指も考慮して、S(x,y,z)のようなスコアが最小化するように更新していく(このとき1音符につき5の4乗=625回のコスト関数の計算必要になる)とさらにリアルな運指が得られる。


さて、そのようにして運指を導き出し、MIDIファイルからMMDのモーションファイルを生成するものをいっちょ作ったろかい!と思って私は考えていたのだが、調べていたらすでにやってる人が居て、しか結構動画の完成度が高くて激しく萎えたのでその動画を紹介してこの記事を終わりたい。


【MMD】ミクさんがビッグブリッヂの死闘を弾いてくれました。.mp4

D



追記。iPhoneの超有名アプリのFingerPianoの作者、和田さんに振ってみました。

f:id:yaneurao:20130111201427p:image

通りすがり通りすがり 2013/01/11 20:37 紹介された動画ではピアノの鍵盤のモーションはmidiから自動生成らしいですけど運指は手動でモーションを作ってるようですね。

yaneuraoyaneurao 2013/01/11 21:29 ↑そうなんですか…。動画中のグリッサンドのところとか、「手動生成っぽいなー、でも自動生成できる範囲だしなー」とか思いながら見てました。

VARDIGAVARDIGA 2013/01/13 10:20 このページの中程を参照。 > http://ist.ksc.kwansei.ac.jp/miwa/miwaLab/research

yaneuraoyaneurao 2013/01/13 12:07
[引用] ピアノ演奏コンピュータグラフィクスアニメーションの制作 これは,これまで不可能であった,ピアノ演奏中のピアニストの手指の動きのアニメ制作を可能とする技術に関するものである.一つは,楽譜を入力データとし,最適化理論・逆運動学・解剖学の知見に基づいて運指および手指の挙動を決定するものであり,もう一つは,モーションキャプチャによって取得したピアニストの演奏時の手指の動きからCGを制作するものである.前者については,これまで効率的なアルゴリズムを設計・実装してプロトタイプを開発した.後者については,ピアノ演奏時の手指の動きが速いこととカメラの死角が不可避であることから欠落・誤認識が極めて多く,これまではモーションキャプチャを用いてもピアノ演奏CGアニメ制作は不可能であったが,動きの滑らかさを最適化する補正アルゴリズムを設計したことにより,元の動きを再現する技術を開発した.実際にこれを用いて,TVアニメとして放映された「のだめカンタービレ(巴里編第10話以降・フィナーレ編は全編)」におけるピアノ演奏シーンをすべて制作した.

前者はたいしたことないですが、後者は凄いですね。のだめの演奏シーン、そうやって作ってたんですね…。

zubybeenzubybeen 2013/01/14 02:23 あの有名な「トムとジェリー」のピアノコンサート(ハンガリー狂詩曲第2番)、トムの指がきちんと楽譜通りになっていました。子供のころは全く気付きませんでしたが、多少わかるようになって改めて見て、あらゆる意味で驚愕いたしました。
・・・そんな国と戦争をして、勝てる訳がありませぬ。

yaneuraoyaneurao 2013/01/25 10:46 私も子供のころ、「トムとジェリー」が大好きで欠かさず観てました。そのシーンは、ピアノのなかに入り込んだジェリーをトムがピアノを普通に弾いているように見せかけながらジェリーをピアノのハンマーとかでやっつけようとするところですかね。

確かにトムの運指はきちんとなっていた気がします。いやー、言われてみれば、凄いことですね…。

foxfox 2013/02/24 06:07 アナログモデム時代に実装したことのあるこのアルゴリズムを思い出しました。
https://ja.wikipedia.org/wiki/%E3%83%93%E3%82%BF%E3%83%93%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0

2013-01-02 多次元メモリ空間プログラミング

[] 多次元メモリ空間プログラミング  多次元メモリ空間プログラミング - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  多次元メモリ空間プログラミング - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


新年会で酒を飲み過ぎて頭が痛くて眠れないので、新年の挨拶代わりにプログラミングの話でも適当に書き散らしておく。


それがるうるの支配魔術    Game6:リライト・ニュー・ワールド (角川スニーカー文庫)

以前、私の知り合いのラノベ作家である土屋つかささんが、「プログラミングのソースコードって本当に1次元(plain text)でいいんですかね?」みたいなことを言っていた。


例えば、フローチャートは普通、二次元上に表現する。条件分岐(菱形の図形)が何箇所もあるようなフローチャートを描く場合、本来のソースコードよりも流れが見やすいということは多々ある。それは何故だろうか?


「条件が成立したらソースコードのXXX行目に移動する」というような1次元的な移動より、「条件が成立したら下に移動、成立しなかったら右に移動する」というような2次元的な移動のほうが可視化する上ではわかりやすいというのがあるのではないかと私は思う。


こう考えると、ソースコードは最終的に直列化(1次元化)するにせよ、頭のなかではそのように直列化されているわけではなく、マインドマップのように2次元、もしくはN次元で構成されていて、それを1次元のソースコードとして書きだすことになる。


これが、プログラミングを難しく、そして複雑にしている要因の一つではないだろうか。


例えば、頭のなかに複数のアイデアがあるとする。そのアイデアは相互に関連づけられているとする。それを話し言葉として話そうと思ったときに、順を追って一つずつ書きだす必要がある。箇条書きにする、なんていう行為もこのシリアル化に相当する。


この思考のシリアル化は、子供のころから国語教育のなかで培われているはずではあるが、苦手な人は苦手だし、そもそも、頭のなかでどう考えるべきかという部分については我々はこれと言った教育は施されておらず、他の人の出力(シリアル化された模範解答)から自分の頭のなかの思考回路をフィードバック学習のようなことをして学んできたに過ぎない。(ゆえにその部分には個人差がかなりある。)


なんにせよ、なるべく頭のなかで考えている図に近い形でソースコードを書き出せたほうがいいというところまで話を進め、次にこれをバイナリレベルで考える。


Binary Hacks ―ハッカー秘伝のテクニック100選


そういや、私は年末に「Binary Hacks ―ハッカー秘伝のテクニック100選」(asin:4873112885)の著者の一人である浜地 慎一郎さん(id:shinichiro_h)にたまたまお会いした。


そのときに私は「FPGAでCPU作ったりするの、コードゴルフ的な側面があって面白いっすよ。」みたいなことを彼に言った。DE0-nanoという8000円ぐらいで買えるFPGAの評価ボードでも相当な規模のCPUが作れるのだと。


このように自分で考えたアーキテクチャCPUが簡単に自作できる時代になったいまこそ、1次元メモリ空間的なプログラミングに拘泥する必要はないのではなかろうか。


そこで、もう少し具体的な話をしていく。


まず、2次元メモリ空間でのプログラミングを考える。2次元メモリ空間上にどのようにプログラムを書きだすかという問題があるが、まずはお手軽にExcelでいいと思う。Excelは二次元的なメモリ空間を表現したり、編集したりするのにもってこいである


私は以前、VBAを用いて、Excelのワークシート上に書かれたプログラムを実行するインタプリタを作成した。


第29回 Excel Interpreter(ExcelによるExcelのための変態的プログラム

http://bm98.yaneu.com/rsp/rsp29to2F.html


もう13年前も経っていることに驚きを隠せないが(開発していたのはそのさらに3年ぐらい前なので15年以上経っているのか…)、当時、私が上記のようなメタプログラミング環境(DSL?)が必要だったのは、私はそのころ、仕事で製図設計に携わっており、定型的な業務に飽き飽きしていたので図面の自動生成をしようと思ったのだが、AutoCADのマクロのようなもので書いてしまうと他の社員が見たときにちんぷんかんぷんになるので、Excel上で処理させようと思ったのがそのきっかけである


これならExcelのワークシート関数を理解している程度の非プログラマであっても、プログラムを追いかけたり、プログラムが定数として使用している値(セル)に計算式を書くことによって、自分なりにカスタマイズしたりすることが出来る。


ところで、バイナリアンにとっては時としてソースコードもバイナリコードもほとんど等価である

バイナリコードこそがソースコードという場合も少なくはない。


Excelのワークシートを2次元メモリとみなして、そこにプログラムを書いていくと考えたときに、そこに書くコードは、バイナリ(2進数的な)コードであるのか、アセンブリ命令であるのか、それとももう少し粒度の大きな命令セットからなるソースコードであるのか。それは、命令セットの違いという程度の意味しかないので、ここではアセンブリ命令に限定して話を進める。


命令を解釈して実行する部分は上記のExcel Interpreterのようなコードを書けばいいだけなので30行程度のVBAのコードで容易に実装できるだろう。なので、この部分は問題としない。いま問題とするのは、条件分岐に関してである


条件分岐は従来のプログラミング言語では制御構文(if,while,forなど)が必要であった。バイナリレベルで捉えるとこれらは条件ジャンプである。例えば、2数を比較をしたときに、その値が等しいとEqualフラグが1になる。「Equalフラグが1のときだけジャンプしなさい」という命令(例えばjumpzero、略してjz命令)が用意されていて、それによって条件ジャンプが実現できる。


このjz命令ではジャンプでの飛び先を書かなければならない。それは相対アドレスか絶対アドレスか、いずれにせよ、飛び先の番地を書かなければならない。


バイナリアン(バイナリ好き)でもこの番地を計算するのは少々面倒くさい。ハンドアセンブルする場合、CISCアーキテクチャだとそれぞれの命令のサイズが異なるので、それぞれの命令をサイズを足していき、飛びたい先の番地を求める必要がある。


これが面倒なので、バイナリアンと言えども長いコードを書かなければならない場合、簡易アセンブラを自作するのが普通で、この簡易アセンブラでは普通ラベルジャンプをサポートする。そうすると、


LOOP_START:

なにか命令

jz LOOP_START


のような書き方が出来るというわけだ。


まり、バイナリアンにとって、このような条件ジャンプ時のアドレス計算こそが癌であって、これさえなければハンドアセンブル上等!なのである。(バイナリアンの総意ではなく、あくまで私個人の見解です)


そこで、今回の2次元メモリプログラミングモデルでは、jz命令のあとは、ラベルやアドレスではなく何も書かないことにする。すなわち、条件が成立したときは右のメモリに移動する(非成立であれば下のメモリに移動する)というようにする。


こういうメモリモデルというのは、実用上も価値がある場合がある。


例えばFPGAでこのようなメモリモデルのCPUを実装するとしよう。NUMAアーキテクチャ( http://ja.wikipedia.org/wiki/NUMA )を採用していて、それぞれのCPUコアはなるべく小さく保ちたいとする。


そこに書くプログラムは非常に小さなコードなのでコードサイズはそれほど問題とはならず(どうせCPUコアからアクセスするコードメモリはFPGA内のブロックRAMで実装されるのでブロックRAMを一つに収まればそれで良い)、条件ジャンプのときに飛び先の番地を計算するためにフルサイズの加算器(メモリ空間が12bitならば12bitの加算器)を用意するのがもったいないとする。


そこで、条件成立時は現在のアドレスに0x100(256)を加算したアドレス(二次元メモリだとみなしたときの“右”がこれだとしよう)にジャンプするような条件ジャンプ命令を実装したとする。これなら、フルサイズの加算器よりはいくぶん規模を小さくできるし、条件ジャンプ命令がジャンプ先のアドレスを含まなくて済むので、データバスのビット数とアドレス空間のビット数を合わせる必要がなくなるというようなメリットもあるかも知れない。


まあともかく、二次元メモリモデルというのは、空想の産物ではなく、案外実用になるのではないかというところまで話が進んだので、次に、これをN次元に拡張していく。


まずさきほどまでの話だとプログラムは基本的に下方向に向かって命令が実行されていく。条件ジャンプがあると、条件が成立したときにのみ右側に1つ移動するだけであった。


しかし、これだとループが書けない。メモリ空間自体がどこかでメビウスの輪のように終端と開始アドレスが繋がっているのならば別だが、その仮定は制約が強すぎる。(たとえば0x1FFのつぎの番地が0x100に戻るような実装は可能かも知れない。条件ジャンプの条件成立時には実行アドレスを指すレジスタに0x100が加算されるとして)


そこで、プログラムの実行方向を下ではなく、現在の亀の向いている方角だとしよう。なぜここでいきなり“亀”が何故出てくるかというと、その昔(1970年代に)、LOGO言語というタートルグラフィックス環境が流行った。(仮想的な)亀にペンを持たせて、その亀に対して次のような命令を指令する。


REPEAT 4 [FD 100 LEFT 90]

※ 100歩歩いて(直進して)90度左回転という動作を4回繰り返せ の意味。これにより正方形が描かれる。


このタートルグラフィックスの考え方を、この2次元メモリプログラミングに応用し、現在の亀が向いている方向に命令を実行していくとするわけだ。


まり条件分岐であれは、条件成立時には左90度回転。(非成立時には直進)


無条件左90度回転命令(無条件ジャンプに相当する)も欲しいところではあるが、それはしかし、わざと成立するような条件比較を行ない、そのあと条件ジャンプ命令を書けばかならず条件が成立し、左90度回転するという動作になるので、命令セットを最小化するという観点からは不要だとも言える。


まあともかく、このようなプログラミングモデルであれば、ループを実現したければ、無条件ジャンプを4回行えば、もとの位置に戻ってくることも出来るであろうことがわかった。


次に、このプログラム同士を戦わせることを考える。


プログラム同士を戦わせるというのは、一例として挙げるならCore Warsという1985年ごろに流行った、小さな命令セットを持つ仮想CPU同士をサンドボックス環境で走らせ、相手にhalt(実行停止命令)を実行させれば勝ちというバトルゲームである


f:id:yaneurao:20130102053356p:image

※ 画像引用元 : http://www.gamesetwatch.com/2009/03/column_pixel_journeys_corewar_the.php


私は高校1年のときにこのCore Warsのtiny版がOh!MZ誌(のちのOh!X誌)に掲載されていたので、これでずいぶん遊んだ覚えがある。


私は当時、「ダロス」というアニメ(スタジオぴえろが制作、世界初のOVAと言われている)を観て、そのアニメに出てくる「自己修復機能」を持った要塞都市という中二病的な設定がいたく気に入り、Core Warsでそのような自己修復機能を持ったプログラムを書けないかとやってみた。


まり自分プログラムのcheck sum的なものを調べ、コードが破損していたら、それを元のコードに戻すというわけである。戻すためには元のコード必要なので自分自身のプログラムを+0x100番地離れたところにコピーしておく。そのコピーしたほうも壊れるといけないので、そのプログラムもさらに+0x100番地離れたところにコピーしておく。(以下、繰り返し)


このCore Warsは仮想的なマルチスレッドモデルを採用しており、forkに相当する命令があったので、それぞれのスレッドがそれぞれ自己修復(破損していれば+0x100番地先からコピーして復元)、また、増殖(+0x100番地に自分のコピーがいなければ、自己をコピーしてfork。より正確に言えば、+0x100番地のプログラムのheartbeat(自分が生きていることを示すためにメモリに書き込む値)が確認されなければそこの担当スレッドが死んでいることを意味するので復元してfork)みたいなプログラムを書いた。


いまにして思えば、それは自己修復型のワームなのだが、当時私はそういう用語すら知らなかった。


さて、このようなそこそこ複雑なプログラム(とは言っても30命令程度ではあったが)を書いて満足していたのだが、他の人が作ったプログラムと対戦させてみると、このプログラムがなかなか勝てないプログラムがあった。


それは一寸法師と呼ばれるたった5命令から成るプログラムである。その5命令のうちのひとつは5命令目に書かれたhaltであり、ここはそのプログラムは実際には実行せず、この5命令目に書かれた命令をその5番地先にコピーするというだけのプログラムである。要するに5番地ごとにhaltを書きこんでいくプログラムで、そのプログラム自体のコアは4命令から成るので自分自身には被害は及ぼさないというプログラムであった。


これが単純ではあるが、そのような、フットプリント(≒コア部分のメモリ使用量)が小さなプログラムはいたく強烈で、ある意味チートであり、ある意味、Core Warsのゲームバランスを損ねる元凶でもあった。


そのあと長年、このゲームバランスをなんとか改善し、そして、視覚的に現在実行している命令がわかりやすいCore Warsを作れないかと私は考えていたわけではあるが、ここに至って、今回の2次元メモリプログラミングモデルがすこぶる有効なのではないかと気づいたわけである


まり、アドレスジャンプではないので、急にあっちからこっち、というようなジャンプをしないので視覚化したときに非常にわかりやすい。チクタクバンバンのように必ず隣のメモリにしか移動しないかである


また、ループを構成するために、ダミー比較(Equalフラグを立てるためのもの)と条件ジャンプ(jz命令)の2命令を4回使わないとループにならないので少なくとも8命令は必要であり、一寸法師的なプログラムであっても12命令では書けないような命令セットであれば、16命令か20命令程度使わざるを得なくなってくる。


そうするとフットプリントを小さくしておいて絨毯爆撃するというようなプログラムが書きにくくなるので、もっと高度で高機能プログラムのほうが勝率が上がるのではないかと思う。そうなったほうがCore Warsとしては面白い。


これは大変いいアイデアなので、Core Warsの試合用のサーバーを用意して、比較的大きなメモリ空間で複数のプログラムを放って、その生存率(24時間に何回死んだかをカウントし、その平均生存時間から算出する)を競わせるような競技場を気が向いたら作ることにする。(注:いま酔っ払っているので、酔が覚めたら忘れているかも知れません。)


さて、以上で、2次元メモリプログラミングモデルというのは、実用上も、そして、Core Warsのような試合用のアーキテクチャとしても非常に興味深いことがわかった。次に、これをN次元に拡張していく。


N次元なので現在の命令の番地はベクトルρで表されるとしよう。向いている方向はベクトルνだ。νは単位ベクトルとしよう。


このとき次に実行する命令の番地はρ+νである。条件ジャンプ命令で条件が成立時には左90度回転をするのであるが、N次元空間での回転だと回転軸が必要で、それを固定してしまうとうまくメモリ全体を巡れない。


2次元での左90度回転だとベクトルνは (0,1)下方向 → (1,0)右方向 → (0,-1)上方向 → (-1,0)左方向のように推移するので、同様にN次元でも(たとえば3次元ならば)(1,0,0)→(0,1,0)→(0,0,1)→(-1,0,0)→(0,-1,0)→(0,0,-1)→(1,0,0)のように推移すれば、メモリ全体を巡ってもとの場所に戻ってこれるのではないかという。


この変換行列をΤとすると、新しいν=Τνみたいな計算でどうか。


例えば3次元時なら

Τ= [ [ 0 , 0 , -1],[ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ]

みたいな直交行列かつ、テプリッツ行列(対角一定行列)でどうかいな。


とりあえず、以上の方法でN次元メモリプログラミングも出来そうではある。

(ExcelのワークシートがN次元に対応したようなソフトウェアがないとプログラムを書くのは困難かも知れないが)


行列Τのバリエーションを変えれば、もう少し面白い実行が出来るかも知れないが、話が収拾がつかなくなるので今回は割愛する。


ここまでは命令の実行を、

・基本的に直進

・条件分岐では条件成立時にν=Τν、非成立時は直進

としてきた。


ところが、ここで「条件分岐では条件成立時に直進」となるようなプログラミングモデルだとどうだろうか。


・基本的にはうねうね

・条件分岐では条件成立時に直進、非成立時はそのままうねうね


こうなるわけである。この“うねうね”として、全メモリを被覆するようなうねうねした直線を持ってくればいい。


たとえば、ヒルベルト曲線にする。ヒルベルト曲線は空間充填曲線である


2次元だと次図のようになる。


f:id:yaneurao:20130102053357j:image

※画像引用元 : http://d.hatena.ne.jp/ototoi/20090315/p1


3次元だと次図のようになる。


f:id:yaneurao:20130102053355g:image

※画像引用元 : http://blog.atake-i.com/?eid=1060863


ヒルベルト曲線はN次元空間でも充填できるので、これを採用し、

・基本的にはヒルベルト曲線上の番地を実行していく

・条件分岐では条件成立時に直進、非成立時はそのままヒルベルト曲線上を辿る

のようなプログラミングモデルを考えることが出来る。


この場合、さきほどまでの90度回転や行列Τで向きを変えるのとは違って、少しパズルじみた要素が出てくるし、条件分岐がなければ基本的にすべてのメモリを使い切る(空間充填曲線なので)のでメモリ効率はいいかも知れない。


さて、このような実行モデルをプログラムの難読化に利用することを考える―――という話を書いていこうと思ったところで眠くなってきたのでこのへんでお休みなさい。


以上、酔っ払いの戯言を新年の挨拶に代えまして。


■ 追記 2013/09/09


KickstarterのプロジェクトのRobot Turtlesが、本記事で書いた二次元プログラミングっぽいゲーム仕様になっているのでご紹介。


Robot Turtles: The Board Game for Little Programmers

http://www.kickstarter.com/projects/danshapiro/robot-turtles-the-board-game-for-little-programmer

t_tutiyat_tutiya 2013/01/02 10:21  懐かしい! 確かにその話したけど多分10年くらい前ですよ!?
 冒頭に仰っている事がまさに当時言いたかった(けど上手く言葉に出来なかった)事です。
 脳内ではn次元方向に展開しているロジックを、ソースコードにする時は1次元(plain text)にシリアライズする必要があり、それを解読する際にはまた脳内に展開してn次元にマッピングするのが馬鹿馬鹿しいのでは(非効率的なのでは)と思っていたのでした。
 当時は、今で言うスワイプによる拡大縮小をブロック化したプログラミングパーツに対して適用するなどで、3次元空間上に配置したプログラミングパーツ同士をつなぎ合わせるプログラミングスタイルが、作り得るんじゃないかなと思っていました(思っていただけですが)。
 カルネージハートのプログラミング画面が、まさに2次元マッピングプログラミングですね(動作方向は各チップが情報を持つ形ですが)。

t_tutiyat_tutiya 2013/01/02 10:22 「プログラミングパーツ」ってなんだよ。「プログラムパーツ」だよ……。

yaneuraoyaneurao 2013/01/02 10:34 > カルネージハートのプログラミング画面が、まさに2次元マッピングプログラミングですね

あー、そうですね。

二次元上にプログラムパーツ(矩形ブロック、もしくはテトリスのブロックみたいなもの)を敷き詰めていって、ロボットのAIを書いて戦わせるのとか面白そうですね。

ビデオゲームでなくボードゲームでもあれば、その手の仮想CPUを脳内でシミュレートする訓練になって、プログラマにはいいかも知れませんね。

プログラムを書いてロボット(?)同士を対戦させるのはシステムソフトの『SeeNa』(1986)が日本では最初の商用ゲームかと思うのですが、PC-8801用だったので私はやっておらず。当時、ベーマガの広告で「光速の風になれSeeNa」というキャッチコピーが書いてあって「やってみたいなー」と指をくわえて見てました。

yaneuraoyaneurao 2013/01/02 15:56 そう考えるとチクタクバンバンや水道管ゲームは、時計ロボットが現在存在する場所がプログラムの実行アドレスを指し示していると考えることが出来、二次元上に命令が書いてあって、それを次々と実行していくというタイプのゲームだと捉えることが出来そうです。命令がジャンプ命令(方向変更)しかないがちょっとつまらない感じですが。

もう少し面白い命令があればあの手のゲームはもっとプログラマーに愛されるゲームになるかと思います。

先祖返り ?先祖返り ? 2013/01/02 21:48 計算の数学的モデルとしてチューリングマシンが考え出されたとき、
計算の内容を記述する箇所すなわちプログラムに相当すると考えられていたのは無限長の磁気テープに書かれたデータ「ではなくて」、
テープリールのモーターとヘッドに「あっち逝け」「こっち来い」「読め」「書け」と指令を出す有限状態制御部でした☆

無限長の磁気テープに書かれた一次元のデータをプログラムとみなすようになったのは、
フォン・ノイマンがプログラム内蔵方式を言い出してからなわけで、

そう考えると生のチューリングマシーンにおける有限状態制御部のワイヤードプログラミングこそ
究極にして至高の多次元メモリ空間プログラミングなんだとあなたもだんだん思えてきとうあー!

ぽぺぽぺ 2013/01/03 00:24 新年あけましておめでとうございます

やっぱり「誰でも書ける」という点において、1次元は最も優秀なんじゃないかと思います。絵などの2次元以上のモノは才能がないと素晴らしいのは努力してもなかなか書けないけど、1次元のテキストは、ちょっと訓練すれば、何故かそこそこ誰でも綺麗に書けたりするんですよね。
なので、プログラムは1次元が流行っていて、一部の訓練された人がやればいいアーキテクチャや設計は、モノができてしまえば説明しやすい2次元が流行っているのかなー、なんて。

最近は「新規参加メンバーにいかに品質の高いプログラムコードを書かせるか」ということが、結構自分の職責になることが多いので、そんなこと思いました。
ただ、「2次元プログラムで難読化」のアイデアはすごい面白ろそうですね。続きの記事を期待してます。

yaneuraoyaneurao 2013/01/03 10:50 ↑*2
ああ、そうですね。チューリングマシンっぽいものをレゴで作ったら教育上、よいのではないかと思ったりしてきました。

↑*1
> 続きの記事を期待してます。

いや、実は何も考えてなかったのですが・・。

まあ、よく、ソースコードが何かの絵になっている難読化があるじゃないですか。あんな感じでこの記事にあるようにヒルベルト曲線を用いてプログラムする場合、空間充填率をうまく調整するような難読化をすれば、2次元とか3次元上に描かれたソースコードが、何かの絵や立体物に見えるというのはありなんじゃないかと、いまとっさにひねり出しました。

2012-12-06 blogをメモ代わりに使う実験5

[] ExcelでA1セルにIDとか書いてはいけない件  ExcelでA1セルにIDとか書いてはいけない件 - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  ExcelでA1セルにIDとか書いてはいけない件 - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


カウントをCSV形式のファイルで管理したいときにA1セルに"ID",B1セルに"PASSWORD"などと列名を書いておくことはよくあると思うのだけど、A1セルに"ID"と書かれているとExcelで開いたときに「SYLK:ファイル形式が正しくありません。」というエラーメッセージが表示される。("ID_xxxx"でも同様のエラーメッセージが表示される)


たぶんいまどき誰も知らないと思うけどSYLK形式というのはExcelの前身であるMultiplan(1982年〜)の形式である


ちなみにExcel 2011(Mac版)、Excel 2012(Windows版 来年1月発売予定?)でも動作を確認してみたが、A1セルに"ID"と書かれていると上記のエラーメッセージが表示される。迷惑極まりない。


誰がいまどきSYLK形式のデータを使っているというのか…。

そもそもファイルの拡張子がCSVとなっているではないか。拡張子を見てくれよ、拡張子!


※ ↓に補足記事を書きました。こちらも併せてどうぞー。

http://d.hatena.ne.jp/yaneurao/20121206#p7



[] スーパープログラマーへの道がいまごろはてブされまくっている件  スーパープログラマーへの道がいまごろはてブされまくっている件 - やねうらお−ノーゲーム・ノーライフ を含むブックマーク  スーパープログラマーへの道がいまごろはてブされまくっている件 - やねうらお−ノーゲーム・ノーライフ のブックマークコメント


最近知ったのだが、10年ぐらい前に書き散らした、私の黒歴史(?)とも言うべき、「スーパープログラマーへの道」がいまごろになってはてなブックマークされまくっているのだ。(現在、430users)


http://b.hatena.ne.jp/entry/bm98.yaneu.com/rsp/loglist.html

f:id:yaneurao:20121206160737p:image


10年も前に書いたものがいまさらこんなにはてブされるということがあり得るのだろうか…。にわかに信じがたい。

何がどうなったのかさっぱりわからないが、きっとどこか大手の会社さんの組織票なのではないろうか。


「やねうらおさんは豚もおだてりゃ木に登るってな感じの性格なので、これくらい喜ばせておけばいい仕事しよるだろ!」とか言うことなのだろうか…。


どこの会社の組織票かは存じませんが、本当にありがとうございます。(木に登ってきます)

Ta(ryTa(ry 2012/12/06 14:04 ブルートルエン?

yaneuraoyaneurao 2012/12/06 14:08 ↑誰がうまいこと言えと…

Ta(ryTa(ry 2012/12/07 12:13 そういえば、最近のGoogleの検索結果はGoogleのサービス利用者のページを上位にするのは仕方ないとして、00年代後半の○○のために△△をやったけど○○はできませんでした終わり(テヘペロ系のブログが上位に来ることがほとんどなくなって、替わりにそれ以前の単色背景で中身がみっちり詰まったページが上位で引っかかってくるようになった感じはある。

yaneuraoyaneurao 2012/12/07 12:17 > Googleのサービス利用者のページを上位にするのは仕方ないとして

cookie見て、そのユーザーがクリックしたドメイン等が上位に来るように調整されているからですね。検索結果URLに「&pws=0」とつけるとニュートラルな検索結果になります。

Ta(ryTa(ry 2012/12/08 11:43 Cookieを消すしかないと思っていたらそのような抜け道があるのか。
ありがとうございます。

Ta(ryTa(ry 2012/12/19 22:41 Excel「これはSYLKファイル形式で…(ぶつぶつ)」
ユーザ「そんな形式SYLK(知るか)!」

 

1900 | 01 |
2004 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2010 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2011 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2012 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2013 | 01 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2014 | 01 | 02 | 03 | 04 | 06 | 08 | 10 | 11 | 12 |
2015 | 01 | 02 |


Microsoft MVP
Microsoft MVP Visual C# 2006.07-2011.06