週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
生協の出資金返還をしましょう。一万六千円が返ってきます。
http://www.utcoop.or.jp/Hbumon/somu/info/info4Pn.html
必要なものは組合証と印鑑です。キーホルダーとかよくわからないものが指定されていますが私の場合は特に必要ありませんでした。
スポンサーサイト
はい,n階は第n階層とはちがいましたね。道理でまだ簡単だとか短すぎないかとか思いました。あと全然全滅しないとか。

たった今ちゃんと全滅してきました。回避策はわかったので次は負けませんよ。

ところで、スキルのHPブーストとかを、ブースト発動のときにHPが上昇する能力だと思っていたのは私だけでしょうか。ブーストという単語がかぶってるので混乱すると思うのですが。
こんなこと書きつつ実は買っていました。

世界樹の迷宮を。

昨日はちょっとキャラを作って一階をマッピングしていろいろ死に掛けて終わったんですが、今日は気がついたら五階に到達してしまいました。私は特に何もしていないんですが。。

なんかよく全滅するとかめんどいとか面白いとかいろいろ聞いたような気がしましたが、まだ全滅してません。チキンですから。
アイスティーを頼んだら、アイスティーとガムシロップと、それから牛乳の入った小さなポット(?)が出てきました。

そのままガムシロップ、牛乳をアイスティーに入れて混ぜると、よくガムシロップの一部が底にたまってしまいます。

ここでふと思いついて変な行動を取りました。まずガムシロップを牛乳に投入してよく混ぜます。そしてこれをアイスティーに注ぎました。すると、とけ残りもまったくないミルクティーができました。めでたしめでたし。

なんでこの行動はうまく行ったのでしょう?ガムシロップをアイスティーに投入すると溶け残りが多く、ガムシロップを牛乳に溶かしてから投入すると溶け残りが少ない。この差はどこからできるのでしょう?

確かにうまく行くような気がして、さらにそれは成功したのですが、その理由を説明できません。

3/16 帰ってきてからなぜかDungeon Crawlを進めていました。こういうときにやるのは正気の沙汰ではないのですが...

獣にヒドラがいたのでオークの坑道に逃げ込み、オークの坑道にオークの魔道士がいたので蜂の巣に逃げ込みと散々でした。蜂も数匹に囲まれると非常に危険なので、吹き矢を使ってちまちま片付けています。まだLv12しかないので危険ですね。

ダンプは続きに

3/16 ACM ICPC World Finalsから直行して聞きに行きました。
最速の班は20秒きり。去年20秒台がでてすげーと言っていたのにこの水準には驚きです。
でも全体で動いたのは二つの班だけでした。動かないとさびしいとしか言いようがありません。

早い班では+NOPフラグをつけて"ADD&NOP"のような命令を開発してました。NOPをこれで処理すると命令キャッシュが汚染されにくいとか。この辺はいろいろ知らないので私が正確に理解しているかは疑問です。あと、クロックを90度や180度ずれたタイミングで使うのは一般的なんでしょうか?配線遅延を回避したいと思うとそういう手段に出るのはありそうですが。

それからCでコンパイラを書くのは正直すごいといわざるを得ないです。

sqrtを書くのに失敗したり、なぜか開平方で求めようとしたりしていたのが非常に気になりました。今年は連続系の担当が替わってしまって、ニュートン法とかsqrtはsqrtの逆数を求めたほうが楽とかをやってないとかいう話で。カリキュラムであれになるのはいろいろあれですねぇ。

それから、「とりあえず動かす」と言った班が最終発表会で動かないケースが多かったですね。意欲の問題でもあるのかもしれませんが、「とりあえず動かす」は「動くものを最速で作る」とかにするといいのかもしれません。
「『適当に作る』を『適当にすぐ作る』に変更する」と解釈すると、日常生活にも適応できそうな気がします。気のせいです。変更するのも締め切り直前です。

一年前まで参加していたACM ICPCの世界大会です。 今年は舞浜のヒルトン東京ベイで行われました。世界中の超頭脳が日本に集まる!!

年齢制限のためもう選手としては参加できません。代わりにスタッフとして参加してきました。もう一度世界大会に参加できて非常に感動です。

やったことは案内とか設営手伝いとかいろいろ。 広報部門であるDigital Media Teamを案内したりもしました。ディズニーリゾートラインを何周もしました。くるくるくるーっと。

