きのうに引き続き Iagno のソース眺め。squares[] 配列は 置ける場所が並べられた配列で、先頭から消費していって、 置くごとにその場所の数字が入ったところと交換していく的な。 一応バグは見あたらなかった。
search() は簡単に言えば、ベストな置き場所とそのスコアを返す関数と言える。 これの再帰呼び出しが意味するところは、仮にあるところに置いたとして、 その相手がベストな場所に置いた時のスコアはいくつかということ。 もしその相手が勝つのなら大きな正の値、その相手が負けるなら小さな負の値。 これを符号反転してその時の自分のスコアとする。
around() は今までにお互いに置いた場所の、 周りにまだあいている場所があるかを数えてる。 自分の石の周りなら引き、相手の石の周りなら足してる。 あいてる場所がなければ逆に、自分なら 2 足し相手は 2 を引く。 その意味するところはいまいちよくわからないが、 なんとなく最適化の余地はあるような気がする。
eval_heuristic() は、石が置かれている場所の heuristic[] を取り出し、 自分の石の周りならそのまま、相手の石の周りなら符号反転した値の合計を出す。 よくありがちな、角は有利とか、そのひとつ内側は不利とか、 そのへんの判断をする目的と見られる。
高速化の肝は search() の再帰呼び出しではないかと思われる。 先読みの深さの最後に達するのは、序盤でも数千回に達する。 すなわち先読みしていって数千種類の盤面の評価を実行している。 それはいいのだが、return する時には中身をすっかり忘れてしまうので、 一手進むとまた同じように再帰呼び出しの繰り返しをすることになる。 数千種類の盤面を覚えておけば、その続きだけを実施すればいいので、 かなり時間短縮できるんじゃないかなぁという予想。 ただし、そのためには再帰呼び出しを根本的に書き直さないといけないし、 ソートや打ち切りの処理もあるので、あまり単純にはいかない。
昼飯を食いに外に出たら、スーツやら振り袖やらの人々を見かけた。 場所的には大國魂神社、までは遠いな、もっと東府中よりだったんだけど、 見かけたのは 10 人前後で、そんなに大勢ではなかったので、 神社方面はすげぇことになっていたのかも知れない。
Sun の Java には簡単なプロファイラが標準でついてるのな。 全く、OpenJDK が出てからというもの、Java のイメージはあがりっぱなしだ。
それで、主に、どこに置けるか判定する処理が、 大変な時間を消費していることがわかった。 確かに、リバーシの思考アルゴリズムでもっとも基本的で多用される処理だ。 しかし実装はかなりまともで、それ自身にあまり高速化の余地はなさそう。 それより、search() で再帰呼び出し処理に入る前の部分、 つまり、置ける場所を探す処理と、そこに置いてみて相手の mobility()、 すなわち、相手が置ける場所の数を数えてソートする処理、 この部分をキャッシュすると、比較的簡単に性能改善が見込めるものと想定。
試しに実装してみたが、C じゃないんだからリスト構造を 自分で実装しなくてもよかろう > 自分。 単純な考え方で、再帰呼び出しと相性がいいように、 オブジェクトが木構造をなす形にしたんだが、 パスの扱いは面倒なのでとりあえず再利用はせず new するようにしてみた。 そのせいかは知らないが、終盤の全探索でメモリを食いすぎてしまい落ちたw 一応線形リストだからガベージコレクションはされると思うんだけどなぁ。
お昼頃、外を見ると雪が降ってやがった。 東京で初雪だったそうな。 確かに今朝は雪が降りそうな寒さではあったが。
人生を書き換える者すらいた。: 人材獲得作戦・４ 試験問題ほか
ちまたではこの問題を解くのが流行っているらしい。 さっそく挑戦したのだが、思ったように縮められず、 そんなうちに某ブックマークコメントには 100 字以内を達成した人がいて、 もうどうでもいいや。
$ cat c.c
#include<string.h>
int I[9999],S[9999],l[9999],i,o,n=-9999,m;f(O){if(l[O]>n){o=I[O]+2;o==7&&n<
m?m=n,memcpy(S,I,sizeof I):0;!(o&3)?l[O]=n++,I[O]=o,f(O-99),f(O-1),f(O+1),f
(O+99),I[O]-=2,n--:0;}}main(_){for(;o=getchar()+1;i+=o?1:99-i%99)I[i]=o/=13
,_=o-6?_:i;f(_);for(_=0;_<i;_++)putchar(98-_%99?S[_][" *$GS$S"]:10);}
$ cc c.c
$ cat a.txt
**************************
*S* * *
* * * * ************* *
* * * ************ *
* * *
************** ***********
* *
** ***********************
* * G *
* * *********** * *
* * ******* * *
* * *
**************************
$ time ./a.out<a.txt|sed 's/ *$//'
**************************
*S* *$$$$$ *
*$* *$ * $************* *
*$*$$$* $$************ *
*$$$ * $$$$$ *
**************$***********
* $$$$$$$$$$$$$ *
**$***********************
* $$$$$*$$$$$$$$$$$$$$G *
* * $$$ *********** * *
* * ******* * *
* * *
**************************
0.00 real 0.00 user 0.00 sys
経路探索のアルゴリズムとか覚えてないし、 調べないで書いた割には上出来じゃね? と自己満足してみるテスト。 プログラム的には、総当たり方式を若干改善した程度のものに過ぎないので、 きっと元ネタの人に言わせれば Lv3 であろう。 時間はプログラムを縮めて 読みにくくする作業 (笑) を含めても 2 時間かかってない程度。 確かに 3 時間かかっても Lv2 って人はちょっと修行が足りないのかもね。
買い物に行ったら店についてもアイドリング回転数が規定値まで下がってなかった。 水温がまだ十分でない証拠。 さすがに寒いね。
雨はほぼ上がっていたが、 強めに発進すると横断歩道の白線で軽くホイールスピンするレベル。 まあそれは良いとして、 段差を乗り越える時にいつもよりもガコガコ感があったのは、 もしかしてダンパーが冷えてたからとかそういうの? 往復で水温は 上がってたがサスペンションが十分機能するにはまだ距離が足りないってか。
回生ブレーキのやっかいな問題が出ているみたいだねぇ。 回生制動時の ABS は、普通の ABS とは全く違うので、 まだ制御がうまくできていない部分があるようだ。 普通のブレーキなら、かけすぎればほぼロックするのだけど、 回生制動の場合はロックではない中途半端なところがありそうなのと、 もしかすると、差動装置 (ディファレンシャルギヤ) を介しているのが、 またやっかいなのかも知れない。 速度が遅い時に起きているようなので、 何か事故になっても大きな事故にはならないだろうけど、 早く改善されてほしいところ。
きのうの迷路解きプログラムは、 案の定もっとまともなアルゴリズムがあるらしくて、 それを斜め読みしたあとアセンブリ言語で書いて機械語にしてみた。 なんとか 256 バイト以内には縮めたが、こうして C のソースにするとやっぱり長い。 当たり前か。
$ cat s.c char main[]="1\300fH\215L\0\2)\314\t\304\211\346F1\304\374\211\347\363\252" "1\333\215C\3\215N\2g\215\227\0@\215,\26\315\200PU\211\367\211\301`\260\n\252" "\252\255\211\4\17a\260S\362\256O\211}\0\377E\4\215]\bf\270\n\3\213}\0\350" "\204\0\0\0\211\372)\362\367\322\215\24\226\213\n\200\341\374;M\4v'\212\17" "\200\371Gt\31\200\371 u\33\211;\213M\4\215I\4\211K\4f\203\303\bu\3\213\34$" "\213M\4\b\341\211\n\376\314y\272f\203\305\bu\3\213,$9\353u\251\374Y\213\f$" "\211\367\260G\362\256\260\nO\211\372)\362\367\322\212$\226\200\364\1\350\32" "\0\0\0\200?St\5\306\a$\353\345Z1\333\215C\4C\215N\2\315\200\211\330\315\200" "1\311I\366\304\2u\31\375\362\2569\376t\21\211\312\366\304\1t\5\374GGBB\362" "\256)\327O\303\366\304\1t\371G\303"; $ gcc s.c $ ./a.out < a.txt ************************** *S* * $$$$ * *$* *$$* $************* * *$* $$* $$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$* $$$$$$$$$$$$$G * * * $$$$*********** * * * * ******* * * * * * **************************
コードは x86 Linux 用。 他の環境で動かす場合はシステムコールをなおすこと。 データ領域の実行禁止を有効にしている場合は、動かないはず。 アルゴリズム的にはきのうのよりまともで、入力も 16KiB まで受け付ける。 元のソースコードを読みたいという変人のために、 アセンブリ言語のソースも置いておく: 20100113-s.s
いすゞエルガのフィンガーシフト車で、2→3 も 3→4 もダブルクラッチを 踏む人だった。 別に乗り心地が良いわけではなかったので (クラッチミートは雑だった)、 癖なんだろうな。 でも、フィンガーシフト車はクラッチ操作とのタイミングがまずいとギヤが入らない らしいので、それで毎回ダブルクラッチってのはそれはそれで慣れがいると思うけど。
おもしろいのは、いすゞエルガ特有のギヤ選択時のガクッて振動が、 やっぱり時々発生していたことだな。 あれはダブルクラッチで軽減するものかと思ったが。
Thunderbird で、IMAP で受信しているメールの添付ファイルを開くときに、 ダイアログに出る imap:// のアドレスが間違っていることに気づいた。 アカウントを作成した当時とはサーバーのアドレスが変わっているのだが、 そこには古いサーバーのアドレスが出ていた。
アカウントの設定をいくら確かめても、 古いアドレスなど出てこないのだが、about:config の設定を探すと、 以下のことが判明した。
そこに古いサーバーのアドレスが残っていたというわけ。 とてもバグっぽい香り。
きのうのプログラムをさらに改良。232 バイト。20100114-s.s
$ cat s.c char main[]="1\300fH\215L\0\2)\314\t\304\211\346F1\304\374\211\347\363\252" "1\333\215C\3\215N\2g\215\227\0@\315\200P\211\363\211\367\211\301`\260\n" "\252\252\255\211\4\17a\260S\362\256Oj\0j\0f\203\353\b\211;\217C\4_\205" "\377u\362Wf\270\n\3\213;\371\353R\211\362\31\372\215\24\226\213\n\203\341" "\374\213k\49\351v\25\212\17\200\371Gt\n\200\371 u\t\215M\4QW\211*\b\"\376" "\314y\317f\203\303\bu\305_\205\377u\261\374\213\f$\211\367\260G\362\256O" "\270\n\306\a$\211\362)\372\212d\226\374\200\364\1\234P1\311I\375\362\256" "9\376t\32\211\312\200\344\3t\16\374GB\200\354\2r\4w\4B<GB\362\256)\327OX" "\235r\204\200? t\303Z1\333\215C\4C\215N\2\315\200\211\330\315\200"; $ gcc s.c $ ./a.out < a.txt ************************** *S* * $$$$ * *$* *$$* $************* * *$* $$* $$************ * *$$$$* $$$$$ * **************$*********** * $$$$$$$$$$$$$ * **$*********************** * $$$$$* $$$$$$$$$$$$$G * * * $$$$*********** * * * * ******* * * * * * **************************
我ながら何やってるんだか...
マーケットを見ていると、なんと、 ロック画面を独自のものに置き換えるアプリケーションもあるようだ。 よくできてるな。 標準の API でどこまで制御できるんだろ。
きのうの迷路解きプログラムのバグを修正した上、 さらに小さくしてみた。204 バイト。 さすがにこれ以上小さくするのは厳しいかな。20100115-s.s
char main[]="1\300fH\215L\0\2)\314\t\304\211\3461\304\374\211\347\363\252" "1\300\231\200\306@\215X\2\215N\3\223@\315\200PSSKt\366\215^\1\211\337\211" "\301\260\n\252\252\210\4\17\260S\362\256Of\203\353\b\211;\217C\4_\205\377" "u\362W\264\4\213;\371\376\314y&f\203\303\bu\361_\205\377u\335\213~\375\353" "\fZ1\300\353\257< u\367\306\a$\211\362)\372\212$\226\200\364\2\234P\260\n" "\320\354\31\311\375\362\256\211\312\320\354r\a\374GG\343\2BB\362\2569\376t" "\350\31\327X\235\212\as\311\211\362)\372\215\24\226\213\n\203\341\374\213k" "\49\315s\232<Gt\n< u\222\215M\bQW<\211~\375\211*\b\"\353\347";
きのうのプログラムは、1 行目を経由する経路を探索しないという バグがあった。1 行目が壁だったらいいんだけど。
このプログラムは、読めばわかるように、行ごとに分割せず、 経路を探す時にいちいち改行文字を探しながら行単位の移動を実現している。 その処理に 34 バイトも使っているので、そのへんは改良の余地あり。 しかしそこを変えると、最後の出力処理が長くなってしまうので、どっちもどっちか。 あと、システムコールを他 OS 用に変えることさえ困難な状態にしてしまったw
Wii に入れたスーパーマリオ USA を時々やってみている。 いつも 1-1 → 1-2 → 1-3 → ワープ → 4-1 → 4-2 → 4-3 → 5-1 → 5-2 → 5-3 → ワープ → 7-1 → 7-2 まで割と順調にこれるのだが、7-2 がほんとに難しい。B ダッシュで 飛ばしまくって、EXTRA LIFE をもらうチャンスすら逃しているのが、 いけないのかも知れない。
この前やった時は、1-3 で薬瓶をテキトーに投げたら、 扉が壺の上の横っちょに浮いた状態で現れてしまって、 扉に入ることができずワープできなかった。 他にも、いつもジャンプが使いやすいピーチでやってるのだが、 つい癖でボタンを連打したことにより、5-3 にピーチで突入してしまったため、 ワープゾーンに行くことができなかったりもした。(ルイージ以外では かなり難しいと思われる。)
ちょいとレンタルビデオ屋まで出かけたのだが、 途中妙に学生 (に見える人々) をたくさん見かけた。 最初は部活帰りか何かかと思っていたのだが、そうだ、 大学受験な人たちはセンター試験の季節なのか。 このあたりは大学もたくさんあるから、センター試験の会場になっているのだろう。
ベッドのシーツを洗濯。 最初普通に洗濯機を回し始めたのだが、 ふと気になって説明書を読んでみると、 「毛布」コースの説明に 「シーツなどの大物が洗えます」みたいなことが書いてあって、 途中で止めて「毛布」コースに切り替えたのであった。 「毛布」コースでは、水位が強制的に 60L に設定され、 洗濯槽に見たこともないほどたっぷりの水が注がれる。 ふろの残り湯を使うのが良い。
洗剤と洗濯機のおかげで黒ずんでいたシーツはぴかぴかに。 ついでにマットレスをどけてベッド下などを掃除。 本当は去年の年末の大掃除でやるつもりだったのだが、まあいいか。
スーパーマリオ USA の 7-1 と 7-2 のショートカット技を知り、 だいぶ楽になることはわかったものの、7-2 の最終ボス今日だけで 5 回以上 挑戦したのだが全部失敗した。 難しい。
YouTube で見つけた動画はたぶん GBA か何かの焼き直し版で、 絵がきれいになってた。Wii のバーチャルコンソールは、 色遣いから音楽まで全て NES そのまんまで、 スプライトが増えると処理落ちするのももしかして NES と同じか。 モニターは 15 インチブラウン管テレビなので、 画面も NES と同じ... いや、当時はフラットブラウン管なんてなかったはずだし、 ビデオ信号は RF 端子を通していたから今とは違うか。
調べてみたら Wii を RF 接続する方法もあるらしい。 へぇー。
職場の Windows Vista の PC で、 何もしてなくても HDD をアクセスしているのが気になっていたので、 少し調べてみたところ、SuperFetch と Prefetch という機能が原因らしい。 試しにオフにしてみたら HDD アクセスはなくなった。(最適化もすでに切ってたかも。) しかしこの PC はメモリー 2GiB あるので、 オフにしたことで全体としての性能が良くなるかは不明。 ただ毎日使ってる環境ではないし、 たまにしか使わないオフィスとかは、起動遅くても気にならないしな。
それより私物の工人舎 SC3WP06GA のほうが効果ありそう。 メモリー 1GiB しかないし、HDD は サムスンのもっさり 1.8 インチだし、Atom Z520 は SuperFetch のタスク切り替え だけで CPU 使用率が跳ね上がりそうな代物だし。 この中で HDD が一番重要かな。 かちゃかちゃうるさいしたまにカキーンとか変な音するので、 アクセスがやまないのは精神衛生上もよろしくない。 まあそもそも最近使ってないんだけどねぇ。
二次会のカラオケに行ったら、あっという間に終電を逃してしまい タクシー帰宅。日産ティアナの個人タクシーだった。2,420 円。予想の範囲内。
カラオケ屋には、スリープ中のリモコンを持ち上げただけで、 演奏中の曲がいきなり一時停止したり演奏終了したりしてしまう 地雷リモコンがあった。2 人で別々のタイミングで起きたので 偶然ではなかろう。どんな故障だよw
スロット部分でうまいこと EXTRA LIFE を稼げて、 最大で 9 までいっていた。7-2 はさすがに何回かミスったが、 それでも 5 くらい残してクリアできた。 エンディングで各キャラクターの使用回数が出るけど、ピーチ 9 回の表示。 つまり 1-3 と 5-3 のワープまでの分は含まないらしい。
Wii のバーチャルコンソールなんだが、ゲーム途中で「Wii メニュー」に戻ると、 その状態が保存されるという機能がある。 それで、この The End 画面の状態も保存されてしまう。 このエンディング画面では NES のボタン操作はすべて無視されるので、 ゲームを最初からやるには、The End 画面のままで電源を落として入れ直すか、 メニューからリセット操作を行う必要があるようだ。
Powered by Tomsoft Diary System 1.7.4
Hideki EIRAKU