2013年9月21日土曜日

クッキークリッカーとプログラマ

このブログ記事をはてなブックマークに追加

先週ぐらいからクッキークリッカー(Cookie Clicker)というJavaScriptを使ったブラウザゲームが流行っている。クリックするだけのゲームと聞いて、最初はあまり興味を持てなかったのだが、自分の周りであまりにもやっている人が多いので少し遊んでみることにした。

クッキークリッカーを簡単に説明すると、まずはクリックすることでクッキーを作り、作ったクッキーを使ってクッキーの生産性を高めるためのアップグレードやアイテムを購入し、たまに出現するゴールデンクッキー(Golden Cookie)をクリックすることでさらに多量のクッキーが得られるので、それらを駆使してできるだけたくさんのクッキーを作るというゲームだ。

このようにとてもシンプルなゲームなのだが、最初はちまちまとしか作れなかったクッキーが徐々に増えていき、様々なアイテムやイベントを通すことで、終盤では毎秒数千億クッキーを作れるというところに人々を惹きつける魅力があるらしい。しかし、自分は「人間の代わりにプログラムを働かせることでどこまで効率が良くなるか」という目的のために自動化プログラムを作成したくなった。コンピュータは人間を楽にさせるために存在するべきだ。

このゲームはJavaScriptで作られており、そのコードや変数を修正すれば簡単にチートを行うことができる。しかし、自分はそれについては全く興味がない。元のシステムには全く手を入れずに人間が操作する部分のみをプログラムで最適化したいのだ。

まず、最初に考えついたのは自動クリックだ。これは様々なツールが世に溢れているのでそれを使っても良いのだが、プログラマだったら、このぐらいは自分で作りたい。そこで、Pythonとpymouseを使って自動クリックプログラムを作成した。これで、毎秒100~200クリックすることができるようになった。これ以上の速度にするとブラウザがついて行けずプチフリーズを頻繁に起こし逆に生産性が落ちてしまう。因みに画面上のエフェクトなどは設定で消しておくほうが良いだろう。

次に、ゴールデンクッキーへの対処だ。ゴールデンクッキーはランダムな間隔でブラウザ上のどこかに出現する。そのクッキーをクリックすると溜まっているクッキーの1割分の枚数が貰えたり、一定時間現在の7倍の効率でクッキーを焼けるようになったりする。この効果はかなり大きく是非ともこれを自動化したい。

最初は一般的なテンプレートマッチングにより検出しようと思ったが、ゴールデンクッキーは360度ランダムに回転した状態で出現するので、それに対処しようとすると、PILで簡単に済ませるには処理時間が掛かってしまいそうだし、OpenCVを入れるのも面倒だし、クッキー1枚ごときの検出で手間を掛けたくない。そこで、ゴールデンクッキーだけに使われている色を検出することにした。まず、PILでデスクトップのキャプチャを行い、ブラウザの領域のみをクロップし、その領域内でゴールデンクッキーで使われている色を検出できれば、その位置がクリックする位置になる。検出されなければクリックを行わない。

以上の自動化でかなり効率よく稼げるようになり、最終的に作ったクッキーの約7割がクリックによる生産になった。1回目は10京個以上のクッキーを作ったあとにResetを行い、2回目でアップグレードが100%になるまでに要した時間は「リサーチ」の待ち時間を含めて9時間程だった。途中で一時的に中断したり、効率的にアップグレードしたわけではないので、その辺を考えてクッキーを焼けばもっと早く100%になったと思う。また、9時間と言っても自動化プログラムが動いている間は席を離れていても良いので、自分で操作したのはアイテム購入ぐらいだったが。

というわけで、自分はクッキークリッカーをそれなりに楽しんだ。楽しんだ部分は主に自動化プログラムを作成したところなので、一般にプレイされている方とは楽しみ方が違うのかもしれないけど。最後に作成したプログラムを以下に示しておく。


続きを読む...

2013年5月26日日曜日

Pythonを使って簡単にデータを視覚化する

このブログ記事をはてなブックマークに追加

世の中のことをもっと知るにはどうしたら良いだろうと思うときがある。世の中の多くの事柄はログやデータに落とされる。Googleなどの検索サイトは良い例だろう。さて、そのログやデータをどうすれば良いのか? 多くの場合、視覚化が有効な手段となる。

まずは身の回りの日常的なデータやログを何とかしたい。ただ、日常のデータを視覚化するのに数十行以上のコードは書きたくない。まるで息をするかのごとく自然に視覚化を行いたいのだ。そのためには1~2行、長くて数行で済ませることが必要だ。そこでPythonとmatplotlibを使う。加えて、IPythonがあればなお良い。IPythonの導入については以前のブログ記事であるIPythonの埋め込みプロットが素晴らしいを参考にして欲しい。

