囲碁の思考ルーチン作成に挑戦
今から半年位かけて、囲碁の思考ルーチンを書くことにしました。
１回目は１年半ほど前に、盤面認識プログラムと簡単な探索を実装しただけで投げちゃったんですよね...これは２回目の挑戦です。
以前よりもコードも書けるようになったこと、英語のドキュメントや論文を読むのにためらいがなくなったこと、機械学習を研究室で専攻したことなどが重なって、なんか書けそうな気がしたので、学生のうちに頑張ってみますよ。
とりあえず、今後１ヶ月はじっくり思考ルーチンのインターフェースや、簡単な実装方法について考えてみようと思います。GNUGOのソースも今読んでるんですが、なんかしっくりこないんですよね。ソースだけを見たら、どうも人間と同じ思考の過程を経ることは難しいのかなと感じます。
目標としては、以下の３つ
実装するだけなら、最初の２つはいける気がするんですよね。最後の条件は、いつだかプロ棋士の武宮九段が言っていた記憶があるのと、強いよりも個性のあるプログラムが作りたいなという希望です（実現するかは謎）。あくまで優先であって、無視ではないです。
言語はC++です。Cでも良かったのですが、ライブラリの恩恵を受けられるかなぁと。GUI周りはpythonがいいかなと思うので、pythonで書きます。ついでに飽きたら使いやすい棋譜ビューアも作ろうかなと思います。前から全部キーボード操作(emacs風)できるものが欲しいと思っていたので。
"Monte-Carlo tree search and rapid action value estimation in computer Go"
MCTSは、囲碁における次の手を求めるために有効なアルゴリズムである。MCTSでは、手の有望性を確認するために、その手を打った後にランダムにシミュレーションを行う。そのシミュレーションの勝率が高いほど、良い手であると判断される。
その際、どのようにシミュレーションを行うべき盤面を決定するかが問題となるが、UCTという基準を用いると、シミュレーション回数を無限にすれば最善手が求まることが理論的に保証されている。UCTは、平均勝率が高く、シミュレーション回数が少ない手を優先的に選ぶ。この論文は、平均勝率以外にもシミュレーションする盤面を選ぶ方法を提案している。
アイディアとして、囲碁では手順に（ある程度）関係なくいい手というものが存在することが仮定となっている。盤面sから打つ着手aの価値を判断する方法として、それまでのシミュレーションで盤面sを経由して（直後でなくても）aにたどり着いたようなケースの勝率を考えている。
ただし、単独では良い基準とならない（仮定が常に成立するとは限らないため）ので、UCTとの重み付き線形和を最大にするような手を選択する手法を提案している。
"A Lock-Free Multitheaded Monte-Carlo Tree Search Algorithm"
概要：
マルチスレッドでモンテカルロ木探索(MCTS)を効率良く行う方法
MCTSのマルチスレッド版がある。アルゴリズムは、全スレッド共通の木が一つあり、シミュレーションを各スレッドが行う。そしてシミュレーションの結果を１回ごとに共通の木に反映させる、といったもの。
問題点は、このアルゴリズムではスレッド数が増えても勝率が上がらないような場合が経験上存在していた（らしい）。
直感的には、スレッド数とシミュレーション回数が比例せず、その理由が、共通の木にアクセスする際の排他制御が遅いからだとは思うが、明記はされてなかった。
そこで、排他制御をなくしたMCTSを提案している。変更点は、スレッドごとにシミュレーションする盤面を決定した後、複数回シミュレーションを繰り返し、排他制御しないで結果を親にリンクさせるという単純なもの。その際、２つのスレッドが同一盤面をシミュレーションしていたら情報が失われる可能性はあるが、著者曰く経験上大丈夫らしい。
結果として勝率は良くなっているんだけど、シミュレーション回数がどれだけスレッド数に対してスケールしてるかや、排他制御を無視したことでどれだけ情報が失われたかなどは計測していなかったのが非常に残念。
また、Fuegoを拡張してC++で書いているらしいけど、シミュレーションが19x19の盤で2750回/秒・コアできるらしい。結構思ったより高速なので、春休みにプログラム覗いてみたいなーと思う。
「実数値GAのための正規分布交叉の多数の親を用いた拡張法の提案」
概要：
UNDXの拡張
GAの世代交代に関する設計指針の一部に、
-
- 世代交代時に統計量（集団の平均、分散）を保持する
- 1を満たした上で、子の多様性を保つ
というものがある。
UNDXという交叉オペレータは、良い性能を示す。これは、１を満たすことが理論的に保証されていることが大きいと考えられている。しかし、２を満たしていないことがわかっており、UNDXを拡張して２も満たすようにすることで、より性能が良くなる可能性がある。
改良点としては、UNDXは良い関数の入力分布を推定するために親の遺伝子を3個使ってるけど、提案法ではm個使ってみましたという話。
「単峰性正規分布交叉UNDXを用いた実数値GAによる関数最適化」他2本
今日読んだ論文3本のまとめです。
「単峰性正規分布交叉UNDXを用いた実数値GAによる関数最適化」
概要：
子を生成するための方法の改良
子を生成する手法として、BLX-αが有力だった。BLX-αでは、親の遺伝子群からランダムに２つ選択し、２つの遺伝子を取り囲む超立方体から子をランダムサンプリングする。
しかし、入力変数間に強い依存性がある場合はうまく行かないことがわかっている。
そこで、超直方体ではなく親の３遺伝子から正規分布を推定し、それを元に乱数を生成する手法を提案した。
実験的に、変数間に強い依存性がある場合に有効であると確認された。
「Saving MGG: 実数値GA/MGGにおける適応度評価回数の削減」
概要：
世代交代モデルの改良
MGGは、遺伝子の多様性を保ったまま探索するための、世代交代モデルである。
子の生成には、UNDXを拡張したUNDX-mやSPXを用いると、変数間の強い依存がある場合でも、変数におけるスケールがかなり異なる場合でも有効である。
しかし、遺伝子の多様性を維持するために、多くの子供を生成し、より多くの遺伝子群を保持する必要がある。そのため、適応度の計算回数が膨大になってしまう。
そのため、適応度を用いた重み付きサンプリングで正規分布を推定し、その分布でよさそうな子を特定する（正規分布の中央ほど良い個体）。それで良さそうな子だけ適応度を計算することで適応度計算の回数を減らす。
実験的に、適応度計算が減らせることを確認している。
この論文に関しては、いくつか疑問があったので列挙すると、
-
- MGGでは適応度の多様性を重視していたのに、適応度で重み付きサンプリングしたら多様性が無くなる気がする。
- 生成した子と、よさそうな子の比がさほど大きくないので、計算回数を減らす効果が薄い気がする。
- そもそも、適応度の計算ってコスト高いのだろうか。
「GAの探索におけるUV現象とUV構造仮説」
概要：
GAの働きを説明する仮説
GAで探索する関数の中には、大雑把に関数の形を見ると、大きな谷がいくつか存在するような形が存在し（大域的多峰）、各谷底には局所解or最適解がある。このような大域的多峰な関数でGAが上手く働かない現象を、UV現象と名付け、３つのモデルに分類している。
-
- 大域的最適解を持つ谷が、多数の細かい局所最適解をもつ
- 局所最適解を持つ谷が、探索の初期段階で最適化しやすい
- 局所最適解を持つ谷が、大域的最適解を持つ谷と比べて非常に広い
実験的に、最適解を求めるのが難しい原因を、この３つのモデルで説明している。
「遺伝的アルゴリズムにおける世代交代モデルの提案と評価」
今日読んだ論文は、「遺伝的アルゴリズムにおける世代交代モデルの提案と評価」
自分なりに解釈してまとめたので、多少間違ってるかも。
概要：
遺伝子の世代交代モデルと、手法の評価方法の提案
遺伝的アルゴリズムだと遺伝子は最適化する関数の入力を表す。遺伝子に関して探索中に気をつけることが２つある。
-
- 探索の初期段階に遺伝子があまりに高速に収束してしまうこと。
- 適応度の数値的差異がほとんどなくなること。
１の理由は、遺伝子が変化しないから探索が進まなくなるため。
２の理由は、基本的に残す遺伝子を適応度で選んでいるため、最も有力な遺伝子が選ばれにくくなる恐れがあるため。
これらを改善するためには、世代間で適応度の分散をできるだけ維持して選択するのが望ましいと思われる。この論文では、ルーレット選択と最良選択を組み合わせて、分散維持を試みたMGGを提案している。
また、手法の評価方法に関して。従来は、最適解への収束速度を測定していたけど、適応度が多様な方が望ましいなら、多様性を測定すべき。ということで、適応度の最良値と分散、世代交代した回数を同時にグラフにし、考察している。
ブログ始めます
趣味と研究に関するモチベーション維持のために始めました。
しばらくは、論文をまとめるような記事ばっかりになるかと思います。
