コンピュータがゲームを行う上で、コンピュータの取る戦略を
どのように評価するかを考えなくてはならない。
教科学習をゲームの評価関数として使用する場合、
その戦略におけるゲーム終了後の局面の勝敗を報酬として
評価し、途中局面の報酬を 0 とするのが一般的だが、
途中局面にも報酬を与えるとどうなるか実験した論。

将棋プログラムの大規模並列実行
http://id.nii.ac.jp/1001/00069710/

コンピュータ将棋プログラムは強力なマルチコアGPUと、
膨大な主記憶装置によって実行されることで、
プロ棋士を破るレベルの強さを実現している。
こうした1台のPCの性能に頼るのではなく、複数台のPCを
クラスタ構築して、演算を行う実験を論した論。
課題として通信遅延及び負荷分散が述べられている。

終わり

アブストラクトと結論だけ読んでてもそれなりに楽しい。

2016-02-06

REPEATABLE READをスナップショットという言葉使って語るのは今すぐやめるべき

MYSQLのデフォルトのトランザクション分離レベルは
REPEATABLE READです。

REPEATABLE READにおいてもファントムリードが起こることは
避けられませんが、MySQLのREPEATABLE READでは、
MVCCを採用しているため、ファントムリードは起こりません。

MVCCにおいてはよく「トランザクション毎にスナップショットを作成し、それを参照することで他のトランザクションからの干渉を受けない」といった説明がされます。

スナップショットという表現のため、我々はトランザクションが始まるたびに、
そのトランザクションが扱うテーブルのメモリコピーをいちいち作成するような
イメージを受けますが、実はそのようなスナップショットという表現のイメージと
実装は異なっています。

MVCC とは

MVCC(MultiVersion Concurrency Control)という名の通り、
バージョニングによりトランザクションの独立性を保ちます。

以下は MySQL の InnoDB のMVCC 実装の話です。

MySQLはシステムバージョン番号を持っています。これはトランザクションが
1つ開始されるたびに +1 インクリメントされます。これによって
各トランザクションは一意なシステムバージョン番号を持っています。
古いトランザクションより新しいトランザクションの方が
大きいシステムバージョン番号を持ちます。

InnoDB上の各レコードは、内部的に2つの値を持っています。1つが行が
作成された時のシステムバージョン番号、もう1つが行が削除された時の
システムバージョン番号です。

これを踏まえて、CRUDの各処理において MySQLがどのような挙動をしているかを示します。

SELECT

SELECT時に、トランザクションは自分の持っているシステムバージョン番号と
同じかそれ以前のバージョンの行しか取得しません。

これにより自分より新しいトランザクションのレコード作成や更新の影響を
受けません。 (なぜ更新の影響まで受けないかはUPDATEの項で説明します)

またトランザクションはSELECT時に、行の削除バージョンが未定義か、
自分の持っているシステムバージョン番号より新しいバージョンの行を
取得します。これにより自分より新しいトランザクションの
レコード削除の影響を受けません。

INSERT

トランザクションはINSERT時に自分のシステムバージョン番号を
新規レコードに記録します。

DELETE

トランザクションはDELETE対象のレコードに、自分のシステムバージョン番号を記録します。
自分より古いトランザクションがこのレコードを参照する可能性があるため、
この段階では物理的にレコードはまだ削除されません。
SELECT時の挙動によりDELETEしたレコードはトランザクションから
あたかも削除されたかのように見えなくなります。

UPDATE

UPDATE時、トランザクションは UPDATE対象の行をコピーして新しい行を作成します。

新しい行には自分のシステムバージョン番号を記録し、古い行には
削除バージョンとして自分のシステムバージョン番号を記録します。

これにより古いトランザクションはUPDATEされる前の古いレコードを参照し、
新しいトランザクションはUPDATEされた新しいレコードを参照することで、
トランザクションの独立性を保ちます。

終わり

こうしたMVCCの仕組みによりREPEATABLE READな MySQL の InnoDB は
行をロックすることなく、またテーブル全体のスナップショットを取るような
マネもせず、トランザクションの独立性を担保しています。

