Hatena::ブログ(Diary)

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

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

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

 | 

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ばかりが出てきたのだろう。


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


ドルアーガの塔ではCPUMotorola社の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-23 ゲームの世界の経済学が現実世界に通用するという話

[][] ゲーム世界経済学現実世界に通用するという話  ゲームの世界の経済学が現実世界に通用するという話を含むブックマーク  ゲームの世界の経済学が現実世界に通用するという話のブックマークコメント


最近、私の会社では年商1,000億円ぐらいの規模の会社の販売管理系のシステムを開発しているのだが、どうもこのシステム設計意図が私にとってはまさにデジャヴというか、「もうかれこれ10年ぐらい前にこれと同じこと考えてたよなー」と思ったので、そのあたりのことをだらだらと書いてみる。


いま、話を単純化するために店頭販売価格をいくらにすればいいかを決定するシステムを作りたいとしよう。


まず、経済学教科書によく載っている需要曲線というのは次図のような反比例っぽいグラフである


f:id:yaneurao:20130123040323p:image


経済学教科書では、これと供給曲線とを重ね合わせて、その交点が均衡価格(市場価格)だと説明がある。


販売する側の視点に立った場合、最適な価格(利益を最大化できる価格)というのは、均衡価格では決してない。そこで、いま供給曲線については考えないことにして、利益を最大化できる価格で売る、とだけ考えよう。


近年、インターネット価格比較サイト等の発展により、インターネット上で最安価格を見つけることが容易となった。それゆえ、需要曲線は上記のような反比例っぽいグラフにならない。典型的には次のようなグラフになる。(ただし経済学ではこれは需要曲線とは呼ばないようなので、以下で「需要曲線」と書いてあるのは「価格に対して実際に売れる量の曲線」とでも読み替えて欲しい。)


f:id:yaneurao:20130123040324p:image


安価格でなければほとんど売れない。ほとんど売れないながらも、ゼロではない。それは例えば、店頭販売であれば、わざわざ他の店を回るコストを考えるとそこで買ったほうがいいというような判断もあるだろうし、そのお客さんはその店のことがお気に入りなのかも知れない。あるいは、他の店のほうが安いことを知らないのかも知れない。


この傾向はインターネットでも同様であり、同じ店で買ったほうがまとめて発送できて送料が安くなるからだとか、ちょっとぐらいの差なら信頼できるほうの店で買うだとか、比較サイト比較するのが面倒なのでいつも買っているところでいいやだとか、まあ、そういう人たちが一定数は存在して、最安価からある程度離れていてもそこで買うのである


また、需要無限にあるわけではなく(いくら安くとも要らないものは要らない)、値段をかなり下げたところで一定数以上は売れないという需要限界値がある。


上図のような需要曲線になるとき、販売者側に立って、利益を最大化する価格とはどこかというのをいま問題として考える。


ここで前提条件をさらに追加しておかなければならないのだが、正確な需要限界値は、売り手は事前にはわからないということである。「おおよそ100ぐらいだろう」だとか、予測を立てることは出来るが、正確な数字ではない。販売できなくて在庫が余るリスクを考えれば、資金効率を考えるなら、確実に売れるとわかっている程度の数だけ仕入れたほうが効率が良い。(価格を少し下げれば、売りきることができるタイプの商品であれば、このようなリスクをあまり考えなくて良く、一括仕入れによる値引きがあるなら、多めに仕入れることにも合理性があるのだが、私がいまここで取り扱おうとしている商品は、そういうタイプの商品ではないとする。)


このとき需要限界値の半数ぐらいしか仕入れていないので、多少売れ残った場合でも最安価格にすれば在庫を処分することができる。最安価格がそれほど変動しないなら、利益を最大化できる販売価格というのは、最安価格では決してないことがわかる。


例えば、次のような売り方に合理性がある。


