- Les règles de combat de Pokémon s’apparentent à un moteur de règles où s’entremêlent matchups de types, capacités, statistiques et talents, ce qui permet de les exprimer de façon concise avec le modèle relationnel et les règles de Prolog
- Prolog pose des faits avec des prédicats comme
pokemon/1 et type/2, puis retrouve les Pokémon qui correspondent aux conditions de type ou de capacité grâce aux variables commençant par une majuscule et à l’unification
- Pour trouver un Pokémon de type Ice qui apprend Freeze-Dry et dont la Special Attack est supérieure à 120, une requête Prolog est plus courte que plusieurs
EXISTS en SQL
- Une équipe de draft peut être représentée avec des prédicats comme
alex/1 et morry/1, et les règles sur les capacités de priorité peuvent intégrer par couches des conditions d’exclusion et l’effet de Prankster
- Les feuilles de calcul comme Techno's Prep Doc sont puissantes, mais une base de données Prolog est plus souple pour des requêtes sur des combinaisons arbitraires, avec une implémentation via prologdex et Scryer Prolog
Pourquoi les règles de combat de Pokémon se prêtent à la programmation logique
- Les combats Pokémon ressemblent davantage à un moteur de règles où de nombreuses règles s’imbriquent de façon complexe, et la programmation logique comme Prolog est bien adaptée pour exprimer ce type de relations de manière concise
- Les Pokémon sont des créatures portant un nom d’espèce, et il en existe plus de 1 000, de Bulbasaur #1) à Pecharunt #1025)
- Dans les combats de la série principale, deux équipes de 6 Pokémon s’affrontent, et chaque Pokémon choisit en général l’une de ses 4 capacités — le plus souvent pour infliger des dégâts à l’adversaire —, la victoire revenant à l’équipe qui réduit à 0 tous les PV adverses
- Les performances en combat dépendent des statistiques de base, de la liste des capacités apprenables, des talents et du type, et le grand nombre de combinaisons rend leur suivi logiciel particulièrement utile
- Le type s’applique à la fois aux capacités et aux Pokémon, et lorsqu’un type de capacité est efficace contre le type adverse, il inflige 2x dégâts, et 1/2 s’il est peu efficace
- Les modificateurs de type se cumulent
- Scizor) est de type Bug/Steel, et comme ces deux types sont faibles face à Fire, il subit 4x dégâts des capacités Fire
- Si l’on utilise une capacité Electric contre Swampert) de type Water/Ground, les dégâts tombent à 0 à cause de l’immunité de Ground
Modèle de base de Prolog
- Dans Prolog, on déclare les relations avec des prédicats (predicate)
pokemon(bulbasaur).
pokemon(ivysaur).
pokemon(venusaur).
pokemon(charmander).
pokemon(charmeleon).
pokemon(charizard).
pokemon(squirtle).
pokemon(wartortle).
pokemon(blastoise).
pokemon/1 est un prédicat nommé pokemon avec un seul argument, et une requête comme pokemon(squirtle). vérifie s’il est possible de rendre cette proposition vraie
?- pokemon(squirtle).
true.
?- pokemon(alex).
false.
- Les types des Pokémon peuvent être représentés comme une relation à deux arguments avec
type/2, et pour un Pokémon ayant deux types, on place deux faits type pour ce même Pokémon
type(bulbasaur, grass).
type(bulbasaur, poison).
type(charmander, fire).
type(charizard, fire).
type(charizard, flying).
type(squirtle, water).
- Les noms commençant par une majuscule sont des variables, et Prolog tente d’unifier une requête contenant une variable avec toutes les valeurs possibles
?- type(squirtle, Type).
Type = water.
?- type(venusaur, Type).
Type = grass
; Type = poison.
- En mettant une variable dans le premier argument, comme dans
type(Pokemon, grass)., on peut retrouver tous les Pokémon de type Grass, et sur les données réelles cela renvoie 164 résultats
- Une virgule signifie que plusieurs prédicats doivent tous être satisfaits, et le même nom de variable doit prendre la même valeur dans toute la requête
?- 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.
- Comme pour Iron Bundle), on peut aussi interroger les relations portant sur les statistiques et les capacités apprenables
?- 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.
- En ajoutant une contrainte comme
SpA #> 120, on peut directement trouver les Pokémon dont la Special Attack dépasse 120, qui apprennent Freeze-Dry et qui sont de type Ice
?- 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.
- Les règles (rule) de Prolog se composent d’une tête et d’un corps, et si le corps est vrai, la tête s’unifie elle aussi
damaging_move(Move) :-
move_category(Move, physical)
; move_category(Move, special).
- Cette règle classe directement comme capacités offensives les capacités de catégorie Physical ou Special
?- damaging_move(tackle).
true.
?- damaging_move(rest).
false.
Expressions de requête comparées à SQL
- Jusqu’ici, les exemples sont logiquement de simples combinaisons de
and et or, mais dans Prolog, les requêtes relationnelles deviennent plus courtes et plus faciles à modifier qu’en SQL
- Avec les mêmes données en SQL, on peut séparer Pokémon, types et capacités dans des tables distinctes
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);
- Pour trouver en SQL les Pokémon de type Ice, avec une Special Attack supérieure à 120 et qui apprennent Freeze-Dry, il faut utiliser plusieurs
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'
);
- La requête Prolog équivalente énumère directement les relations nécessaires
?- pokemon_spa(Pokemon, SpA),
SpA #> 120,
learns(Pokemon, freezedry),
type(Pokemon, ice).
- À mesure qu’on ajoute des conditions, les requêtes SQL ont tendance à devenir complexes, alors que les requêtes Prolog restent faciles à lire et à modifier une fois qu’on s’est familiarisé avec le fonctionnement des variables
Empiler les règles de combat par couches
- Les combats Pokémon comportent de nombreuses règles d’interaction : échec de précision, hausse ou baisse des statistiques, effets des objets, plage de dégâts, altérations de statut, effets de terrain comme la météo, le terrain ou Trick Room, talents, répartition préalable des statistiques, etc.
- Quand on crée un logiciel pour Pokémon, il faut gérer cette complexité tout en gardant un modèle maîtrisable
- Prolog est particulièrement à l’aise avec un modèle de requête décrivant des combinaisons à la volée et avec une superposition cohérente des règles
- Le damage calculator permet de constater directement cette complexité
Draft league et requêtes sur les capacités à priorité
- En draft Pokémon, chaque Pokémon a une valeur définie, et les joueurs composent une équipe d’environ 8 à 11 Pokémon en les choisissant dans une limite de points donnée
- Comme les vrais combats se jouent en 6v6, il est important de préparer les combinaisons de six Pokémon que l’adversaire peut amener, puis de choisir les six qui y répondront
- Les Pokémon que l’on a draftés peuvent être représentés directement avec un prédicat comme
alex/1
alex(meowscarada).
alex(weezinggalar).
alex(swampertmega).
alex(latios).
alex(volcarona).
alex(tornadus).
alex(politoed).
alex(archaludon).
alex(beartic).
alex(dusclops).
- La requête pour trouver les Pokémon de cette équipe qui apprennent Freeze-Dry est simple, mais ne renvoie aucun résultat
?- alex(Pokemon), learns(Pokemon, freezedry).
false.
- L’ordre d’action en combat est déterminé par la Speed par défaut, mais les capacités ont aussi une priorité (priority), et une capacité de priorité plus élevée part d’abord
- La plupart des capacités ont une priorité de 0, mais une capacité de priorité 1 comme Accelerock passe avant une capacité de priorité 0 d’un Pokémon plus rapide
- On peut trouver les capacités à priorité positive qu’un Pokémon donné apprend en combinant
learns/2, move_priority/2 et une condition sur la priorité
- Une requête simple inclurait aussi des capacités surtout utiles en Double Battles comme Helping Hand ou Ally Switch, ainsi que des capacités peu pertinentes en pratique comme Bide
\+/1 est vrai quand l’objectif échoue, et dif/2 signifie que deux termes sont différents ; on peut donc ajouter une règle pour exclure les capacités de Double Battles et Bide
learns_priority(Mon, Move, Priority) :-
learns(Mon, Move),
\+ doubles_move(Move),
dif(Move, bide),
move_priority(Move, Priority),
Priority #> 0.
- Si l’on exclut aussi les capacités défensives comme Protect, Detect, Endure et Magic Coat, il ne reste que les capacités à priorité capables d’infliger des dégâts ou des effets négatifs à l’adversaire
?- 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.
- En appliquant la même règle au prédicat de l’équipe adverse, on peut immédiatement trouver aussi les capacités à priorité de l’adversaire
?- 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.
Extension du talent Prankster
- Les Pokémon dotés du talent Prankster obtiennent un bonus supplémentaire de +1 à la priorité des capacités de statut, et cet effet peut lui aussi être ajouté à la règle existante
learns_priority/3
- Dans l’équipe, Tornadus possède le talent Prankster
?- alex(Pokemon), pokemon_ability(Pokemon, prankster).
Pokemon = tornadus
; false.
- En utilisant la syntaxe if/then
->/2 de Prolog, on peut faire en sorte que si un Pokémon a Prankster et que la catégorie de la capacité est status, 1 soit ajouté à la priorité de base, sinon la priorité de base reste inchangée
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.
- Après cette règle, la même requête inclut les capacités de statut de Tornadus comme Agility, Defog, Nasty Plot, Rain Dance, Tailwind, Taunt et Toxic avec une priorité de 1
- En étendant une seule règle pour y intégrer l’effet d’un talent, on voit bien l’avantage du layering en Prolog
Contraste avec les outils basés sur des feuilles de calcul
- La communauté Pokémon dispose déjà de ressources pour trouver des informations comme les capacités prioritaires d’une équipe adverse, notamment des Google Sheets avancés comme « Techno’s Prep Doc »
- Cette feuille de calcul génère de nombreuses informations de matchup lorsqu’on y saisit une équipe, avec prise en charge de divers formats, supports visuels faciles à parcourir et autocomplétion
- La formule qui sert à trouver les capacités prioritaires combine
FILTER, VLOOKUP et INDIRECT, ce dernier renvoyant une référence de cellule
={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"))}
- La feuille Backend liste toutes les capacités, et cette structure se rapproche d’une version où les requêtes Prolog sont hardcodées
- Une base de données Prolog est plus extensible qu’une approche qui hardcode une liste de capacités notables, et permet d’interroger n’importe quelle capacité
- On peut aussi formuler brièvement des questions combinatoires absentes des outils existants, comme chercher les capacités
special apprises par Tornadus qui sont super efficaces contre les membres de l’équipe de 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.
Notes d’implémentation et limites
- Le code à reproduire est disponible dans le dépôt prologdex, avec un guide de configuration rapide
- L’implémentation Prolog utilisée est Scryer Prolog, une implémentation Prolog moderne qui met l’accent sur les standards et la rigueur formelle
- Comme ressources d’apprentissage, on peut consulter le livre en ligne de Markus Triska « The Power of Prolog » ainsi que la chaîne YouTube associée
- Scryer Prolog recommande l’usage d’une syntaxe qui préserve la complétude logique et la monotonie, donc l’utilisation de
\+/1 ou ->/2 ne correspond pas totalement à cette orientation recommandée
- Les données ont été converties en prédicats Prolog à l’aide de l’API NodeJS de Pokémon Showdown, et le script de conversion se trouve dans generate-dex.js
1 commentaires
Avis sur Lobste.rs
Je me demande s’il y a des gens qui utilisent réellement Prolog de manière productive. Que ce soit au travail ou pour des usages personnels, jusqu’ici je n’ai vu que ce genre d’exemples jouets
À strictement parler, j’ai aussi au moins un bout de code Prolog en production : un tableau de bord d’analyse interne, et auparavant j’avais même écrit le serveur backend d’une app iOS en Prolog. En faisant cela, j’ai aussi fini par créer une bibliothèque cliente HTTP/2 pour Prolog afin d’envoyer des notifications APNS sans service externe
Il y a clairement dans la communauté Prolog des gens qui aiment l’utiliser pour des choses comme des serveurs web, mais pour moi, c’est plutôt comme débloquer un autre arbre de compétences. Par exemple, je repère mieux quand un parseur sur mesure ou un DSL conviendrait bien à un problème
Avec les connaissances acquises en écrivant cet article, j’ai réimplémenté un sous-ensemble utile du moteur de logique fiscale d’IRS Fact Graph. Prolog convient étonnamment bien à ce travail, parce qu’il fait ressortir des recoins non documentés qu’une implémentation impérative laisserait facilement passer, et force à les résoudre
Je n’ai pas encore terminé la partie « exécution », mais l’analyse est suffisamment avancée pour que j’aie pu rédiger un assez bon premier jet de documentation. Il manque une grosse fonctionnalité, l’arithmétique sur les dates, et je compte la présenter séparément quand elle sera prête
Avec les DCG, Prolog est excellent pour analyser des textes structurés complexes. Avant, quand awk ne suffisait plus, je pensais à Python ou JS, mais maintenant Prolog me semble bien adapté là où il faut de la structure et de la discipline. J’aime aussi ce côté un peu old-school d’écrire une base de code complexe qui tient dans un seul fichier, sans être excessivement condensé comme APL
L’exemple en lui-même est trivial, mais le cas Pokémon ne l’est pas. Si la plupart des exemples apparemment triviaux sont possibles, c’est parce qu’il existe déjà du code qui implémente de façon extrêmement complète des mécaniques de combat ridiculement complexes. Je m’intéresse à la création d’un moteur de règles Prolog qui effectue une partie du travail des outils existants, et j’y expérimente petit à petit ; l’avantage est qu’avec une recherche en profondeur, il est plus facile de faire émerger les possibilités et de maintenir le tout qu’avec du code impératif
La documentation de Scryer Prolog est elle aussi générée par un programme Prolog que j’appelle DocLog. J’ai également créé quelques bibliothèques utilisées par ces programmes. SWI Prolog utilise aussi directement SWI pour son site web, son IDE web Swish, le serveur ClioPatria, etc.
J’ai déjà utilisé SQLite comme une sorte de tableur typé et sûr pour organiser des informations. C’était possible même sans aucune interface CRUD par-dessus
Cela dit, ce n’était pas toujours le langage le plus agréable à lire. J’ai aussi regardé Datalog pendant un moment, mais la plupart des implémentations semblaient davantage destinées à être embarquées dans de plus gros programmes qu’à servir d’outil simple pour enregistrer des informations comme dans cet article
Peut-être que Prolog est en fait l’outil qu’il faudrait utiliser
Prolog est un sur-ensemble de Datalog, donc il peut faire tout ce que fait Datalog, et plus encore. Mais ce « plus » peut parfois poser problème : on a alors un langage turing-complet, donc l’exécution peut ne jamais se terminer, le raisonnement peut devenir un peu plus difficile, et on peut aussi l’utiliser de façon non sûre
Datalog, grâce à ses restrictions, permet d’emprunter certains raccourcis, donc les performances sont souvent meilleures aussi
Enfin, dans Prolog, les données sont identiques au code, c’est-à-dire qu’il y a homoiconicité, donc les opérations de création/modification/suppression reviennent en pratique à modifier le code source. C’est possible dynamiquement aussi, mais il ne faut pas s’attendre à ce que le flux soit très fluide, et il reste un certain besoin de synchronisation manuelle entre les fichiers et le programme chargé
J’aimerais apprendre Prolog plus en profondeur pour l’utiliser sur des requêtes d’ensemble d’instructions
Mais modéliser de la logique en incluant des quantités et des entiers au niveau du bit est assez difficile