Qhapaq Lab

業務連絡

  • まだ書きかけですし、間違いも多いと思うので積極的に加筆修正してください。(兵頭_AI-AN,Ari)

概要

コンピュータ将棋における探索とは、人間が行う「先読み」をコンピュータに行わせるための技術(のグループ)のことである。

前提知識

  • 二人ゼロ和有限確定完全情報ゲームの概要
  • コンピュータ将棋の基本的な用語
  • ゲーム木の概要
  • 将棋のルール

キホンのキ

minimax法

  • 雑な説明: 「先手は先手の評価値が最大になるように手を選び、後手は先手の評価値が最小になるように手を選ぶ」という考えに基づいて行う探索

  • 以下のルールでノードの評価値を決定する。

1: ノードが木の末端にある(終局しているか、評価関数を呼ぶ位置にある)場合は勝敗や評価関数でノードの評価値を決める 
2: (評価値がすべてルートノードの手番視点とした場合)ノードの手番がルートノードの手番と同じなら、子ノードの評価値の中で最大のものをそのノードの評価値にする
3: ノードの手番がルートノードの手番と異なるなら、子ノードの評価値の中で最小のものをそのノードの評価値にする

  • 例えば、ノードXの子ノードの先手から見た評価値がそれぞれ[A: 10, B: 20, C: -40, D: -1000]だった場合、 ノードXが先手番なら子ノードの(先手番から見た)評価値の中で最も高い20を評価値にし、 そのノードが後手番なら子ノードの(先手番から見た)評価値の中で最も低い-1000を評価値にする。

  • minimax法ベースの探索部を持つソフトは多い。

アルファベータ法

  • 一言で説明: 「minimax法の改良版」
  • "調べるべき範囲"を"アルファ"と"ベータ"という変数で表す。アルファ < ベータのいう関係で、調べるべき範囲はアルファとベータの間である。
  • 探索した後の評価値が"調べるべき範囲"の外にあった場合は探索を打ち切ることができる。
  • どれくらい枝刈りが起こるかは手を調べる順番で決まる。有望な手を先に調べるほど多く枝刈りが起こる。
  • 条件が同じであればminimax法と同じ答えを返す。
  • ここの解説は雑すぎるので、電竜戦のYouTubeチャンネルで公開されているアルファベータ探索超入門という動画の視聴をお勧めする。

原始モンテカルロ探索

  • 評価関数が要らない探索手法。
  • モンテカルロはランダムという意味だと思っていい。
  • ランダムシミュレーション(終局までランダムに行動する)を何回も行い、その結果で局面の評価値を推定する。
  • ランダムシミュレーションの事を専門用語で「プレイアウト」または「ロールアウト」という。
  • プレイアウトでの行動選択を工夫するだけでも精度が上がると言われている。

モンテカルロ木探索(MCTS)

  • 原始モンテカルロ探索の改良版。
  • 原始モンテカルロ探索と木探索を融合させた手法。
  • 精度の高い評価関数を作るのが困難だったコンピュータ囲碁で開発された。

キホンのホ

置換表

  • 一言で説明:ハッシュ値とそれに対応する局面での探索結果の値、最善手などを記憶する表

反復深化

  • minimax系の探索部の技術。
  • ある深さまで探索する際に一気にその深さまで探索するのではなく、徐々に深くする手法。
  • 前述の置換表で記憶している、浅い探索の時の最善手から調べることで枝刈りが起きる頻度を上げることができる。

move ordering

  • minimax系探索部の技術。
  • 手を調べる順番を工夫することで枝刈りを多く発生させる。
  • 前述の置換表を使った方法だけでなく、一般的に良い事が多い手(将棋やチェスだと駒を取る手など、オセロだと四隅に打つ手など)を先に調べる方法などもある。
  • 探索開始局面(ルート局面)に近い局面では処理が重い代わりに精度が高い方法で、 遠い局面では軽い代わりに精度が低い方法で並び替える、 という方法もある。

  • ざっくりした説明: アルファベータ法のアルファとベータの間のことを"探索窓"と呼び、この探索窓を0してから探索を行う。minimax値が探索窓の上にあるのか下にあるのかを高速に求めることができる。

  • move orderingがしっかりしていれば多くの枝刈りを行う事ができるが、move orderingの精度が悪いと後述の再探索を多く行う事になるため逆に効率が落ちる事がある。

  • 探索の結果、厳密な評価値を求める必要がある事が分かった場合は通常の探索を行って厳密な評価値を求める。

静止探索

  • ざっくりした説明: 駒がぶつかり合っている局面を正確に評価するのは難しいので、駒の取り合いなどが終わった静かな局面まで進めてから評価する手法の事。

  • 静止探索では通常、全ての指し手を調べるのではなく、駒を取る手・王手がかかる手・(王手されている場合は)王手を回避する手などのみを調べる。

キホンのン

PV-MCTS

  • まだ

並列化

  • まだ

小テクニック集

  • ある合法手が駒を取る手かどうかは、その手で駒が移動する先に別の駒があるかどうかで判定できる。(味方の駒がいるマスには移動できない & 敵駒がいるマスに移動すればその敵駒を取ることができるため)

  • minimax法などは関数の再帰呼び出し(自分自身を呼び出すこと)で簡単に実装できる。

  • 「ランダムプレーヤーによるプレイアウト、泥沼の戦いになって全然終わらない問題」は1 ~ 3手詰めルーチンを入れるだけでかなりマシになる。

  • 探索の途中でも時間が切れたら適当な値を返してすぐに打ち切るようにすれば時間切れ負けはかなり減る。

その他

  • 探索部のデバッグをする際は駒得評価関数を使うことをお勧めする。

  • コンピュータチェス・コンピュータオセロ・コンピュータ囲碁などの文献も参考になるものが多いので、時間があったら読んでみよう。(特にチェス)。

  • 強いソフトのソースコードを読んで技術をパクろう。自分のソフトを簡単に強くできるし、何より勉強になる。

参考にした・する予定のリンク集