Skip to content

ゲーム木探索

ゲームの分類

  • 0人ゲーム/1人ゲーム/2人ゲーム/多人数ゲーム
    • ゲームの参加者数による分類
  • 完全情報/不完全情報
    • 局面(盤面、状態)がすべてプレイヤーに見えているか、そうでないか
      • トランプなどは、手札を公開しない場合は、相手の手札の情報がわからないため不完全情報
  • 確定/非確定
    • 着手以外の確率的に不確定な要素があるかどうか
      • すごろくなどは、状態遷移がサイコロに依存して決まるため非確定的
  • ゼロ和/非ゼロ和
    • ゲームの結果が、勝ちを+1、負けを-1、引き分けを0などにしたとき、合計が0となるためゼロ和ゲーム
    • 3人以上でのじゃんけん、など

ゲーム木

  • 局面(盤面、状態)をノード、着手(合法手)をエッジとした有向グラフ
  • 局面を、経路が違った場合にすべて区別すれば、これは初期局面をルートノードとした木になる
    • 最終局面はリーフノード
  • すべて展開できればよいが、通常、ノード数が膨大なため現実的には難しい
    • そのため、着手の良さや局面の評価、探索手法などの工夫が必要
  • また、「ゲーム木」として考えてしまうと、探索方法が限られてしまう
    • 状態に局所性があるなら、部分破壊再構築などできる可能性があり、近傍として局所探索/焼きなまし法など検討できる可能性がある

合流/重複局面

  • 異なる着手列から同じ局面(重複局面)に至ること
  • 合流を考慮する場合、その直前の局面の評価値が違ったりするため、訪問回数などを伝播させるときなど注意が必要
  • 局面の重複検知は、Zobrist hashなど
  • (合流が多いというのは、着手列よりも状態に注目できる＝文脈があまりない、可能性がある)

ゲームAI設計のアプローチ

  • いくつかアプローチがあり、また、それらの組み合わせやハイブリッドなものなどが考えられる

ルールベースアプローチ

  • 人間が経験的知識をトップダウン的にルールで記述していく方法
  • 改良や変更を入れやすい一方、記述する人間のゲームの習熟レベルの問題、記述量が膨大でカバーしきれない、例外規則が大量に発生する、各ルール間の整合性・優先順位が難しいなど問題がある
  • 問題によっては強力なルールベースの解法があったり、ある程度までは対応できる可能性はあるが、ルールが複雑化するほど上記の問題から改善が困難になっていく恐れがある

探索ベースアプローチ

  • ゲーム木を形成、および、評価関数を設定することで、各状態で評価の高い手をボトムアップに決定してく方法
    • N手目までのBFS/DFS、貪欲法、ビームサーチ、chokudaiサーチ、など
  • 枠組みに載せられれば強い一方、評価関数設計が難しいケースや、合法手や状態数が膨大になるケースでは適用が難しい問題がある

モンテカルロアプローチ

  • 評価関数設計が難しい、正確ではない、不確定要素(確率要素)が入るような場合、探索した評価値があまり信用できなかったり、評価値を出すのが困難な可能性がある
  • そこで、多くの乱数でのシミュレーションによって評価関数の近似値を求めてそれを用いる
  • 例: 原始モンテカルロ
    • ランダムな手などで最後までプレイすること(プレイアウト)を繰り返し、勝率(=評価値)の近似値を求める
    • さらなる改善として、モンテカルロ木探索、Thunderサーチ、など
      • プレイアウトの質を高める
      • UCBなどで評価が高い可能性のある手へ多く計算資源を割り当てる
      • など

学習ベースアプローチ

  • 評価関数のパラメータを教師データで教師あり学習したり、強化学習の手法を使った行動の最適化などの方法
  • データや試行回数が大量に必要だったり、うまく学習させるのが難しかったり、調整などが難しい問題がある

playout

  • 「(最初から、または、途中の手から)最後まで手を進める」こと
  • 「playout回数」は、playoutを行った回数のこと
  • ゲーム木探索などでは、playoutによって、複数の解を生成したり、手の良さの評価に用いたりする
  • random playoutは、ランダムに手を選んで最後までゲームを進めること
    • 乱択greedy/乱択山登り的な感じのこと
      • 合法手の集合を決めてその集合内を乱択、盤面の評価がよくなる手の集合を乱択で選んで山を登る
  • playoutは、高速にして何回も行うか、評価関数を導入してplayoutの質を高めることで有益な情報(近似値)として活用できる
    • 通常、random playoutはあまり品質の良い解は得られないことが多いので、量か質でカバー

ヒューリスティックな評価関数設計

  • ゲーム木で最後の状態(局面)まで探索するのが難しい場合、各状態(ノード)での評価値を考え、それをもとに探索することを考える
    • ある状態の次の手(エッジ)の評価値とかも考えられるが、より複雑になる可能性がある
  • 適当な評価関数を設計することで実現する
  • 評価関数が完璧であれば、次の状態で一番良い評価となる手を貪欲に選べば良いが、難しいので探索(先読み)と組み合わせたアプローチを取る

実スコア

  • 一番単純な評価関数は、「その状態の時点での実スコア」を用いること
  • ただし、通常は、コンボが決まったら高得点など、直近でやや損しても後で高スコアになるような場合があったりするため、そういう場合を考慮できていない
  • そのため、探索を深くするとか、評価関数になんらか補助スコアを導入するなどの工夫が考えられる

補助スコア

  • 実スコアの他に、補助スコアなどを考えて加えることで、実スコアでは区別ができない/差がつかない/反映されていないような「状態の良さ/悪さ」を評価関数に取り入れる
    • 状態が違ったら評価値が異なるようにしたい
  • 一例として、評価関数を実スコア/補助スコアの重み付き線形和などで考える
    • V(s) = \Sigma w_i * f_i(s)
      • f_i(s): 状態sでのi個目の(実/補助)スコアの値
      • w_i : i個目のスコアの重み
    • 素性・特徴量f_i(s)と考えても良い
  • 例
    • オセロとかでいうと、隅を取ってる数、確定したマスの数、合法手の数、など
    • 〜までの最短距離、周辺の〜の個数、全体のカバー率、など
    • プレイアウトした場合の最終スコア
  • 考えている問題・ゲームに合わせて、良さそうなことには+で、悪そうなことには-で特徴を加える
    • ビジュアライザなどを見るなどでそのような特徴を発見する、問題や制約から考察する、など
  • ただ、各重みの調整は、適当にするとバランス調整などがどんどん難しくなってしまったりするため、何らかの基準をベースに考えたりする方が良い
    • 将棋で歩を1点と考える(飛車は20点分として取るコマを決める)とか、オセロで石の数をベースに考える(4つ角を取る行為は石何個分に相当するか)とか
    • または、パラメータとして、学習やoptunaを使って最適化する、など

特徴量の関数の形状

手法例、改善例

  • ルールベースを考える
    • 評価関数のと組み合わせる
  • 原始モンテカルロ法(random playout+貪欲に最終スコアが高い手を選ぶ)
    • playoutの質を高める
      • ルールベースで手を選ぶ方法に置き換える
  • 評価関数設計して評価値が高い手を探索(BFS/DFS,貪欲法,ビームサーチ、chokudaiサーチなど)
    • 評価関数を改善する
    • 探索の質を高める、探索量を増やす
      • 可能性が高い手だけ調べる、合法手の一部だけ探索する、モンテカルロで浅くてもたくさん調べる、など

問題