df-pnアルゴリズムを用いた詰将棋Solverによる最善解・余詰の導出

以前書いた、詰将棋問題生成の続き。

memo.sugyan.com

逆算による詰将棋の問題生成の方法自体は悪くないとして (バグによって有り得ない局面が出来上がったりしてしまったりもしたけど)、正しく詰将棋問題として成立するものが出来上がっているかどうかを検証するためのSolverが必要不可欠であり、これのパフォーマンスが生成のパフォーマンスにも影響してくる、というようなことを書いた。

実際、前回の記事のときに実装したSolverでは

  • 総当たり的に探索するのは3〜5手が限界
    • 詰将棋のルールに則る動きに限定しても、有り得る局面は指数関数的に増加する
  • 合駒が絡む問題に対して正しく解が導けないことがある
    • 先の展開まで読まないと無駄な合駒かどうかの判定ができない

といった問題があった。

df-pnアルゴリズムによる探索

2002年の論文「df-pn アルゴリズムの詰将棋を解くプログラムへの応用」がとても有名なもののようだ。

ざっくり、概要というか考え方について書いてみる

AND/OR Tree

まず、指し手とそれによる局面の変化を "AND/OR Tree" で考える。

例えば前回の記事で作成した問題に対しては、2手目までで以下のようなパターンが考えられる。

f:id:sugyan:20171119212134p:plain

├─┬ ▲4三金
│ ├── △3五玉
│ ├── △4五玉
│ └── △5四玉
├─┬ ▲3四金
│ ├── △4五玉
│ └── △5四玉
├── ▲3四竜
├─┬ ▲2四竜
│ ├── △4五玉
│ ├── △3四歩
│ ├── △3四香
│ ├── △3四桂
│ ├── △3四銀
│ ├── △3四金
│ ├── △3四角
│ └── △3四飛
└─┬ ▲5五銀
  ├── △同玉
  ├── △3五玉
  └── △4五玉

「詰み」をTrue、「不詰」をFalseと考えると、攻方手番の局面は「OR節点」、玉方手番による局面は「AND節点」となる。そして深さが変わるごとに「OR節点」⇔「AND節点」を交互に繰り返すことになる。

すなわち、上図での根(攻方手番)では「どれか1つの子節点でもTrueになればTrue、すべての子節点がFalseならばFalse」であり、その子となる深さ1の節点(玉方手番)では「すべての子節点がTrueになればTrueになり、どれか1つでも子節点がFalseならFalse」となる。

これはまさに詰将棋のルール通りで「どうやっても詰むことが出来なくなったら不詰」「どう応じられても詰ますことが出来れば詰み」といったものを 論理演算のAND/ORで表現している。

なので、最終的に上述のAND/OR Treeの根がTrueであることを証明できれば、それが詰将棋問題の解答に繋がる、ということになる。

単純に考えると すべての節点をどんどん掘っていって その節点が葉となったら(つまりもう子節点が作れない)、動かせる有効な手が存在しないということなので それが攻方手番ならTrue、玉方手番ならFalseである、と確定できる。 しかし全節点を探索していくとなるとその探索空間は非常に膨大なものになり、特に不詰の場合は玉がどこまでも逃げていく局面があったりして、大変な計算時間になってしまう。

AND/OR Treeは上記の性質上、どこか1つの節点の真偽値が確定するとその時点で親節点の真偽値も確定し 他の兄弟節点について調べる必要がなくなる場合もあるので、探索の方法次第では効率的に根の真偽値を確定させることができる。根の真偽値を確定させるだけなら、すべての節点についてTrueFalseであるかをハッキリさせる必要がなく、不確定の節点があっても構わない。 上の例で示した問題の場合、1手詰で▲3四竜の場合にもう玉方の応手が無く「詰み (True)」になっているので 他の手から伸びていく深さ2以上の節点は調べるまでもなく「詰み」であることを言える。

df-pnアルゴリズム

df-pnアルゴリズムでは、このAND/OR Treeを効率良く探索するために、「証明数 (proof number)」「反証数 (disproof number)」という概念を用いる。簡単に言うと「その節点がTrueであることを証明するためにTrueであることを証明しないといけない節点の数」、またはその逆、という感じで、詰将棋でいうと「この手を指して詰むことを証明するためには、玉方の応手この手とこの手が考えられて…これらの局面でも詰むことを証明できなければ…」というパターン数のようなものになる。

これらの値を各節点で計算し、より値の小さいもの(その局面の真偽値を確定させるために証明すべき節点の数が少ないもの)を優先的に深さ優先で探索していく。これが depth first proof number (df-pn) アルゴリズムの基本的な考え方、のようだ。 実際に詰将棋を解くときも、まずは応手が限られる手から考えたり それに対する応手も最悪のパターンを優先的に考えたりすると思うし、直感的に近いものはあるんじゃないだろうか。

ポイントとしては、必ずしもすべて節点の真偽値を確定させる必要はなく、「詰み (True)」「不詰 (False)」「未知 (Unknown)」の3つの状態が許されると考えて木を探索していき、その上で簡単に確定させることが出来そうな未知節点から優先的にさらに深く探索していく、というところ。

このアルゴリズムに用いられている手法により、探索の結果として各節点の証明数・反証数が更新されていく。証明数が∞になると「この節点がTrueであると証明するために証明すべき節点が無限にある → つまりこの節点はFalse」、反証数の場合はその逆で、これらの値によって節点の真偽値を確定させることが出来る。

論文内では、単純にそれだけではなく ハッシュ(というかハッシュテーブル、辞書?)を用いて、同一局面が現れる場合の無駄な探索を減らし、それらに加えて局面がループするときに起きるGHI (Graph History Interaction)問題に対する対処などの工夫を入れている。

実装

論文の付録に疑似コードが載っているので、これをそのままコードに落とし込めば ほぼ問題ない、はず (全然簡単には出来なかったけど、、)。

先行例としては以下のものなどを参考にさせていただきました。

自分はGoで将棋プログラムを書いていたのでGoで。

df-pn Solverの特徴・制約

ということで、df-pn Solverを実装することで詰将棋の問題を正確に速く解くことが出来るように… と言いたいところだけど、これですべて解決というわけではない。

df-pnアルゴリズムによって解くのはあくまでも『その局面が「詰み」か「不詰」かを判定し、その証明ができる』だけであって、『詰将棋の問題に対する正解を導ける』わけではない。

例えば、以下のような問題。

f:id:sugyan:20180217212826p:plain

これを自作のdf-pn Solverを使って解くと、以下のようにAND/OR Treeと各節点の真偽値が得られる。

├─┬ ▲3二と (?)
│ ├── ...
│ └── ...
├─┬ ▲2二と (?)
│ └── ...
├─┬ ▲2二銀 (?)
│ └── ...
├─┬ ▲1二銀 (?)
│ ├── ...
│ ├── ...
│ └── ...
└─┬ ▲3二銀 (T)
  └─┬ △1二玉 (T)
    ├── ▲2一銀 (?)
    ├─┬ ▲2三銀成 (T)
    │ └─┬ △2一玉 (T)
    │   ├── ▲3二と (T)
    │   ├── ▲2二と (?)
    │   ├── ▲2二成銀 (?)
    │   ├── ▲1二成銀 (?)
    │   └── ▲3二成銀 (?)
    ├── ▲2三銀 (?)
    ├── ▲2三と (?)
    └── ▲2二と (?)

()内に書いてあるのが?は真偽未確定、TTrueFFalseを表す、とする。 ...で省略しているけど実際にはもう少し他の1手目に対しても深く探索されている。

結果としてこの得られた木のTrue節点を辿っていくことで「▲3二銀 △1二玉 ▲2三銀成 △2一玉 ▲3二と」という5手の詰み手順を得ることができる。 これは確かに詰んでいるのだけど、「正解ではない」。

実際は「▲3二銀 △1二玉 ▲2三と」までの3手詰で、これが最短の正解となる。

df-pnアルゴリズムは性質上、各節点の証明数・反証数を計算し対象となる節点の値が閾値を超えた時点で探索を終了する。つまり多くの場合は根の真偽値が確定した時点で終了となり、当然ながら現れている全部の節点について探索を行うわけではない。

ので、このように深さ優先で探索した結果、3手目の▲2三との節点を探索する前に▲2三銀成の節点から詰みを見つけてしまい、それで終了してしまう、ということがある。

