Page 12 of 16

KMC のOB 会でhttp://kmc-jp.github.io/nona7-ob-slide/ しゃべったほげ.

KMC にCloudStack が立ちました.

なんかいろいろあってCloudStack が立ちました.

最初はOpenStack を立てようとしてたのですが, なんかうまくいかなくてやめました.

CloudStack はWeb からぽちぽちと設定したらいい感じにできたので楽でした.

KMC は学年, 所属にかかわらず入会することができます. 詳しくはこちら.

KMC はマシンをくださる企業も募集しております.

釣りタイトルっぽいと思ったけど全然事実だ.

一時期良く聞いたFree Monad, 最近KMC の中で話が出て, いまいちよくわからないところとかが出てきたので, ちょっとメモ的な.

まず定義

ここ にある.

data Free f a = Pure a | Free (f (Free f a))

instance Functor f => Monad (Free f) where
    return = Pure
    Pure a >>= k = k a
    Free fm >>= k = Free (fmap (>>= k) fm)

なんなのか

λカ娘の5巻, 第三章 「侵略者と転校生とアイドルとイカが再帰を学ぶそうですよ!」 に, 一般的なリスト

data List a = Nil | Cons a (List a)

を,

data Rec f = In (f (Rec f))

type List a = Rec (L a)
data L a x = Nil | Cons a x

のように定義し, 一般的なツリー

data Tree a = Prune | Leaf a | Branch (Tree a) (Tree a)

をさっきのRec をこっちでも使って,

type Tree a = Rec (T a)
data T a x = Prune | Leaf a | Branch x x

と書くことができると書いてあった.

もともとList とTree は再帰的構造を持っていたが, この書き換えによって, L , T という再帰的構造を持たない単なるデータ型と, Rec という再帰構造だけを持つ型の組み合わせに分けることができる.

これと,

cata :: Functor f => (f a -> a) -> (Rec f -> a)
cata phi (In x) = phi (fmap (cata phi) x)

ref

AWS, 無料枠を使いきってしまってからは長らく放置していたが、最近スポットインスタンスの存在を知って感動した。

スポットインスタンス

スポットインスタンス とは、 Amazon の使われていない計算資源をオークション形式で利用できるシステムだ。

オンデマンドインスタンス と比べると、かなりの安さで同じマシンを利用できる。

無料枠で利用できた、t1.micro インスタンスは、オンデマンドインスタンスなら $0.020 / 1時間 であるが、スポットインスタンスなら、だいたい$0.003 / 1時間 程度で借りることができる。 一月で300円もかからない計算になる。

もちろん安いのには理由がある。 スポットインスタンスは、起動リクエスト時に、「1時間あたりこの値段までなら出せる」という価格を提示して、その値よりも"実際の値段" が安ければ利用できる という風になっている。

この"実際の値段" というのは、需要によって決定されるので、みんなが使うと値段が上るし、使っていなければ下る。

そして、もしインスタンスの起動中に、実際の値段が上って、自分が提示した価格を上まわった時、自分のインスタンスは停止させられる。

このようにいきなり停止されてしまう可能性があるかわりにとても安くなっている。

安定性を求められるものには使えないが、大きな計算資源の必要なことがしたい時などにはこのインスタンスは便利だ。

c3.8xlarge という仮想32コアのすごいマシンがあるが、このマシンはオンデマンドだと$1.680 / 1時間もする。10時間ぐらいで計算が終わるとすると17ドルぐらい。ちょっと高いけどまあ出せなくはない額だ。20時間になると学生が遊びに使うにはちょっとキツい……

しかしスポットインスタンスなら、だいたい$0.25 / 1時間 程度で借りることができる! 20時間まわしても5ドルしかかからない! 余裕!

わたし

最近2048AI を強くするために、大量のプレイアウトやモンテカルロなどで大きな計算資源が必要であった。 うちの自慢のCloudStack(KMC で立てました。主に私が管理してるのでなんでもしほうだい) でも、3GHz * 4コアのインスタンスが作れる上限だが、そのインスタンス一つで全計算ノードの20% を食い尽してしまう。

