格闘ゲーム AI 論文 11 本斜め読み

論文メモ

現在自分が作っている横スクロールアクションについて 少し凝った AI を搭載したいと考えているので、システムとしては近そうな格闘ゲームの AI についての論文を漁った。

Fighting Game AI Competition という格闘ゲーム AI のコンペティションに関連する論文が多い。

以下なんとなくジャンルに分けつつ概要を載せる。 気が向いたら個々のトピックの記事とかも書きたい。

モンテカルロ木探索

Opponent Modeling based on Action Table for MCTS-based Fighting Game AI

http://www.cig2017.com/wp-content/uploads/2017/08/paper_92.pdf

  • 前提
  • 目的
    • モンテカルロ木のノードを展開する際、相手の行う行動を予測して効率的なノード展開を行う
      • 格闘ゲームはプレイヤーの取れる行動が多く、また AI が計算に使用できる時間も限られているため、既存手法はモンテカルロ木の相手の行動についてのノード展開を行う際、ランダムな行動を 5 種類だけ選んで展開をしていた
  • 手法
    • 相手の状態を 6 パターンに離散化
      • 相手と自分の距離 3 パターン、地上/空中のどちらにいるか
    • 状態 6 パターンそれぞれについて、相手がとってきた行動のランキングを作成し、そのトップ 5 をモンテカルロ木の展開時に使用する
      • この行動テーブルはゲーム中もラウンドごとに更新する
      • 行動テーブルには初期値が必要だが、これは AI コンペティションのトップの AI と戦わせた結果から作成した

Monte Carlo Tree Search Based Algorithms for Dynamic Difficulty Adjustment

http://www.cig2017.com/wp-content/uploads/2017/08/paper_73.pdf

  • 前提
  • 目的
    • プレイヤーに合わせて動的に難易度を変える (Dynamic Difficulty Adjustment)
      • 常に対戦相手への勝率が 50 % になるようにする
  • 手法
    • モンテカルロ木探索において行動を決定する際、スコア (相手に与えたダメージ - 相手からの被ダメージ) を最大化するのではなく、0 に近づけるような行動を選択する
    • モンテカルロ木を構築する際も、各ノードの評価について、スコアが 0 に近づくようなものほど高い評価を与え、優先的にその子ノードを展開するようにする

Dynamic Scripting

A Method for Online Adaptation of Computer-Game AI Rulebase

http://www.ice.ci.ritsumei.ac.jp/~ruck/PAP/ace06.pdf

  • 前提
    • Dynamic Scripting を使う
  • 目的
    • Dynamic Scripting は、与えるルール群が効果的でないとうまくいかないという欠点があるが、これを改善する
  • 手法
    • 学習中、ルール群の中で非効率的なルールを発見し、新しく生成したルールで置き換える
      • ウェイトが一定以下になったルールを非効率的なものとみなし、ランダムに生成した if-then 形式のルールで置き換える
  • 結果
    • ナイーブな手法から性能改善
    • 収束が遅いのが課題

Investigation of Various Online Adaptation Methods of Computer-Game AI Rulebase in Dynamic Scripting

http://www.ice.ci.ritsumei.ac.jp/~ruck/PAP/dime-arts06.pdf

  • 前提
    • Dynamic Scripting を使う
  • 目的
    • 一つ上の論文と同様に、 Dynamic Scripting に与えるルール群が効果的でないとうまくいかないという問題を改善する
  • 手法
    • 一つ上の論文と同様に、ルール群の中で非効率的なルールを新しく生成したルールで置き換えるが、このとき追加する新たなルールは、複数生成したルール群から選ばれたひとつを用いる
    • 新しいルールの選び方は 3 種類で実験
      • MOS : ウェイトの最も高いルールに似ているルールを選択
      • LES : 破棄されたルールに最も似ていないルールを選択する
      • MIX : ウェイトの最も高いルールに似ており、かつ、破棄されたルールに似ていないルールを選択する
  • 結果
    • LES が最も性能が良かった

k近傍アルゴリズムとか

Deduction of fighting game countermeasures using Neuroevolution of Augmenting Topologies

http://ieeexplore.ieee.org/document/7936127/

  • 前提
    • ルールベースの AI は対戦相手の次の行動を予測してカウンター行動を取るのが難しい
  • 目的
    • 対戦相手の行動予測を行ってカウンター行動をとる AI を作成する
  • 手法
    • 相手が行った攻撃行動を自分からの相対位置とともに記録する
      • 自分/相手 がそれぞれ 地上/空中 どちらにいるか で 4 パターンについて別々に記録を行う
    • 相手の現在の相対位置について、近傍に一定個数以上の攻撃記録がある場合、相手が攻撃を行うと予測する
    • 相手の攻撃内容の予測については、現在の相手の相対位置から近い記録 k 個を参照する
  • 課題
    • ゲーム開始時には記録が空の状態から始まるので、正確な予測ができない