期間中に日記を書くような体力すらありませんでした。昨日もばたんきゅーでしたし。

私は行きませんでしたが、今日とか明日とかは秋葉原に奇妙な観光客が増えていることでしょう。と思いましたがあそこはそもそもいつも奇妙な観光客でいっぱいでしたね。

囲碁の記事は一週間以上お待ちください^^;
モンテカルロ法とmultiarmed Bandit problemの話を書かないといけないと思っているのですが。一身上の都合で物理学の論文ばっかり読んでいます。

取り急ぎリンクだけで失礼します。

やねうらおさんの記事でこのことについて触れていて、そのコメントでやねうらお氏本人が探してきた記事があります。

行く先々で世界樹の話が書いてあると、
ネタばれ回避のために私も買わなくてはいけないような気がしてきます。

えーとこれでよいんでしたっけ?

間違いました。
直前のエントリーのように、awkとHaskellに頼りまくってまでgnuplotを使うのはどうなんでしょう。 awkのone-linerやsortなどの小さいプログラムを使うのはまだいいんです。

問題はHaskellのコードです。この中では、gnuplot命令を柔軟に使うためにデータ型や関数をたくさん定義しています。 たとえばgnuplotのplot命令を、次のような型の関数にしています。

plot :: Maybe (Double,Double) -> [PlotData] -> GPScript ()
第一引数はxの範囲、その次にグラフそのものであるPlotDataを可変個数で与えると、結果はWriter MonadであるGPScriptというところにgnuplotのplotコマンドが送られます。 yの範囲を指定できなかったり、媒介変数モードを考えてなかったりするほかは、 基本的にplot命令すべてがHaskell的文法で実行できるようになっています。 さらにPlotDataは、ファイルに保存されたデータと"sin(x)"のような式とが両方扱えるような形式になっています。 結果、このGPScript.hsというHaskellライブラリは200行くらいあります。長くはないですが、簡単に書けるコードではなかったです。

ここまで固めてしまうと、ちょっと違うグラフを描きたいときに柔軟に対応できないという事態にもなりかねません。そうすると、データを別の角度から見るとかそういうことに億劫になって、作りやすいグラフだけ作る見たいなことになり、研究の妨げになりえます。

RとかROOTとか、もうちょっと記述力のありそうなデータ処理ソフトを使ったほうがいいかも知れません。あるいは私がもう少しそういう別のグラフを描く手間を惜しまないか。惜しみますが。

ちなみにAn Introduction to Rはデータ型の説明ばかりでなんか興味が惹かれなかったんですよね。他の文章をさがしてみます。

[学習意識調査]日本の小学生は中韓より「学ぶ意欲」低い livedoor ニュース

この調査をした日本青少年研究所って何でしょう?

日本青少年研究所のウェブサイト発見。財団法人。
以下このサイトの中で発見したもの。リンクは面倒なので探してください。

概要:所長は千石保。

役員一覧:あれ、所長しか常任じゃないぞ。東京高検検事出身。

財団の歩み: 昭和50年に千石保が一人で作って、それからずっと一人なんですね。

結論:よくわかりません。
昨日、初めてawkスクリプトを触りました。
awk '$3==200.0 && $4==3.0 && $2==1.0{print$1,$5}' peaks.dat
こんなコードです。テーブルが5列あって、四変数の関数となっていたので、 そのうち三変数を固定したテーブルを作りました。 今までこのような操作はperlでやっていました。今回はなぜか、気がついたらawkを調べていました。魔がさしたんでしょうか。 awkスクリプトは全く知りませんでしたが、 検索してトップに出てきたサイトを参考にしたら、この程度のことはすぐに書けました。 簡単に書けて感動です。 awkはこういう操作を簡単にするためにあるんだ、という感じの簡単さです。 作者の意図が伝わってくるというかなんというか。

上のコードの周りはこうなっていました。

plot "< awk '(中略)' peaks.dat | sort -n" notitle w lp
gnuplotのplotコマンドのファイル名が、awkのone-linerになっています。 gnuplot tips/UNIXのコマンドを利用するを参考にしました。 そう、このページを参考にしていたからawkを見たのでした。

はじめはawkに頼らず、

