Pokémon으로 설명하는 Prolog 기초

(unplannedobsolescence.com)

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개의 기술 중 하나를 선택하고 상대 팀의 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이고 인수가 하나인 술어이며, pokemon(squirtle). 같은 질의는 해당 문장을 참으로 만들 수 있는지 확인함

?- pokemon(squirtle).
   true.

?- pokemon(alex).
   false.

Pokémon 타입은 type/2처럼 두 인수의 관계로 표현할 수 있고, 두 타입을 가진 Pokémon은 같은 Pokémon에 대해 type 사실을 두 개 둠

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).처럼 첫 번째 인수를 변수로 두면 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이므로, 상대가 가져올 수 있는 여섯 마리 조합을 대비하고 그에 맞설 여섯 마리를 고르는 준비가 중요함
자신이 뽑은 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는 두 항이 다르다는 뜻이므로, 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.

Prankster 특성 확장

Prankster 특성을 가진 Pokémon은 상태 기술의 우선도가 추가로 +1 되며, 이 효과도 기존 learns_priority/3 규칙에 더할 수 있음
팀 안에서는 Tornadus가 Prankster 특성을 가짐

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

Prolog의 ->/2 if/then 구문을 사용해, Pokémon이 Prankster이고 기술 분류가 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로 포함함
규칙 하나를 확장해 특성 효과까지 반영할 수 있어 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 도구가 못 하는 웹앱을 만들려면 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에 있음

▲

GN⁺ 2시간전 [-]

Lobste.rs 의견들

Prolog을 실제로 생산적으로 쓰는 사람이 있는지 궁금함. 업무든 개인 용도든 괜찮고, 지금까지는 이런 장난감 예제만 봤음
- Prolog을 꽤 좋아하고, 아마 가장 널리 쓰이는 Prolog 언어 서버 구현을 만든 사람으로서, 자잘한 스크립팅에 많이 씀
  엄밀히는 운영 중인 Prolog 코드도 하나 이상 있는데, 내부 분석 대시보드가 그렇고, 예전에는 iOS 앱의 백엔드 서버도 Prolog로 작성했음. 그 과정에서 외부 서비스 없이 APNS 알림을 보내려고 Prolog용 HTTP/2 클라이언트 라이브러리도 만들게 됨
- 만족스러운 답이 될지는 모르겠지만, 이 블로그 글을 쓴 뒤로는 예전 코드와 완전히 다른 축의 문제에서 Prolog을 꺼내 쓰게 됨
  Prolog 커뮤니티에는 웹 서버 같은 데 쓰는 걸 좋아하는 사람도 분명 있지만, 개인적으로는 다른 스킬 트리를 여는 느낌에 가까움. 예를 들어 어떤 문제에 맞춤 파서나 DSL이 잘 맞을지 더 잘 알아보게 됨
  이 글을 쓴 뒤 얻은 지식으로 IRS Fact Graph의 세금 로직 엔진 중 유용한 부분집합을 다시 구현했음. Prolog은 이 작업에 놀라울 정도로 잘 맞는데, 명령형 구현으로는 그냥 넘어가기 쉬운 문서화 안 된 구석을 드러내고 해결을 강제하기 때문임
  “실행” 부분은 아직 완성하지 못했지만, 파싱은 충분히 끝나서 꽤 괜찮은 문서 초안을 쓸 수 있었음. 큰 기능 하나인 날짜 산술이 빠져 있고, 그게 들어가면 따로 정리할 예정
  DCG를 쓰면 Prolog은 복잡한 구조화 텍스트 파싱에 훌륭함. 예전에는 awk로 감당 안 되면 Python이나 JS를 떠올렸지만, 이제는 구조와 규율이 필요한 곳에서 Prolog이 잘 맞음. 한 파일에 들어가는 복잡한 코드베이스를 쓰는 구식 느낌도 만족스럽고, APL처럼 지나치게 축약적이지도 않음
  예제 자체는 사소하지만 Pokémon 사례는 그렇지 않음. 사소해 보이는 예제 대부분도 우스울 만큼 복잡한 전투 메커니즘을 매우 철저히 구현한 코드가 이미 있어서 가능했음. 기존 도구가 하는 일 일부를 수행하는 Prolog 규칙 엔진을 만드는 데 관심이 있고 조금씩 시도도 했는데, 장점은 명령형 코드보다 깊이 우선 탐색으로 가능성을 더 쉽게 드러내고 유지보수하기 좋다는 데 있음
- 프로그램 분석에 가끔 사용했음. 꽤 많은 도구가 Datalog로 프로그램 정보를 저장하고 그 위에 질의를 쓰게 해주는데, 가끔은 실제 SWI-Prolog를 제공하는 도구를 써서 백트래킹이나 함수를 활용함
- 내 블로그는 Prolog로 생성되고, 소스 코드도 공개돼 있음
  Scryer Prolog 문서도 DocLog라고 부르는 Prolog 프로그램으로 생성됨. 이 프로그램들이 쓰는 라이브러리도 몇 개 만들었음. SWI Prolog도 자기 웹사이트, Swish라는 웹 IDE, ClioPatria 서버 등에서 SWI를 직접 씀
SQLite를 일종의 타입 안전 스프레드시트처럼 써서 정보를 정리해 본 적이 있음. 그 위에 CRUD 인터페이스가 전혀 없어도 가능했음
다만 항상 가장 보기 좋은 언어는 아니었음. Datalog도 한동안 살펴봤지만, 대부분 구현체가 이 글처럼 손쉽게 정보를 기록하는 도구라기보다 더 큰 프로그램에 내장하는 용도로 보였음
어쩌면 Prolog이 실제로 써야 할 도구일지도 모름
- 외부 데이터베이스 형태의 Datalog로는 Mangle과 Datomic이 있어서 맞을 수도 있지만 직접 써본 적은 없음
  Prolog은 Datalog의 상위집합이라 Datalog가 하는 일은 전부 할 수 있고 그 이상도 가능함. 다만 그 “이상”이 문제가 될 때가 있는데, 이제 튜링 완전 언어라 끝나지 않을 수 있고, 추론이 조금 더 어려워질 수 있으며, 안전하지 않은 방식으로 쓰일 수도 있음
  Datalog는 제약이 있는 덕분에 지름길을 쓸 수 있어서 성능도 더 나은 경우가 많음
  마지막으로 Prolog에서는 데이터가 코드와 같아서, 즉 동형 코드성이 있어서, 생성/수정/삭제 작업이 사실상 소스 코드를 바꾸는 일이 됨. 동적으로도 가능하긴 하지만 흐름이 매끄럽다고 기대하긴 어렵고, 파일과 로드된 프로그램 사이에 어느 정도 수동 동기화가 여전히 필요함
Prolog을 더 깊게 배워서 명령어 집합 질의에 써보고 싶음
하지만 수량과 비트 수준으로 본 정수를 포함해 논리를 모델링하는 일은 꽤 어려움

답변달기

Pokémon으로 설명하는 Prolog 기초

Pokémon 전투 규칙이 논리 프로그래밍에 맞는 이유

Prolog 기본 모델

SQL과 비교되는 질의 표현

전투 규칙을 층층이 쌓는 방식

드래프트 리그와 우선도 기술 질의

Prankster 특성 확장

스프레드시트 기반 도구와의 대비

구현 메모와 한계

함께 보면 좋은 글 β

Lobste.rs 의견들