こうした仕組みはスナップショットと呼ばれ、各種RDBMSの公式docでも
使用されていますが、スナップショットという言葉のイメージに惑わされ、
InnoDBのREPEATABLE READ の挙動を勘違いする人たちが後を絶たないので、
皆様も今すぐスナップショットという言葉でREPEATABLE READを理解するのでなく、
バージョニングの概念を使って REPEATABLE READ の仕組みを理解するようになってほしい。

2016-01-10

転職して1年が経った

お疲れ様です。さいです。
現会社に入社しておおよそ1年が経ったので
振り返るいい機会だと思ったので振り返ります。

リードエンジニアリング

既存のWebサービスの機能追加・改修のリードエンジニアを
担当しました。エンジニア8人チームのうち、
2〜3名と一緒に開発を行ったり、あるいはプランナーやデザイナーと
コミュニケーションして、Webサービスの機能追加・改修に対して
QCDの面から責任を持ちました。

Backbone.js 導入

UI/UX向上施策に乗じて、フロントエンドに
backbone.jsの導入を進めました。

単体テスト導入

jenkins サーバーを使って、単体テストできる仕組みを
導入しました。

人のパフォーマンスを最大化するのは難しい

あなたはリーダーです。あなたの周りには2名ないし3名の
エンジニアがいます。最近アサインされた彼らは
技術には知見がありますが、業務ドメインや
社内手続きには詳しくありません。

あなたが責任を持つプロダクトに対して、
最大限のQCDを担保するには、あなたは何をすべきでしょうか。

彼らが最大限のパフォーマンスを発揮できるように、
露払いをすることだと思います。

彼らの知識が疎い業務ドメインについて、適切に情報を共有し、
社内手続きを肩代わりすること。彼らのスキル次第では技術的なところも
知識を共有してサポートします。

あなたが優秀なプレイヤーである自負があればあるほど、
自分でやったほうが早い病になると思います。あるいは、
自分が開発のメインを担当して、彼らに落穂拾いをさせることを
考えるかもしれません。

自分のプレイヤーとしての能力に限界を感じ、見切りをつけられるまで
マネジメントというのは上手にならないと思います。

自分より優秀な人たちのパフォーマンスをよりよくするにはどうするか。

自分の方が優秀だと驕っていると、彼らがパフォーマンスを発揮できないときに、
なぜ自分と同じようにできないんだと、非生産的な考え方に陥ると思います。

ノウハウのない技術を導入するのは難しい

Backbone.js 導入にあたっては、私/社内にフロントエンド開発の
知識がない点がもろにネックとなりました。

教訓として、ノウハウのない技術を導入する際は、いきなりプロダクション環境に
導入することを進めず、社内システムやツールに導入して、
ある程度知見を貯めてから、プロダクション環境への導入を考慮するべきでは
等があります。

社外でのアウトプット

香霖堂書店というWebサービスを作りました。
Frandre という Bootstrap テーマを作りました
github.js にプルリクを出してマージされました。
YAPC 2015でhubotについてLTしました。
同人活動を始めました。⇛自作ラバーストラップ

あと Elasticsearch や fluentd で遊んでました。成果は特に
ありませんが、ブログ記事くらいにはなりました。

自分がどう変わったか

稚拙ながらも個人でアウトプットをするようになりました。
作りたいと思うものを曲がりなりにも一人で完成まで持っていける
ようになったと思います。

一方アウトプット自体はまだまだ稚拙で、人々から評価を
得られるレベルまで達していません。

第一言語が perl なのですが、第二言語として javascript を
触るようになりました。フロントエンドからサーバサイドまで
全部 javascript で書きます。hubotスクリプトや
google app script なんかも javascript で書けるので、
ほとんどなんでもできる感があって javascript を選択しました。

これから

個人で Webサービスをガシガシ作っていきたいと思います。またリリースした
既存のWebサービスについてもガシガシアップデートしていきます。
それらを通してまずはリーンスタートアップを実践していきます。

