Neo4j を駆使して格ゲーに勝つ

Fighting game is something so great.
　　　　　　　　　　　　　―― ときど（Evolution 2017 ストリートファイター5部門 優勝）

この記事は Nifty Advent Calendar 2017 23日目の記事です。 今回は、グラフDB「Neo4j」を使って格闘ゲームにおける「暴れ潰し」を効率よく探索し、勝率を高める方法を紹介します。大丈夫です、順を追って説明します。

なお、この記事では特に「ギルティギア イグザード」という格闘ゲームを取り扱っていますが、他の格闘ゲームに対しても応用可能です。

予備知識：フレームとは？

本題に入る前に、1つだけ用語の解説をさせてください。フレームという言葉をご存知でしょうか？フレームとは、格闘ゲームにおける時間の単位のようなものです。格闘ゲームに限らず、世の中のゲームはたいてい1秒間に60コマの画像を作り出して、それをパラパラ漫画のように見せています（ちなみに映画は24コマ/秒）。その1コマのことをフレームといいます。「この技は全体動作が40フレームある」という風に使います。よくわからなければ「1フレーム = 0.01秒」と思ってしまって大丈夫です。

以後、1フレームのことを「1F」と略記します。

暴れとは？

格闘ゲームにおける「暴れ」とは、対戦相手の攻撃をガード中にしゃがみパンチなど動作の小さい攻撃を連打することで、攻撃の隙間に割り込むことを指します。うまく割り込むことができれば攻守を交代することができるため、重要なテクニックのひとつです。特に初心者は、相手の接近を嫌がってやみくもに暴れを入力することが多い印象です（私もそのひとり）。