おそらく指し将棋プログラムでの思考ルーチンとして組み込むぶんにはそれほど問題なく使えると思うのだけど(指し将棋の目的は通常「勝つこと」なので 最短の手順である必要はない)、詰将棋においては「最短で最善の手順で詰む(玉方も最長になるよう最善の手で応じる)」ということを踏まえて解を導かなければならない。 単純に探索終了したら正解が導ける、というものでもないようだ。


また、「不詰」の証明にも少し弱いようで(これは自分の実装のミスか何かなのかもしれないけど)、例えば以下のような局面を解かせようとすると、いつまでも計算が終わらない。

f:id:sugyan:20180217220442p:plain

df-pnアルゴリズムは各節点での証明数・反証数が閾値を超えると一度探索を止めて その閾値以下の別の節点の探索に移り また別のところで閾値が上がるとそこに戻ってきたりする、という仕組みになっているようなのだけど、どうも上記の局面などの場合 別々の節点から辿り着く複数の節点がそれぞれ閾値をお互いに上げていってしまい どちらも譲らずどこまでも証明数やその閾値が増加しつづけていって止まらなくなってしまうようだ。

最善解の導出

…と、ここまで書いてきたところで ここからが本題。

df-pn Solverは完璧に答えを出すことが出来るものではないけど、効率的に探索を行い特定の問題を解くのには利用できるので、これを応用することで「詰将棋の解答プログラム」を作ることを考えた。

別解を探す

先述のように、実際は3手で詰めるものに対して5手で詰む解を導いてしまう、といったことが起きる。 これを回避するためには「実際に他の手でもっと短く詰むことが出来ないかを調べる」ということになる。

単純には、探索が終了してもまだ真偽値が確定していない節点に対して再度Solverにかけて探索していく、という手法をとることになるけど、結局それだと総当たりで調べるのとほぼ変わらなくて効率が良くない。

一つ大事なのは、これを探し始める時点で1つの正解候補となる解答が導出できているので、「それより短い手順で解ける手はないか」だけを探索すれば良いことになる。 既に導いている解より長くなる詰み手順を見つけても無意味なので どこまでも深く探索する必要はなく、ある閾値以上の深さに辿り着いた時点で「これは不詰」と扱って探索を打ち切ってしまっても良い。

既に見つけている正解手順以外の手を探索した結果 より短い詰み手順を見つけることが出来たら、正解候補を更新して またもっと短い手順が無いか探索する。こうしていくことで探索の深さ上限を小さくしながらすべての未確定節点の真偽値を確かめていける。

また大事なのは探索対象の未知節点を選ぶ順番で、例えば1手目から正解候補と違う節点を調べようとしても大抵は不詰なので(いわゆる完全作の場合、正解手順は1つのみで最終手以外に余詰は存在しない)、探索空間が大きく無駄に時間がかかってしまう。 先にもっと短い解候補が発見できていれば探索深さの上限を下げられるので効率が良くなる。

なので基本的には深さ優先で、その時点で発見できている正解候補の手順の周辺の未知節点から探索していくのが効率が良い。7手の詰みが見つかっているのならその手順を辿りつつ別の5手目、別の3手目、という順番で選択して探索していくと より速く短い解候補が発見できる。はず。 その結果として例えば3手で詰む手順が発見できれば、1手目で違う手順を探索する(不詰であることを証明することになる)場合にはもう4手目以降の深さは考慮せず打ち切ることができる。

また、先述のように不詰の証明は計算が終わらない事態が起こることがある。 これについてはどうしようもなかったので、計算時に用いる∞の値をギリギリまで小さくすることで回避した。 正しく「詰み」を導くことができる場合は証明数はせいぜい数百〜千程度の値までしか上がらないので、それより少し大きな値を∞としておけば 先述のような状態になってもいずれは「証明数が∞に到達した」となり、不詰として扱うことができるようになる。 現時点で自分で試している限りでは 2^12 (= 4096) くらいの値にしていても大抵の7〜9手くらいまでは問題なく解けている。

最善経路の探索

Solverによる探索によって新規に詰みの手順が見つかるごとに、「最短・最善の解候補」を算出することになる。

解となる詰み手順は、基本的には探索後のAND/OR Treeの根からTrueの子節点を選択して葉に到達するまで下っていくことで求められる。 とはいえその経路は一意ではなく 複数の兄弟節点で詰みに繋がる場合も多い。特に玉方手番は「すべての子節点がTrueになればTrueになり、どれか1つでも子節点がFalseならFalse」というAND節点であり、どう応じられても詰むことができる ということが確定していない限りTrueにはならないので、玉方に複数の応手がある場合はすべてが詰みに繋がるようになっているはず。

ではどの経路を正解候補として選択するか。 詰将棋のルールとして「玉方は最善を尽くし、最も長く手数がかかるように逃げる」そして攻方は「最善・最短で詰ます」というのがあるので、これを満たすよう考える。

さらに駒余りも考慮して、すべての節点において

  • 攻方手番で複数の選択肢がある場合は最も手数が短くなる経路
    • 同手数のものが複数ある場合は駒を余らせる方を優先
  • 玉方手番で複数の選択肢がある場合は最も手数が長くなる経路
    • 同手数のものが複数ある場合は駒を余らせない方を優先

を選択するようにして、再帰的に求めていく。

合駒問題

このあたりで登場してくるのが「無駄合駒判定」の問題。

なかなか厄介なルールで、玉方による合駒が有効な場合と無効な場合がある。 すぐに取られて王手が続くなら無効、ということで「玉方の利きが無い位置に打つのはすべて無駄」と考えて そういう場所に合駒できない前提で解いてしまうのがラク… だと思いきや、そうとも限らなくて。 有名なのは看寿賞作品の3手詰「新たなる殺意」のような場合。

f:id:sugyan:20180218183219p:plain

ここに▲7三香成としたときの△8六歩は玉方の利きもなく無駄…に思えるのに、▲同角により9筋が開くことによって最終的に詰みが無くなってしまう。有効な合駒となる。

こういう場合もあるので、応手の候補を考える段階ではまだ「ここには合駒できない」という明確な判断はできず、結局すべての可能性を考慮した上で「合駒で打った駒がすぐ取られて、最終的にその駒を余らせて詰ますことができる」場合は無駄合駒、と判断するしかない。

なので、AND/OR Treeの探索の時点ではとりあえず合駒も含めてすべて探索し、その上で解答候補の詰み手順を探索する段階で 合駒が無効なものであったかどうかを判断する必要がある。

再帰的に解答を探索している中で、「玉方合駒 → 攻方同取る」があった場合には最終的な駒余りを確認し、その合駒に打ったものが余る場合は解答候補から外す。このようにすることで無駄合駒の絡む問題に対しても正しく解を導けるようになる。

ただしそれはつまり、必ずしも「節点の深さ=詰み手数」にはならない、ということで、ちょっと例が見つからなかったけど「先に5手の詰みが見つかったが、実は3手の合駒利かずの詰みがある」といった場合に、先に見つかった5手を探索深さの上限値として打ち切る設定で他の手を探索すると 「連続無駄合駒により深さ7で詰むが結果的には3手の詰み手順となる」といった手順を見つけられなくなってしまう。 ので、合駒を含む経路に現れる節点は例外として上限値よりもさらに深いところまで探索する、といった処理を入れるようにした。

余詰の検出

こうしてAND/OR Treeを使った「最善解の導出」が出来ると、同じように「余詰の検出」も簡単に行うことが出来る。

詰将棋の問題生成におけるSolverの重要性は前記事に書いた通りで、生成された問題が

  • 正しく意図した手数で詰ますことができる
  • 駒余りが無い
  • 余詰が無い

ことをチェックする必要がある。 最善解を導く過程で最短手数以内の全節点についての真偽値は確定しているはずなので、同様に根から探索しつつ「攻方に同手数で解ける複数の解が存在しないか」をチェックしていくだけ。 1手詰め以外の場合の最終手は複数あっても良いのでそこだけは許容する。

問題生成への応用

こうして、最善解・余詰をそれなりに速く正確に導くことができると 5手詰や7手詰の問題の場合でも前記事で書いたような問題生成ロジックで「正しく詰将棋の問題として成立しているか」をチェックしていくことができる。

ただしどうしても先述のように不詰の証明でループし続けたり、合駒の探索が余計な深さを必要とするなどで解答に異常に時間がかかってしまう場合がある。 なのでtimeoutを設定し、解答に一定以上の時間がかかってしまった場合はそこで「この問題は解けない」と判定して次のパターンで生成を試みるように、とした。