github上の何かしらのOSSにコミットしていきたいです。
コントリビュートを豪華にしたいだけの動機なので、
優先度は低いです。

あとはちょっとゲーム作ってみたいですね。弾幕シューティングゲーム。
phina.js やツクールMVの登場で、JS製ゲームエンジン
自分の中でアツいです。

同人活動としてグッズ作成を継続していきます。

お仕事では引き続き単体テスト・UIテストの自動化を進めていきます。
そして既存コードのリファクタ。

終わり

そういえば昨年の前半はMySQL周りの情報を集めてた気がします。
RDBMSの仕組みは面白いですが、そろそろ外部から見える挙動を
確認するのに飽き、Cを学んでソースコードとか読みたいなと
思って、最近手をつけてない感が。

2015-12-29

MySQL の order by と index

MySQLの order by と index の仕組みがわからなくなったので調査。

前提の自分の仮定

MySQLは降順インデックスをサポートしないので order by desc にインデックスを使用できない
(user_id, point)という複合インデックスがあれば、where user_id = ? order by point ascというクエリはインデックスを最大限に使用できる

準備

MySQLのバージョンは 5.1.61

CREATE TABLE `sample` (
  `id` int(10) unsigned NOT NULL,
  `user_id` int(10) unsigned NOT NULL,
  `point` int(10) unsigned NOT NULL,
  PRIMARY KEY (`id`),
  KEY `i1` (`user_id`,`point`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

mysql> select count(*) from sample;
+----------+
| count(*) |
+----------+
|  1048576 |
+----------+
1 row in set (0.22 sec)

試す

mysql> explain select * from sample where user_id = 50;
+----+-------------+--------+------+---------------+------+---------+-------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref   | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+-------+------+-------------+
|  1 | SIMPLE      | sample | ref  | i1            | i1   | 4       | const |   98 | Using index |
+----+-------------+--------+------+---------------+------+---------+-------+------+-------------+
1 row in set (0.00 sec)

user_id を where 句に指定すると当然i1インデックスを使用してselectできる。 key_lenはint型なので4

mysql> explain select * from sample where user_id = 50 and point = 1000;
+----+-------------+--------+------+---------------+------+---------+-------------+------+-------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref         | rows | Extra       |
+----+-------------+--------+------+---------------+------+---------+-------------+------+-------------+
|  1 | SIMPLE      | sample | ref  | i1            | i1   | 8       | const,const |    1 | Using index |
+----+-------------+--------+------+---------------+------+---------+-------------+------+-------------+
1 row in set (0.00 sec)

user_id 及び point を指定しても、i1インデックスを最大限利用して select できる。key_lenが8なので、user_id及びpointまでインデックスを使用している。

mysql> explain select * from sample order by user_id asc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL |   10 | Using index |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

user_idをascで order by。limitに10を指定してrowsが10なのでインデックスを使用して絞っていることがわかる。

mysql> explain select * from sample order by user_id desc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL |   10 | Using index |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

ascでなくdescでも同様。

mysql> explain select * from sample order by user_id asc, point asc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL |   10 | Using index |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

(user_id, point)の複合キーなので、order by に user_id と pointを指定しても絞り込める。

mysql> explain select * from sample order by user_id desc, point desc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows | Extra       |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL |   10 | Using index |
+----+-------------+--------+-------+---------------+------+---------+------+------+-------------+
1 row in set (0.00 sec)

こちらもdescでも同様。

mysql> explain select * from sample order by user_id asc, point desc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows    | Extra                       |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL | 1049137 | Using index; Using filesort |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
1 row in set (0.00 sec)

ascとdescが混合するとインデックスが有効に活用されない。

mysql> explain select * from sample order by user_id desc, point asc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows    | Extra                       |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL | 1049137 | Using index; Using filesort |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
1 row in set (0.00 sec)

desc asc の順でも同様。

mysql> explain select * from sample order by user_id asc, id asc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows    | Extra                       |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL | 1049137 | Using index; Using filesort |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
1 row in set (0.00 sec)

pointでなくidをorder by に含めるとインデックスが効かない

mysql> explain select * from sample order by id asc,user_id asc limit 10;
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
| id | select_type | table  | type  | possible_keys | key  | key_len | ref  | rows    | Extra                       |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
|  1 | SIMPLE      | sample | index | NULL          | i1   | 8       | NULL | 1049137 | Using index; Using filesort |
+----+-------------+--------+-------+---------------+------+---------+------+---------+-----------------------------+
1 row in set (0.00 sec)

order by の順序を逆にしてもしかり。

mysql> explain select * from sample order by id asc limit 10;
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------+
| id | select_type | table  | type  | possible_keys | key     | key_len | ref  | rows | Extra |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------+
|  1 | SIMPLE      | sample | index | NULL          | PRIMARY | 4       | NULL |   10 |       |
+----+-------------+--------+-------+---------------+---------+---------+------+------+-------+
1 row in set (0.00 sec)

idをorder by に指定すると、idはPRIMARY KEY なのでそっちのインデックスが使用される。

mysql> explain select * from sample where user_id = 50 order by point limit 10;
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref   | rows | Extra                    |
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | sample | ref  | i1            | i1   | 4       | const |   98 | Using where; Using index |
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

where 句にuser_id, order by にpointを使用すると、user_idだけインデックスを使用して探索される。

mysql> explain select * from sample where user_id = 50 order by point desc limit 10;
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
| id | select_type | table  | type | possible_keys | key  | key_len | ref   | rows | Extra                    |
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
|  1 | SIMPLE      | sample | ref  | i1            | i1   | 4       | const |   98 | Using where; Using index |
+----+-------------+--------+------+---------------+------+---------+-------+------+--------------------------+
1 row in set (0.00 sec)

descを使用しても同様の結果。

結果

MySQLは降順インデックスをサポートしないが order by desc にインデックスを使用できる
(user_id, point)という複合インデックスがあっても、where user_id = ? order by point ascというクエリは user_id 部分までしかインデックスが使用されない

2015-12-27

IDCFクラウド上に Elasticsearch 2.0 + kibana 4構築

IDCFクラウド上に Elasticsearch 2.0 + kibana 4を構築して
可視化して遊んでみます。

IDCFクラウドのS2 CentOS6.5です。

各種インストール

Elasticsearch は java で動くので java をインストール

# Install Java
sudo yum install -y java-1.8.0-openjdk

# Install Setting Elasticsearch 2.0
sudo rpm --import https://packages.elastic.co/GPG-KEY-elasticsearch
vim /etc/yum.repos.d/elasticsearch.repo

elasticsearch.repo に以下の記述をします。

[elasticsearch-2.0]
name=Elasticsearch repository for 2.0 packages
baseurl=http://packages.elastic.co/elasticsearch/2.x/centos
gpgcheck=1
gpgkey=http://packages.elastic.co/GPG-KEY-elasticsearch
enabled=1

# Install Elasticsearch 2.0
sudo yum install elasticsearch
chkconfig --add elasticsearch
sudo service elasticsearch start

日本語解析プラグインのkuromojiを入れます。

# Install Kuromoji
sudo yum install -y /usr/lib64/libssl3.so
/usr/share/elasticsearch/bin/plugin install analysis-kuromoji

# Install Kibana 4.3.0
wget https://download.elastic.co/kibana/kibana/kibana-4.3.0-linux-x64.tar.gz
tar xvzf kibana-4.3.0-linux-x64.tar.gz
mv kibana-4.3.0-linux-x64 kibana

sense は kibana のプラグインです。kibana の可視化とは関係ありませんが、
kibana 上から query を記述・発行できるエディタが使用できるので便利です。

# Install Sense
./bin/kibana plugin --install elastic/sense

# start kibana
cd kibana/
./bin/kibana >/dev/null 2>&1 &

ポートを開ける

kibana はデフォで5601ポートを使用するので、5601のポートを開放します。

kibana 4から静的ファイルベースでなく Node.jsのアプリケーションになったため、 Elasticsearch のポートを開ける必要はありません。

データを突っ込む

東方創想話というサイトがあります。
東方プロジェクトの二次創作SSが投稿されるサイトです。
実はこのサイト、JSON APIを公開しているので、それを取得して、Elasticsearchにぶっこむコードを書きます。

API · mfakane/Megalopolis Wiki · GitHub

JSONをスクレイピングするスクリプトですが、Node.js を使って今回は書きました。

# Install Node
sudo yum install -y epel-release
yum install -y nodejs npm --enablerepo=epel

Node.js でスクレイピングするときのポイントですが、

非同期でhttpアクセスするので、逐次処理でアクセスしないと、一斉にアクセスされて先方に迷惑がかかる
timestamp 型のデータを突っ込んでおくと、kibana で時系列順に可視化できて便利。

というのがあります。1については、Promise と Array.prototype.reduce を使うと解決できます。

コードは下記にて公開しておきます。使用される方は、先方に迷惑のかからないようにしてください。

github.com

kibana

kibana にアクセスします。デフォルトでは最新15分のデータを表示するので、2005年〜2010年辺りにデータを絞ってみます。

このように Elasticsearch にぶっこんだデータが表示されたことかと思います。

可視化

東方創想話にはタグ機能があるので、これでキャラを絞ってデータを可視化できたりします。

古明地こいしに絞って、Y軸にSSの投稿数、X軸に時系を取り、Area chartで表示しました。東方地霊殿の発表が2008年頃なので、2008年ごろから投稿数が始まっているのも納得です。

こちらはLine chart 。八雲紫の投稿数をY軸に取って表示しています。

こちらは pie chart 。円グラフのことですね。タグで領域分けしているのですが、うまいこといっておらず、1文字だけで領域分けされていますね。

これはインデックス時にタグを kuromoji でアナライズしちゃったせいですね。 terms で絞りたいカラムは not_analyzed にする必要があります。

最後に vertical bar chart。棒グラフのことですね。創想話自体の投稿件数を時系列順に表示しています。

終わり

X軸・Y軸に取る値をさまざまに変えられるので、elasticsearch の aggregation 機能をよく知れば、もっと面白いデータを見ることができるかもしれない。

2015-12-21

【後編】Bootstrap テーマ Honoka を fork してみる

先日、Honoka を実際に fork して、Frandreという Bootstrapテーマを作ってリリースしました。

Frandre

Ubuntu 12.04を意識した配色となっております。 Bootwatch の United のHonoka バージョンだと言えばわかりやすいでしょうか。

前回までの続き

前回では Honoka をちょっとカスタマイズする方法について書きました。

後編では、Honoka をフォークしてそれっぽい Bootstrap テーマを作りたいと思います。

配色を変える

Honoka の配色は全て、scss/_variables.scss にまとまっています。

自動コンパイル

$ npm run-script server

上記を実行すると、sassファイルの変更を察知して、自動で sassをcss にコンパイルしてくれます。立ち上げておきましょう。

gh-pages の作成

Githubには gh-pages という機能があります。詳しい解説は他のサイトに任せるとして、この機能を使うと Github上に静的サイトを構築できます。

Frandre の紹介サイトも http://sairoutine.github.io/Frandre/ という githubページ上に構築されています。

Honoka には gh-pages というブランチがあるのでそのブランチに切り替えて index.html などを編集しましょう。

終わり

思ったより書くことがなかった。配色が scss/_variables.scss にまとまってるので、想像以上に手軽に Honoka の fork テーマは作れます。

みんなも積極的に Honoka を fork して自分だけの Bootstrap テーマを作ろう！

終わり

まるまるこふこふ

数々の次元が崩壊し、全ての生命が塵と化すのを見てきた。私ほどの闇の心の持ち主でも、そこには何の喜びも無かった。

toho-like-js のソースコードを読む 0

情報処理学会のゲーム情報学の論文を読む

終わり