論文メモ（2013/04/28-2013/05/04）：複雑ネットワーク，進化計算，ゲーム

ゲームAI 進化計算 General Game Playing

B. Georgeot and O. Giraud (2012), "The game of go as a complex network"

  • 囲碁を複雑ネットワークとして捉え，その性質を分析
  • 石の周囲8マスのパターンを1ノードとし，一定距離以内で連続して石が置おかれた場合に有効辺を追加
  • プロの棋譜とアマの棋譜でそれぞれ分析
  • アマは近い距離に連続して打つ傾向がある
  • ノードの出現頻度はZipf's lawに従う
  • ネットワークはスケールフリーである
  • outgoing linkとingoing linkの分布がほぼ等しい
  • Google matrixの右固有ベクトルがそれぞれ異なる性質の着手の分布を表し，それらはプロとアマで異なる

Carlos A. Coello Coello (2001), "Theoretical and numerical constraint-handling techniques used with evolutionary algorithms: a survey of the state of the art"

  • 進化計算において解の制約をどう扱うか
  • 5つのクラスに分類
    • Penalty functions：充足されない制約の数や程度に応じて適合度を減少させる
    • Special representations and operators：infeasibleな個体が生じないような表現方法やオペレータを用いる
    • Repair algorithms：infeasibleな個体をfeasibleな個体に変換する（適合度を計算するときだけrepairする or 個体を永久的に置き換えてしまう）
    • Separation of objectives and constraints：目的関数と制約を組み合わせず別々に扱う
    • Hybrid methods：他の最適化技術と組み合わせる
  • 各手法について長所短所を考察し，さらに一部の手法については実験により評価
  • 最も単純なDeath penalty（制約を1つでも満たさない個体の適合度は0にする）でも，問題についての知識がない場合はそれほど悪くない

Joseph Reisinger, Erkin Bahçeci, Igor Karpov and Risto Miikkulainen (2007), "Coevolving Strategies for General Game Playing"

  • ミニマックス探索に用いる評価関数をNeural Networkで表現，NeuroEvolution of Augmenting Topologies（NEAT）で進化
  • Neural Networkの入力の数は40（ランダムな射影とあるが詳細は不明），出力の数は1（評価値）
  • パレート最適な解への単調な進化を保証するCovering Competitive Algorithm（CCA）を利用
  • 5ゲーム中4ゲームでパフォーマンス向上，1ゲームでは低下
  • 1-plyで学習した評価関数は2-ply以上の探索ではランダムに対するパフォーマンスが落ち，スケールしない
  • disengagement（一方の集団が強すぎるせいで他方の集団の個体間に適合度の差が生まれず，個体を適切に選べなくなるという，共進化アルゴリズムに見られる問題）が一部のゲームで生じる
  • nnrg.hazelは2006年のコンペティションで6位