using 1:($3==200.0&&$4==3.0&&$2==1.0?$5:1/0)
のように、プロットしたくない点を1/0と指定して消去する方法を使おうとしていました。 しかしこれではだめです。プロットしたい点の間に消された点が大量にあるため、 プロットしたい点は孤立しているとみなされ、点同士を線でつないでくれません。 awkを使えば、必要な点だけがgnuplotにわたるので、このような問題はなくなります。 ちなみにawkの後のsortコマンドは、グラフをx軸の小さいほうから順番に書くために必要です。 これがないと、点が変な順番でつながれてしまいます。

さらに、上のgnuplotコードは次のコードから生成されたものでした。

plotFile="< awk '"++condition graphIndex1 cond1
     ++" && "++condition graphIndex2 cond2
     ++" && "++condition drawIndex z
     ++"{print"
     ++"$"++show (xaxisIndex+1)
     ++","++yaxis
     ++"}' peaks.dat | sort -n",
これはHaskellのコードです。 x軸に指定する変数を順番に変更し、 そのほかの変数を固定する値も変えつつ、さまざまなパターンのグラフを生成しています。 実物がないとうまく説明できませんが、グラフを縦横に並べることで五次元のグラフを生成しているという荒業をやっていた、と書けば、むちゃくちゃさがわかるでしょうか。 これはHaskellのListモナドとWriterモナドを駆使して出来たものです。 Haskellがあればこの程度のグラフの大量生産も苦もなく出来ます。 あ、本当は半日くらいかかりました。大変な苦労でした。 それでもこの作業のおかげで、今後着目すべき値の範囲がわかり、 闇雲に計算をしなくてすむようになりました。

というわけで、私の初めてのawkスクリプトは、モナドまみれになったのでした。 おしまい。

前回モンテカルロ法の論文の紹介をしましたが....どうも読みにくいですね。数式を分析するよりも実用を紹介したほうがわかりやすいのでしょうか。実用例の論文をあまり探していませんが。特定の例にはあまり興味がないです。

閑話休題。

Kearnsらの示したモンテカルロ法は、計算時間がゲームの状態数に依存しません。 しかし、計算時間そのものがまだかなり大きく、単純に実装しただけでは現実的な計算量にならない(らしい)です。

適用するゲームを限定すれば、いろいろと改善策は作れます。山下さんのページにもありますが、明らかにだめな手をランダム候補からはずすだけで性能はよくなります。

そして本題です。id:ajitakへの解説の意味をこめて。

Kocsisらはもっと汎用的に、モンテカルロサンプリングの性能を向上させる手法を提案しました。 それは、モンテカルロ法で「ランダムに手段を選ぶ」際に、一様なランダムではなく、特に調べる必要のある有利な手段だけを優先的に調べるよう、確率を偏らせることでした。

Kocsisらの手法におけるモンテカルロ法は、Kearnsらの論文のものとはちょっと違います。 探索開始の際の状態から、たとえば10手先までランダムに手段を選んでシミュレーションします。この選んだ手段と、その結果の状態の成績を記録します。 この「10手先までランダムに予測する」を何度も繰り返して、最も成績のよいものを最適手段として最終的に選びます。 たぶん、Kearnsらの提案手法と比較して、性能は大して変わらないのではないかと思います。(後で調べます。)

Kocsisらの改良点はここからです。 「10手先までランダムに予測する」を何度も繰り返すと、たとえば1--3手目などでは、以前のシミュレーションと同じ途中状態になることがよくあります。 このとき、その次にとれる手段のうちいくつかについては、以前のシミュレーションの得点がわかるわけです。この情報を根拠に、以前成績がよかった手段がより多く選ばれるように確率を偏らせます。

ゲーム木の探索で知りたいのは、「各プレーヤーが最適の判断をすると仮定したときに、この局面での最適の手段は何か」です。 そのため、先の局面で最適と思われる手段については、より詳しく調べる、というのが合理的ですね。

さて、ここでひとつ問題があります。 モンテカルロシミュレーションは全探査していないので、計算途中で成績がよくなっていても、それは偶然かもしれません。 ある手段をとったときに成績がよいと評価されても、それは実はその後の局面をシミュレートする際に相手がひどく悪い手段を選択したため偶然成績がよく見えるだけであり、全探査した際にはぜんぜんよい成績でないかもしれません。 このような当てにならない途中の成績を手がかりにして乱数を偏らせるようなKocsisらの手法は、本当に安定なのでしょうか。モンテカルロ法の初期の結果にその後のシミュレーションが引きずられて、時々ひどく失敗したりすることはないのでしょうか。

