2015年6月15日月曜日

自作裁縫システムについて

現在ふと思い立って裁縫システムを作ってます.
現状はPython3でかたりべのぼうし(ただし虹布非対応)まで縫えるようになったところなのですが,スピードの限界を感じてC++で書き直そうとしてます.
Cythonとか使ってみてもよかったかなあと思いつつ,よくわからなかったので….
ここまでのまとめをしてみます.

評価関数

TD-Learningを用いて機械学習をした.
特徴量を「任意の2箇所の値の組み合わせ(順不同),int(残り集中力/7),現在のシフト」として,次の式で学習を行った.
V(s_t) = V(s_t) + \alpha(r + \gamma V(s_{t+1}) - V(s_t))
ここで,報酬rは大成功時1000/考えられる特徴の数,それ以外は0とした.
実際の評価値は,仕上げれば大成功な局面では1000,それ以外の局面ではmax(0,特徴量ごとの評価の和)とした.
実際この特徴量がどの程度適切なのかは不明で,頭で残り集中0,数値が10,0,0,0という局面になると絶対に大成功しないにもかかわらず{0,0}の組が3通り,{10,0}の組が3通りとなるためにそれなりの評価値がついてしまうというような問題はあります.
次元をなるべく上げずにこの問題に対処できるような評価値を見つけたいんだけど,なかなか簡単ではないです.

探索

期待値ベースでオーソドックスに木探索してます.
深さ0の探索は現在の局面に対してそれっぽい手を全部やってみて,評価値の期待値が一番高い手を指す,深さ1幅dの探索は深さ0の探索で求まった上位d個の指し手から得られる全局面について,深さ0の探索を行いその結果で評価値を更新しその中で一番評価値の高い手を指すって感じです.
こちらの問題点は枝刈りの方法があまりうまく考えられていない点です.
深く読ませても幅が小さくならないので,必要な時間が深さに対して底がけっこう大きい指数オーダーで増えていってしまいます.
期待値ベースで探索しているのでα枝刈りみたいなことが出来ないのがつらいです.
何気に時間がかかっているのが,水平ぬいなどの縫う箇所が多い特技の局面生成です.
水平ぬいはダメージを与える対象が3箇所あり,それぞれについて14通りのダメージが発生するので,それだけで14^3=2744通りの局面が発生することになります.
水平ぬいを連打出来るような状況で深く読むのが計算量的に難しい原因です.
水平ぬいを2回使うことを考えるだけで,1回目の水平ぬいで発生した2744通りの局面それぞれについてもう1度水平ぬいを適用し(合計14^6通りの局面が生成される),発生した局面の評価値をすべて計算してやっと水平ぬい2連打の評価が求まります.

現状の成果

(集中力が減ってきたり,0になった場所が増えてきた)終盤は手が狭いのでかなり深く読むことが出来ます.
終盤の局面であれば何もできなくなるまでのほぼすべての局面を読み切り,大成功率の根拠付きで手を推薦することができます.
まれに人間には思いつかないような手筋が最善として推薦されることがあり,これはひとつの成果になっていると感じます.
最初から終盤の「皮のぼうし」(さいほうシミュレータで誤差2まで許されていたので誤差2オッケーとしてます)の銀針★3での大成功率は43/60と7割を上回っており,これは人間にとっては容易ではないです.

今後の展開

とりあえずC++への移植を目指します.
現在困っているのは,
  • PythonでいうところのPickle(C++的にはboost::serialization?)の使い方がよくわからず,学習した評価値を外部に保存できない
  • タイムアウト付きの複数コア対応(1手5秒で指して欲しいという状況で,時間切れで探索を打ち切ってほしい)
あたりです.
特に前者の学習した結果が保存できないのは切実な問題で,これを解決しないと学習が開始できなくてつらいです.
C++に自信ニキがいたら教えてください.