Logic programming in general and miniKanren specifically

[tuturto]

I tried searching the forum for topic about logic programming and not many popped up. Numeron mentioned a blog about his game that does use it, but the topic is old and the link was dead. Has there been others who has done anything roguelike related with logic programming?

miniKanren (http://minikanren.org/) is an embedded DSL for logic programming. I'm using Adderall (https://pypi.python.org/pypi/adderall/0.1.1), which is pretty new implementation. So far I haven't done anything that special, mainly just been trying to learn the new thing. I wrote about it at: http://engineersjourney.wordpress.com/2014/06/18/manipulating-levels-in-adderall/

I'm thinking that level generation and some AI routines could benefit from logic programming. Maybe even things like when a trap will trigger, if the conditions are sufficiently complex. Would there be other areas where this thing would be well suited?

[mushroom patch]

It's something I thought about a long time ago. I was interested in NPC behavior/planning and knowledge representation.

I don't know of any examples of logic programming in roguelikes (although I'm sure they exist), but I know of roguelike developers who know something about logic programming. Would you be willing to say more about what you have in mind with respect to logic programming in level generation? ([edit:] Presumably your blog has this information, but unfortunately I'm stuck in a country where wordpress is blocked =\)

[tuturto]

One angle is that I would like to write goals for placing dungeon features inside of rooms. For example: "don't place traps right in front of doors", "have guards to stand at choke points between walls and other obstacles".

The more interesting one is placement of whole rooms. I divide levels into sections that are then connected together to form a graph. Then I fill in rooms and corridors that make actual level layout.
I would like to be able to write things like:

"place starting stairs in a dead end"
"place exit stairs in another dead end, as far as from the first one as possible"
"place big battle, next to room with exit stairs"
"placed locked door somewhere in between big battle and starting location"
"if possible, place key to dead end between locked door and starting location"
"if previous is not possible, place key to somewhere between locked door and starting location"

and so on. I could have multiple goal sets and then randomly pick some to see if they can be used in current layout and then choose one of them.

There are multiple question marks with this, one of the biggest being "is this a correct tool for the task?". Another approach could be constraint propagator as explained by James King in https://www.youtube.com/watch?v=DZl2ebl_Pnw, but I was thinking of giving miniKanren a try, since it's so different of what I have done previously.

[Numeron]

Heyo, it seems like I might be a good person to join this thread since I'm mentioned in the OP

Yeah, my old blogspot is long gone sorry, but I do have some scraps from that project.

I wanted to be able to design an AI using an easy tile drop interface that could be used by non programmers. If you build something you think is intelligent enough, you can then watch your brain battle through some preset scenario or duel another person's brain.

The interface would have been something like this:



I lost my notes on what that program does, but I remember the first bit:

Starting from the GO tile, you move down into an IF with internal settings PLAYER HEALTH < 30. If true, then go right else go down. To the right the next IF will have something like PLAYER HEALTHPOTION >= 1, and if so right again to use it, otherwise down to continue the original thread.

I can't remember the rest exactly, but I'm pretty sure it goes on to check whether a target has been set and if so move towards/attack it, possibly move away if still on low health. Try and set a new target, otherwise go wandering etc. Standard AI stuff. Other settings for the IF blocks include checking whether a target is set, or whether things exist in the FOV, and so on. The target tile sets the target, the FUNC tile lets you jump between places if one area of the setup gets too crowded. The SET tile allows you to store variables between turns that can be referred to in IFs.

And of course it can all be expanded to rational use of spells and abilities, and working with others in a team (for example a brain designed for a warrior unit will charge through, while another designed for a priest body will follow the warrior healing and staying out of trouble)

As for the logic part of things, I had a flow diagram of how to manage the IF blocks, and work through what needed to be done in standard order of precendence. So you could, if you wanted to, combine the first two IFs into one by adding an AND operator inside of it.

Looking back at this makes me want to make this game all over again haha.

[mushroom patch]

One angle is that I would like to write goals for placing dungeon features inside of rooms. For example: "don't place traps right in front of doors", "have guards to stand at choke points between walls and other obstacles".

The more interesting one is placement of whole rooms. I divide levels into sections that are then connected together to form a graph. Then I fill in rooms and corridors that make actual level layout.
I would like to be able to write things like:

"place starting stairs in a dead end"
"place exit stairs in another dead end, as far as from the first one as possible"
"place big battle, next to room with exit stairs"
"placed locked door somewhere in between big battle and starting location"
"if possible, place key to dead end between locked door and starting location"
"if previous is not possible, place key to somewhere between locked door and starting location"

and so on. I could have multiple goal sets and then randomly pick some to see if they can be used in current layout and then choose one of them.

There are multiple question marks with this, one of the biggest being "is this a correct tool for the task?". Another approach could be constraint propagator as explained by James King in https://www.youtube.com/watch?v=DZl2ebl_Pnw, but I was thinking of giving miniKanren a try, since it's so different of what I have done previously.

I see. So perhaps what you have in mind is first running some procedure that generates a basic dungeon layout without a lot of structure and features a priori, then running some kind of analysis procedure to produce a set of geographical facts about your layout (e.g. it has a dead end at some location, the distances between various points of interest, etc.), then using some logic engine to apply a set of rules using these facts to generate instructions to fill out features like stairs. I wonder if this is significantly simpler or better than coding if-else ladders by hand. It quite possibly is. Probably more data-oriented anyway.

The general idea of replacing code for decision making, which is often quite complicated (or isn't complicated and results in boring decision making), with code that computes some relevant facts then hands them off to a logic engine seems nice to me. The question is whether this really reduces the complexity or length of code.

[miki151]

I use constraints and attributes in level generation, though without any logic engine. Every tile contains a set of attributes, and every generator can add and remove attributes from a tile after doing its work. I can set constraints on where a generator will work, for example for a village generator I use and(not(MOUNTAIN), not(LAKE)). Some generators take constraints as arguments, for example for placing NPCs (usually empty tile).

There is a natural order to use the generators, typically: terrain, buildings, NPCs, items, etc, so I don't see any need for a logic engine here, but I may be wrong. I can easily implement stuff like:

"place starting stairs in a dead end"
"place exit stairs in another dead end, as far as from the first one as possible"
"place big battle, next to room with exit stairs"
"placed locked door somewhere in between big battle and starting location"
"if possible, place key to dead end between locked door and starting location"
"if previous is not possible, place key to somewhere between locked door and starting location"

You can read a little on how I designed the level generation system here:
http://keeperrl.com/index.php?option=com_content&view=article&id=20&Itemid=102

[tuturto]

Heyo, it seems like I might be a good person to join this thread since I'm mentioned in the OP

Yeah, my old blogspot is long gone sorry, but I do have some scraps from that project.

I wanted to be able to design an AI using an easy tile drop interface that could be used by non programmers. If you build something you think is intelligent enough, you can then watch your brain battle through some preset scenario or duel another person's brain.

Looking back at this makes me want to make this game all over again haha.

That AI editor looks totally sweet. One could easily build a game around just that. It's not quite what I had in my mind when I was asking about logic programming though. I'm more after thing where you specify goals and constraints and computer then figures out how to fullfil them. Or where you have a given situation and you want to check if it fulfills are the specified goals.

I see. So perhaps what you have in mind is first running some procedure that generates a basic dungeon layout without a lot of structure and features a priori, then running some kind of analysis procedure to produce a set of geographical facts about your layout (e.g. it has a dead end at some location, the distances between various points of interest, etc.), then using some logic engine to apply a set of rules using these facts to generate instructions to fill out features like stairs. I wonder if this is significantly simpler or better than coding if-else ladders by hand. It quite possibly is. Probably more data-oriented anyway.

The general idea of replacing code for decision making, which is often quite complicated (or isn't complicated and results in boring decision making), with code that computes some relevant facts then hands them off to a logic engine seems nice to me. The question is whether this really reduces the complexity or length of code.

That's the basic idea. I'll generate a graph that tells me how rooms are connected and then let the logic engine try and figure out the rest. It probably makes goals easier to understand at high level, but their actual implementation probably will be harder to understand, especially since this is radically different to what I have ever done before.

If I were to use those goals only in one or two problems, the effort for writing them would be too much when compared to the results. But if I could use the same routines for figuring out where melee and ranged fighters want to position themselves during combat or how to place some other dungeon features it might make sense.

I use constraints and attributes in level generation, though without any logic engine. Every tile contains a set of attributes, and every generator can add and remove attributes from a tile after doing its work. I can set constraints on where a generator will work, for example for a village generator I use and(not(MOUNTAIN), not(LAKE)). Some generators take constraints as arguments, for example for placing NPCs (usually empty tile).

There is a natural order to use the generators, typically: terrain, buildings, NPCs, items, etc, so I don't see any need for a logic engine here, but I may be wrong.

You can read a little on how I designed the level generation system here:
http://keeperrl.com/index.php?option=com_content&view=article&id=20&Itemid=102

That posting was interesting to read. But if I understood correctly, you can go only to one direction? After a generator has finished the given task, results of that task are final, unless some other generator overwrites them?

This is some pseudo-code that I wrote to highlight what I'm after:

Code: [Select]

(run 5 [q]
  (fresh [chest trigger boulder dart-trap]
    (next-toᵒ chest trigger)
    (straight-lineᵒ trigger boulder)
    (in-angleᵒ chest trigger boulder)
    (condᵉ
      [(long-distanceᵒ trigger boulder)]
      [(medium-distanceᵒ trigger boulder)])
    (next-toᵒ boulder dart-trap)
    (≡ #t(chest trigger boulder dart-trap) q))))

I'm after maximum of 5 solutions to a problem where:
 - there is a chest and next to it there is a trigger
 - in a straight line from trigger, there is a boulder
 - chest, trigger and boulder form an angle (so the rolling boulder will roll over trigger, but not break the chest)
 - trigger and boulder are either long or medium distance from each other (preference to long distance)
 - next to boulder there is a dart trap
 - result of all this is a list of locations for chest, trigger, boulder and dart-trap

For example, if the initial placement of the chest is such that not all goals can be satisfied, a new location is considered and process starts from beginning. I could also fix the position of chest (or any other components) before starting and let the routine figure out the rest.

But all this is pretty far-fetched currently. I'm still learning how to write goals and programs and how to overcome even simplest problems.

[miki151]

But if I understood correctly, you can go only to one direction? After a generator has finished the given task, results of that task are final, unless some other generator overwrites them?

Yes, but there is a 'meta-generator', which takes a list of generators and area sizes and tries to place them on the level according to some constraints. For now the constraints are min and max distances between the areas and predicates on the tiles where they are placed, but I can easily add things like angles from your example.

This 'meta-generator' has a limited number of tries, after that it throws an exception. Normally I retry the whole world generation when that happens, but I could easily catch it earlier and make a 'if not possible then try this' generator.

[tuturto]

Yes, but there is a 'meta-generator', which takes a list of generators and area sizes and tries to place them on the level according to some constraints. For now the constraints are min and max distances between the areas and predicates on the tiles where they are placed, but I can easily add things like angles from your example.

This 'meta-generator' has a limited number of tries, after that it throws an exception. Normally I retry the whole world generation when that happens, but I could easily catch it earlier and make a 'if not possible then try this' generator.

Right, then it can achieve the exact same result. Sounds pretty nifty approach.

[reaver]

Rerunning the whole world generation if a couple constraints (or sub-generators) fail sounds costly! A more fine-grained approach would be to run your constraints on room shapes and find ones that you're happy with. Then you could constrain your level to accommodate one of those room shapes. I think this two-level approach would be much faster compared to the whole world generation retry-on-exception approach.

[Zireael]

That AI generator does indeed look spiffy!

[mushroom patch]

So I guess I believe that using a logic engine with some updating fact database and rules for making decisions via a logic engine is more maintainable and maybe even easier than ad hoc if-else ladders for every decision process. For relatively infrequent computations, like dungeon generation, there's probably no performance issue, but is this kind of thing really a viable option for something like monster AI? There's no way a logic engine is going to do these kinds of computations as fast as a custom if-else ladder, but how much slower is it?

It seems pretty clear to me that you wouldn't be using a logic engine to do anything very involved (e.g. pathfinding) but just to make high-level decisions, like perhaps whether to run or hide. If you're not making these decisions every turn, maybe it's okay. Any thoughts on that?

[tuturto]

Using logic engine is pretty much always slower than custom written algorithm. Getting started is much harder, but as soon as you have the goals written down, it gets much easier. It might be viable for monster AI, depending on how big problem space you have and how much other stuff is going on at the same time. I haven't had any performance problems, yet, but I'm just getting started. Pathfinding probably isn't one of those problems where this would shine, but higher level decisions like you said sounds much better.

Results are also deterministic, miniKanren program will always give the same results, as far as I have understood it. That's part of the reason I'm planning to generate high-level topography of the level with other means.

The power really comes from how short and clear the programs are: input, bunch of rules and output. If you can describe something in terms of those goals, you can generate those things from scratch, or take pre-existing situation and fill the blanks or check if a given situation satisfies the goals. Another big advantage is that the engine knows how to try different combinations. If it doesn't succeed at first, it will keep trying until required amount of solutions have been found or the problem space has been fully covered.

[mushroom patch]

I took a look at a python (the only thing I'm willing to write anything in these days) logic package linked from the minikanren page (not the one you mentioned). It looks like it uses native python datastructures (e.g. nested tuples) as its "syntax," which seems quite nice. I guess the way this kind of thing would go is you initiate a decision process, which determines some information requirements to proceed, then you hand this off somewhere to grab or compute these prerequisites, then you pass the information to the logic engine rules and see what happens.

For something like monster AI, you probably can't expect to run a process like this every turn for every monster. It's probably doable using some combination of group AI and heuristics to cut decision making down to turns when something interesting has happened will likely alter the decision calculus. Obviously, you'd want to keep this relatively abstract. It shouldn't be deciding how to escape a situation, only whether to (and whether or not there is a viable method of escape and what it is should be computed elsewhere).

On a tangentially related note, this Hy thing seems pretty interesting. I always liked lisp, but never really got into it because it's too far from the kinds of things I already use, but a python-based lisp seems to blow that up. Is Hy any good?

[tuturto]

I haven't gotten any experience with other miniKanren implementations. I did play around with pyDatalog, which is sort of similar, but completely different package. But with that I couldn't even get started. With miniKanren I know how to check if something is in a list or not

For monster AI it probably doesn't make sense to run logic program on each and every turn. But you could use it for high level decision making (fight or run?) or maybe even deciding what kind of formation your monsters would like to form before attacking.

I might also work in cases where you have complex combinations of rules and would like to keep the code as small as possible still. Like:

 - a character who steps on pit fill fall down
 - character with activated levitation spell will not fall down
 - activated levitation spell will deactivate in null magic zone
 ...
 - will this character fall down or not? (dealing with character stepping on the pit)
 - how can I fly across the pit, give me 10 different solutions? (in case you're dealing with monster AI)

Maybe, not sure about the example and if it makes sense or not. I'm still working my way through "The Reasoned Schemer", which is a tutorial/guide written about miniKanren. It's probably the hardest book I have read in a long time, and I'm not even halfway done The book is great, but the subject is just so different compared to anything that I have ever done before.

Hy is pretty nifty. I like that it can peacefully coexists with Python inside of the same program without too big problems. When the program starts, Hy code is translated to byte code and handed of to Python. After that it's just pure Python. There isn't really much that I miss and I can always mix Python and Hy in cases where it makes more sense. There are macros (which are really cool I think), Python is nice and functional to begin with and we try to smooth some differences between Python 2.x and 3.x where it makes sense. It's not quite as fast as Python, but in my experience it's fast enough for roguelikes.

Latests docs are at: http://docs.hylang.org/en/latest/