Online Adjustment of the AI's Strength in a Fighting Game Using the k-Nearest Neighbor Algorithm and a Game Simulator

http://www.ice.ci.ritsumei.ac.jp/~ruck/PAP/ieeeGCCE2014-nakagawa.pdf

  • 目的
    • 対戦相手のレベルをわずかに上回るよう、対戦中に AI プレイヤーの強さを調整する
  • 手法
    • 上の論文と同様、相手の過去の攻撃行動を相対位置と共に記録して、現在の相対座標の k 近傍の情報から相手の次の攻撃行動を予測する
    • 予測した相手の攻撃行動を元に 1 秒後の状態をシミュレートし、適度な強さになる行動を選択する

Predicting the Opponent's Action Using the k-Nearest Neighbor Algorithm and a Substring Tree Structure

http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=7398673

  • 目的
    • 対戦相手の次に行う行動を予測する
    • キャラクターが画面端に居る場合不利なので、それを避けるようにする
  • 手法
    • 攻撃行動の予測アルゴリズム 3 種
        1. k近傍アルゴリズム
        2. 上の論文と同様
        1. Substring tree structure algorithm (訳語わからない)
        2. 相手の攻撃行動のシーケンスの履歴から、木構造を作成
        3. 構築された木から、相手が現在行っている攻撃行動のシーケンスと最も長く一致する部分を求め、次の行動を予測する
        1. AとBの出力で多数決を行い、最終的な予想とする
    • 画面端からの距離をボルツマン方程式に代入し、回避行動の確率とする
      • ステージ端からの距離が近いほど回避行動を取りやすい

Applying Fuzzy Control in Fighting Game

https://ipsj.ixsq.nii.ac.jp/ej/index.php?active_action=repository_view_main_item_detail&page_id=13&block_id=8&item_id=164245&item_no=1

  • 目的
    • k近傍アルゴリズム AI のコールドスタート問題を解決する
      • 対戦開始直後は相手の行動記録がなく、効果的な予測と行動ができない問題
  • 手法
    • k近傍アルゴリズムに使用するデータが十分に蓄積されているかどうかに応じて、k近傍アルゴリズムとルールベースの戦略を確率的に選択する

ニューラルネット系

ニューラルネットワークによる格闘ゲームAI の難易度調整及び行動多様性向上手法

http://www.ice.ci.ritsumei.ac.jp/~ruck/PAP/gas09-nakagawa.pdf

  • 前提
  • 目的
    • AI プレイヤーの強さは適度にしたい
    • また、AI プレイヤーの取る行動には多様性をもたせたい
      • 単に強くなることを目標とした AI は、行動が収束して同じ行動ばかり取りがちになる
  • 手法
    • ニューラルネットの学習時、相手よりもゲームのスコア (与ダメージ) がある閾値以上勝っている場合には、負ける方に学習を進める
      • とった行動に対するスコアを正負逆転させて評価する
  • 結果
    • スコアの比は定義した閾値に収束していく
      • 柔軟な難易度調整が可能
    • 提案手法は行動の多様性が向上

Deep Q Networks for Visual Fighting Game AI

http://www.cig2017.com/wp-content/uploads/2017/08/paper_90.pdf

  • 前提
    • Deep Q Network (DQN) を使う
  • 目的
    • 格闘ゲームの AI でも DQN が使えるように、プレイヤーの入力の次元数を減らしたい
  • 手法
    • 人の手でいい感じに減らした
      • 方向 3 種、パンチ/キック、事前定義したコンボ 6種、で 11 種類
  • その他
    • AI の入力は画面情報 4 フレーム分
    • 対戦相手は何も行動しないプレイヤーとし、与えたダメージを最大化するように学習

Optimized Non-visual Information for Deep Neural Network in Fighting Game

http://www.scitepress.org/Papers/2017/62481/62481.pdf

  • 目的
    • ゲーム画面の画像ではなくゲームの状態を表すパラメータ群を入力とする AI をニューラルネットを用いて作成する。このとき、AI の判断に有用な、パラメータ同士の意味のある組み合わせを発見するようにしたい。
  • 手法
    • 畳み込みニューラルネットワーク (CNN) を用いる
      • パラメータ群をグリッド状に配置
      • いくつかのグリッド形状で試した
      • 特に重要そうなパラメータ 5 つについては、その 5 つ全てが常に畳み込みのウィンドウ内に含まれるような位置に配置した

所感

実践的にゲームに組み込む場合、 チューニングのし易さや動作速度の速さなどを考えると k近傍アルゴリズムとルールベースの組み合わせあたりが一番扱いやすい気がする。