時間はかかるが、とりあえず前記事と同様のロジックで5手詰の問題も生成できるようになったようだ。

今後の課題や展望など

評価・解説

AND/OR Treeを丁寧に探索することで、「どれくらいのパターン数の手を考慮することでこの解答を導くことが出来たか」を測ることができる。 攻方も玉方もほぼ1手に絞られるような簡単な問題なら総節点数の少ない小さな木になるし、多くの選択肢が考えられる場合は幅の広い木になる。 この木を作る過程で考慮した節点の数を「問題の難しさの指標」として使うことができそうだ。

未知のままでも兄弟節点の真偽により親節点の真偽が確定している場合などは考慮しなくて良いので、基本的には真偽値が確定している節点の数だけを数え上げれば良いことになる。 ただし単純にそれだけを考えると、持駒に飛車角があって離れた場所にも打つことが出来る場合や 玉方が合駒する場合など(最大で7種類を合駒の候補として考えられる)に どうしても選択肢が増えるので、そういう場合には間引きするように少し調整してみている。

とりあえずはこうして得られる「スコア」を各問題の生成時に一緒に計算しておき、@などではそれなりにスコアの高めのものを優先的に選択して出題するようにしてみている(…つもりなんだけど、あんまりうまくいってないかも)。

問題が「良問かどうか」というのは探索量などとはまた別の評価指標もありそうなので、このへんも研究して より「良い問題」も量産できるようにしていきたいところ。


もう一つAND/OR Treeを有効利用できる点として、その木を見ることで「この手はどうして詰むか、この手だとどうして詰まないか」が説明できるようになる、というのが挙げられる。 つまり解いた問題に対して 例えばFalseの節点とその子節点を見れば「▲3二と▲2二とには△同玉▲2二銀には△1二玉で詰みません」、Trueの節点を辿れば「▲3二銀が正解で△1二玉の一手、これに△2三とで詰みです」という文章を、ある程度のテンプレートを用意しておけば作れる、はず。

まだ出来ていないけど、生成した問題にそれぞれこういった解説文をつけられると良さそうだな、と思っている。

計算速度

問題生成時にはランダムな詰み局面を生成してからそれを巻き戻して局面を作って それが詰将棋として成り立っているかどうかをチェックする…、というのを繰り返していて、運次第ではあるけど それなりに時間がかかる。

現状、3手詰くらいなら数秒〜数十秒程度で生成できるが、5手詰めは相当運が良くない限りは数分〜十数分計算し続けてようやく出来上がる、といった感じになってしまっている。 生成するたびにかけるSolverが速く解いてチェックしてくれればそれだけ生成速度も上がるはずではあるのだけど、まだまだパフォーマンス不足なようだ。 1.0秒でtimeoutする設定にしているけど、それも頻繁に起きている。

先述のように、合駒が絡む場合にどうしても探索の幅・深さが深くなって計算時間がかかってしまう問題がある。 いちいちすべての合駒パターンを考慮していると膨大な計算時間になってしまうので、これは減らす必要がありそうだ。 これには引用論文にもある「優越関係の利用」が使えそうで、ある局面が詰むならそれより持駒の少ないこれらの局面も詰みである、といったことが言えるようになるので 計算量を減らすことができそうだ。

あとはまぁ 自分が書きやすく管理しやすいGoでゼロから書いてみていたけど、やはりパフォーマンスを考慮するならC++とかで良いライブラリを利用して作るのが良いのかもしれない…とか。 それで実際どれくらい速くできるのか分からないけど。

生成ロジック自体もまだ無駄な計算を減らせる部分があると思うので、じっくり見直して改善していきたい。

ISUCON7 勝てなかった

ISUCON7id:kazeburo さんと id:gfx さんと、チーム「スギャブロエックス」で出場して、入賞もならず、最終結果5位で終わりました。

f:id:sugyan:20171127124436p:plain

うーん 悔しい。

お題

WebSocketで通信しつつ各ルームで複数のユーザが操作するので同期をとりながら値を更新していく、的なもの。

チームの動き

予選のときと同様に、言語はNode.jsを選択。 今回はTypeScriptを使うようにしていっても良いのでは、と gfxの発案で序盤にすべてのコードをTypeScriptに変換して それを中心に進めていくことに。

実際、TSLintが良く効いて構文エラーや簡単な型の不一致などはすぐに気付くことができて編集しやすくて良かったです。

序盤の各サーバへのログインやNodeのバージョン変更、deployのためのscriptなどの環境整備はお2人に任せて、自分はとにかくアプリケーションをまずgitリポジトリに入れて ローカル環境で動かせることの確認、コードの確認など。

MySQLトランザクションを使っている部分などは正直あまり詳しく分からなかったので そこらへんの解消はkazeburoさんにお任せして、とりあえずは 参照だけで更新のない数レコードだけのm_itemテーブルを使わないよう定数化して排除する、くらいのところから始める。

トランザクションによる負荷を少しでも軽減させるために、と各サーバでMySQLも立ち上げて 同じroomへのリクエストは単一のサーバにリクエストが集まるように4台それぞれ分けて動かすように kazeburoさんによる変更も。

1000回ループ問題

昼御飯の時間あたりから CPUの高負荷をとにかく取り除きたいな…と思いながらコード見ていて calcStatus関数の中で1000回のforループを繰り返しているのに気付いて、そこを消そう…!と思い至って そこを完全に任せてもらい改善の作業をすることに。

元のコードはこんな感じ。

  calcStatus (currentTime, mItems, addings, buyings) {

    ...

    // currentTime から 1000 ミリ秒先までシミュレーションする
    for (let t = currentTime + 1; t <= currentTime + 1000; t++) {
      totalMilliIsu = totalMilliIsu.add(totalPower)
      let updated = false

      // 時刻 t で発生する adding を計算する
      if (addingAt[t]) {
        let a = addingAt[t]
        updated = true
        totalMilliIsu = totalMilliIsu.add(bigint(a.isu).mul(bigint('1000')))
      }

      // 時刻 t で発生する buying を計算する
      if (buyingAt[t]) {
        updated = true
        const updatedID = {}
        for (let b of buyingAt[t]) {
          const m = mItems[b.item_id]
          updatedID[b.item_id] = true
          itemBuilt[b.item_id] = itemBuilt[b.item_id] ? itemBuilt[b.item_id] + 1 : 1
          const power = m.getPower(b.ordinal)
          itemPower[b.item_id] = itemPower[b.item_id].add(power)
          totalPower = totalPower.add(power)
        }
        for (let id in updatedID) {
          itemBuilding[id].push({
            time:        t,
            count_built: itemBuilt[id],
            power:       this.big2exp(itemPower[id]),
          })
        }
      }

      if (updated) {
        schedule.push({
          time:        t,
          milli_isu:   this.big2exp(totalMilliIsu),
          total_power: this.big2exp(totalPower),
        })
      }

      // 時刻 t で購入可能になったアイテムを記録する
      for (let itemId in mItems) {
        if (typeof itemOnSale[itemId] !== 'undefined') {
          continue;
        }
        if (0 <= totalMilliIsu.cmp(itemPrice[itemId].mul(bigint('1000')))) {
          itemOnSale[itemId] = t
        }
      }
    }

    ...
  }

currentTimeより以後のaddingAt, buyingAtの情報を元に、1000ms後の状態をシミュレーションする、というもの。

addingAtbuyingAtも無ければ、少なくとも totalMilliIsuの値の計算はtotalPowerの値を足すのを繰り返すだけなのだから 掛け算に変換すればいいだけ。 ただ それによって途中でアイテムが購入可能になったらその時刻は記録しておかないといけない、というのがあるので それだけは逆算して割り算で求める。

まずは 「addingAtbuyingAtも無ければ」という条件に限定して上記の変更をしてみたが、(実際どうだったか確かめていないけど)殆ど効果なかったようで、やはりaddingAt, buyingAtがあるときも処理していかなくては、と大幅に変更をしていく。

基本的な考え方は 「addingAtがあった時刻」or「buyingAtがあった時刻」だけ必要な更新をして、その間の区間totalPowerが加算されるだけだから掛け算で加えていく、という形。