まずは事前にnumpyとmatplotlibをインポートしておく。できればscipyも。

>>> from numpy import * >>> from pylab import *

短いコードで視覚化を行うためには、Pythonの内包表記は必須だ。例えば、5, 2, 1, 5, 8をデータとするグラフを書きたいのならIPythonを使って以下の1行で実現できる。

>>> plot([5, 2, 1, 5, 8])



数値が行ごとにinput.txtというファイルに書かれていた場合は以下の通り。

>>> plot([int(x) for x in file("input.txt")])

map関数を使えばもっとスマートに書ける。ファイル内の数値を文字列として配列で読み込み、それらの文字列をmap関数によりintで整数に変換する。

>>> plot(map(int, file("input.txt")))

さて、ログが2次元で書かれていた場合はどうするのか。例えば以下のデータがinput.txtに書かれていたとする。

2, 2.5 5, 6.2 6, 3.6 7, 6.3 10, 1.9

この場合、以下のようにすればプロットできる。ファイルから行ごとの文字列を読み出して、それを","を区切りとしてリスト化する。文字列で格納されている数値をmap関数を使ってfloatで実数に変換している。最後にmap(list, zip(*data))を使って転置している。ここでdataはリストによる行列とする。リストによる行列の転置はイディオムとして覚えておくと便利だ。

>>> x, y = map(list, zip(*[map(float, xs.split(",")) for xs in file("input.txt")])) >>> plot(x, y)



ログファイルなどの場合、単に数値が並んでいることは少なく一緒にテキストが書き込まれていることが多い。例えば次のログ(input.log)について視覚化を行なってみる。

Data analysis log: Cycle 1: Calculating ... done! Factor = 0.265 Unit = 25.8 Cycle 2: Calculating ... done! Factor = 0.315 Unit = 28.2 Cycle 3: Calculating ... done! Factor = 0.415 Unit = 30.5 Cycle 4: Calculating ... done! Factor = 0.625 Unit = 40.6 Cycle 5: Calculating ... done! Factor = 0.895 Unit = 55.2

Unitの値をそのままプロットするなら以下のようにすれば良い。予めreモジュールをインポートしておき、re.matchで先頭の文字列と一致したものだけ選び出している。

>>> plot([float(l.split("=")[1]) for l in file("input.log") if re.match("Unit =", l)])



Unitを横軸、Factorを縦軸にしてドットでプロットしたい場合は以下のようにする。

>>> x = [float(l.split("=")[1]) for l in file("input.log") if re.match("Unit =", l)] >>> y = [float(l.split("=")[1]) for l in file("input.log") if re.match("Factor =", l)] >>> plot(x, y, "o")



最後に少し複雑な例を挙げておく。あるデータに対してスペクトラルクラスタリングを行いたいとする。まずは、numpyとmatplotlibの他に、scipy関連の固有値問題・k近傍法・kd木のモジュールをインポートしておく。

>>> from scipy.linalg import eig >>> from scipy.cluster.vq import kmeans2 >>> from scipy.spatial.kdtree import KDTree

そして、クラスタリングしたいデータをcircles.datとすると、以下のコードで視覚化できる。

>>> ps = array([map(float,l.split()) for l in file("circles.dat")]) >>> kt = KDTree(ps) >>> knn = [[((lambda a,b:exp((-(sqrt(dot(a-b,(a-b).conj()))**2))/1.5))(p,ps[nb]),nb) for nb in kt.query(p,16)[1] if i!=nb] for i,p in enumerate(ps)] >>> W = zeros([len(knn)]*2) >>> _ = [W[p].__setitem__(nb,d) for p,nn in enumerate(knn) for d,nb in nn if p in zip(*knn[nb])[1]] >>> w,v = map(real,eig(diag([sum(Wi) for Wi in W])-W)) >>> Y = array([e[1] for e in sorted(zip(w,v.T))[:3]]).T >>> res,idx = kmeans2(Y,3,minit='random') >>> _ = [plot(p[0],p[1],('ro','go','bo')[i]) for p,i in zip(ps,idx)]



ここではforループを行うために内包表記を使っており、また、内包表記のリストが必要ない場合は、_(アンダースコア)に入れておく。これはシェル上で余計なデータを表示させないためである。また、内包表記上では配列への代入ができないので__setitem__を利用している。さらに、Pythonのリストの代わりにnumpyのarrayを利用すれば転置などもmap(list, zip(*data))の代わりにarray(data).Tとすれば良いので分かりやすい。

Pythonを使えばたったこれだけだ。これだけのことで、これまで見えなかったものが見えてくるのは楽しい。

続きを読む...

2013年3月10日日曜日

Python: timeitモジュールを使ってお手軽に実行時間計測

