Pokémonで説明するProlog入門

(unplannedobsolescence.com)

3 ポイント投稿者 GN⁺ 3 시간 전 | 1件のコメント | WhatsAppで共有

Pokémonのバトルルールは、タイプ相性、技、能力値、特性が絡み合うルールエンジンに近く、Prologの関係・ルールモデルで簡潔に表現できる
Prologは pokemon/1、type/2 のような述語で事実を置き、大文字の変数と単一化によってタイプ・技の条件に合うPokémonを見つけ出す
Freeze-Dryを覚え、Iceタイプで、Special Attackが120より大きいPokémonを探す場合、SQLの複数の EXISTS よりもPrologの問い合わせのほうが短い
ドラフトチームは alex/1、morry/1 のような述語で表現でき、優先度技のルールには除外条件やPrankster効果を段階的に積み上げられる
Techno's Prep Docのようなスプレッドシートも強力だが、Prologデータベースは任意の組み合わせクエリにより柔軟で、prologdexとScryer Prologで実装されている

Pokémonのバトルルールが論理プログラミングに向いている理由

Pokémonのバトルは複数のルールが複雑に噛み合うルールエンジンに近く、Prologのような論理プログラミングはこうした関係を簡潔に表現するのに適している
Pokémonは種族名を持つキャラクターであり、Bulbasaur #1)からPecharunt #1025)まで、1,000種を超える
メインシリーズのバトルは6匹で構成されたチーム同士で戦い、各Pokémonは通常、相手にダメージを与える4つの技のうち1つを選び、相手チームのHPをすべて0にすれば勝利する
バトル性能は基本能力値、覚えられる技の一覧、特性、タイプによって変わり、組み合わせの数が多いためソフトウェアで追跡する価値が高い
タイプは技とPokémonの両方に付与され、ある技タイプが相手タイプに強ければ2倍のダメージ、弱ければ1/2のダメージを与える
タイプ補正は累積する
- Scizor)はBug/Steelタイプで、どちらもFireに弱いため、Fire技から4倍のダメージを受ける
- Water/GroundタイプのSwampert)にElectric技を使うと、Groundの無効化によりダメージは0になる

Prologの基本モデル

Prologでは述語(predicate) で関係を宣言する

pokemon(bulbasaur).
pokemon(ivysaur).
pokemon(venusaur).
pokemon(charmander).
pokemon(charmeleon).
pokemon(charizard).
pokemon(squirtle).
pokemon(wartortle).
pokemon(blastoise).

pokemon/1 は名前が pokemon で引数が1つの述語であり、pokemon(squirtle). のような問い合わせは、その文を真にできるかどうかを確認する

?- pokemon(squirtle).
   true.

?- pokemon(alex).
   false.

Pokémonのタイプは type/2 のような2引数の関係として表現でき、2つのタイプを持つPokémonについては同じPokémonに対して type の事実を2つ置く

type(bulbasaur, grass).
type(bulbasaur, poison).
type(charmander, fire).
type(charizard, fire).
type(charizard, flying).
type(squirtle, water).

大文字で始まる名前は変数であり、Prologは変数を含む問い合わせを可能なすべての値と単一化(unify)しようとする

?- type(squirtle, Type).
   Type = water.

?- type(venusaur, Type).
   Type = grass
;  Type = poison.

type(Pokemon, grass). のように第1引数を変数にすると、GrassタイプのPokémon全体を探せる。実データでは164件の結果が返る
カンマは複数の述語をすべて満たさなければならないことを意味し、同じ変数名は問い合わせの中で同じ値を取らなければならない

?- type(Pokemon, water), type(Pokemon, ice).
   Pokemon = dewgong
;  Pokemon = cloyster
;  Pokemon = lapras
;  Pokemon = laprasgmax
;  Pokemon = spheal
;  Pokemon = sealeo
;  Pokemon = walrein
;  Pokemon = arctovish
;  Pokemon = ironbundle
;  false.

Iron Bundle)のように、能力値や覚えられる技も関係として問い合わせできる

