WCSC2016 March アピール文章(真)
2016/5/3 大渡　勝己 (Katsuki Ohto)

下方の***以下が前のアピール文章になりますが、結果的にこの目標の0.1%程度のことしか
出来なかったため、上に追記することにしました。
斬新なプログラムを期待されていた方、私の力と時間が足りず申し訳ございませんでした。

アピール文章の時点では以下のようなプログラム製作を考えていました。
①条件分岐を含む探索的行動のモデルを実際に動かす
②出力（着手）に対して以下のA, Bいずれかの学習をかける
 A.出力着手を教師の着手によって教師あり学習
 B.実際に出力着手を使って試合を行い、強化学習

実際に単純に上記の学習を回しても、関数の形や時間的に上手く進む気はしませんが、
それでも実行はできるだろう…と思っていました。

しかし大きな問題として、探索のような複雑かつリカレントなモデルに対して自動微分するライブラリを、
現実的にchainer等の高級言語系でしか知らないという問題があり、
仮に探索部をpythonで書いたとすると、
やねうら王ライブラリの着手生成,評価（c++）と 探索(python)との間を行き来することになり、
実装が大変という問題がありました。
私が1から学習を書くことも短時間では不可能のため、結果的に計画はすぐに頓挫しました。

そのため学習も、ニューラルネットも諦め、簡単に実装可能な部分としては、
「ゲーム木上のノードを自由に移動できる」
という根本部分だけだったので、
その部分だけ忠実に再現し、実際に自由に移動させてみました。
さらにゲーム木探索の核となるminimax性については、
すぐにどうにもならないので、木の前提条件として使用しました。
（この条件でも、探索を学習するというモデルとしては成立し得る）

さらに、いじる予定のなかったはずの局面表現・進行部分にバグが生まれ、
局面進行でおかしな次局面を生成することがあったため、
局面を2回進行することができなくなってしまったので、
落ちずに動かすには、どう頑張っても１手読みしかできないような状況でした。
（さらに最初の方は必ず反則になってしまっていた）
結局、時間→∞で1手読みに結果が収束するだけのプログラムでした。

最初から奇をてらった計画をたてた場合には、
それを実現することに確固たる目的が必要で、
なかなかそれは得られるものではないので、成功は難しいということですね。

アピール文章に書いて独自性を狙うためのアイデアだったので、
今回の計画を今後特に頑張って実装するつもりはありません。

探索アルゴリズムの自動生成・習得に趣味がある方は、
より良いアイデアを実現していただけますと幸いです。

***

Marchのコンセプトは以下に尽きます。

「探索コードを書かずにコンピュータが自動で探索を習得する」

コンピュータ将棋においては高度な探索手法が発展してきました。
これは人間の叡智の結晶です。

一方で、こういった高度なアルゴリズムをコンピュータ自身が獲得することも
人工知能の大きな目標と言えるのではないでしょうか。

Marchではニューラルネットによってこの課題に向き合いたいと思います。

具体的なアイデアはいくつかあるのですが、
現時点では製作は1行も進んでいないので、完成に近そうな方針が定まり次第こちらの文章もアップデートしていく予定です。

また、今回は探索をメインテーマとしているため、
ユーティリティ(と場合によっては評価部分)には
やねうら王ライブラリを使用させていただこうと考えています。

4月になったら頑張ります。

4/19追記

「探索をネットワークに学習させる」とは
Marchでは具体的に、以下の内容とします。

まず「探索」の、ゲーム木を前提にした上での定義は、

①「ある主体がゲーム木上を移動し、訪れたノードの内部状態ベクトルと
自分自身の内部状態ベクトルを更新する」
②「一定条件を満たした際には、主体の移動経路をルートノードまでの逆行に制限し、
主体の内部状態の中の特定の要素値を結果として返す」

としました。

②は、アルゴリズムの終了を保証する条件になり、メインは①です。

この時行動決定が必要になる点は、
A.自分自身の内部状態ベクトルの更新
B.主体が現在位置しているノードの内部状態ベクトルの更新
C.ゲーム木上での移動方向(可能な着手数+1)

です。出来れば全てをまとめて1つのネットワークで表現したいのですが、
A,Bにおいては以下の操作

if value(now) > best_value
    best_move = now
    best_value = value(now)

の表現が難しく、
Cは移動可能なノードの数が可変のため、
答えとしてどういったものを出力するのかが課題です。

遠い理想は、反復進化アルファベータ探索らしきものを学習することです。
現実的な目標としては評価関数による1手読み相当のことが出来れば万々歳ですが、
よほど高性能なネットワークが出来ない限りランダム着手の範疇を超えるとは思えないので、
一次予選最下位を恐れている方は、私が出場にこぎつけられるよう
応援メッセージを送るのが良いと思われます。