最終的なコードは以下のようになった。

  calcStatus(currentTime, mItems, addings, buyings) {

    ...

    const eventTimes = new Set<number>(); // adding or buying times

    for (let a of addings) {
      if (a.time <= currentTime) {
        ...
      } else {
        ...
        eventTimes.add(a.time);
      }
    }

    for (let b of buyings) {
      ...
      if (b.time <= currentTime) {
        ...
      } else {
        ...
        eventTimes.add(b.time);
      }
    }

    // イベントが起きる時間だけ時系列に列挙する
    eventTimes.add(currentTime + 1000)

    let prevTime: number = currentTime
    Array.from(eventTimes).sort((a, b) => a - b).forEach((time) => {
      // 1000以上は計算する必要なし
      if (time > currentTime + 1000) {
        return
      }
      // 直前の状態は保持しておく
      const prevToatalMilliIsu = totalMilliIsu
      totalMilliIsu = totalMilliIsu.add(totalPower.mul(Number(time) - prevTime))
      if (addingAt[time]) {
        let a = addingAt[time]
        totalMilliIsu = totalMilliIsu.add(a.isu + "000")
      }
      // 購入可能になっていたらその時刻を逆算
      for (let itemId in mItems) {
        if (typeof itemOnSale[itemId] !== 'undefined') {
          continue;
        }
        if (0 <= totalMilliIsu.cmp(itemPriceX1000[itemId])) {
          if (totalPower.cmp(BI0) == 0) {
            itemOnSale[itemId] = time
          } else {
            const diff = itemPriceX1000[itemId].sub(prevToatalMilliIsu)
            const div = diff.div(totalPower)
            const mod = diff.mod(totalPower)
            const t = mod.eq(BI0) ? div.toNumber() : div.add(1).toNumber()
            if (prevTime + t < time) {
              itemOnSale[itemId] = prevTime + t
            } else {
              itemOnSale[itemId] = time
            }
          }
        }
      }
      if (buyingAt[time]) {
        const updatedID = {}
        for (let b of buyingAt[time]) {
          const m = mItems[b.item_id]
          updatedID[b.item_id] = true
          itemBuilt[b.item_id] = itemBuilt[b.item_id] ? itemBuilt[b.item_id] + 1 : 1
          const power = m.getPower(b.ordinal)
          itemPower[b.item_id] = itemPower[b.item_id].add(power)
          totalPower = totalPower.add(power)
        }
        for (let id in updatedID) {
          itemBuilding[id].push({
            time: time,
            count_built: itemBuilt[id],
            power: this.big2exp(itemPower[id]),
          })
        }
      }
      if (time != currentTime + 1000) {
        schedule.push({
          time: time,
          milli_isu: this.big2exp(totalMilliIsu),
          total_power: this.big2exp(totalPower),
        })
      }
      prevTime = Number(time)
    });

    ...
  }

currentTimeからその1000ms後までの区間で、addingAtbuyingAtがあった時刻を時系列に並べ、その区間ごとに前のイベント時刻との差分を使って掛け算でtotalMilliIsuに加える値を計算。

なんとなく実装して 用意されていたユニットテスト(めっちゃ有り難かった)も通った、のが14:40。 これでどうだ!と走らせてみると

負荷走行前のバリデーションに失敗しました。time = 1511588407211 の status において on_sale[item_id = 5].time が正しくありません : actual 1511588407999, expected 1511588408000

!!! 1msずれてる !!!

どっかで境界値バグがあったか… と試しにitemOnSaletimeの値を+1してみたりしたけどやっぱり通らず(当たり前か。この時間は無駄だったな…)、思った以上にバリデーションが細かくチェックしていた。

うーん うーん と唸りながらコードを見直して totalMilliIsuの更新タイミングと購入可能チェックのタイミングが順番がおかしかった…と思って 直したり

負荷走行中のバリデーションに失敗しました。room ROOMmVe0gsm8OU7zKMKUGNOQ にて schedule に同一の時刻が含まれています

と出て そうかaddingAtbuyingAtは同時刻に起こることもあるから単純に混ぜるんじゃなくてuniqueにしなきゃダメじゃん、ってなったり

あとはon_saleの時刻がどうしても大きくズレることがあって まとめて加算後に購入可能になったときitemPrice - prevToatalMilliIsutotalPowerで割ってprevTimeに足すだけだと思ってたけど 実はtotalPowerの値は小さくてaddingAtで大きく加算されたことによって購入可能になった場合もあるな、ということに気付いて直し。

さらに割り算も単純に割ってたらダメで小数は切り上げないといけない。これが境界値バグだった、のに気付いたのは一番最後だった。しかしbigintではMath.ceilは出来ないのか… divmodで分けて計算して、mod0より大きかったらdiv+1に…と修正。

とにかくことごとく勝手に罠にハマりまくって、ようやくちゃんと通ったのが 16:15頃。結局3時間くらいここにかかってしまった…。 とりあえずスコアは20,000点を越えるようにはなったけど、そこまですごいブレイクスルーにはならなかった。。

終盤

あとは無駄な部分を少しずつ潰しておこう、と itemのgetPrice(count)getPrice(count)countの値が同じなら同じ値を返すだけだしキャッシュしていこう、と一度計算したものは記憶させてそれを返すように、など。 あとで気付いたけどこういうのはinitialize時にある程度の数まで計算してしまえば走行中に計算するのは1回も無くなるんだった。

結局あまり時間も残っておらず そこから大幅な改善も出来ず、あとは2人の作業を見守るだけ、みたいな感じになってしまった。

再起動テストや微調整などを見守り、最高スコアは18:03に29,944を記録していたけど、それ以上の数字は出ないまま フィニッシュ。

反省

インフラよりアプリケーション寄りの問題だったので、主にアプリケーション担当として参加させてもらっている以上はもっとバリューを出していかなければダメだった。

もっと素早く正確にコードの変更をガンガン進めていければ インメモリ化してMySQLから離れる施策も検討できたかもしれないし、他にもチューニングしていける箇所は改善していけたはず。

1000回ループ問題も そこまで効果をちゃんと考えずに取り組んで すごい時間かかってしまったし…。 (このへん 競プロ勢のヒトとかだったらもっと簡単にサクっと解決できていたんだろうなー とか)

そもそもbigintの演算がどれくらい負荷になっていて どこを最優先で減らしていくべきかをちゃんと分析できていなかった、というのもある。 もっと各所でどんな値が流れていてどんな処理が時間とCPUを食っているか、を意識して調査しながら解決していく姿勢・技術が必要だった。

などなど、アプリケーションエンジニアとしての力不足を痛感する敗戦でした。 この先もまだこういう道で生き残っていきたいし、ちゃんと勉強して精進していかねばなー… と思ったのでした。

まとめ

  • やれるだけのことはやった
    • けど力不足でした

懇親会では色んな方と反省会しながらお話できて良かったです。ISUCONケーキめっちゃ美味しかった。

f:id:sugyan:20171125192629j:plain

運営・出題の皆様、主催・協賛の皆様、そして一緒にチームを組んで戦ってくださった id:kazeburoさん、id:gfx氏、本当にありがとうございました!

f:id:sugyan:20171125234916j:plain

逆算方式による詰将棋の問題生成プログラム

将棋を始めた ので、詰将棋を毎日のように解いているのだけど、せっかくなら詰将棋の問題を自動生成してみたい、と思って試してみた。

前提知識

詰将棋とはどんなものか

  1. 攻め方(先手)が玉方(後手)の玉を詰ますのが目的。
  2. 攻め方は必ず王手をかける(玉方は必ず王手をはずす)。
  3. 玉方は盤上と攻め方の持駒以外すべての駒(ただし玉は除く)を合駒として使用できる。
  4. 玉方は最善を尽くし、最も長く手数がかかるように逃げる。
  5. 玉方は無駄な合駒をしない。
  6. その他は指し将棋のルール通り。二歩、打ち歩詰め、行き所のない駒、連続王手の千日手はいけない。

(日本将棋連盟の詰将棋ページより)

手法

コンピュータによる詰将棋の解答・問題生成というのは20年くらい前から既に様々な論文などで研究されているようだ。生成については、主に「ランダム法」「逆算法」といった方式があるらしい。

あまり論文にちゃんと目を通して調べてはいないけど、だいたい手法は述べられているものの 実際に利用できそうな公開されているプログラムが見当たらなかったので、自分で作ってみることにした。

手法について調べる前に最初に思いついたのが逆算法だったので、その方式で。

詰み状態の生成

逆算法は、詰みの状態から巻き戻すような形で問題を生成していくので、まずは最終的な「詰み」の形を生成する。