?- pokemon_spa(ironbundle, SpA).
   SpA = 124.

?- learns(ironbundle, Move), move_category(Move, special).
   Move = aircutter
;  Move = blizzard
;  Move = chillingwater
;  Move = freezedry
;  Move = hydropump
;  Move = hyperbeam
;  Move = icebeam
;  Move = icywind
;  Move = powdersnow
;  Move = swift
;  Move = terablast
;  Move = waterpulse
;  Move = whirlpool.

SpA #> 120 のような制約を組み合わせると、Special Attackが120より大きく、Freeze-Dryを覚え、IceタイプのPokémonをすぐに見つけられる

?- pokemon_spa(Pokemon, SpA), SpA #> 120, learns(Pokemon, freezedry), type(Pokemon, ice).
   Pokemon = glaceon, SpA = 130
;  Pokemon = kyurem, SpA = 130
;  Pokemon = kyuremwhite, SpA = 170
;  Pokemon = ironbundle, SpA = 124
;  false.

Prologのルール(rule) はヘッドとボディで構成され、ボディが真ならヘッドも単一化される

damaging_move(Move) :-
  move_category(Move, physical)
; move_category(Move, special).

このルールはPhysicalまたはSpecialの技を直接ダメージ技として分類する

?- damaging_move(tackle).
   true.
?- damaging_move(rest).
   false.

SQLと比較したクエリ表現

ここまでの例は論理的には単純な and と or の組み合わせにすぎないが、Prologでは関係クエリをSQLより短く、修正しやすい形で書ける
同じデータをSQLで構成するなら、Pokémon、タイプ、技を別々のテーブルに置ける

CREATE TABLE pokemon (pokemon_name TEXT, special_attack INTEGER);
CREATE TABLE pokemon_types(pokemon_name TEXT, type TEXT);
CREATE TABLE pokemon_moves(pokemon_name TEXT, move TEXT, category TEXT);

Freeze-Dryを覚え、Iceタイプであり、Special Attackが120より大きいPokémonをSQLで探すには、EXISTS を何度も使う必要がある

SELECT DISTINCT pokmeon, special_attack
FROM pokemon as p
WHERE
  p.special_attack > 120
  AND EXISTS (
    SELECT 1
    FROM pokemon_moves as pm
    WHERE p.pokemon_name = pm.pokemon_name AND move = 'freezedry'
  )
  AND EXISTS (
    SELECT 1
    FROM pokemon_types as pt
    WHERE p.pokemon_name = pt.pokemon_name AND type = 'ice'
  );

同じPrologクエリでは、必要な関係をそのまま列挙する

?- pokemon_spa(Pokemon, SpA),
SpA #> 120,
learns(Pokemon, freezedry),
type(Pokemon, ice).

条件が増え続けるとSQLクエリは複雑になりがちだが、Prologクエリは変数の振る舞いに慣れれば、読みやすく修正しやすい形を保てる

戦闘ルールを積み重ねていく方法

Pokémonの対戦には、命中失敗、能力変化、アイテム効果、ダメージ量の幅、状態異常、天候・フィールド・Trick Roomのような場の効果、特性、事前の能力値配分など、多くの相互作用するルールがある
Pokémon向けソフトウェアを作るときは、この複雑さを扱いながら、モデルを管理可能な形に保つ必要がある
Prologは、その場での組み合わせを記述するクエリモデルと、一貫したルールのレイヤー化に強みがある
damage calculator を使えば、こうした複雑さを直接確認できる

ドラフトリーグと優先度技クエリ

Pokémonドラフトでは、Pokémonごとに価値が定められ、プレイヤーは決められたポイント内でPokémonを指名し、8〜11匹ほどのチームを構成する
実際の対戦は6v6なので、相手が持ち込める6匹の組み合わせを想定し、それに対抗する6匹を選ぶ準備が重要になる
自分が指名したPokémonは alex/1 のような述語でそのまま表現できる