(元動画: http://www.nicovideo.jp/watch/sm26510042)

暴れ潰しとは？

それに対して、相手が暴れることを見越してそれに勝てるように技を出すことを「暴れ潰し」といいます。具体的な暴れの潰し方はいくつか方法があるのですが、ここではそのうちの1つを紹介します。

ひとことで説明すると、「相手の暴れ技の出がかりにこちらの攻撃を当てる」という手法です。例えば、カイというキャラクターの「しゃがみパンチ → 立ちパンチ」という暴れ潰しについて見てみます。フレームデータによると、各技の性能は以下のようになっています。

• しゃがみパンチ:

  • 攻撃レベル が 0
    • → 地上で通常ガードさせると相手は 9F 動けない（参考）
  • 判定が 4F 持続
  • その後 4F 硬直
    • → 自分は技をガードさせたあと (4 - 1) + 4 = 7F 動けない
  • つまり、しゃがみパンチをガードさせると自分の方が 9 - 7 = 2F 早く動ける

• 立ちパンチ:

  • 当たり判定が 発生 するまで 5F かかる

これらの情報をあわせると、「しゃがみパンチと立ちパンチの間に、相手は 5 - 2 = 3F だけ自由に動くことができる」ことがわかります。このとき相手が暴れ、つまり攻撃ボタンを連打していると、3Fの間にそのボタン入力がなまじ受け付けられて、技が漏れてしまいます。ギルティギアというゲームでは大抵のキャラが最速でも発生 5F 前後の技しか持っていないため、3Fでは技が発生し終わりません。漏れた暴れ技の出がかりにこちらの立ちパンチがヒットしてしまうのです。これが暴れ潰しの原理です。

もう1つだけ違う例を見てみます。今度は「しゃがみパンチ → 立ちHS」という連携を考えます。ギルティギアには「ガトリングコンビネーション」というシステムがあり、特定の技から特定の技へは「持続の残りと硬直をすっ飛ばして（＝キャンセルして）」次の技を繰り出すことができます。前述したとおり、しゃがみパンチをガードした相手は 9F 動けなくなるのですが、しゃがみパンチから立ちHSにキャンセルすると、ガードさせた直後に 発生 10F の立ちHSを繰り出すことができます。つまり、しゃがみパンチ ～ 立ちHSの間に 10 - 9 = 1F だけ隙間が生まれているのです。ここで相手が暴れていると、ボタン入力が受け付けられてしまい・・・暴れ潰しが成立するわけです。

暴れ潰しをどうやって探す？

ギルティギアは1人のキャラがたくさんの技を持っているため、上記のような暴れ潰しを探すのはそれなりに労力が要ります。ある2つの技が暴れ潰しになっているかどうか調べたかったら、

• フレームデータ で攻撃レベル、発生、持続、硬直を調べる
• 基礎データ で、攻撃レベルごとに割り振られたガード硬直時間を調べる
• キャンセルする場合としない場合で、それぞれ隙間が何 F あくか計算する

という手順が必要です。新しいキャラに触れ始めたときに、これを1から調べるのは大変です
そこで、Neo4j のようなグラフ DB を使って、効率的に暴れ潰し連携を探すことを考えます。具体的には、

• ノード: 各技。プロパティとして、攻撃レベル・発生・持続・硬直を持たせる。
• エッジ: 技から技を続けて出せるかどうか。プロパティとして、キャンセルできるかどうかを持たせる。

のような有効グラフを考え、技と技の隙間が4F以下になるようなパターンを探索したいと思います。

グラフを構築する

今回は、最近個人的に触り始めた レオ の暴れ潰しを探します。

ノードを登録する

まず、先ほどからたびたび登場している フレームデータ のページを ruby でスクレイピングして、表から CSV を作成します。

make_node.rb

# coding: utf-8
require "mechanize"
require "CSV"

URL = 'http://www.4gamer.net/guide/ggxrd/031723052/'
SELECTOR_LEO = 'div#table_result_18 table'

agent = Mechanize.new
table = agent.get(URL).at(SELECTOR_LEO)

data = (
  table.search('tr').to_a.map do |row|
    row.search('th,td').to_a.map do |el|
      (el.at('img') ? el.at('img').attribute('alt') : '').to_s + el.content
    end
  end
)

puts (
  CSV.generate do |csv|
    data.each do |arr|
      csv << arr
    end
  end
)

残念ながら、このあと若干の手作業が必要です。

手作業1: 不要な技の削除

簡単のために扱う技を「地上通常技と一部の必殺技」のみに限定します。取得した CSV から不要な技の行を手で削除していきます。

手作業2: バリデーション

今回は表中の「攻撃レベル」「発生」「持続」「硬直」に特に興味があるわけですが、まれにこの項目に整数以外の値（6 [3] など）が入っていることがあるので、昨年のアドベントカレンダー でも登場した cvlin を使ってバリデーションを行います。使用したルールファイルは以下のとおり。

rule.toml

name          = ".*"
damage        = ".*"
gauge         = ".*"
lv            = "^[0-4]$"
rlv           = ".*"
scaling       = ".*"
type          = ".*"
start         = "^[0-9]+$"
active        = "^[0-9]+$"
recovery      = "^[0-9]+$"
advantage     = ".*"
invincibility = ".*"
misc          = ".*"

引っかかった項目は適宜修正していきます。

登録

最終的に以下のような CSV が得られました。
https://gist.github.com/megane42/60bba8d858176c7659898734abd886d4#file-leo_node-csv

あとは neo4j の LOAD CSV クエリで CSV からデータを読み込んでノードを作成するだけです。CSV ファイルは、公式ドキュメントの表 の Import 列に示されたフォルダに置くとよいでしょう。

LOAD CSV WITH HEADERS FROM 'file:///leo.csv' AS line
CREATE (:Leo {
          name          : line.技名,
          damage        : line.攻撃力,
          gauge         : line.ゲージ,
          lv            : toInt(line.Lv),
          rlv           : line.Rlv,
          scaling       : line.基底,
          type          : line.攻撃属性,
          start         : toInt(line.発生),
          active        : toInt(line.持続),
          recovery      : toInt(line.硬直),
          advantage     : line.硬直差,
          invincibility : line.無敵,
          misc          : line.備考
        })

LOAD CSV はあくまで CSV からデータを読み込むだけで、これ自身にノードやエッジを作る効果があるわけではありません。逆に言えば、とりあえず何でも CSV にさえしてしまえばクエリ上で扱えるようになるためとても便利ですね。

エッジを登録する

方針としては、

# 技名A, 技名B, キャンセルできるかどうか

立ちP,立ちP,TRUE
立ちP,立ちK,TRUE
:

という構造の CSV を作成し、それを LOAD CSV してエッジを作成していきます。まずは、先ほどの CSV から雛形を作成します。作成後は、残念ながら再び手作業の時間です。

make_edge.rb

# coding: utf-8
require "CSV"

# header
puts "former,latter,cancel"

names       = CSV.read("leo_node.csv").select{|row| row[0] != '技名'}.map{|row| row[0]}
names_pairs = names.product(names)
names_pairs.each do |pair|
  puts "#{pair[0]},#{pair[1]},FALSE"
end

手作業1: 派生技の処理

キャンセルを考えなければ、基本的にはどの技からどの技へも連続して出すことが可能ですが、

• ツヴァイトはエアーストからしか出せない
• ドリットはツヴァイトからしか出せない

という制限があるため、ここはエッジを切る（行を削除する）必要があります。

手作業2: キャンセル可否を記入

ここが辛い作業でした・・・。

フレームデータと違い、キャンセルの可否に関する情報は構造化されたものがまとまっていません。あるのは下記の画像のみです（公式攻略サイトより引用）。

これを見ながら、あるいはゲーム内で実際に試しながら、CSV の3カラム目を TRUE にしたり FALSE にしたりしていきます。できあがった CSV はこちら。
https://gist.github.com/megane42/60bba8d858176c7659898734abd886d4#file-leo_edge-csv

登録

今回はノードに付与された「技名」で検索してエッジを結ぶことになるので、あらかじめ技名に対してインデックスを張っておくことで処理の高速化が期待できます。

CREATE CONSTRAINT ON (x:Leo) ASSERT x.技名 IS UNIQUE;

これでようやくエッジが登録できます。CSV の各行に出てくる2つの技名でノードを検索し、その間にエッジを結びます。このとき、例の3カラム目を使って cancel という属性を設定します。

LOAD CSV WITH HEADERS FROM 'file:///leo_edge.csv' AS line
MATCH (a:Leo { name: line.former}), (b:Leo { name: line.latter})
CREATE (a)-[:Possible { cancel: toBoolean(line.cancel) }]->(b)

関数を自作する

薄々勘付いている人もいるかもしれませんが、フレーム計算をするためには攻撃レベルからガード硬直時間への変換が必要になります。しかも、ガード硬直時間はガードの種類（通常ガード、直前ガード、フォルトレスディフェンス）によって異なります。

そこで今回は、この記事 を参考に変換用の関数を自作してみました。なぜかどう頑張ってもテストケースが実行できませんでしたが、テストをスキップすることで無事にビルドができました。

暴れ潰しを探す

ようやく、ようやく暴れ潰しを探すことができます。今回は、通常ガード時に5F未満の隙間があく連携を探してみます。params という機能を使うと、クエリ内で使える定数をあらかじめ設定することができます。下記のクエリを実行します。

:params {
  target_frame : 5,
  situation    : "normal_ground"
}

ここでもし situation を just_ground に変えれば、地上直前ガードされたときの連携を調べることができるというわけです。

ノーキャンセル暴れ潰し

ノーキャン暴れ潰しを探すクエリは以下のとおりです。Possible エッジで結ばれた2つのノード、というパターンを全て抽出し、そのうち隙間 (gap) が 1 以上 5 未満のものを検索します。gap は前述の説明通りに計算しています。WITH は可読性のために使っています。

 MATCH (a:Leo)-[r:Possible]->(b:Leo)
  WITH a,
       b,
       b.start - (ggxrd.alv2frame(a.lv, $situation) - (a.active - 1 + a.recovery)) AS gap
 WHERE 0 < gap < $target_frame
RETURN a.name, b.name, gap

結果は以下のとおり。

a.name                                 	b.name	gap
"6＋HS"                                	"立ちP"	1
"6＋K"                                 	"立ちP"	2
"しゃがみS"                            	"立ちP"	2
"近距離立ちS"                          	"立ちP"	4
"6＋HS"                                	"立ちK"	3
"6＋K"                                 	"立ちK"	4
"しゃがみS"                            	"立ちK"	4
"6＋HS"                                	"近距離立ちS"	2
"6＋K"                                 	"近距離立ちS"	3
"しゃがみS"                            	"近距離立ちS"	3
"カルタスゲシュトゥーバー・ツヴァイト" 	"しゃがみP"	4
"6＋K"                                 	"しゃがみP"	1
"しゃがみS"                            	"しゃがみP"	1
"近距離立ちS"                          	"しゃがみP"	3
"立ちK"                                	"しゃがみP"	4
"6＋HS"                                	"しゃがみK"	2
"6＋K"                                 	"しゃがみK"	3
"しゃがみS"                            	"しゃがみK"	3

おお！それっぽいですね。実際にやってみると距離の関係で当たらないものが多かったですが、しゃがみS → 立ちK はかなり使いやすいです。

キャンセル暴れ潰し

続いてキャンセルを使った暴れ潰しを見ていきます。クエリは以下のとおりです。先ほどと大きくは変わりませんが、エッジの cancel 属性を使っているのと、gap の計算が少し変わっています。

 MATCH (a:Leo)-[r:Possible]->(b:Leo)
  WITH a,
       b,
       r,
       b.start - ggxrd.alv2frame(a.lv, $situation) AS gap
 WHERE r.cancel = TRUE
   AND 0 < gap < $target_frame
RETURN a.name, b.name, gap

結果は以下のとおり。

a.name                 	b.name	gap
"しゃがみP"            	"遠距離立ちS"	1
"立ちP"                	"遠距離立ちS"	1
"しゃがみS"            	"立ちHS"	2
"しゃがみK"            	"立ちHS"	4
"遠距離立ちS"          	"立ちHS"	2
"立ちK"                	"立ちHS"	4
"しゃがみP"            	"しゃがみS"	1
"立ちP"                	"しゃがみS"	1
"しゃがみP"            	"しゃがみHS"	1
"立ちP"                	"しゃがみHS"	1
"しゃがみK"            	"6＋P"	2
"しゃがみP"            	"6＋P"	4
"立ちK"                	"6＋P"	2
"立ちP"                	"6＋P"	4
"しゃがみS"            	"6＋K"	2
"遠距離立ちS"          	"6＋K"	2
"しゃがみK"            	"足払い"	1
"しゃがみP"            	"足払い"	3
"立ちK"                	"足払い"	1
"立ちP"                	"足払い"	3
"しゃがみS"            	"カルタスゲシュトゥーバー・エアースト"	2
"しゃがみK"            	"カルタスゲシュトゥーバー・エアースト"	4
"遠距離立ちS"          	"カルタスゲシュトゥーバー・エアースト"	2
"立ちK"                	"カルタスゲシュトゥーバー・エアースト"	4
"→ツヴァイト（派生）" 	"→→ドリット（派生）"	1

これもいい感じです。立ちHSで潰すとリターンが高そうなので、それらのルートは覚えておきたいところです。ツヴァイトからドリットが暴れ潰しになっているので、あえてツヴァイトで止めて構え状態で攻め継続するなど悪いことも思いつきます。

連続暴れ潰しを探す

ここからが GraphDB の本領発揮です。少し長いですが、下記のクエリが何を検索しているかわかるでしょうか？

 MATCH (a:Leo)-[r:Possible]->(b:Leo)-[r2:Possible]->(c:Leo)
  WITH a,
       b,
       c,
       r,
       r2,
       b.start - ggxrd.alv2frame(a.lv, $situation) AS gap,
       c.start - ggxrd.alv2frame(b.lv, $situation) AS gap2
 WHERE r.cancel = TRUE
   AND r2.cancel = TRUE
   AND 0 < gap < $target_frame
   AND 0 < gap2 < $target_frame
RETURN a.name, gap, b.name, gap2, c.name

そう、キャンセル暴れ潰しからさらにキャンセル暴れ潰しできるルートを検索しているのです！グラフDB以外のツールでとっさにこれを検索するのはなかなか難しいのではないでしょうか？早速検索してみましょう。

a.name      	gap	b.name	gap2	c.name
"しゃがみP" 	1	"遠距離立ちS"	2	"6＋K"
"立ちP"     	1	"遠距離立ちS"	2	"6＋K"
"しゃがみP" 	1	"遠距離立ちS"	2	"カルタスゲシュトゥーバー・エアースト"
"立ちP"     	1	"遠距離立ちS"	2	"カルタスゲシュトゥーバー・エアースト"
"しゃがみP" 	1	"遠距離立ちS"	2	"立ちHS"
"立ちP"     	1	"遠距離立ちS"	2	"立ちHS"
"しゃがみP" 	1	"しゃがみS"	2	"立ちHS"
"立ちP"     	1	"しゃがみS"	2	"立ちHS"
"しゃがみP" 	1	"しゃがみS"	2	"カルタスゲシュトゥーバー・エアースト"
"立ちP"     	1	"しゃがみS"	2	"カルタスゲシュトゥーバー・エアースト"
"しゃがみP" 	1	"しゃがみS"	2	"6＋K"
"立ちP"     	1	"しゃがみS"	2	"6＋K"

素晴らしい！かなり実用的な連携が見つかりました。しかもこれらの連携はちゃんとエッジ情報を使って検索しているので、机上の空論ではなく全て実際に繰り出すことができるのです。

まとめと課題

今回は、格闘ゲームの攻略という分野におけるグラフDBの応用事例を紹介しました。最後に見せた例のように、特定の条件を満たすような「経路」を検索することができるのは、グラフDB特有の強みではないでしょうか。

最大の課題は、かなりの手作業が発生してしまうことです。特に、今回は都合よくカットしましたが、多段技を持つキャラクターはさらに手間がかかります（多段技を1段ずつ1ノードに分解する必要がある）。データ作成が効率よく行えれば、Web UI をつけてサービスとして公開したら需要あるかな、などと夢見たのですが、難しいですね。

Fighting game is great

ところで、みなさんは最近ガッツポーズをとったことはありますか？声をあげて悔しがったことはありますか？サラリーマンとして生きていると、つい日々を漫然と過ごしてしまいがちですが、格闘ゲームはそんな日常に99秒間の真剣勝負を与えてくれるのです。難しい？覚えることが多い？残念ながらそのとおりです。格ゲーは甘えを許してくれません。お金の力で強くなることもできませんし、負けを誰かのせいにすることもできません。その代わり、勝利もすべてあなたの力によるものです。あなたが勝ったのは、ラッキーでも何でもなく、あなたが相手より強かったからです。それを格ゲーは認めてくれます。会社の評価制度のように、自分の評価の理由がわからないなんてことはありません。もしこの記事を読んで少しでも格ゲーに興味を持ってくれたら、そんなに嬉しいことはありません。

---

明日は @licht110 君がビットコインで有り金を全部溶かしたときの話をしてくれます。