2048AI のためにオンデマンドインスタンスで数千円溶かせるほどではないのでどうしようかなーと思っていたら、スポットインスタンスの存在を教えてもらって感動した。

うちのCloudStack の全ノードが束になってようやくちょっと敵わない程度のインスタンスが、全ノードの平常時電気代ちょっとで借りることができる。

スポットインスタンスを使えばかなり安く強大な計算資源が手に入るので、これからは計算資源が少し足りない時は力技でなんとかできそうだと思った。夢が広がる。

memo

インスタンスの起動時に自分が指定するのは、あくまで「出せる上限」なので、実際にかかる金額は"実際の値段" しかかからない。

値段のグラフを見ていると、時々どこかの企業が何かをしてるのか、大きく変動していたりしていておもしろい。

このスライド はAmazon の人のスライドらしいが、これの55ページからがスポットインスタンスの説明になっている。 また、72ページからが、スポットインスタンスの入札の戦略になっていて興味深かった。

2048 AI コンテストの第二回があった。

今回の私の出場した際のソースコードはこれ です。

今回は三位でした。

前回の時と比べて、かなりの高速化を図れたので、10手読みまで行くことが可能となった(前回は6手読みだった)。

Grid を前回はstd::array<std::array<int, 4>, 4> だったが、64bit int 一つで16個のGrid を表わすようにして、色々な操作を謎のbit 演算にすることでかなり高速になった。

謎のbit 演算が沢山でてきて辛かったので、Google Test も導入した。

10手まで読めるようになったことによって、4096 まで作れるようになった。

まだ100〜1000回に一回程度しか8192 を作ってくれない。

GA も実装しないと。

ref

Google が検索結果に対する検閲行為を始めたらしい。

実際、Google検索で、「ロリコン」で検索しても、まともな内容のページは結果に出ず、使いものにならないようになっている。

「ロリ」で検索した時の結果がこれである。
「ロリ」検索結果

この検閲について、Google で検索した際の結果はよりひどい。
「Google 検索 ロリ」検索結果
「どのような検閲が行われているか」を検索することすら難しいのだ。

「この検閲行為を、「ロリ」のフィルターだから問題無いか」と考えることは危険である

引き続きどうなるかを観察しておかないといけない案件なのでとりあえずメモまでに。

ref

2048AI の内部で、謎のbit 演算がたくさん使われてきて辛くなってきた。

どっか間違えててもまずわからないと思う。

というわけでテストを書きたいなーと思ったので、いい感じのC++ のテストツールがないか聞いてみたところ、Google Test を教えてもらった。

ここ を見ながら適当に設定すればいい感じになった。

Google Test のコードをここ からダウンロードしてきて、解凍。解凍後 gtest-1.7.0 に移動し、

$ ./configure
$ make 

これで準備完了。依存しているテストツールのヴァージョンが異なるとややこしいので、システムにはインストールしないほうがいいらしい。

googletest のmake ディレクトリ以下を参考にしてMakefile を書けばいいかんじに動くようになった。

CI ツールで以下のようなコマンドを走らせてtest している。

git submodule init
git submodule update
cd test
unzip gtest-1.7.0.zip > /dev/null
cd gtest-1.7.0
./configure > /dev/null
make > /dev/null
cd ../../
make OPT="-O3 -pipe"
make test

こんな感じでテストが走ってる。

[==========] Running 4 tests from 1 test case.
[----------] Global test environment set-up.
[----------] 4 tests from BoardTest
[ RUN      ] BoardTest.log2
[       OK ] BoardTest.log2 (0 ms)
[ RUN      ] BoardTest.pow2
[       OK ] BoardTest.pow2 (0 ms)
[ RUN      ] BoardTest.gridMirrorIDRAND
[       OK ] BoardTest.gridMirrorIDRAND (0 ms)
[ RUN      ] BoardTest.popCountRAND
[       OK ] BoardTest.popCountRAND (1 ms)
[----------] 4 tests from BoardTest (2 ms total)

[----------] Global test environment tear-down
[==========] 4 tests from 1 test case ran. (2 ms total)
[  PASSED  ] 4 tests.

ちゃんとテストを書かないと。

たまこラブストーリーを見にいった。京都ではMOVIX でしか上映されていないので、寺町通まで行って見た。