実はこの辺もちゃんと調べてあります。詳しくは次回。

日本語版Dungeon Crawlのバージョンがあがっていたので、ちょっと日記のねたになるかと思ってやってみました。このダウンロードが命取り、かも知れませんが。

いろいろ忘れているので、とりあえず信仰を選ばなくてすむ神々の末裔でやってみました。職業は聖戦者。

新バージョンで、 探索が中断したときに何の理由でとまったのかいちいち聞いてくるのはよい感じですね。昔はよくわからない理由でとまっていたので、探索コマンドを連打していました。 今も連打していますが。

キャラクタは二三人燃えるショートソードを持ったコボルドに焼かれたりした後、一匹が普通に序盤を突破しました。ポイントは次のとおり。

  • 3Fくらいで吹き矢筒を持った敵が出てきて毒矢ゲット。モンスターの持ち物のバグを直したから吹き矢筒が手に入りやすくなったのでしょうか。おかげでオーガも余裕
  • 久しぶりなのでスキル成長をどうすればよいかわかりません。とりあえずたまった経験値は躱し身につぎ込んでいます。
  • 6Fでオークの魔術師/司祭の群れ。透明の指輪で翻弄しようとするもののダメージが大きく、上に戻って回復してもう一回透明になってとかやったところ魔力汚染。虚弱+空腹+草食がついてしまいました。獣で出た突然変異治癒で消しましたが。
  • 魔除けのツモがよく、早いうちに耐減速を拾いました。聖戦者でこれはうれしいです。
  • 獣の棲み処1Fで、装備してもわからない指輪を発見。鑑定したら耐毒。
  • 大トカゲをヤモリ並みの敵と勘違いしてうっかり近づいてしまい瀕死に。
  • 獣2Fでやっと長剣を発見。
  • 現在、獣8Fに人喰いヤクの群れとヒドラがいて、ヒドラだけ7Fに引きずってきたら大ダメージを受けて死に掛けました。一ターンで50くらい食らったような。AC低いので仕方ないですね。

今のところは

  1. 効く敵は毒矢
  2. 火炎の武器で殴り
  3. やばかったらバーサーク
という感じでやっています。スキルは今は長剣につぎ込んでいます。

なんか装飾品のツモが異常にいいです。耐毒と霊視がそろったので20F位までは安心してもぐれます。一方で武器と消耗品の出がよくない気がします。高レベルワンドが出てないのでいきなり階不相応の敵が出てくるとやばいです。俊足もないですし。

神々の末裔はパラメータが高く、特にMPが高くて苦手なスキルがないので、この手の魔法戦士をやると結構楽だったような記憶があります。この戦法だと経験値が不足気味になりますが。

それから重要なこととして、魔法系統では神の下賜に期待できません。 魔法書は出なくても泣かないですむような戦略を組む必要があります。 どうしたらよいか思い出してます。

ダンプは続きに