50個仕入れたとして、一気に50個が売れるわけではない。だから10個と40個に分け、別の店舗にて、前者は最安価格よりかなり高めで売り、後者は最安価格で売る。


前者を「かなり高め」に設定するのは、「最安価格より少し高め」と「最安価格よりかなり高め」とどちらのケースでも販売できる個数に大差がないため(上図のグラフを見ればそれが如実にわかる)、それならばかなり高めにしたほうが利益を最大化できるからである


前者が売れ残ったら、後者店舗で売る。前者が売り切れたら後者店舗から在庫を補充する。このように、店舗ごとにそれぞれ異なる価格で販売することで売り手が利益を拡大出来る。


これが店頭販売価格インターネット上の最安価格よりかなり高めに設定し、ネット販売の価格インターネットでの最安価格に設定するという価格設定を行なうことで利益の拡大ができるということに対する合理的な説明である。(最近家電量販店でそういう価格のつけかたをしているところがよくある。)


私がこの仕組みに気づいたのは10年ほど前にオンラインゲームをやっていたときである。そのときに売り手(販売商人)として利益を最大化するためにこの手の統計をとっていたときに需給曲線が上図のようないびつな形であることに気づいた。


そこで、そのオンラインゲームでは私は複数アカウントを用いて、同じアイテムに対してそれぞれに違う価格をつけて販売していた。これはそこそこうまくいった試みだった。


しかし、そのオンラインゲームにはゲームオークションのような仕組みはなく、単に露店売り(マップ上に直接露店を出すタイプ)であったために、露店ひとつひとつクリックせねば販売商品を確認できなかった。それゆえ、最安の露店を探す手間が馬鹿にならず、面倒くさいので少しぐらい高くとも買っていく人が一定存在した。


まりゲーム世界は上のような極端な需要曲線にはなっていなかったし、そのとき、私は「ゲーム世界(非現実世界)と言えども、どこか現実味があるな」と思った。


ところが、インターネット販売では近年比較サイト興隆により、最低価格より少しでも高いと途端に売れなくなるという、ある意味ゲーム世界以上に極限化された世界となった。あのとき私が体験したゲーム世界より、さらに非現実的な世界、それが現実世界として眼前に広がっているのだ。


それゆえ、私が10年も前に考えたオンラインゲーム内のアイテムの販売価格の決定のための仕組みが、現代において、年商1,000億円規模の会社で通用するというわけだ。イギリス詩人バイロンは「事実小説よりも奇なり」と言ったが、私に言わせれば「(インターネットを含めた)現実世界ゲーム世界よりゲーム世界なり」である

yaneuraoyaneurao 2013/01/23 08:29 私の書き方が悪くて、今日の記事の最後の段落の趣旨が読み取りにくいと思うので、少し補足。

「私が10年も前に考えたオンラインゲーム内のアイテムの販売価格の決定のための仕組み」と言うのは、「一物一価ではなく一物に複数の価格をつけることで収益を拡大できるという仕組み」のことではなく、今日の記事の2つ目の図のような特徴のある需要曲線といくつかの前提条件が与えられたときに、収益を最大化するための手法のことである。

これは私が10年ぐらい前にオンラインゲームをやっているときに思いついたものだが、その具体的な内容については今日の記事では触れていない。なぜ触れていないかと言うと、この部分を詳しく書くためには、前提条件をさらにいくつか追加しないといけなくてその議論やら説明やらが面倒だったからである。

そのオンラインゲーム内では、この仮定が強すぎて、私の考えたアルゴリズムが有効に機能していないときがあったのだが、実世界(現在)だと、オンラインゲーム内で流通していたアイテム数と比較にならないほどの商品数、そして購入者がいて、かつ、価格比較サイトにより、最低価格を知ることが比較的容易になったので、これらの条件の変化により、オンラインゲームのときよりも、モデル化しやすく、収益を最大化する販売価格を決定するのが容易になりつつある。

ともかく、「ゲームの世界より実世界のほうがゲームっぽいなー」と言いたかっただけである。