とりあえずは一般的な詰将棋ということで玉は攻め方(先手)は無しで後手側だけに存在する前提。 まずは何も考えずそれ以外の38個の駒をランダムに配置してみよう。

f:id:sugyan:20171119212056p:plain

…まず二歩があるし、王手もかかってないし、関係ない駒が多すぎる。 少し条件を追加してみる。

  • 二歩を回避
    • 1筋につき1個しか歩が置かれないように
    • 無理矢理置かず 適当に後手側の持駒に
  • 有り得ない駒配置を回避
    • 先手だと1段目に歩・香車、2段目以下に桂馬、などは有り得ない
    • 成らせる、もしくは後手側に変えてしまう
  • 成駒を追加
    • せっかくなので成れる位置に居る駒は適当な確率で成らせる
    • 飛車・角はもうちょっと下の方でも成って良いことにする

f:id:sugyan:20171119212106p:plain

これで一応、有り得なくはない局面になった…かな。 たまに王手になっている状態のものは出るけど、「詰み」の状態にはなかなか遠い。関係ない場所に居る駒が多すぎる。 さらに以下の条件を追加する。

  • 後手側の玉の位置を1〜4筋、1〜4段に限定
    • その他の駒を、その近くに集中させる

f:id:sugyan:20171119212111p:plain

惜しい!

f:id:sugyan:20171119212116p:plain

王手すらかかってない!

f:id:sugyan:20171119212120p:plain

OK!

感覚としては、上述の条件で10回程度試行すれば、「詰み」の状態は得られるようだった。

ところで「詰み」とは。

  • 既に王手がかかっている状態であり、
  • どう応じても必ず王が取られてしまう状態
    • どの応手を選択しても王手状態から逃れることができない

というロジックで判定する必要がある。

1手前に戻す

さて、「詰み」が出来たので、そこから逆算していきたいところだけど、まだちょっと関係ない駒が多すぎるので、「詰み」の状態が崩れない 影響を受けない駒を取り除いて後手側の持駒にする。

とはいえ最終的に出来上がる問題には効果のある位置にある駒もあるかもしれないので、すべては取り除かず、確率として8割程度を消す感じで。

f:id:sugyan:20171119212125p:plain

だいぶスッキリした「詰み」状態になっている。

ここから、先手側を1手「戻す」ことで王手状態でなくなれば、それを辿る手が正解となる1手詰の問題が出来上がる、はず。

1手前の有り得る状態、とは。

  • 盤上の先手駒の動き得る範囲から逆算
  • 持駒を使う場合も
    • しかし打ち歩詰めは回避する

たとえば歩が一歩手前に居るかもしれないし、成っていない駒は持駒の中から打たれたものかもしれない。成駒なんかは金の動ける範囲での前の位置かもしれないし、桂馬が跳ねてそこに成ったものかもしない、など色んなパターンを考慮する必要はある。

ただ生成すべきは1手詰の問題なので、1手前は「王手ではない」状態になっている必要がある。 なので、上図の場合は必然的に3四の龍が別の位置に居た、という状態が選ばれることになるだろう。

2三2五3六 のどこかに居た状態であれば、王手ではないので大丈夫そう。

f:id:sugyan:20171119212128p:plain

というわけで出来たのが上図。ここから ▲3四龍 と動けば玉はどこにも逃げられず、詰みとなる。

とはいえなんかまだ関係ない駒が多いな… というわけで改めて、問題に関係ない、取り除いても問題ない駒を排除する。

ついでに、成香・成桂など通常の問題図にはあまり現れない慣習がある?ので、微妙な成駒は金将やと金があればそれに置き換えるなどの処理をする。ここでは金を優先にしたので と金 が 金将 に置換される。問題には影響ない。

f:id:sugyan:20171119212134p:plain

これで1手詰の問題が完成となる。 この問題の場合は1, 2段目が完全に無駄な空白になってしまっているので 全駒を丸ごと上段に(さらに右にも)ずらしてしまっても良さそうだけど 特にそういう処理は入れていない…

解答をSolverでチェック

上述の例はたまたま上手くいったけど、場合によっては 1手巻き戻した結果が 1手詰の問題にはなっているものの「解が複数ある」という状態になってしまうこともある。

f:id:sugyan:20171119212136p:plain

例えばこういう場合。元々は2二に成銀が居る状態から巻き戻して作られたのだけど、実際には ▲2二飛成 でも正解になってしまう。正解が複数できてしまう、「余詰」という不完全作品になってしまう。

なので これは失敗とみなして最初から作り直すべき。 ということで 「正解が1通りしか無いこと」をチェックするためのSolverが必要となる。

1手詰だけを考えるのであれば、これはとりあえず先手の動かし得る手を全探索して 詰みになる手を列挙していけば良いだけなので Solverというほどのものじゃなくてもいいかも。

3手詰への拡張

さて、とりあえず1手詰は作れるようになったので、次は1段階ステップアップして3手詰の問題生成にチャレンジ。 基本的には同じ考え方で、

詰み -> 先手を巻き戻してNOT王手に

から

詰み -> 先手を巻き戻してNOT王手に -> 後手を巻き戻して王手に -> 先手を巻き戻してNOT王手に

と巻き戻しを増やすことに。 1手詰の場合は先手の動きだけ考えれば良かったが、3手詰から先は後手側の動きも入ってくるので面倒になる。

まず最初の巻き戻しだけど、1手詰の問題を生成する場合は

  • 詰み方が1通りしかないようにする
  • 関係ない駒は最終的に取り除く

という処理をしていたけど、3手詰における最終手は複数通りあっても良いし、やはり周りの駒が問題に影響することもあるので完全には取り除かないでおく。とにかく「あと1手で詰む」という状態になっていれば良い(駒余りなどは避ける必要あるけど)。

次の後手側の巻き戻し。問題を解く際には最善手で逃げることを考えないといけないけど、そのへんは考えず とりあえず有り得る状態を作り出す。

前の状態が王手で 今が1手詰の王手ではない状態、ということは

  • 玉が安全地帯に動いて逃げた
  • 後手側の駒(玉も含む)が王手をかけていた駒を取った
  • 飛車・角・香車などの道を塞ぐように持駒を打った

というパターンが考えられる。 なので、巻き戻す際には

  • 玉を先手駒の効きがある位置に突っ込む
  • 後手側の玉付近の駒の位置に 先手側の王手駒があった状態にする
  • 成駒でない駒を取り除く

ということを考えることになる。 特に2番目のパターンが複雑で、まずその位置から王手をかけられる駒でないといけないし、それを取れる位置に後手の駒が居ないといけない。

f:id:sugyan:20171119212139p:plain

例えばこの図でいう3一の歩は、持駒から打った状態しか有り得ないので、この位置から先手側の駒で王手していた、ということは有り得ない。

そして有り得る状態のパターンはかなり多くなり、例えば上図で2二の銀が元々1一とかに居て 何かしら先手の駒を取ってこうなった、と考えるとその駒は 歩、香車、金、成銀、… つまり桂馬と角以外すべてが有り得る。

ので、生成され得るパターンも膨れ上がることになる。

まぁそうやって多くのパターンが有り得るけども、全部を検証する必要はなくて それらの中からランダムで選択して生成したものが偶然にでも良い形になっていれば良いのだけど。

こうして後手側の巻き戻しで王手状態が作れたら、1手詰のときと同様にまた先手側を「王手ではない」状態に巻き戻す。

こちら側のロジックは同じで問題ないけど、唯一違う部分としては最終手ではないので打ち歩が許される、くらいかな。王の目の前に歩がいる状態が、持駒から打ったものとして処理しても許される。

3手詰Solver

上述のように 先手 -> 後手 -> 先手 と巻き戻したことでなんとなく3手で詰む問題になりそうだけど、「後手は最善手で逃げる」ということを考慮せずに巻き戻しているので、実際には全然意図通りにならないことが多い。

3手戻したのに結局1手で詰めてしまうものになっていることもあるし、意図せず5手詰や7手詰の状態になっていることもあるし、余詰だらけになったり そもそも解けない問題になってしまうこともある。

というわけで1手詰の場合と同様に、

  • 3手で詰める問題である
    • 駒余りなどもない
  • 少なくとも1手目は一通りの解しかない
    • 3手目は複数あっても良い

といったことを検証し、そうでない場合はもう一度作り直し、という方針でいきたい。

…が、1手詰と違って3手詰以上の問題を解く解答プログラムはなかなか奥が深く、簡単ではなかった。

