Was initially nonplussed, but toward the end I realized the choice of pokemon for an example actually works out well for showing how prologue can solve problems. I’m now a bit curious about trying it out somewhere.
Are there public tournaments of games like Pokemon where contestants have to compete with eachother using a specific class of algorithms (e.g., logic programming, neural nets, linear programming, etc.)?
It continues to be immensely surprising to me that Joe Armstrong was able to write the initial Erlang implementation in Prolog. I wish I’d asked him about getting a copy of the source code.
What does this say about Forth? Not much except that it isn't for me.
Take Prolog. I know few things more insulting than having to code in
Prolog. Whereas Armstrong developed Erlang in Prolog and liked it much
better than reimplementing Erlang in C for speed. I can't imagine how
this could be, but this is how it was. People are different.
from Yossi Kreinin's "My history with Forth & stack machines" [0]. Some people write APL and enjoy it. Some can't bear Lisp even after 10 years of working with it.
I’ve always heard the first wave of AI was all lisp. Why is that? Just cause it had superpowers over the other languages of the day?
I can see why someone would think prolog could bring an AI wave. Even after messing around with it for a few hours, I feel like there are things I could build in prolog that I couldn’t build in typescript.
In the Scryer Prolog discussions, Alex has shared a few ideas and considerations for possible improvements to the Prolog code, including the use of metaprogramming to automatically generate more general relations:
Love this use case, makes me want to implement something similar for Magic the Gathering. I love using scryfall, but I think a more cli first approach with descriptive rules would suffice much better for brewing in eternal formats like Commander with ever growing card pools. I mostly work off of keyword search.
This might be your jam. I should revisit this, most of it is unimplemented. But the parsing part was interesting, since MTG has such a codified language for explaining the rules. My idea here was to take a card's rules text from the official API and parse it into smth that can be used in the game, so you could keep up with new sets with implementation. The weird rule-breaking edge cases will always fail, but a large set of design space can fit, I think.
>> The weird rule-breaking edge cases will always fail, but a large set of design space can fit, I think.
Well, in that case you just update the parser or the rules engine. That's precisely how M:tG Arena works and they 've managed to keep up with new sets at a pace never before seen in official M:tG engines. There was a time when writing an M:tG parser was considered impossible [1] and M:tG engines, both official and community ones, each had their own little DSL that they had to manually translate ability text into which could take months especially if the engine also had to be updated to use the new rules in a set. Eventually someone in Wizards realised this is just dumb and they did it the way you go about it above.
______________
[1] Source: my conversations with the folks behind Forge and other community-made M:tG engines.
Somewhat related, check out https://github.com/wordbots/wordbots-parser, a digital card game where you write the cards and the engine parses them to determine what they do. It's fun to mess around with.
> "Don't be bothered with by the fact that the solutions end with "or false" here. It's a function of how the search algorithms work; the solver looked for more solutions, then failed. I'll admit, I don't totally understand why it only sometimes does this, but it's expected."
I think this is explained in The Power of Prolog[1] that the answers coming from Prolog are not printing text to a terminal, they are valid Prolog terms(/data/code). That's why the result uses the same `;` for OR as code does. Answer (x ; y ; false) is "query can be answered by x or y or no other answer found". (This would let you do meta-programming, reasoning about the results and rewriting the results in a LISPy data-as-code way, if you were more advanced than I am).
Prolog systems do optimisations to jump to the correct answer without searching, if they can, (e.g. database style indexing on the facts and rules) and in those cases there is no code left to search after showing the first answer, no need to prompt the user "should I search for more answers in the remaining code?", and so no need for an output "false" to say "I finished searching and found no more solutions".
This embodies why I don't like Prolog. Prolog's philosophy is that you should just write the predicates without thinking about how the engine works. But as soon as you do something actually complicated, you realize that the different optimization modes of the engine give different results, and shortly after that you'll find yourself in the "exhaustively try every possible combination until we get one that satisfies the predicates" mode, and your code will go from taking 1 second to run to taking 8 days.
And because you don't control the engine (you're not supposed to think about it, after all), there's nothing you can do but rewrite the whole thing in a traditional programming language.
Eh, no, admittedly this is a bit confusing but the ";" at the top-level is not the same as the ;/2 disjunction operator. At the top-level the ";" is just a switch to say "give me more". In most Prolog systems you can also press space for the same thing.
Whether a query will end with "false" or "true" really depends entirely on the query, and the predicates it's calling. So it depends on how a predicate is called. You just have to analyse the predicate in the good, old-fashioned way of eyballing it and maybe running it a couple of times to see why it fails or succeeds, and why it first succeeds and then fails like above.
This is really all down to determinism, which is to say, whether a predicate leaves behind a choice point or not. In this particular case, what's going on can be revealed by looking at the trace of the query. For the following, I loaded the Pokemon database from https://github.com/alexpetros/prologdex/blob/main/src/dex/po...) into SWI-Prolog and traced it like this:
Now, if you squint real hard you'll see that the Prolog engine first unifies the variable 'Pokemon' with the name of a Pokemon, "squirtle". That happens to be the first pokemon in the database that has "water" as the type. Basically the engine looks for a type/2 fact where the second argument is "water" and finds type('squirtle', 'water') first.
In the second call... I mean this one:
Call: (15) dex:type(squirtle, ice) ? creep
The engine looks for a fact that would satisfy the second goal in the top-level query. This is the top-level query:
Since "Pokemon" is already bound to "squirtle", the engine tries to satisfy the fact
type(squirtle, ice)
It can't, so it fails. And then it repeats with the second water pokemon in the list, which is wartotrtle.
What happens when the engine finds a pokemon that is both water and ice? The first one in the database is dewogong, at which point the tracer goes like this:
So this time both goals in the top-level query are satisfiable and the engine returns the name of the value of "Pokemon" that makes the query true (well, satisfiable).
At that point the "." means I pressed "enter" and that's basically saying "no more thank you". I was getting a little impatient. If I had pressed ";" (or space) instead, we'd have a repeat of the previous pattern with successive failures until another water and ice pokemon was found. The next one in the database is cloyster, and so it goes.
That back-and-forth between success and failure goes on until we run out of pokemon. At some point the engine can't unify either goal of the top-level query with a fact in the database so the final result is "false"; because after succeeding a bunch of times, it ca...
Are those the results of a disjunction? I think it's clear that not: our rule says that "sam likes X if X is a fruit, for all X"; "for all" because in Prolog every variable is implicitly universally quantified. So the interpretation of the results of the query is:
sam likes apples AND sam likes oranges AND sam likes bananas
Not:
sam likes apples OR sam likes oranges OR sam likes bananas
Sam likes all the fruit! The different values of X are not disjuncts, they're conjuncts.
All that'll probably get me lynched because it flies in the face of a lot of fudging perpetrated by Prolog courses and even some textbooks that should know better, and that tell you that e.g. a set of rules is like an if-then-else and that when you get more results at the top-level those are alternatives. That's just wrong and I don't know why people teach Prolog like this, all it does is confuse students and make them hate Prolog more, but the formal definition of a logic program is that it's a conjunction of definite program clauses; where a definite program clause is a ... clause, therefore a disjunction. So a logic program is a conjunction of disjunctions, i.e. basically a formula in conjunctive normal form.
So the ";" that appears automatically at the end of your query when you press space is not an "OR", otherwise it wouldn't appear when the results of the query are the members of a conjunction. What is it then?
Try this. Instead of pressing ";" after the first result of your query (after the X = 1) press "h" for "help". On SWI-Prolog you'll get this menu:
?- X = 1 ; X = 2.
X = 1
Possible actions:
; (n,r,space,TAB): redo | t: trace&redo
*: show choicepoint | . (c,a,RET): stop
w: write | p: print
+: max_depth*5 | -: max_depth//5
b: break | h (?): help
Action?
Thus finally* revealing the meaning of ";" at the top-level: it instructs the listener (i.e. the Prolog REPL) to enter the redo port. The ";" at the top-level means "redo" not "OR".
And that's true even in your query which is explicitly formulated as a disjunction. With an ";". It's confusing.
SELECT DISTINCT pokemon, 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'
);
Hmm. I wonder if this
SELECT DISTINCT pokemon, special_attack
FROM pokemon as p
NATURAL JOIN pokemon_moves as pm
NATURAL JOIN pokemon_types as pt
WHERE
p.special_attack > 120 AND
pm.move = 'freezedry' AND
pt.type = 'ice'
;
A while ago I was playing the romhack Run&Bun, which drastically ups the difficulty of Pokemon Emerald. Watching others play, most of the game was doing 'calcs': calculating how to approach a battle. This was done using a javascript frontend to a simulator, and a lot of excel sheets.
My runs died pretty early, but there are some notes here as I was implementing that are fun to read. I implemented each battle as a test case and let my solver find a solution, then amended the plan and commented on what actually happened. For example: https://github.com/deosjr/runbuncalc/blob/master/run10.pl#L2...
33 comments
[ 3.1 ms ] story [ 45.5 ms ] thread[0] https://yosefk.com/blog/my-history-with-forth-stack-machines...
https://github.com/mthom/scryer-prolog/discussions/3322
and also in the course of a discussion on various approaches to implement concurrency in Prolog:
https://github.com/mthom/scryer-prolog/discussions/3307
I can see why someone would think prolog could bring an AI wave. Even after messing around with it for a few hours, I feel like there are things I could build in prolog that I couldn’t build in typescript.
Do you have an Odin tutorial that's as easy to digest?
Sol
In the Scryer Prolog discussions, Alex has shared a few ideas and considerations for possible improvements to the Prolog code, including the use of metaprogramming to automatically generate more general relations:
https://github.com/mthom/scryer-prolog/discussions/3221
I hope for an interesting followup article!
Another very interesting Prolog program by Alex is factgraph.pl:
https://github.com/alexpetros/factgraph.pl
It's a Prolog implementation of the IRS Fact Graph, an application of Law as Code.
See https://github.com/deosjr/pmtg/blob/master/parse.pl
https://github.com/stassa/Gleemin
Although the code is nigh-on unreadable now ^_^@
>> The weird rule-breaking edge cases will always fail, but a large set of design space can fit, I think.
Well, in that case you just update the parser or the rules engine. That's precisely how M:tG Arena works and they 've managed to keep up with new sets at a pace never before seen in official M:tG engines. There was a time when writing an M:tG parser was considered impossible [1] and M:tG engines, both official and community ones, each had their own little DSL that they had to manually translate ability text into which could take months especially if the engine also had to be updated to use the new rules in a set. Eventually someone in Wizards realised this is just dumb and they did it the way you go about it above.
______________
[1] Source: my conversations with the folks behind Forge and other community-made M:tG engines.
I think this is explained in The Power of Prolog[1] that the answers coming from Prolog are not printing text to a terminal, they are valid Prolog terms(/data/code). That's why the result uses the same `;` for OR as code does. Answer (x ; y ; false) is "query can be answered by x or y or no other answer found". (This would let you do meta-programming, reasoning about the results and rewriting the results in a LISPy data-as-code way, if you were more advanced than I am).
Prolog systems do optimisations to jump to the correct answer without searching, if they can, (e.g. database style indexing on the facts and rules) and in those cases there is no code left to search after showing the first answer, no need to prompt the user "should I search for more answers in the remaining code?", and so no need for an output "false" to say "I finished searching and found no more solutions".
[1] https://www.metalevel.at/prolog
And because you don't control the engine (you're not supposed to think about it, after all), there's nothing you can do but rewrite the whole thing in a traditional programming language.
Whether a query will end with "false" or "true" really depends entirely on the query, and the predicates it's calling. So it depends on how a predicate is called. You just have to analyse the predicate in the good, old-fashioned way of eyballing it and maybe running it a couple of times to see why it fails or succeeds, and why it first succeeds and then fails like above.
This is really all down to determinism, which is to say, whether a predicate leaves behind a choice point or not. In this particular case, what's going on can be revealed by looking at the trace of the query. For the following, I loaded the Pokemon database from https://github.com/alexpetros/prologdex/blob/main/src/dex/po...) into SWI-Prolog and traced it like this:
Now, if you squint real hard you'll see that the Prolog engine first unifies the variable 'Pokemon' with the name of a Pokemon, "squirtle". That happens to be the first pokemon in the database that has "water" as the type. Basically the engine looks for a type/2 fact where the second argument is "water" and finds type('squirtle', 'water') first.In the second call... I mean this one:
The engine looks for a fact that would satisfy the second goal in the top-level query. This is the top-level query: And this is the second goal in it: Since "Pokemon" is already bound to "squirtle", the engine tries to satisfy the fact It can't, so it fails. And then it repeats with the second water pokemon in the list, which is wartotrtle.What happens when the engine finds a pokemon that is both water and ice? The first one in the database is dewogong, at which point the tracer goes like this:
So this time both goals in the top-level query are satisfiable and the engine returns the name of the value of "Pokemon" that makes the query true (well, satisfiable).At that point the "." means I pressed "enter" and that's basically saying "no more thank you". I was getting a little impatient. If I had pressed ";" (or space) instead, we'd have a repeat of the previous pattern with successive failures until another water and ice pokemon was found. The next one in the database is cloyster, and so it goes.
That back-and-forth between success and failure goes on until we run out of pokemon. At some point the engine can't unify either goal of the top-level query with a fact in the database so the final result is "false"; because after succeeding a bunch of times, it ca...
I understand that's the experience of using it, but I mean if I open the SWI Prolog toplevel and query:
Then press space, I get: which is exactly the same Prolog term, two unifications, each is a solution to the query, a disjunction between them, terminated with a full stop.Is that really not the same semicolon usage/meaning/semantics in the query as in the answers?
All that'll probably get me lynched because it flies in the face of a lot of fudging perpetrated by Prolog courses and even some textbooks that should know better, and that tell you that e.g. a set of rules is like an if-then-else and that when you get more results at the top-level those are alternatives. That's just wrong and I don't know why people teach Prolog like this, all it does is confuse students and make them hate Prolog more, but the formal definition of a logic program is that it's a conjunction of definite program clauses; where a definite program clause is a ... clause, therefore a disjunction. So a logic program is a conjunction of disjunctions, i.e. basically a formula in conjunctive normal form.
So the ";" that appears automatically at the end of your query when you press space is not an "OR", otherwise it wouldn't appear when the results of the query are the members of a conjunction. What is it then?
Try this. Instead of pressing ";" after the first result of your query (after the X = 1) press "h" for "help". On SWI-Prolog you'll get this menu:
Thus finally* revealing the meaning of ";" at the top-level: it instructs the listener (i.e. the Prolog REPL) to enter the redo port. The ";" at the top-level means "redo" not "OR".And that's true even in your query which is explicitly formulated as a disjunction. With an ";". It's confusing.
_______________
* I know, sorry.
Prolog must be an adult programming language :)
So I forked the calculator and added a Prolog wrapper so I could find solutions to battles based on the team of Pokemon that I caught. https://github.com/deosjr/runbuncalc/blob/master/main.pl
My runs died pretty early, but there are some notes here as I was implementing that are fun to read. I implemented each battle as a test case and let my solver find a solution, then amended the plan and commented on what actually happened. For example: https://github.com/deosjr/runbuncalc/blob/master/run10.pl#L2...