せーきせーき 2013/01/24 17:59 Roとは懐かしいですね。
この理論は定番商品を取り扱い、商品の陳列スペースは事実上無制限で
これ以上商品を並べても売り上げはほぼ変わらない前提でいいんですよね?

私は「仕入れ→現金化」に要する時間を限界まで圧縮することで時間辺りの利益が最適化すると考え、
・必ず最安価格帯で陳列する
・看板は独創的で探しやすいように
にして固定顧客をできるだけ確保する戦略を取っていました。
定番商品ではなく一品モノ商品中心に取り扱っていたせいもありますが・・・

ゆたゆた 2013/01/24 18:36 これは需要曲線の話というより、価格に対していくら売れるか、という曲線なのではないでしょうか。経済学的にいうとこの状況は同質財のベルトラン競争だと思います。売り手がまったく同じ財を売るとき消費者は1円でも安い売り手から商品を買います。生産者がこのような競争をしているとき、このような売り上げと価格のグラフに直面します。

インターネットの隆盛によって競争の形がある意味で凄く古典的なモデルに近づいてくる、というのは興味深い発見だと思います。

yaneuraoyaneurao 2013/01/24 19:28 ↑*2
1アカウントに対して「時間あたりの利益を最大化」がベストではない状況があるというか、陳列棚(≒アカウント)が無限にあり、商品の陳列にはかなりの時間を要するというモデルの場合(例えば商品スキルでの商店の開設自体に時間を要する以外に、ギルメンに商品の陳列を依頼する場合、その時間を要しますし、自分の寝る時間も必要ですし…)、陳列自体が追いつきませんから、この場合、手持ちの潤沢な資金を使い切れなくなります。(私がそうでした) それゆえ、資金効率を考えますと、利益を最大化するには売れ筋の商品のみを取り扱うのではなく、時間あたりの利益は低くとも販売価格が高額な商品を扱うほうが良いことになります。

つまり「商品の陳列に時間がかかる」というのは、私がそのときに導入していた仮定の一つですが、実世界(現代)において高額商品を取り扱う場合にも、営業マンへの教育などで商品の販売自体に一定のコストおよび時間がかかると考えられるケースにおいて類似性があります。

オンラインゲーム時代のときの私の販売価格の决定のためのモデルが実世界(現代)で通用するという背景には、このへんの類似性が理由にあります。

↑*1
> これは需要曲線の話というより、価格に対していくら売れるか、という曲線なのではないでしょうか。

はい、これを経済学で需要曲線とは呼ばないことは私は理解していて、本文中にその旨を書いています。(初出時には書いてませんでしたが、誤解されるといけないと思い、今朝、追記しました。)

あと、ミクロ経済学をやっている人向けにもうちょっと突っ込んだことをお話しておきますと、比較サイトの興隆により企業がプライステイカーとなり通常の競争市場になるんじゃないのかと思われるかたがいらっしゃると思うのですが、確かに安い商品ですとその傾向が強いのですが、高額商品ではそうはならないケースが実際にあって、価格.comなどで高額商品についてその傾向を調べれば何か見えてくるものがあるのではないでしょうかとだけ言っておきます。

このへんを本文でもぼかしつつ書いているのは、そのへんを具体的に書き出すと私の会社で作っているのがどこの企業の販売管理系のシステムなのか特定できてしまいかねないからです。それゆえ少し消化不良ぎみの記事になってしまっていることをこの場をお借りしてお詫びいたします。

yaneuraoyaneurao 2013/01/24 19:53 ちなみに私はミクロ経済学は言うまでもなくド素人で(ナッシュ均衡をかろうじて理解できる程度)、あまり興味もなくて、ある価格に対して何個売れるのか・どれくらいのペースで売れるのか等の情報が与えられたときにどういう戦略をとるのがベストなのかというのを重回帰分析やら最適制御理論やら機械学習やらのコンピュータ的なアルゴリズムで決定することにのみ関心があります。

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