少なくとも3手程度なら全探索しても現実的な計算量で済むのでは、と思ったけど 合駒・無駄合駒というルールがあり 実際には3手で詰むものも 素直に全探索していると 合駒 -> 同飛 が続いて7手になってしまう、などといったことが起こる。じゃあ無駄合駒を判定してそれは打てないよう考慮して判定、と思っても「どういう条件なら無駄合駒なのか」という明確なルールが存在しない(!)という難しい問題…。「無駄合駒」でググって調べるだけでもだいぶ面白かった。

あと再帰的に調べる際には不詰(もうどうやっても詰ますことができない)になったら探索を打ち切れるのだけど、その不詰の判定も難しく、パッと見ではこれはもう詰まないでしょ という局面からもルールに則った無駄な追いかけっこ状態は起こり得るので それを上手く判定できないとどんどん探索が深くなり無限に時間がかかる。

とりあえずは探索する深さを限定させて それ以降はもう解けない、という制限を設けることで だいたいの3手詰くらいなら解けるようになったけど、パターンによっては数百msかかってしまい、厳しい。

これが遅いせいで、3手詰問題の生成は現状 数秒〜十数秒かかってしまう。

調べると「df-pnアルゴリズム」「最良優先探索」といったものを使うことで長手数のものも解けるようになる、ということだったので ここは今後の課題として早く確実に解けるSolverを実装しておきたい。 5手詰以上の問題を生成しようと思うと このチェックのためのSolverがボトルネックになってしまうので、ここが解決されないと厳しいな、という感じ。


ともあれ、Solverでのチェックが出来れば 1手詰の問題と同様に不要な駒を取り除いたり後処理をして、こんな感じの問題が出来上がる。

f:id:sugyan:20171119215709p:plain

はい。▲2二歩成 △1三玉 ▲2三飛 の3手詰になって…ますよね?

成果物

とりあえずは何となく3手詰の問題までは生成できるようになった、ということで 自動生成された問題を定期的に呟くTwitter BOTは作ってみた。

まだまだ潰しきれていない判定バグなどがあって不完全な問題が出ることもあるかもしれないけど。見つけ次第 随時なおしていきたいと思います。

Chat BOTでも使えるようにと開発を進めているけど、その話は後日 別の場所で…

所感

3手詰の問題生成程度なら、難しいアルゴリズムの知識など無くても とりあえず作ることができる、というのを実感した。 ただ、ひたすら面倒臭いけどw

将棋のルールをプログラムのロジックに落とし込む、というだけでもなかなか大変で。駒によって動きが違うし 大きく動ける駒も途中で阻まれれば先には行けないし 成駒や不成も有り得るし 無駄合駒とか複雑なルールがあったり…

とにかくif文やswitch文だらけでつらい感じのプログラムが出来上がりやすい…。 キレイに書くのはとても難しい、でもプログラミングの練習にはなかなか良い題材かも、というのも思ったりもしたのでした。

ISUCON7 予選通過した

ISUCON7id:kazeburo さんと id:gfx さんと、チーム「スギャブロエックス」で出場して、2日目の上位3チーム枠の2位で予選通過しました。

isucon.net

f:id:sugyan:20171022204129j:plain

スコアの遷移は以下の通り、最終スコアは 522,461。

時刻 スコア
2017-10-22T13:06:44 6012
2017-10-22T13:16:24 5108
2017-10-22T13:35:01 4721
2017-10-22T13:49:24 6870
2017-10-22T14:36:24 4951
2017-10-22T14:41:01 6749
2017-10-22T15:03:44 6164
2017-10-22T15:24:50 15095
2017-10-22T15:29:00 20526
2017-10-22T15:37:00 17957
2017-10-22T15:46:22 30512
2017-10-22T15:50:50 31042
2017-10-22T16:21:24 28323
2017-10-22T16:57:17 17656
2017-10-22T16:58:22 15725
2017-10-22T17:00:50 21895
2017-10-22T17:02:13 23369
2017-10-22T17:07:48 19385
2017-10-22T17:11:06 26365
2017-10-22T17:24:37 51942
2017-10-22T17:36:39 36799
2017-10-22T17:40:00 32550
2017-10-22T17:42:49 85787
2017-10-22T17:52:07 56550
2017-10-22T18:04:06 114636
2017-10-22T18:06:07 144735
2017-10-22T18:16:51 115281
2017-10-22T18:22:16 139258
2017-10-22T18:31:50 108422
2017-10-22T18:40:40 110545
2017-10-22T18:46:12 207937
2017-10-22T18:52:31 224172
2017-10-22T18:57:17 294244
2017-10-22T19:02:48 185747
2017-10-22T19:04:11 197431
2017-10-22T19:13:12 211655
2017-10-22T19:17:02 180887
2017-10-22T19:19:31 324890
2017-10-22T19:21:20 365210
2017-10-22T19:22:34 257398
2017-10-22T19:29:15 313264
2017-10-22T19:34:51 268841
2017-10-22T19:37:42 506162
2017-10-22T19:39:13 465960
2017-10-22T19:43:36 398467
2017-10-22T19:45:31 360072
2017-10-22T19:46:58 312146
2017-10-22T19:48:54 506943
2017-10-22T19:54:15 373185
2017-10-22T20:00:29 255289
2017-10-22T20:09:05 349379
2017-10-22T20:10:42 223452
2017-10-22T20:20:09 304453
2017-10-22T20:22:14 213811
2017-10-22T20:23:30 195622
2017-10-22T20:25:16 235779
2017-10-22T20:27:38 309148
2017-10-22T20:32:19 393837
2017-10-22T20:33:33 212309
2017-10-22T20:35:04 405354
2017-10-22T20:36:55 236184
2017-10-22T20:38:30 264824
2017-10-22T20:40:06 522461

チームで使ったコードの履歴はこちら。

GitHub - gfx/isucon7-qualify: SugyaburoX repo for ISUCON7 (2017) qualify

前日まで

チームは決めて Slack上でやりとりはしていたものの、直接顔を合わせての打ち合わせ的なものは1度もせず。 まぁ開始時間が遅くなっていたおかげで早めに集まって始まるまでの時間があったので良かった。

言語はどれを使おうか、ってのはまぁ悩んで。 元々みんなPerl界隈の人だったはずだけど最近は… って感じで 僕も自分が一体どの言語が得意なのか分からない状態だったので gfxに任せて Node.js で行くことに。

当日

kazeburoさんのMercari社さんで場所と昼食を提供していただけることになったので(ありがとうございました!!!)、六本木に集合。

最初はだいたい決めてた通りに役割分担する感じで kazeburoさんがサーバ周りもろもろセッティングして gfxがコードを読んでアプリケーションを把握して 僕がローカルでアプリケーション動かすのを試してみたり

やったこ

お題はチャットアプリケーション

まずはとにかくユーザのアイコン画像がDBに入っていて毎回アプリケーションから返してるのはないよね、ってことでWebDAVで一箇所に静的ファイルとして保存して返すようにしよう、と。 初期データのものをWebDAVにツッコむだけのスクリプトを書こうとしたのだけど、Nodeの非同期httpリクエストを扱いながら繰り返し処理をする、ていうのが上手く書けず… 結局2人に見てもらって引き取ってもらう という役立たずっぷり orz

そのへんとか N+1的なクエリをgfxが直したり でスコアは上がったものの 他のチームは桁違いに高い数字を出しており… どうしたらそんな点数でるの?? て感じで17時半くらいの時点では敗色濃厚な雰囲気。。

kazeburoさんが1台あたりの帯域を使い切っていることに気付いてベンチマーカの向き先を増やしたりCache-Controlヘッダを上手いことやったりして一気に2〜3万から7〜8万にアップ。 ここからだんだんまたアプリケーションやDBのボトルネックが見えるようになってきたので再び遅いクエリを解消していくなどの作業。

各チャンネルの未読数を全チャンネルに対するCOUNTクエリ発行してるのを解消しよう、と既読数テーブルを作って 全メッセージ数 - 既読数 で未読数を出すように変更。22万くらいから29万くらいに上がった、唯一バリューが出せたところ

あとは全メッセージ数もchannelテーブルで管理するようにとか色々変更を入れていったらだいたい30万以上は出るようになったのだけど とにかくベンチマークのブレが大きくてコード変えてなくても実行するたびにスコアが10万点くらい上下したりして ボトルネックの発見もその解消の検証もしづらい。 まず効果がありそう、なところだけやって、最後の数十分は何度も試して高いスコアが出るまで祈って繰り返す、という感じだった。 20:40で良いスコアが出たのでそこでストップ。