alex(meowscarada).
alex(weezinggalar).
alex(swampertmega).
alex(latios).
alex(volcarona).
alex(tornadus).
alex(politoed).
alex(archaludon).
alex(beartic).
alex(dusclops).

このチームでFreeze-Dryを覚えるPokémonを探すクエリは簡単だが、結果はない

?- alex(Pokemon), learns(Pokemon, freezedry).
   false.

行動順は基本的にSpeedで決まるが、技には優先度(priority) があり、より高い優先度の技が先に出る
ほとんどの技の優先度は0だが、Accelerockのように優先度1の技は、より速いPokémonの優先度0の技より先に出る
特定のPokémonが覚える優先度が正の技は、learns/2、move_priority/2、優先度条件を組み合わせて探せる
単純なクエリには、Helping HandやAlly SwitchのようにDouble Battlesで意味が大きい技や、Bideのように実戦的な意味が薄い技まで含まれてしまう
\+/1 は目標が失敗したときに真となり、dif/2 は2つの項が異なることを意味するので、Double Battles用の技とBideを除外するルールを追加できる

learns_priority(Mon, Move, Priority) :-
  learns(Mon, Move),
  \+ doubles_move(Move),
  dif(Move, bide),
  move_priority(Move, Priority),
  Priority #> 0.

Protect、Detect、Endure、Magic Coatのような防御系の技も除外すれば、実際に相手へダメージや不利な効果を与えられる優先度技だけが残る

?- alex(Pokemon), learns_priority(Pokemon, Move, Priority).
   Pokemon = meowscarada, Move = quickattack, Priority = 1
;  Pokemon = meowscarada, Move = suckerpunch, Priority = 1
;  Pokemon = beartic, Move = aquajet, Priority = 1
;  Pokemon = dusclops, Move = shadowsneak, Priority = 1
;  Pokemon = dusclops, Move = snatch, Priority = 4
;  Pokemon = dusclops, Move = suckerpunch, Priority = 1
;  false.

同じルールを相手チームの述語に適用すれば、相手が持つ優先度技もすぐに見つけられる

?- morry(Pokemon), learns_priority(Pokemon, Move, Priority).
   Pokemon = mawilemega, Move = snatch, Priority = 4
;  Pokemon = mawilemega, Move = suckerpunch, Priority = 1
;  Pokemon = walkingwake, Move = aquajet, Priority = 1
;  Pokemon = ursaluna, Move = babydolleyes, Priority = 1
;  Pokemon = lokix, Move = feint, Priority = 2
;  Pokemon = lokix, Move = firstimpression, Priority = 2
;  Pokemon = lokix, Move = suckerpunch, Priority = 1
;  Pokemon = alakazam, Move = snatch, Priority = 4
;  Pokemon = skarmory, Move = feint, Priority = 2
;  Pokemon = froslass, Move = iceshard, Priority = 1
;  Pokemon = froslass, Move = snatch, Priority = 4
;  Pokemon = froslass, Move = suckerpunch, Priority = 1
;  Pokemon = dipplin, Move = suckerpunch, Priority = 1.

いたずらごころ特性の拡張

いたずらごころ特性を持つPokémonは変化技の優先度がさらに +1 され、この効果も既存のlearns_priority/3ルールに加えられる
チーム内ではTornadusがいたずらごころ特性を持つ

?- alex(Pokemon), pokemon_ability(Pokemon, prankster).
   Pokemon = tornadus
;  false.

Prologの->/2 if/then構文を使い、Pokémonがいたずらごころで技分類がstatusなら基本優先度に1を足し、そうでなければ基本優先度をそのまま使うようにできる

learns_priority(Mon, Move, Priority) :-
  learns(Mon, Move),
  \+ doubles_move(Move),
  \+ protection_move(Move),
  Move \= bide,
  move_priority(Move, BasePriority),
  (
    pokemon_ability(Mon, prankster), move_category(Move, status) ->
      Priority #= BasePriority + 1
    ; Priority #= BasePriority
  ),
  Priority #> 0.