トラックバック - http://d.hatena.ne.jp/yaneurao/20130111

2013-01-06 ゼビウスに関する音楽的考察

[][] ゼビウスに関する音楽考察  ゼビウスに関する音楽的考察を含むブックマーク  ゼビウスに関する音楽的考察のブックマークコメント


スペースインベーダー」(1979年/タイトー)が発売されて以来、他のゲームメーカーがこぞってシューティングゲーム製作した。そのなかの代表作品としては「ゼビウス」(1983年/ナムコ)が真っ先に挙げられると思う。


スペースインベーダー」の翌年に発売された「ギャクシアン」(1979年/ナムコ)ではなく、「ゼビウス」をここでまず第一に挙げるのは、「ゼビウス」の売上が「スペースインベーダー」に次ぐ売上を記録したという理由である


要するに「ゼビウス」は間違いなく大ヒット作であり、ゲーム性のみならず音楽性も高く、当時の時代背景を色濃く反映したものになっているのではないかということで、「ゼビウス」に関して少し音楽的な考察をしてみたいと思う。


まず「スペースインベーダー」のほうのBGMだが、たぶん、次のようなベースラインになっている。

※ 私の耳コピなので間違っているかも知れません。


f:id:yaneurao:20130106115156j:image



シ♭→ラ→ソ→ドのようになっているが、これが延々と繰り返され、そしてテンポが速くなっていくため、だんだん「ド→シ♭→ラ→ソ」の下降ラインのみが耳に残る。


「ゲーセン」最強読本 ―永久保存版名作ゲームBEST100


スペースインベーダー」は開発時は二拍子であったと言われている。(出典 : 『「ゲーセン」最強読本永久保存版名作ゲームBEST100』(asin:4796635793)の開発者西角友宏氏へのインタビュー記事。)


要するに開発時は2音が延々と繰り返されるBGMだったわけだ。当然ながら社内評価が悪かったらしく、それを上の譜面のように4音を延々と繰り返す形に変更した。社内では依然として酷評されていたらしいが、結果的には四拍子だからこそのヒットだと言われている。


一方、ゼビウスのほうのBGMは以下のようになっている。

※ 私の耳コピなので間違っているかも知れません。



f:id:yaneurao:20130106115157j:image


コード進行的には、CM7→C7→FM7→Fm7か。C7→FM7は下属調への転調っぽく聴こえる。(key of FにおけるV7→Iなので) Fm7のところは普通G7なんだろうけど、ここをFm7にしておくことによって、ベース音をずっとドの音に固定できる。


f:id:yaneurao:20130106115159p:image:w800


上図のようにベース音をずっとドに固定して、最高音をミに縛っておいて(そして、その真下のドも断続的に鳴らしておいて)、内声だけ変化させる。


内声は、「シ→シ♭→ラ→ラ♭」と変化している。他の音を固定しておいて一声だけを動かす技法のことを音楽用語では「クリシェ」と呼ぶ。ここでは半音クリシェラインになっている。これを音楽用語では「クロマティッククリシェライン」と言う。


上図では、ミと高いほうのドのところを「sporano pedal point」と書いたが、ずっと鳴っているわけではないので厳密な意味でのペダルポイントではない。ただテンポが速いのでペダルポイント的な何かとみなしていいと思う。


ともかく、音楽のことがわからない人も、ベース音とトップノートを固定しておいて安定感を出しながら、内声をちょっとだけ下方向に動かしていくという技法が使われているということがわかればまずはオッケー。話を先に進める。


これが実際どう聴こえるかというと、ずっと聴いているとこのクリシェ部分のみが顕著に聴こえる。人間は変化する音にだけ注目する能力自然と身についているかである


結局のところ、ゼビウスのこのBGMは、「シ→シ♭→ラ→ラ♭」という下降ラインしか意識には上ってこないことになる。これがゼビウスBGM本質的な部分である。そうみなせば、さきほどのインベーダーゲームの四拍子による下降ラインとの構造的な類似性を見て取れる。