反省

Node.jsの非同期処理まわりが書き慣れてなさすぎてロクにコードを書けなくて足を引っ張ってしまった。 ホントにkazeburoさんとgfxのおかげで通過できました!!!という感じだったので 本選ではもっと役に立てるよう頑張りたいと思います。


出題・準備と、運営の皆様 とっても大変だったと思いますがありがとうございました! また来月よろしくお願いします!!!!!

「[改訂新版]Emacs実践入門」を読んだ

この本です。

[改訂新版]Emacs実践入門―思考を直感的にコード化し、開発を加速する (WEB+DB PRESS plus)

[改訂新版]Emacs実践入門―思考を直感的にコード化し、開発を加速する (WEB+DB PRESS plus)

著者tomoyaさんによるエントリがこちら。

d.hatena.ne.jp

前回のときに献本いただいた縁もあり、今回もまたいただいてしまいました。ありがとうございます!!!

memo.sugyan.com

あれから5年、僕も色々な変化があり 昨年末くらいからはVSCodeをメインで使うようになり この記事を書くにあたり久々にEmacsを立ち上げるか…と思ったら新しいマシンにはインストールすらしていなくてビックリした!

ていうくらい離れてしまっている状態ではありますが、色々と思い出しながら読ませていただきました。

上記以外の初版からの大きな変更は次の通りです。

  • 拡張インストールをpackage.el (ELPA) に全面書き換え
  • Anything から Helm へ
  • Flymake から Flycheck へ
  • Egg から Magit へ
  • 『web-mode』の追加
  • 『コードの実行(quick-run)』の追加
  • 『差分の表示──git-gutter』の追加
  • 『テスティングフレームワークとの連携(phpunitrspec-mode)』を追加

と書かれているあたりは、自分も毎日Emacsを使っていたときに愛用していたものたちばかりで、自分の使い方は間違っていなかった、というのを再確認できました。 最新のアップデートとトレンドを網羅していて とても良い改訂だと思います。たぶん。

Emacsは本当に良いエディタで、VSCodeに移った今でも当然 Emacs Keymap を入れて基本的にはEmacsキーバインドで動かしているし それでも選択まわりの挙動がちょっと気に食わなくてイラっとすることがあるくらい。

じゃあEmacsに戻れよって感じですが。 なんとなく、エディタに縛られることなく多少開発環境が変わっても対応できるようにするためにも慣れておこうというのもあって乗り換えてみたのだけど それはそれで良かったと思うし、この本を読んで 今またEmacsに戻ろうと思ってもそれほど苦労なく切り替えられそうだな、と自信が持ててよかったです。

「プロジェクト」の概念についても思うところはあって 確かにEmacsでは一つのウィンドウですべてバッファの切り替えだけで扱っていたの便利だなーと思うし でもプロジェクトごとにウィンドウが分かれていた方がスッキリするのも確かだし しかし2つ3つならまだしも4つ5つ…となってくると切り替えがすごく面倒で… と 悩ましいところではある

今後もちょいちょいこうしてEmacsを振り返りつつ 他のエディタもそこそこ使いこなせるようになれればいいな、と改めて思えた良い本でした。

顔検出に関する最近の論文

Face Detector関連だけでもなんか色々あるようだ。

(中身はまだまったく見てない)

GitHub の number9473/nn-algorithm っていうリポジトリで、arXivTimes のように論文の紹介をしているようだ。"Face Detection"っていうラベルまである。

github.com

TensorFlowで顔検出器を自作する

f:id:sugyan:20170820172842j:plain

19日に行われた Kyoto.なんか #3 で発表・デモをさせていただいた内容まとめです。

はじめに: 検出器の重要性

アイドル顔識別 をずっとやっている中で、顔の識別・分類(Classification)はCNNを使って出来ているけれど まだ上手く出来ていない別のタスクがあって。

それが画像内からの顔領域の検出 (Detection, Localization)。

「画像内に写っている人物が誰であるか」を識別するためには、まずはその画像に写っている「顔」を検出する必要がある。 その検出された顔それぞれについて分類器にかけて「この顔は○○さん」「この顔は××さん」と分類していくことになるわけで。

分類器に与える入力画像を切り抜いて抽出するのにもまず顔領域を検出する必要があるし、その分類器を学習させるためのデータセットも、様々な画像から顔領域を検出して切り抜いてそれぞれに対してラベル付けすることで作っている。 なので、顔識別タスクには「顔領域の検出」が不可欠となっている。

従来の方法

今までは、データセット作成のための顔画像収集にはOpenCVを使った回転補正機能つきの検出器を自作して使っていた。

OpenCVのHaar特徴によるカスケード型分類器を使った領域検出は、正面向き顔・目などを検出するため学習済みデータが標準で同梱されており、最も手軽に使える検出器と言える。 しかし、この検出器は斜めに傾いた顔に対しては一気に精度が下がるという弱点があり、斜めに写っていることが多いアイドルの自撮りでは上手く検出できない場合が多い。 それを克服するために、元画像を少しずつ回転させたものを生成し それぞれに対して検出器にかけ それらの結果をマージする、という方法を使って斜めのものもそれなりの精度で顔検出できるものを作った。

詳しくは過去のこの記事。

memo.sugyan.com

これによってある程度の精度で顔領域を検出することができ、また 顔と同時に両目の位置も検出するようにしたので その検出された目の座標のx差分, y差分を使った逆正接 atan2 で傾き角度も求めることができる。

これで大体やりたいことは実現できそうだったので、自分の取り組んでいるアイドル顔識別においてはこの検出器を使ってデータセット用の顔画像抽出を行ってきた。

しかし この検出器でもまだ問題は残っていて。

  • とにかく処理が重く時間がかかる
    • 回転した複数の画像を作る、それぞれから検出する、ので当然
  • まだ誤検出が多い
    • 顔ではない壁や服の模様を顔として検出してしまうことが多い
  • 学習させカスタマイズ、などしづらい
    • データセットを用意して学習させることは出来るらしいが…

遅いのはデータセット用の収集にはそれほど問題ではないけれど、例えば顔識別BOTのようにインタラクティブにレスポンスを返したい場面においては致命的で、仕方ないのでBot用の検出には Cloud Vision API を使うようにしているのが現状。

また精度的にも少し問題があって、特に金髪の人物の場合に 実際の顔領域より大きく検出されることが多いようだった。顔と髪の区別がつきづらい、から…?

例:


LBPなど他の特徴を使った検出器に切り替える、またdlibなど他のライブラリを使用することで改善も出来たかもしれないけど、折角なのでここは Deep Learning を使った検出器を作って自前の学習データを食わせて学習させたい、という思いがあり 今回はそれに挑戦してみることにした。

Deep Learning による物体検出

Deep Learning を使った物体検出の手法もたくさん研究されていて近年めざましい発展を遂げているようで、代表的な手法としてこんなものが提案されてきた、と下記記事で紹介されている。

tech-blog.abeja.asia

一番最近のものとして紹介されている SSD (Single Shot MultiBox Detector) がとても高速に高精度で検出をできそうで良さそうだな と思って、いちおう論文も少し目を通してみた。 元の実装はcaffeによるもので、TensorFlow版も書いている人が数人いたけど 何となくの原理は分かったような気がするし自分でも勉強がてらTensorFlowで書いてみよう…として、難しすぎて途中で挫折した。 のが今年の1月頃の話。

Object Detection API

時は過ぎ、今年の6月中旬。 TensorFlow公式のモデル群 TensorFlow Models リポジトリで、 “Object Detection API” が公開された。 ここでは、MS COCO dataset を使って学習済みの5種類の一般物体検出モデルが公開されている。

github.com

Model name Speed COCO mAP
ssd_mobilenet_v1_coco fast 21
ssd_inception_v2_coco fast 24
rfcn_resnet101_coco medium 30
faster_rcnn_resnet101_coco medium 32
faster_rcnn_inception_resnet_v2_atrous_coco slow 37

下の方がより精度が高く、その分モデルは大きくなるし処理も重くなるようだ。 上2つはまさに SSD を使ったものであり、ベースとなる CNN を元論文では VGG16 を使っていたのに対し軽量な MobileNet を使ったもの、 Inception V2 を使ったもの と2種類それぞれで実現しているようだ。 Faster RCNN などを使ったものより検出精度は劣るものの、やはり処理速度は圧倒的に SSD の方が早そう。