Michael Kearns, Yishay Monsour, Andrew Y. Ng, `A Sparse Sampling Algorithm for Near-Optimal Planning in Large Markov Decision Processes', Machine Learning,49,193--208,(2002) [pdf]

まず、モンテカルロ法を利用したゲームのAIについての論文を紹介します。 私はこのあたりも詳しくないので、目的の論文を理解するまでに関連研究を複数読まなければいけませんでした。さらに、その前にark君にちょっと話を聞いて、以下二つの山下さんのページを教えてもらいました。

ゲームのAIではたとえば、ありうる状態を現在状態からすべて探索して、相手がどんなに頭がよくてもあまり負けない手を選びます。ここの「すべて探索」ができてしまえば、コンピュータの完全勝利です。先手必勝か後手必勝かもわかってしまいます。

しかしたいていのゲームは状態数が多いです。状態数が少ないのは○×三目並べみたいな簡単なゲームだけです。すべて探索をしていると日が暮れるどころか鬼が笑います。そのため、コンピュータは10手先とか20手先とかまで読んで、読んだ盤面についてどちらがどの程度有利かを適当に判定して済ませます。

モンテカルロ法は、そもそもすべて探索するのをあきらめます。 ゲームの状態数が非常/無限に大きい場合は、 計算量が状態数に依存するアルゴリズムは不利です。 Kearnsらは、適切な量のサンプリングと適切な深さの探索を行えば、 最適戦略に十分近い戦略を選ぶことができること、そして、 その計算量が状態数に依存しないことを示しました。

彼らの提案は、ゲーム木の幅と深さを両方制限しています。 幅の制限とは、たとえば取れる手段が毎回108式まであるときに、そのうち一定の個数をランダムに選んでます。 この上で先読みの深さも制限していて、結果的にゲーム木の部分木の上で探索をすることになります。

モンテカルロ法では全探査はしないので、この結果提案される手法が間違っている、すなわち全探査でわかる最適手法から外れることもあります。提案される手法によって得られる得点の期待値(提案される手法自体が確率的に変動するので、それを平均化した期待値)を、全探査による最適手法で得られる得点と比較して、差εが一定値より小さくなればよい、とします。Kearnsらはその状態になるまでの計算量を測っています。

計算量が状態数に依存しないなら何に依存するのかというと、εのほかに評価値の最大値、そして深読みの深さに関係するγです。εは当然入るはずで、これと同じ次元を持つ評価値に関係する値も入るのは納得できます。

ただγ、これは個人的に疑問が残ります。

γは次の式に現れます。sがゲームの状態、dが探索の深さ、aが状態sのとき取れる行動、Rsaがsの状態でaの行動をとったときの報酬をあらわし、V(s,d)が、状態sのときに探索の深さdだったときの、合計報酬の見積もりとすると、

V(s,d) = Maxa Rsa + γV(s',d+1)
みたいになります。s'はsの状態からaの行動をとったときの先の状態です。書いていてわかりにくい気がしますが。あと、この式ではdは意味ないように見えますが、dが一定の大きさになるとγVの項自体が消えます。あるいは全部消えてゼロになります。

このようにγ深読みしたときの評価値の重みになっているので、深読みの長さに直接かかわります。そのため、γに依存するというのは間接的にゲームの深さに依存するのではないかなと疑問に思います。

このγが入ってくる理由は、全探査法が一定の深さで打ち切ったりγのような項を入れていて、モンテカルロ法が全探査と性能を比較しているから、条件を同じにするために入れたとかでしょうか。よくわかりません。もっと簡単な話かもしれません。

Levente Kocsis and Csaba Szepesvari Bandit based Monte-Carlo Planning[PDF]

ゲームのAIの話です。 ゲームのAIはID(反復深化法)とα/βカットしか知らない素人ですが、 id:ajitakの記事に興味を持って突っ込みを入れてしまったので、責任を感じでちょっと読んでみました。 ちなみに、この論文は

と経由して見つけました。

この手の論文は検索するとほぼ確実に見つかりますね。特に最近の、コンピュータ系統の論文なので見つからないはずはないと思ってました。

新聞の科学欄とかで出てくる発見も、適当に検索かけると現地の話が出てきます。もっとも、生物化学などのジャンルでは、大学の論文検索を利用しないと、論文まではなかなか到達できませんが。

先ほど紹介した松田さんのページは、gnuplotで検索したときに上位に来ます。
そのため私はgnuplotの情報だけを読んでいました。しかしちょっとトップに戻ると、
データの可視化と解析ツールなんていう面白いページがあるではありませんか。
素粒子系の人たちが使っているROOTとかも載ってますよ。使い方はよく知りませんが。
ここまで、gnuplot体験についてにょろにょろ書いてきました。

最後に、私が採用しなかった方法についてちょこっと書いてみます。 試していないので、こんな方法もあるよー程度の信頼性ですが。

まず、gnuplotを利用するのに、今回のようにgnuplot命令と座標データとを別々にファイルに出力するほかに、C言語の子プロセスでgnuplotを使役させるという方法があります。 東京電機大学の松田さんのGnuplot Tipsに説明があります。私みたいにWindowsで使っている人は、pgnuplot.exeを呼び出せばできるはずです。

複数のスタイルを並べる際に一瞬multiplotという名前を出しました。これは私が血迷っただけで、ここの用途ではmultiplotは完全に誤った判断だと思います。 multiplotは本当にさまざまな図を並べることができる命令です。使用例は gnuplot tips#図の中に図を描きたいgnuplot tips#表示方法の異なる2つの図を横または縦に並べるにあります。 自由度が高いので、逆に同じにしなくてはいけない情報、たとえば今回の場合だとx軸y軸の範囲、などはちゃんと同じであると指定しないといけません。「範囲は二つ同じで適当に決めて」という指定はたぶんできないのではまりです。

鏡はwith vectorsを使わなくてもかけます。たとえばwith linesを使えます。 with linesをそのまま使うと線が全部つながってしまいますが、 線をつないでほしくないところを一行の空行であけると線がちゃんと切れて、 結果、たくさんの線分を描くことができます。

あと、ここで~できないとか書いてあるのは、私がそれをやる方法を知らないだけかもしれません。突っ込み大歓迎です。

前編があります。 前回は gnuplotが出てこないところできってしまいました。 今回はがんがん出てくるのでご安心ください。

画像に出て欲しい情報は次のとおりです。

  1. 鏡の中の人
  2. 鏡の中の鏡
  3. 反射経路、鏡の中の像がどこの像から反転されたかを示す、 鏡によって垂直二等分される線
  4. 視線すなわち像と人とを結ぶ線。視線が所定の鏡の像と交差していれば像は見える。

これらをgnuplotで表示します。gnuplotへはどう情報を渡せばよいでしょうか。 今度はgnuplotの座標指定方法とスタイル一覧を見ます。 gnuplot tipsを参考にしました。以下、このサイトへ多くのリンクを張ります。

まず、目的の絵を描く方法を確認するためにスタイルを決めます。 スタイルは点を打つとか線を引くとかということです。スタイル一覧を参考に。

人と像は点なのでpointsでかまいません。反射経路は折れ線になるので、linesで表現できます。鏡と視線はつながった折れ線にならなかったので、vectorsで対応しました。vectors noheadとすると矢印のない線分がかけるので、これを使いました。

ひとつの図の中に、点や線分など複数の情報を入れる必要があります。複数のグラフを描くならmultiplot と一瞬思いました。しかしこれはフェイクです。 plot (人の座標) w p, (鏡の座標) w vectors, (視線の座標) w vectors のようにplotコマンドに複数の情報を並べて書けば十分です。

データごとにスタイルを変えたいので、逆にスタイルごとにデータを分けました。 一つのファイルに入った複数のデータをプロットするには?を参考に、indexを使うことにしました。そのためデータはそのスタイルごとにまとめて、スタイルの変わるところは改行二つで区切ることにしました。 この方法だと、たとえば像が見えないなどで偶然そのスタイルを使うデータがなかったときに、indexがずれてしまうという欠点が後に見つかりましたが。

以上でgnuplotの情報はすべて確認できました。

使うスタイルを決めると、スタイルの要求する形式に合わせてデータ出力コードを書きます。 像ならx座標 y座標をスペースで区切って一行に並べればよいです。 折れ線も、折れ線の通過する順番に行を並べるほかは、像と同じくx座標 y座標と書いておけばよいです。 鏡のための線分は、x1 y1 x2 y2を空白で区切って一行で出しました。 これらのデータは、入力ケースごとにひとつのファイルに出力することにしました。

最後に、座標データををgnuplotで画像に変換するコードを書きます。この部分はperlに手伝ってもらいました。 複数の入力ケースが存在するため、ケースごとにひとつの画像を作ったほうが便利です。 複数の画像を作るには当然同じ作業を繰り返さないといけませんが、gnuplotは繰り返しが得意でない、正確にはgnuplotに繰り返し作業をさせる方法を私がよく知らないので、ここの部分はperlに手伝ってもらい、入力されたファイルの個数分の長さのスクリプトを作りました。

具体的なperl scriptを載せます。

print "set term post eps enh color\n";
linestyle();
for ($num=1 ; $num<=134 ; ++$num ) {          # # of images is 134
    $f = "graph-$num.dat";                     # coordinate data file name
    $image=sprintf 'eps\\mirror%03d.eps',$num; # output image file name
    hoge();
}
sub linestyle{
print<<"END_OF_HEAD";
set style line 1 lt 1 lw 4
set style line 2 lt 2 lw 4
set style line 3 lt 1 lw 1
set style line 4 lt 2 lw 1
set style line 5 lt 0 lw 1
set style line 6 lt 3 lw 1
set size ratio -1
END_OF_HEAD
}
sub hoge{
print << "END_OF_PLOT";
set out '$image'
plot '$f' index 0 notitle w p pt 1 pointsize 4,\\
'' index 6 notitle w p pt 2 pointsize 2,\\
'' index 1 using 1:2:(\$3-\$1):(\$4-\$2) notitle w vectors nohead ls 1,\\
'' index 2 using 1:2:(\$3-\$1):(\$4-\$2) notitle w vectors nohead ls 2,\\
'' index 3 using 1:2:(\$3-\$1):(\$4-\$2) notitle w vectors nohead ls 3,\\
'' index 4 using 1:2:(\$3-\$1):(\$4-\$2) notitle w vectors nohead ls 4,\\
'' index 5 notitle w l ls 5,\\
'' index 7 using 1:2:(\$3-\$1):(\$4-\$2) notitle w vectors nohead ls 6
END_OF_PLOT
}
こんな感じになります。上のほうは繰り返しとファイル名指定、sub linestyleのところは線や画像のサイズの決定、sub hogeのところがプロットコマンドです。 画像サイズのところで、set size ratio -1とあるのは、xyの縮尺を同じにするという指定です。これをしないと直角が直角に見えなくなるので、ちゃんと反射しているように見えません。 プロットの部分、index ~の部分は実際のデータを見ないと意味不明でしょうが、上から人、見える像、鏡1、鏡2、鏡1の像、鏡2の像、反射の経路を示す線、視線となります。

with vectorsで描画するところには謎のusing指定が入っています。これはvectorsの指定が(x,y,dx,dy)だったのに、私は間違えて(x1,y1,x2,y2)としてしまったので、それを修正するために(x1,y1,x2-x1,y2-x1)と書いたのです。using指定のところは括弧でくくってこのような式を書くことができ、その際$1,$2などと書くことで1,2カラム目の値を参照することができます。ただし$文字はperlの変数開始文字になってしまっているので、バックスラッシュでエスケープしています。

この作業によって、プログラムが何をしているかよくわかるようになりました。 目で確認することによって、どのような位置の像を見逃しているかわかり、 デバッグが驚くほど早くなったのです。

可視化は問題作成に貢献しましたが、それらはほとんどほかの人には見えません。 なんだかもったいないですね。 ということで、解説pptに可視化画像を大量に張り込みました。 解説とかまじめに書いてなくてすみませんね。


追補編を書きました。

プログラミングの問題作成/問題解決におけるgnuplotの活用法について解説します。

先週末にACM-ICPC OB/OGの会による、ACM-ICPC World Finalsへ向けての冬合宿がありました。 私はスタッフとして、問題をいくつか担当していました。 そのうち、"the Phantom"という問題が厄介でした。 部屋に一人の人と二枚の鏡があり、人の座標と、鏡の端点の座標が与えられたときに、人が確認できる人の像の数を数えるプログラムを作れという話です。 想定解法はシミュレーションです。像の位置を計算して、その位置にある像が鏡を通して見えるかどうかを判定します。

評価するために、まず見本となるプログラムを作ってみました。 これ自体は比較的すぐにできました。 次にこのプログラムが本当に正しいかどうか検証しようとしましたが、 これがなかなか難しいのです。 適当な入力については、おそらく正しい値を返してきます。 しかし、鏡と人の配置についてすべてを想定しているわけではないので、 これで正しいとするわけにはいきません。 多くのデータを与えればかすかな間違いも見出せるかもしれません。 しかしそれら多くの値について正しい値は必ずしもわかりません。 こういうデータ生成・検証はプログラムがやればいいのですが、 そのために必要なプログラムはまさに今作っているプログラムです。

このジレンマを解決するために、可視化をしてみました。 与えられた入力に対して、 鏡と人の位置と、それから鏡の中の人の像と鏡の像をすべて二次元上に 画像として出力するのです。 画像を人が見れば、像が正しい位置に来ていること、 それから見える像がすべて列挙されていることが確認できます。 画像を出力するには、解答プログラムであるCやJavaで画像ファイルを出力してしまう、Metapostコマンドを吐き出すなどの方法が考えられますが、今回はgnuplotを使いました。gnuplotを使う利点は次のとおりです。

  1. 解答プログラムは座標情報だけを出力し、他のプログラムで見た目を制御したほうが、結果の図形が複雑になって見た目が損なわれたときに対処しやすい。また、図がおかしかったときに座標の値だけをテキストエディタ等で確認できる。
  2. gnuplotは縮尺を適当に設定し、座標軸を勝手に引いてくれる。
  3. eps形式で出力すればベクタ画像として出力されるため、構造が複雑になったとしても拡大すれば何とかなる
もちろん、私が慣れているということも利点の一つです。

長くなったので続きはWEBで次回.次回書きました。追補編も書きました。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。