音楽理論と言えばコード進行だろjk」と思っている人も多いかも知れないが、なめらかに接続するコード進行というのを考えたときに、1つ目のコードの構成音のうちのいくつかの音は2つ目のコードでも持続していて(固定されていて)、1つ目のコードのうちの1音だけわずかに動く(例えば半音下降)となめらかで自然に聴こえるという聴覚的な(?)原則がある。まあ、いくつもの音が同時にあちらこちらに動くよりは、1つの音だけがわずかに動くほうが変化は少なくて自然に聴こえるのは当然だろう。


他人の曲をコード分析をするとき、たいていはそこに何らかのコードが割り振り、「コード進行的に考えてここはこう解釈できる」みたいな話になるのだが、しか作曲家意図としては単に1音だけ静かに動かしたかったにすぎない場合もある。そういう進行に対して、勝手コードを割り振ってあれやこれや考えても作曲家意図とは違ったものになってしまう。


ともかく、クリシェによって「自然でなめらかなコード進行」に聴こえるようになっているというところまでわかってもらえればここでは十分である


ところが、ずっとこれだけでは音楽としては退屈なものとなってしまう。(半音)下降のクリシェは極めて自然な進行だが、「動と静」で言えば静。ずっと静だと音楽的につまらないのだ。


そこで、この技法ゲーム音楽(特にスペースインベーダー」や「ゼビウス」)として使われたときにどういう効果をもたらすのかについてもう少し突っ込んで話をしていく。


わかりやすい例として、たらいまわし関数(竹内関数)で音楽生成をしてみた記事を挙げる。


竹内関数音楽生成

http://d.hatena.ne.jp/aike/20111112


たらいまわし関数(竹内関数)とは次のような再帰的に定義された関数で、プログラムベンチマークとしてよく使われる。

f:id:yaneurao:20130106115155g:image


D

※ 上の動画たらいまわし関数で生成された音楽


たらいまわし関数で何故音楽が生成できるのか、何故音楽っぽく聴こえるのかについて、原理的な種明かしは次の記事に詳しい。


竹内関数音楽的に聴こえる理由について考えてみた

http://d.hatena.ne.jp/aike/20111115


f:id:yaneurao:20130106115158j:image


要するに「クリシェ → 停滞 → 調性切替 → クリシェ → 停滞 → 調性切替 → クリシェ → ……」が繰り返されることが音楽的なうねりとなって心地良く聴こえるというのだ。


クリシェは「静と動」で言うと静の部分、そして停滞がきて(より静になって)、調性切替のところが「静と動」で言うと動の部分。このように、静と動を繰り返す構造になっている。この停滞からの調性切替には、爆発にも似た開放感があるのではなかろうか。


さて、そう考えると「スペースインベーダー」には途中でUFOが出てくる。これが「静と動」の動の部分ではなかろうか。あるいは、テンポが徐々に速くなっていくこと自体が静から動への移行とも取れる。


ゼビウス」だとアンドアジェネシスが出てくる。アンドアジェネシスが出てきているシーンではBGMは通常のBGMに、SEとしての轟音が加わる。この部分が「静と動」の動の部分ではなかろうか。また、アンドアジェネシスの出現とともに雑魚が出てきて、それを倒すSE音楽の一部とみなすことが出来ると思うし、バキュラや敵を雑魚を倒したときSE音も音域的には、通常のBGMで使われている音域付近であり、これが上記の「調性切替」っぽい小さな音楽的なうねりを引き起こしているのではないかと思う。


Xevious (Arcade) ノーショット (Without firing a shot) 2/2

D

※ 上記動画ゼビウスショットを一切撃たずに1周クリアするという趣旨のもの動画の5:06〜はサウンドトラック音源がかぶせてあるんですかね。よく知りませんが、素晴らしいアレンジですね。


