GA将？開発日記～王理のその先へ～

ネタ勢最強を目指して絶賛開発中。

講演会のメモ

コンピュータ将棋

http://minerva.cs.uec.ac.jp/~ito/entcog/contents/lecture/date/20080614.html

発表の資料は上記URLからダウンロード出来る様なので、そちらをご覧下さい。

ここの内容は個人的なメモですので、私が興味のある事に片寄ってます。

それから、頭に※印のある項目は私の感想とかそんな感じです。

「コンピュータ囲碁におけるモンテカルロ法」（理論編）美添 一樹さん

  • 「Monte Carlo Tree Search」が手法を提案した人の呼称。暫定的に「モンテカルロ木探索」と和訳。
  • UCT登場以前は相手の応手を正しく認識出来なかったのが、UCTで認識可能になった。
  • プレイアウトのスコアを石差から勝敗に変更するとGNU Go相手の勝率が3割から6割にアップした。
    • ※「リスクはあるが大差を付けて勝てる可能性のある手」を選ばなくなった？
  • n本腕バンディッと問題の最適戦略を実用的な処理時間・メモリ量で近似するのがUCB1
  • UCB1値の係数c（発表資料のP.32参照）は、プレイアウトのスコアの値域が0〜1の場合は、理論上は1にするのが最適。
  • AMAF(All Moves As First)という手法の紹介あり。
    • プレイアウト中に出現した全ての手を、ルートノードで指した手と見なす。
      • ※囲碁では有効だとしても、将棋での有効性は不明。ひょっとしたら手の間に依存関係みたいなものがあると上手く行かないかも。
  • General Game（大会の会場に行くまでゲームのルールが不明）でもUCTは有効。
  • UCTは細く（良い手が少なく）深い手順が苦手。
    • 手順の末端まで木が成長しないので。
  • 一部の良さそうな手に絞ったプレイアウトよりも、盤面全体の手を試す様なプレイアウトの方が、最終的な強さは上。
    • ※プレイアウトに必要なのは（プレイアウトの）強さではなく、正確な局面評価の為の情報？

「コンピュータ囲碁におけるモンテカルロ法」（実戦編）山下 宏さん

  • 当りにされた石が逃げる確率は、当たった瞬間だけ上げている。
  • どんな手であっても打つ確率は0にはせず、0.001%等の極めて低い確率にする方が強くなる。
    • ※強化学習でのε-greedy方策みたいな考え方？
  • 連のデータ構造の更新がプレイアウト中のかなりの負荷になっている。
  • UCB1値の係数α*2は実験で決めた。
  • UCB1の式で、logの底は自然対数e*3。

「５五将棋における評価関数の自動学習」柿木 義一さん

私が意見するなんて100年早いと思いますが、あえて色々書かせて貰います。

  • GPW終了日から2週間で作った。
    • ※学習に7〜10日かけているらしいので、実際の開発期間は1週間弱？
  • 評価関数でPINや手番も特徴に追加している。
  • Bonanza登場以前から学習にトライされていて、パラメータは学習で調整すべきと考えている。
    • ※古参のコンピュータ将棋開発者としては珍しいかも。
  • 王将との相対位置のパラメータは0で、それ以外は柿木将棋の値で初期化。
    • ※学習前後で強さの比較をしていない事を考えると、元々強かった可能性もある？
  • 学習時は探索深さ・制限時間を変えたりする事で棋譜にバリエーションを与える。
  • 今回は学習時に乱数は使用していない。
    • ※強化学習をやっている身としてはこれは意外。greedy方策ってあんまり良くないと思ってました。
  • 過去の探索結果を元にした自動悪手修正機能あり。
    • 柿木将棋にも実装されている。
      • ※TD(λ)なら似た効果が期待出来るので、私が実装するかどうかは要検討。
  • 学習時の探索関連・評価関数のパラメータは先後共通。
  • 学習期間は1週間〜10日。491局。
  • 学習時の棋譜は1局ごとに捨てるのではなく、蓄積しておいて後でも利用する。
  • ※後手１一玉に対する先手角のパラメータで、出現頻度が低い事による悪影響らしきものあり。５五（先手玉の初期位置）のパラメータが低い値になっている。
  • ※複数のパラメータが同時に大きく変化しはじめる減少あり。発表資料P.12。
    • 棋譜を蓄積している事による影響らしい。
  • 学習の大まかな考え方は、対局時に深く読んで選んだ最前手を、1手＋静止探索でも最前手になる様にする事。
    • ※勝った時の手はまた同じ手を指す様に、敗けた時は別の手を指す様にすると思っていたので、意外でした。
  • 金銀が中央に向かうパラメータは、一度値が高くなると対局時に中央に向かう頻度が高くなり、さらに値が高くなる。
    • ※あえて端に向かう手も時々は指した方が良いんじゃないか、と思ったり思わなかったり。良く分からないです。
  • 学習前後での強さの比較はしていない。
    • ※柿木さんご本人も、この点は気にされていた様子。

*1:実際にはモンテカルロ木探索と（強化学習の文脈での）モンテカルロは同じものなのかもしれませんが、まだ二者の関係をはっきりと理解出来ていないので…

*2:上で書いたcとほぼ同じもの

*3:そんな事すら私は知りませんでした…