このブログ記事をはてなブックマークに追加

Pythonではtimeitモジュールを使って簡単に実行時間を計測できる。以下に示すコードはPythonでは一般的なコードだと思う。たらい回し関数(竹内関数)と階乗を求める関数だ。これを実行した時の時間計測、さらにコードに含まれている関数の実行時間を簡単に測るにはどうすればよいか。


ここでtimeitモジュールが利用できる。まず、Pythonシェル環境では以下の通り。

main関数の測定は次のように行う。stmtで時間計測したい関数を指定して、setupで最初の1回だけ実行する文を指定する。numberは実行する回数となっている。正確を期するなら複数回を指定するべきだろう。

>>> import timeit >>> timeit.timeit(stmt='test_timeit.main()', setup='import test_timeit', number=1) 12 3628800 2.663659573618423

たらい回し関数(tarai)のみの測定。

>>> timeit.timeit(stmt='test_timeit.tarai(12, 6, 0)', setup='import test_timeit', number=1) 2.6390463109480637

階乗関数(factorial)のみの測定。100万回実行。

>>> timeit.timeit(stmt='test_timeit.factorial(10)', setup='import test_timeit', number=1000000) 2.3606330638673825

さらに、コマンドラインでの計測も可能だ。

main関数の測定。コマンドオプションの-sは最初に1回だけ実行する文、-nは実行する文の回数、-rはタイマのリピート数になっている。

$ python -m timeit -n 1 -r 1 -s "import test_timeit" "test_timeit.main()" 12 3628800 1 loops, best of 1: 2.63 sec per loop

たらい回し関数(tarai)のみの測定。

$ python -m timeit -n 1 -r 1 -s "import test_timeit" "test_timeit.tarai(12, 6, 0)" 1 loops, best of 1: 2.63 sec per loop

階乗関数(factorial)のみの測定。100万回実行。

$ python -m timeit -n 1000000 -r 1 -s "import test_timeit" "test_timeit.factorial(10)" 1000000 loops, best of 1: 2.33 usec per loop

ところで、上に示した階乗関数については「車輪の再発明」なので、通常はmath.factorialを使った方が良いだろう。

続きを読む...

2013年1月1日火曜日

2013年と素因数分解

このブログ記事をはてなブックマークに追加

あけましておめでとうございます。

新年を迎えて、ふと、今年の西暦である2013を素因数分解したらどんな数に分解されるのか気になったので考えてみた。桁をすべて足し合わせると 2+0+1+3=6 と3の倍数になり、3で割り切れることは明白だ。3で割ると671となる。671に対し桁を一つ飛ばしにして足し合わせた数の差が (6+1)-7=0 で11の倍数(0を含む)なので11で割り切れることも簡単にわかる。671を11で割ると61の素数となる。つまり、2013の素因数分解は 3×11×61 となる。

大きな素数同士による合成数の素因数分解は非常に困難であることが知られている。この性質を利用して多くの暗号アルゴリズムで大きな素数による合成数が利用されている。現在のところ、素因数分解アルゴリズムとしては、楕円曲線法(ECM; Elliptic Curve Method)や複数多項式二次ふるい法(MPQS; Multiple Polynomial Quadratic Sieve)がよく使われているらしい。で、手軽にこれらを利用できるライブラリがないかと軽く調べたところNZMATH(ニジマス)という数論のためのPythonモジュールがあることを知ったので、早速インストールして使ってみた。

ところで、大きな素数といえばメルセンヌ素数が有名だが、マラン・メルセンヌは、2n-1 に対してnが257以下のとき、n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257のときにのみ素数となると主張した。しかし、一部に間違いがあり、n = 61, 89, 107のときも素数であり、また、n = 67, 257は素数ではなく合成数であった。

そこで、誤って素数としていたn = 67のときの 147573952589676412927 について楕円曲線法(ECM)で解かせると、すぐに 193707721×761838257287 と結果が出力された。

>>> import nzmath.factor.methods as methods >>> methods.factor(147573952589676412927, method="ecm") [(193707721L, 1), (761838257287L, 1)]

更に、メルセンヌが見落としていた9番目と10番目のメルセンヌ素数である 2305843009213693951 (261-1) と 618970019642690137449562111 (289-1) を掛け合わせた46桁の合成数 1427247692705959880439315947500961989719490561 を複数多項式二次ふるい法(MPQS)で解いてみたところ、30分ほどで正しく2つの素数に分解できた。

>>> methods.factor(1427247692705959880439315947500961989719490561, method="mpqs") [(2305843009213693951L, 1), (618970019642690137449562111L, 1)]

ソースコードも簡単に確認できるし、NZMATHはなかなか楽しい。

それでは、本年もよろしくお願い申し上げます。

続きを読む...