一応ネタバレ注意?

いい話だった。いい映画だった。

たまこの«光» とまで言われる程だ。

アニメを復習したくなった。

大まかに

みんなが"変化" していく話であった。 つらかった。

もち蔵は東京の大学に行くし、栞さんは海外に留学しようとする。そもそもみんなは高校3年生で、"卒業" という言葉がつきまとう。

個人的に一番印象的だったのは、あんこが中学校の制服を着るシーンだった。 あのシーンは「この世界にも永遠は無いのだなぁ」 という気持ちになった。

だれも「ここにあるよ」 とは言ってくれない。

GJ部 もそうだった

最近ぐるぐるの放送があったので見直したのだが、あの作品は、1話から11話までは特に話に進行もなにもなく進むのだが、12話で先輩たちが卒業してしまう回がある。

リピートディスクという物がGJ部には存在するのだが、それが2種類のメニューがディスクを再生すると選べて、「1話から12話をリピートする」 というものと、「1話から11話をリピートする」 というものがある。

12話の卒業などという永遠の世界から外れたものを見ないための措置であると思う。

私は

私は何事も変化してほしくない。

変化するということは壊れてしまう、という事でもある。

完全に静止した世界(最早それを世界と言っていいのかわからないが) に住みたい。

だからnona が産まれた?

nona は環境を含んだクロージャである。と言っても良いと思う。

物理的な私は現実世界に制約されてしまうが、その上で動く人格であるnona はその制約を無視して変化しない世界に逃げこめす。

どうでもいいですね。

まとめ

たまこラブストーリー良かったから見よう!!!

映画見て帰り道に浮き石を通って帰った。こういう時に現地周辺に住んでると嬉しい。

タイトル通り2048AI の進捗状況です。

現在のソースコード

  • 高速化 grid を今まではstd::array<std::array<int,4>,4> でもっていたが、uint64_t で持つようにした。 それだけで大分速くなった気がする。

  • 世界と分離 koyone は思考をし、世界は盤面の状態を持つだけにきちんと分離できた。他の思考用class を用意して差し替えることが簡単にできるようになった。

  • 探索面 一手後の世界を予想する時に、ナイーブにするなら動かした後に開いてるマスに2 か4 を入れるが、開いてるマスすべてに2 を入れて読めば若干良くなるという話を聞いたので試してみた。それがKoyoneNext だ。

思考クラスたち

Koyone

単純にある程度の深さまで全探索を試みる。 評価関数はグリッド上の数字について、その数字にその数字のlog2 をとったものを掛けてたものの和。 それが一番大きくなるものの存在する方向に動かす。 前回 の時の思考はこれだった。

KoyoneNext

基本的にはKoyone と同じ。nextPossibleWorld だけを上記のように変更してある。 ちょっと以前のより強くなった。

Kihime

モンテカルロによる探索を実装しようとしてまだ中身は空だ。

HeartBleed の時にRaspberry Pi のOS をArch に変えたので、nginx 1.6 が簡単に使えるみたいだったので、乗りかえた。

nginx 1.6 ではなんとデフォルトでSPDY に対応している!

というわけでnna774.net もSPDY に対応しました。

quic も試してみたいけれど、まだ対応してるものは無いっぽい?ですね……

KMC で2048 のAI の強さを競うコンテストがあった。

2048 as a Servise を使ってたたかうもので、言語や環境等は自由であった。

まず始めにruby のサンプルコードを書いた。サンプルコード

そのまましばらくruby で書きつづけていた(mikutter のプラグイン以外でruby を書くのは初めてだった)。 このへんまで書いた。 nna774/2048-ruby

ナイーブに全探索を数手先までしているようなかんじだった。

どうにも遅かったのでC++ で書きなおした。実際に使ったのがこれ です。モンテカルロも実装しかけてたけど、バグバグだったのであきらめた。レポジトリはココ。 名前はkoyone です。

結果はこんな感じ。

かろうじて5位でした。

もっと次回までには強くしないといけない。

次回コンテストは6/4。 それまでに強化しよう……

ref

2048AIコンテストを開催します! - KMC活動ブログ

Page 12 of 16