フダンの記録 このページをアンテナに追加

2011-11-23

[][][]モンテカルロ木探索将棋プログラムmcts の解説など 13:20 モンテカルロ木探索将棋プログラムmcts の解説などを含むブックマーク

1年経った今更、floodgate に参加していたmcts*1 について解説。今年のGPW でも、激指でこの手法を使った研究がありました*2

まずは3行で。

  • 評価関数を信用してプレイアウトを打ち切ると得できるのでは
  • 将棋向けに工夫しながら、GPS 将棋を使って実験した
  • 従来のMCTS 将棋よりも強くなったが、アルファベータには敵わない

こんなところ?あとはポスター見るのが早いと思う。

以下、2010年の11月にゲームプログラミングワークショップ (GPW2010) でポスター発表した内容を紹介。

floodgate にいたmcts はこの内容に基づいて作成し、その後工夫を加えたプログラムで、マシンのCPUは、Intel(R) Core(TM)2 Quad CPU Q9650 @ 3.00GHz で1コアだけ使っての参加、並列化していない。

概要

前提

以下の知識は知っているものとして説明しない。

資料

GPW2010 の予稿と発表したポスターは以下からダウンロードできる。

プログラムの中身

OSL とGPS 将棋を利用して作成した。

今回の実装において使った手法パラメータは、ゲーム木探索部分とモンテカルロ部分とでそれぞれ以下のとおり。

  • ゲーム木探索部分
    • UCT (UCB1)
    • 1手詰関数
    • MCTS Solver[4] (MCTS において詰みを扱う)
    • ノードを作る訪問回数の閾値 : 1
    • Progressive Bias (手の選択の際に、実現確率に応じて重み付けする)
    • First Play Urgency : 0.9
  • プレイアウト部分 (モンテカルロ部分)
    • 1手詰関数
    • 実現確率上位5手からランダムに選択
    • 評価関数/静止探索ベースの勝敗判定 (ここが肝)

先行研究

MCTS 将棋

MCTS将棋へと応用した内容を、棋理の開発者佐藤さんが発表している[5][6]。様々な工夫があるが、本研究ではプレイアウト部分の改良がメインであったこともあり、当時は採用していなかった。

    • ゲーム木探索部分で静止探索を行い、評価が悪くなる手の勝率を下げる
    • Killer-Move, History Heuristic
評価関数の利用

Amazons, Lines of Action (LOA) では、評価関数を用いたMCTS が成功しており、それぞれアルファベータを上回るか同程度の結果を得ている。 (Arimaa でも行われたがあまり成功していない) 。

Amazons, LOA で成功した手法は、評価関数が正確という前提のもと、プレイアウトの勝敗判定に評価関数を利用する手法

違いはその判定の仕方、評価関数の使い方であり、それぞれ

  • LOA (EF-Cutoff @ ポスター)
    • 評価値が勝ちの点数以上ならそのプレイアウトは勝ちとする
      • 負けの点数以下なら負け
  • Amazons (EF-Leaf @ ポスター)
    • ある深さまでプレイアウトして、そこでの評価値/評価値の正負を返す

となっている。

なお、LOA ではプレイアウトの指し手の選択にも評価関数を使っているが、今回は省く*3。詳細は文献[1]を参照。

提案手法など

まず、従来のMCTS 将棋における問題点を考える。

  • 従来手法の問題点
    1. 探索が必要な局面は不得意
    2. 優勢な局面において最善手を逃す傾向/緩い手を選びがちになる
    3. プレイアウトが終局しにくい

評価関数の利用で問題点3 は改善する見込みなので、残りの問題点を解決するように以下の手法を提案した。

  • 静止探索の利用
    • 問題点1 に対応
    • 評価値を将棋で使う以上、静止探索の利用は自然な発想
    • 探索コストがかかるため、採用すべきかは自明ではない
  • ルート局面の評価値との差を利用
    • 問題点2に対応
    • ルート局面と評価値を比較することで、ルート局面よりも良くなる手を選ぶようになることが期待される

両方をEF-Leaf, EF-Cutoff に採用した手法が、ポスターの提案手法 (4,5) が該当し、それぞれQS-Leaf-Diff, QS-Cutoff-Diff と呼ぶ。

実験

実装し、実験した。問題集の正答数の比較や自己対戦によって性能評価を行った。

自己対戦のまとめ

が確認された。

静止探索の利用は探索コストと評価値の正確さのトレードオフがあるが、メリットが上回ったと思われる。

レーティング

QS-Cutoff-Difffloodgate に投入し、レーティングを計測した (~2010/9/12)。

2週間レーティングは1821 となった (当時のMCTS将棋プログラムでは最高のレーティングのはず) 。

主要な対戦成績

  • YSS-1S (レーティング(以下Rと表記) 2008) : 19勝33敗
  • gps_normal (R 2150) : 5勝22敗
  • Blunder (R 2378) : 1勝13敗

ただし、同じ評価関数を使っているgps_l はレーティング 2464 であり、従来のアルファベータ探索を行うプログラムには及んでいない。

まとめ

参考文献

[1] Winands Mark H. Bj\"{o}rnsson Yngvi, "Evaluation Function Based Monte-Carlo LOA", Advances in Computer Games 2009

[2] Julien Kloetzer, Hiroyuki Iida, Bruno Bouzy, "The Monte-Carlo Approach in Amazons", Computer Game Workshop 2007

[3] Lorentz Richard J., "Amazons Discover Monte-Carlo", Computers and Games 2008

[4] Winands Mark H., Bj\"{o}rnsson Yngvi, Saito Jahn-Takeshi, "Monte-Carlo Tree Search Solver", Computers and Games 2008

[5] 佐藤 佳州, 高橋 大介,"モンテカルロ木探索によるコンピュータ将棋",13回ゲームプログラミング ワークショップ

[6] Y. Sato, D. Takahashi, and R. Grimbergen: A Shogi Program Based on Monte-Carlo Tree Search, ICGA Journal, Vol.33, No.2, pp.80--92 (2010).

-----

GPW 後の進捗など

  • 自己対戦数を増やした
  • パラメータを多少調整
  • [5][6] の手法の採用
    • ゲーム木探索パートで静止探索
    • Killer-Move, History Heuristic など
  • ルート付近で詰将棋探索
    • 訪問回数が閾値を超えたら軽く呼ぶとか

Misc

  • 評価関数に静止探索まで使ってモンテカルロと呼べるのか
    • 先人がそう呼んでいるし、プレイアウトは行なっているし、良いのでは?
  • プレイアウトしないで評価関数なり静止探索すれば良いのでは
    • 当時、実験したが、深さ2までプレイアウトする方が強かった
  • 読みにくい
    • そんな人のために3行を用意しました。あとはポスター見れば良いと思う

mcts のデータ

mcts (プログラム) のデータを調べたら2011/06/14 までfloodgate にいたらしい。

  • 1手3秒だかで、Bonanza Feliz と100戦した結果: 2勝98敗

Todo

明日から本気出(ry

*1:名前は真面目に考えてつけるべき

*2http://id.nii.ac.jp/1001/00078263/

*3:実装してみたけど、手を進めて戻す必要があるので重い。SEE で代用してみたが振るわず

*4Index of /shogi/LATEST/rating に日付ごとのレーティングが保存されています、便利ですね