読んだ論文メモ（2013/05/05-2013/05/11）：カードゲーム関連

ゲームAI 進化計算

JM Font, T Mahlmann, D Manrique and J Togelius (2013), "Towards the Automatic Generation of Card Games through Grammar-Guided Genetic Programming"

  • Card Game Description Languageによって表現されたカードゲームをGrammar-Guided Genetic Programming（GGGP）により進化
  • Card Game Description Languageはテキサス・ホールデム，ブラックジャック，UNO等を表現できる
  • 各個体に対して一定回数のプレイアウトをし評価を行う
    • 一度も正しく終了しなかった個体，引き分けが20%より多い個体，ルールが複雑すぎる個体は直ちに除去
    • プレイヤ間の勝利数の差，ゲームが終了するまでのターン数の平均，どのプレイヤも合法手を持たないターンの数の平均，ランダムプレイヤとMCTSプレイヤの性能差の4つを用いて適合度を計算
  • 得られたゲームは人間がバランスが取れており，スキル要素もあるが，人間がプレイして面白いものとは言えない

PL Cowling, CD Ward, EJ Powley (2012), "Ensemble determinization in Monte Carlo tree search for the imperfect information card game Magic: The Gathering"

  • MCTSを単純化したMagic: The Gatheringに適用
  • 使用カードは能力のないクリーチャーと土地に限定
  • 2種類のルールベースプレイヤを用意
    • 豊富なヒューリスティックを元に攻撃・ブロックの選択を決定的に行うプレイヤ（Expert）
    • ごく単純なヒューリスティックしか使わず，確率的に選択を行うプレイヤ（Reduced）
    • 互いに対戦させると，Expertの方が強い
  • MCTSのための様々な改良の組み合わせを評価
    • ターン中にプレイするカードの選択に二分決定木を用いる手法が効果的
  • MCTSプレイヤのプレイアウトのために上記の2種類のルールベースプレイヤを用いた場合は，Reducedを用いた方が強い
  • 不完全情報ゲームにMCTSを適用するための様々な技術を紹介

T Mahlmann, J Togelius and GN Yannakakis (2012), "Evolving Card Sets Towards Balancing Dominion"

  • ドミニオンの王国カード10枚の組み合わせを評価し，バランスのとれた組み合わせを進化計算により獲得
  • 3種類のプレイヤを用意
    • vDomエンジンが提供するEarlとDrew
    • NeuroEvolution of Augmenting Topologies（NEAT）を使用し，購入するカードの選択とプレイするアクションカードの選択のための2つのArtificial Neural Network（ANN）を学習したプレイヤ
  • 基本セットのカードのみ使用
  • 2種類の適合度関数を提案し評価
    • プレイヤの技術の差に基づいた適合度：プレイヤ間の得点差の大きさ（大きいほどよい）
      • 異なるプレイヤ間で評価（3通りの組み合わせそれぞれにつき別々に進化させる）
    • ゲーム中の展開に基づいた適合度：1ゲーム中におけるプレイヤの優位の入れ替わりの回数（多いほどよい）と最後の優位の入れ替わり（遅いほどよい）の組み合わせ
      • 同じプレイヤ間で評価（3プレイヤそれぞれにつき別々に進化させる）
      • 優位の推定のためのANNはカードセットごとに学習
  • 各適合度関数によってカードセットを進化させた場合に選ばれやすいカードを分析
    • プレイヤ間の得点差を最大化するカード：Cellar（地下貯蔵庫），Militia（民兵），Witch（魔女），Woodcuter（木こり）
    • プレイヤ間の得点差を最小化するカード：Bureaucrat（役人），Spy（密偵）
    • 優位の入れ替わりに関する適合度を最大化するカード：評価に用いたプレイヤにより大きく異なる