なんかだらだら書いてしまったが、「スペースインベーダー」と「ゼビウス」では、構造的な類似を見て取れ、そしてこれらのゲームではSE音を含めて全体として一つの音楽になっているのではないかというのを結論としてこの記事を終わりたいと思う。

コードコード 2013/01/06 13:10 あんまり本質的じゃない部分ですが…コード進行はFの音が鳴っていないのにCM-C7-FM-Fmとするのは先走りしすぎでは?

楽譜そのものからだけだと単純にC-C7-C6-Caugでいいと思います。これでもペダルポイントとクリシェの分析は有効ですし、どちらかというとこのほうが「単に1音動かしたかっただけ」の意図を汲めると思います。

CM-C7-FM-Fmは自然で音楽的な進行(トニック-サブドミナントのセカンダリードミナント-サブドミナント-サブドミナントマイナー)なので曲をアレンジするとなったら(ベースを動かして)再解釈できるうちの1つになると思いますが。

この種の音楽はコード進行云々で作ってるわけじゃないよねというのもその通りだと思うので枝葉末節な指摘かと思いますが…

yaneuraoyaneurao 2013/01/06 19:19 > コード進行はFの音が鳴っていないのにCM-C7-FM-Fmとするのは先走りしすぎでは?

CM7,C7のほう、ソの音が省略されているので、この部分に相当する声部は省略されていると解釈したときに、まあ、FM7-Fm7は普通にあり得るかなと思います。「Namco Game Classic CollectionVol.I」でゼビウスの曲のアレンジ担当された福澤 正洋さんがそう解釈されていたのでそれに倣いました。(http://earthnotes.blog34.fc2.com/blog-entry-5.html)

もしかしたら私の耳コピが間違っている可能性もなくはないですが…。いやー、ソの音は鳴ってないかと思うのですが…どうでしょう…。

> 楽譜そのものからだけだと単純にC-C7-C6-Caugでいいと思います。これでもペダルポイントとクリシェの分析は有効ですし、どちらかというとこのほうが「単に1音動かしたかっただけ」の意図を汲めると思います。

これはまさにそうですね。本記事上は、CM7-C7-C6-Caugにしたほうがわかりやすかったですね。

yaneuraoyaneurao 2013/01/06 19:36 「竹内関数で音楽生成」の記事を書かれたaikeさんからツイートが。

> aike1000 やねうらおさんのブログに僕が以前書いたエントリーが引用されててびっくり。嬉しい。ゼビウスのBGMがクリシェだったりボスキャラのSEが一種の曲展開という解釈は面白い。

私は「竹内関数で音楽生成」という記事にインスパイアされたのがこの記事を書く直接のきっかけだったので、お褒めいただき光栄です。

passed bypassed by 2013/01/07 13:06 ゼビウス・アレンジメントの継ぎ目なく変化していくBGMが凄かった。

トラックバック - http://d.hatena.ne.jp/yaneurao/20130106

2013-01-04 ゲームROMの吸出しの歴史

[][] ゲームROMの吸出しの歴史  ゲームROMの吸出しの歴史を含むブックマーク  ゲームROMの吸出しの歴史のブックマークコメント


日本ゲーム史はインベーダーゲーム嚆矢とする。インベーダーゲームゲームセンターから消えて10年ぐらい経ったのちも、中学校校則には「インベーダーゲーム店への入店を禁ずる」とか書かれていたケースも少なくはない。それほどインベーダーゲームの影響は絶大だった。


インベーダーゲーム」とはタイトー1978年に出した「スペースインベーダー」とこの類似ゲームおよびクローン(模倣品)に対する総称であるタイトースペースインベーダーを発表すると同時に一大ムーブメントが巻き起こり、各社一斉にシューティングゲームを作りはじめた。


例えばナムコ(現ナムコバンダイ)は翌年(1979年)にギャラクシアンを発表し、その2年後(1981年)にギャラガ1984年ギャプラスを発表している。


パックマンのゲーム学入門

NHKスペシャル 新・電子立国〈4〉ビデオゲーム・巨富の攻防


このころの著名な作品のROMを吸出し競合他社がリバースアセンブルして研究するのは普通であった。


えー、要出典


うーん。そういう話が「NHKスペシャル 新・電子立国〈4〉ビデオゲーム・巨富の攻防 」(asin:414080274X)に出てきていたと思う。「パックマンゲーム学入門 」(asin:4757717520)にもちらっと書いてあったと思う。あとは直接私がゲームメーカーの人に聞いた。


そこでROM吸出しがどのようにして成されていたかというところまで話を進める。


当時のゲーム機版で使われている部品はほとんどが汎用部品であり、どこかのCPU(典型的にはZ80MC68000)や汎用ROMを用いて構成されていた。CPUの命令セットは当然既知であるからROMさえ吸い出せればそこに書かれているプログラムを解読できた。


当時のROMはいまのSDRAMのように複雑な制御必要なく、単にアドレスピンに読み出したいアドレスを設定し、read/writeを指定するピンにはread(読み出し)を指定すれば、データピンにそのアドレスに書かれているデータが現れるというものであった。


汎用ROMなのでROMの書き込み装置(市販のROMライター)で読み出せたはずだが、当時ROMライター比較的高価だったし、どんなROMでも読み書き出来るROMライターというものはなく、手持ちのROMライターだけでは対応していないこともあった。


そこで、ROMの吸出し機を自作することもあったのではないかと思うのだが、そのへんの事情は私はよく知らない。自作していたと仮定して、空想で話をもう少し進める。


当時のPC(たとえばPC-80011979年発売)でこの手のI/Oとして使われていたのはプリンターポート(いまで言うパラレルポート)だったはずだ。


PC-8001プリンターポートセントロニクス社仕様から、つまり8bitのデータ送受信ピン(≒汎用I/Oピン)とacknowledge,write strobe信号ピンなどで構成される。要するに汎用I/Oとしてみなしたとき、これらの8〜10bit程度が自由にCPUから扱える。


当時のROMアドレス空間12〜14bit程度であり、データが8bitであるからROMを吸いだすためにはI/Oピンが不足することになる。だから、ひと工夫必要になる。


アドレスは0にリセットしたあとインクリメントしていけば(1ずつ足していけば)いいので、74HC393に代表されるようなインクリメンタルカウンタ(バイナリカウンタ)を用意する。


またデータは1ビットずつ選択して取得出来ればそれでいいので74HC299に代表されるようなshift registerを用意して1ビットずつ取り出すようにする。


あとは、TTL/CMOSのレベル変換(≒電圧の変換)のために74HC645などを間に入れればハードとしては完成である


これはそのあとに流行ったファミコンROM吸出し機などの典型的な構成例である


本当にこのようなハードゲームメーカー各社が作ったのかどうかは知らないが、まあこれに相当する何かを作ったのではないかと私は思う。(いまであれば、I/Oピンの多いUSB対応の1チップマイコン安価にて手に入るのでこのようなことをする必要はないだろうが。)


競合他社のROMの吸出しが各社可能であったというところまで話を進め、次にその対策などについて書いていく。


当時、ゲーム基板のクローン自体は法的にはグレー(もしくは合法)であったため、他社からクローン基板も多数発売された。クローン基板が安くで流通してしまうとゲームの開発・販売元としては商売があがったりになるので、これらのクローン対策のために何らかのプロテクトを施しはじめた。


そのプロテクト電気的なものソフト的なものなどいろいろあり、枚挙にいとまがない。

これについては機を改めて書きたいと思う。


電子部材用途におけるエポキシ樹脂 (CMCテクニカルライブラリー―エレクトロニクスシリーズ)


そのなかでもとりわけシンプルな例としては、チップ刻印されているIC名を削ったり、エポキシ樹脂で基板全体やROMを固めてしまうというものだった。


ただ、エポキシ樹脂はこれを本当にやってある基板は数が少なかったと思う。その理由には、基板は売れ残ったあと、破棄するのはもったいないのでROMだけ差し替えて別のゲーム基板として発売する意図があったからだと思われる。実際、「スペースインベーダー」は大量に残り、タイトーではROMだけ別のゲーム差し替えて出荷している。(スペースチェイサー、バルーンボンバーetc…) あるいはエポキシ樹脂自体は溶剤で綺麗に溶かせるので競合他社への対策としてはあまり意味がないのかも知れない。(私はよく知りません。)


ともかく、ここではROM吸出しに関して技術的にもう少し突っ込んだ話をする。


オールゲーム保全のためにROMを吸いだしている人達がこのエポキシ樹脂で固められたROMの中身をどうやって吸いだしているかという点にフォーカスを絞る。


たとえば、「SUPER RIDER」(Venture Lineが開発。1983年タイトーが販売)では12kBのROMがエポキシ樹脂によって固められていた。これを吸いだしたAaron Giles氏のブログ記事によると、これを吸いだすためにトロイの木馬を書いたとのこと。(http://aarongiles.com/old2004.html)


具体的には、下図のようになる。(下図は私が書いた。)


f:id:yaneurao:20130104110508p:image


CPUは既知であり、そのCPUにエポキシ樹脂で固められたROMがぶら下がっている。このROMはパレットデータゲームの動作のために必須情報が入っていると思われる。それとは別にゲームプログラムコードは、別のROM(上図の「original game ROM」)に入っており、ゲームはここから起動する。


このCPUの命令セットは既知であるから、このCPU用のプログラムコードを書くことは出来る。


ゆえに、この「original game ROM」の部分を「epoxy ROMS」をダンプするプログラム(トロイの木馬)に差し替えれば、「epoxy ROMS」の内容を吸い出せるというわけだ。


なぜ「original game ROM」の部分自体をエポキシ樹脂で固めないかと言うと、それだと売れ残った基板のROM差し替えて販売することが出来なくなるし、また、CPUのどのピンが接続されているかを見れば、どこがアドレスピンで、どこがデータピンであるかが確定してしまうためあまり意味がないからである。ゆえに、エポキシ樹脂で固められたROMCPUI/Oピンにでもぶら下げておくのが普通だったのではないかと思う。


このようにトロイの木馬を書いてROMを吸いだすという手法ROM吸出し方面の人には比較的ポピュラーなものであるしかし、ゲーム開発会社でこのような行為が行われてきたということに関しては私は否定的である


というのも、プログラムの参考のためにリバースアセンブルするだけであれば、大作を数本やれば十分だっただろうし(そんなに延々とリバースアセンブルばかりしているゲーム開発会社存在しなかっただろうし)、クローン基板の製作業者にとってはクローン基板が作れるかどうかは死活問題なので吸出しには懸命だっただろうけど、それでも吸出しのためにここまで手間暇をかけると元が取れるかどうかが微妙になってくる。


結果として、ゲーム開発会社にとっては上に書いたようなトロイ作成する方法はあまり馴染みがないのではないかと思う。

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)にたまたまお会いした。


そのときに私は「FPGACPU作ったりするの、コードゴルフ的な側面があって面白いっすよ。」みたいなことを彼に言った。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次元拡張していく。


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


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


次元での左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次元対応したようなソフトウェアがないとプログラムを書くのは困難かも知れないが)


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


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

・基本的に直進

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

としてきた。


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


・基本的にはうねうね

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


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


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


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


f:id:yaneurao:20130102053357j:image

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


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


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次元上に描かれたソースコードが、何かの絵や立体物に見えるというのはありなんじゃないかと、いまとっさにひねり出しました。

トラックバック - http://d.hatena.ne.jp/yaneurao/20130102
 | 

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