このルールの後では、同じ問い合わせにTornadusのAgility、Defog、Nasty Plot、Rain Dance、Tailwind、Taunt、Toxicといった変化技が優先度1として含まれる
ルールを1つ拡張するだけで特性効果まで反映でき、Prologのレイヤリングの利点がよく表れている

スプレッドシートベースのツールとの対比

Pokémonコミュニティには相手チームの優先度技のような情報を探すリソースがすでにあり、代表例としては「Techno’s Prep Doc」のような高度なGoogle Sheetsが使われている
このスプレッドシートはチームを入力すると多くのマッチアップ情報を生成し、さまざまなフォーマット対応、一覧しやすい視覚資料、オートコンプリートを提供する
優先度技を見つける数式はFILTER、VLOOKUP、INDIRECTを組み合わせており、INDIRECTはセル参照を返す

={IFERROR(ARRAYFORMULA(VLOOKUP(FILTER(INDIRECT(Matchup!$S$3&"!$AV$4:$AV"),INDIRECT(Matchup!$S$3&"!$AT$4:$AT")="X"),{Backend!$L$2:$L,Backend!$F$2:$F},2,FALSE))),IFERROR(FILTER(INDIRECT(Matchup!$S$3&"!$AW$4:$AW"),INDIRECT(Matchup!$S$3&"!$AT$4:$AT")="X"))}

Backendシートにはすべての技が列挙されており、この構造はPrologの問い合わせをハードコードした版に近い
Prologデータベースは、注目すべき技リストをハードコードする方式よりも拡張性が高く、どんな技でも照会できる
たとえば、Tornadusが覚えるSpecial技のうちJustinのチームメンバーに効果抜群な技を探すように、既存ツールにない組み合わせ型の質問も短く表現できる

?- justin(Target), learns(tornadus, Move), super_effective_move(Move, Target), move_category(Move, special).
   Target = charizardmegay, Move = chillingwater
;  Target = terapagosterastal, Move = focusblast
;  Target = alomomola, Move = grassknot
;  Target = scizor, Move = heatwave
;  Target = scizor, Move = incinerate
;  Target = runerigus, Move = chillingwater
;  Target = runerigus, Move = darkpulse
;  Target = runerigus, Move = grassknot
;  Target = runerigus, Move = icywind
;  Target = screamtail, Move = sludgebomb
;  Target = screamtail, Move = sludgewave
;  Target = trapinch, Move = chillingwater
;  Target = trapinch, Move = grassknot
;  Target = trapinch, Move = icywind
;  false.

タイプ相性表はtype-chart.plにエンコードされている
既存のPokémonツールではできないWebアプリを作るには、scryer-prologをWASMにコンパイルする課題が残っている

実装メモと限界

試してみられるコードはprologdexリポジトリにあり、簡単なセットアップガイドが含まれている
使用したProlog実装はScryer Prologで、標準と形式的正確性を重視するモダンなProlog実装である
Markus Triskaのオンライン書籍「The Power of Prolog」と関連するYouTubeチャンネルを学習資料として参照できる
Scryer Prologは論理的完全性と単調性を保つ構文の使用を推奨しているため、\+/1や->/2の使用は推奨方針に完全には沿っていない
データはPokémon ShowdownのNodeJS APIを使ってProlog述語へ変換しており、変換スクリプトはgenerate-dex.jsにある

1件のコメント

GN⁺ 3 시간 전

Lobste.rs の意見

Prolog を実際に実用的に使っている人がいるのか気になる。仕事でも個人用途でもよくて、これまではこういうおもちゃのような例しか見たことがなかった
- Prolog はかなり好きで、おそらく最も広く使われている Prolog 言語サーバー 実装を作った者として、ちょっとしたスクリプトによく使っている
  厳密には実運用中の Prolog コードも 1 つ以上あって、社内分析ダッシュボードがそうだし、以前は iOS アプリのバックエンドサーバーも Prolog で書いていた。その過程で、外部サービスなしで APNS 通知を送るために Prolog 用の HTTP/2 クライアントライブラリも作ることになった