さらにこのリポジトリでは、学習済みモデルを利用した転移学習で 別のデータセットを利用して学習しなおす方法についても仕組みが用意され 丁寧に説明されている。 つまり、このリポジトリのモデルで扱う形に適合した tfrecord ファイルを自分で用意できれば、簡単にそれを使った検出器を学習させ使うことができる、ということのようだ。

これを使わない手は無い、ということで試してみた。

FDDB dataset から学習用データセットを作る

自分が集めてきたアイドル顔画像から用意しても良かったけど、まずは一般に公開されているデータセットで試してみよう、と思って探してみたところ、FDDB というデータセットがヒットした。

FDDB : Main

2,845点の画像それぞれについて、写っている顔領域を楕円で表現し その中心座標、長径・短径、傾き角度 のセットがアノテーションとして計5,171件 与えられている。

これで顔領域の検出だけなら学習させられそうだけど、これだけでは顔の傾きは取得できない。 OpenCVを使ったものと同様、両目の位置さえ取れればそこから角度は算出できそうだけど、両目の位置の情報は残念ながら付属のアノテーションには含まれていない。

しかし「顔の存在する位置」「傾き」が与えられているなら、その領域を狙い打ちして OpenCV で検出することも可能なはず。

アノテーションそれぞれについて、

  • 与えられている傾きを補正するよう回転させて
  • 顔の中心座標を中心とする 長径 * 1.1 の、少し大きめのサイズの正方形で切り抜く

という操作で「縦に真っ直ぐになった顔が写っているはずの領域」を抽出した画像を一度作り、それに対して OpenCV による顔検出をかける。 そうして検出された目の領域を表す座標をそれぞれ回転前の座標に変換すれば、元画像に対する目の領域も取得できる。

やはりある程度の誤検出はあるので、適当にフィルタリングして補正し、除外。 こんな感じのコードで

import cv2
import math
import os

CASCADES_DIR = os.path.normpath(os.path.join(cv2.__file__, '..', '..', '..', '..', 'share', 'OpenCV', 'haarcascades'))
FACE_CASCADE = cv2.CascadeClassifier(os.path.join(CASCADES_DIR, 'haarcascade_frontalface_default.xml'))
EYES_CASCADE = cv2.CascadeClassifier(os.path.join(CASCADES_DIR, 'haarcascade_eye.xml'))

def detect_faces(img, lines):
    results = []
    for line in lines:
        e = line.split(' ')
        size = max(float(e[0]), float(e[1])) * 1.1
        # 小さすぎるものは除去
        if size < 60.0:
            break
        # 真っ直ぐになっているはずの領域を切り抜く
        center = (int(float(e[3])), int(float(e[4])))
        angle = float(e[2]) / math.pi * 180.0
        if angle < 0:
            angle += 180.0
        M = cv2.getRotationMatrix2D(center, angle - 90.0, 1)
        M[0, 2] -= float(e[3]) - size
        M[1, 2] -= float(e[4]) - size
        target = cv2.warpAffine(img, M, (int(size * 2), int(size * 2)))

        # 切り抜いた画像から顔と目を検出する
        faces = FACE_CASCADE.detectMultiScale(target)
        if len(faces) != 1:
            print('{} faces found...'.format(len(faces)))
            break
        face = faces[0]
        face_img = target[face[1]:face[1] + face[3], face[0]:face[0] + face[2]]
        eyes = []
        for eye in EYES_CASCADE.detectMultiScale(face_img):
            # 始点の高さが元画像の下半分にあるようならおそらくそれは誤検出
            if eye[1] > face_img.shape[0] / 2:
                break
            eyes.append(eye)
        if len(eyes) != 2:
            print('{} eyes found...'.format(len(eyes)))
            break
        # 両目のサイズがあまりにも異なるのは不自然なので検出失敗とする
        if not (2. / 3. < eyes[0][2] / eyes[1][2] < 3. / 2. and 2. / 3. < eyes[0][3] / eyes[1][3] < 3. / 2.):
            break
    ...

これでだいたいは上手く検出できたようだった。

この方法で上手く検出でき、与えられているアノテーションと同数の顔が正しく両目と共に検出されたものだけを用いてデータセットを作成。 結果として、使用できたのは2,845点のうち936点だった。 ちょっと少ないけど仕方ない。 train用とvalidation用に分ける必要があるようだったのでこれをさらに 843:93 に分割して使用した。

で、あとはこれをそれぞれ画像に対する image/objcet/bbox/*image/object/class/* といったkeyに情報を含めて tfrecord 形式に書き出す。

feature = {
    'image/height': tf.train.Feature(int64_list=tf.train.Int64List(value=[h])),
    'image/width': tf.train.Feature(int64_list=tf.train.Int64List(value=[w])),
    'image/filename': tf.train.Feature(bytes_list=tf.train.BytesList(value=[filepath.encode('utf-8')])),
    'image/source_id': tf.train.Feature(bytes_list=tf.train.BytesList(value=[filepath.encode('utf-8')])),
    'image/encoded': tf.train.Feature(bytes_list=tf.train.BytesList(value=[encoded])),
    'image/format': tf.train.Feature(bytes_list=tf.train.BytesList(value=['jpeg'.encode('utf-8')])),
    'image/object/bbox/xmin': tf.train.Feature(float_list=tf.train.FloatList(value=xmin)),
    'image/object/bbox/xmax': tf.train.Feature(float_list=tf.train.FloatList(value=xmax)),
    'image/object/bbox/ymin': tf.train.Feature(float_list=tf.train.FloatList(value=ymin)),
    'image/object/bbox/ymax': tf.train.Feature(float_list=tf.train.FloatList(value=ymax)),
    'image/object/class/text': tf.train.Feature(bytes_list=tf.train.BytesList(value=class_text)),
    'image/object/class/label': tf.train.Feature(int64_list=tf.train.Int64List(value=class_label)),
}
example = tf.train.Example(features=tf.train.Features(feature=feature))
writer.write(example.SerializeToString())

これで一応、データセットが作成できたので あとはこれを使って学習させる。 ssd_inception_v2_coco の学習済みモデルをベースにFine-Tuningする形で。 Google Cloud Machine Learning を使う方法も書いてあったのだけど ちょっと何故か上手くいかなかった(要 再挑戦)ので、今回はEC2のg2.2xlargeインタンスを使って学習を行った。 1stepあたり2秒弱くらい、丸一日で 50,000stepほど学習が進み、だいたいは学習が出来た雰囲気だった。

f:id:sugyan:20170820190012p:plain

これを使って検出してみた結果が冒頭の画像。

用意したデータセットに傾いている顔もある程度は含まれていたので、そういうものもある程度は検出できるようだった。 たった800件ちょっとの画像でのデータを用意だけでもこれだけ検出できるようになっているのだから十分かな、という感触。 ここからさらにデータセットを増やしていけばどんどん精度は上げられそうな気がする。

あとは実際の顔識別に使うような自撮りの多い画像たちを どうアノテーション付けてどう管理し、どう性能評価していくか、って話になってくると思う

Webアプリ化

ここからは完全に余談なのだけど、せっかく高速に顔検出できるモデルをTensorFlowで構築できたのだから、Webサービスとして公開できるようにしよう、と。 顔検出モデルはFlaskを使ってJSON API化できる。 あとはフロントエンドだけどうにかしてUIを作るだけ。

以前もちょいちょいReactとかwebpackとか使って似たようなものは作っていたので使い回しだけど、今回はTypeScriptで.tsxを書いてts-loaderでトランスパイル、という感じでやってみた。 型が付くと分かりやすく書きやすい、んだけど なかなか慣れなくて思った以上に苦戦した…

で、とりあえず最低限動くところまで出来たので公開したのがこちら。

これくらいならHerokuで動かせるかと思ったけど、いざdeployしてみたところ “Memory quota exceeded” のエラーが出まくってしまって、どうもメモリの使用量がヤバいらしい…。 いちおう動くことは動くけど、いつ止まってしまってもおかしくない、という感じ。 畳み込み4層の識別モデルくらいなら大丈夫だったけど これくらいの規模だと厳しいか、、、

Herokuでメモリ多めのdynoにアップグレードすると$25くらいかかるみたいだし、それだったらどこかのVPSで2GBくらいあるやつを借りた方がいいか…? 真面目に運用することになったら考えよう。。

Repository