- 満足のいく答えになるかは分からないが、このブログ記事を書いてからというもの、以前のコードとはまったく別軸の問題に Prolog を持ち出すようになった
  Prolog コミュニティには Web サーバーのような用途に使うのを好む人も確かにいるが、個人的には別のスキルツリーを開く感覚に近い。たとえば、どんな問題にカスタムパーサーや DSL がうまく合うかを、より見極められるようになる
  この記事を書いたあとに得た知識で、IRS Fact Graph の税務ロジックエンジンの有用な部分集合を再実装した。Prolog はこの作業に驚くほどよく合っていて、命令型実装なら見過ごしがちな文書化されていない隅を表に出し、解決を強いるからだ
  「実行」の部分はまだ完成していないが、パースは十分進んでいて、かなりまともな文書の草案を書けた。大きな機能として日付演算がまだ欠けており、それが入ったら別途まとめる予定だ
  DCG を使うと、Prolog は複雑な構造化テキストのパースに優れている。以前は awk で手に負えなければ Python や JS を思い浮かべていたが、今では構造と規律が必要な場面では Prolog がしっくりくる。1 ファイルに収まる複雑なコードベースを書く古風な感覚も心地よく、APL のように過度に省略的でもない
  例自体は些細でも、Pokémon の事例はそうではない。一見些細に見える例の多くも、ばかばかしいほど複雑な戦闘メカニクスを非常に徹底して実装したコードがすでにあるからこそ可能だった。既存ツールの仕事の一部をこなす Prolog ルールエンジンを作ることに関心があり、少しずつ試してもいるが、利点は命令型コードよりも 深さ優先探索 で可能性を見つけやすく、保守もしやすい点にある
- プログラム解析 に時々使っていた。かなり多くのツールが Datalog でプログラム情報を保存し、その上でクエリを書けるようにしているが、ときどき実際の SWI-Prolog を提供するツールを使って、バックトラッキングや関数を活用している
- 自分のブログは Prolog で生成されていて、ソースコードも公開している
  Scryer Prolog のドキュメントも、DocLog と呼んでいる Prolog プログラムで生成されている。これらのプログラムが使うライブラリもいくつか作った。SWI Prolog も、自身の Web サイト、Swish という Web IDE、ClioPatria サーバーなどで SWI を直接使っている
SQLite を一種の 型安全なスプレッドシート のように使って情報を整理してみたことがある。上に CRUD インターフェースがまったくなくても可能だった
ただし、いつも最も見栄えのよい言語だったわけではない。Datalog もしばらく見ていたが、ほとんどの実装は、この記事のように手軽に情報を記録する道具というより、大きなプログラムに組み込む用途に見えた
もしかすると Prolog こそ実際に使うべき道具なのかもしれない
- 外部データベース型の Datalog なら Mangle や Datomic があるので合うかもしれないが、自分では使ったことがない
  Prolog は Datalog の上位集合なので、Datalog ができることはすべてでき、それ以上も可能だ。ただ、その「以上」が問題になることもあって、チューリング完全な言語なので終わらない可能性があり、推論も少し難しくなり、安全でない形で使われることもある
  Datalog は制約があるおかげで近道が使えるため、性能もより良い場合が多い
  最後に、Prolog ではデータがコードと同一、つまり ホモイコニシティ があるので、生成・更新・削除の作業は実質的にソースコードを書き換えることになる。動的にもできるが、流れがスムーズだとは期待しにくく、ファイルとロード済みプログラムの間である程度の手動同期が依然として必要になる
Prolog をもっと深く学んで、命令セット問い合わせ に使ってみたい
ただし、個数やビットレベルで見た整数を含めて論理をモデル化するのはかなり難しい

Pokémonで説明するProlog入門

Pokémonのバトルルールが論理プログラミングに向いている理由

Prologの基本モデル

SQLと比較したクエリ表現

戦闘ルールを積み重ねていく方法

ドラフトリーグと優先度技クエリ

いたずらごころ特性の拡張

スプレッドシートベースのツールとの対比

実装メモと限界

関連記事

1件のコメント

Lobste.rs の意見