Graph traversal for problem solving tutorial

I’ve put a new tutorial at https://swish.swi-prolog.org/p/Graphs1.swinb looking at how to do problem solving (using the old cabbage, goat, wolf puzzle).

So far I only have one method, using breadthfirst search plagiarized from Ivan Bratko, but hope to gradually grow it. I’m keen to learn how to use SWI Prolog’s heap library, so will hopefully add that next.

2 Likes

Nice. :smiley:

For those in need of a more specific reference to the code in the book, for the 4th edition see: Section 11.3 Breadth-first search page 271 and Figure 11.10 An implementation of breadth-first search. on page 273.

1 Like

Still only breadth first, but I’ve neatened the common code up quite a lot to make it more general, so hopefully A* etc will be coming soon.

A thing I’ve done, which I’m not sure is really necessary, is converting states from lists to strings following my experience with Python where comparing two lists of identical elements often results in false because it is looking at their pointers, not their contents. Is this also true for Prolog?

Work in progress is at https://swish.swi-prolog.org/p/Graphs1.swinb

I don’t think you should implement transition by modifying the database, otherwise you can’t do backtracking and search properly. Rather meta-interpret the GDL rules against a game state argument, for example a list of facts which you check membership for in order to meta-interpret true/1 .

Goodness, no! What resource are you using to study Prolog?

1 Like

This StackOverflow Q&A might might be of help:

Prolog planning using retract and assert

While the OP of the question tried to solve it using assert and retract, the answer does it by maintaining the state in a variable.

1 Like

The following example of a state-space search framework may be useful to mine for ideas and code, although it uses clauses instead of lists to represent states:

https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching

It includes implementations of both blind and heuristic search methods.

1 Like

In Prolog (unlike Python), if two things look the same they are the same. An uninstantiated variable in Prolog is similar to a pointer in conventional programming language. (Explaining Python’s memory model requires a long digression, which you can find by looking for tutorials on == vs is, for example.)

Of course, there are some details to the “look the same, are the same”:

  • “look the same” is using something like write_canonical/1, without using portray/1.
  • =/2 succeeds if the two terms unify.
  • ==/2 can be used to check whether two unistantiated variables are the same (but they might subsequently become the same with a subsequent unifcation).
  • =@=/2 can check whether two terms would unify, without instantiating variables.

Both ==/2 and =@=/2 are non-logical operations, as are var/1, nonvar/1, ground/1. They usually aren’t needed; if you find you do need them, you should consider changing your program so that they aren’t needed.

3 Likes

I’ve advanced to both breadth first and depth first, using the same shared predicates, working. I haven’t tested depth first on tougher problems like eight queens and towers of hanoi yet, but hope to shortly after polishing depth first to use iterative deepening and heuristics. The tutorial is at https://swish.swi-prolog.org/p/Graphs1.swinb

I’ve pretty much rewritten this tutorial entirely, moving from my original idea of solving the cabbage, goat, wolf (or grain, goose, fox if you prefer) puzzle in various ways to solving various puzzles in essentially one way.

I’ve added the eight queens puzzle (for which I’ve omitted a query using breadth first search since that takes over 40 seconds vs 0.4 seconds for depth first), and I’m planning to add the eight sliding tiles puzzle as a third and probably final example.

The tutorial is at https://swish.swi-prolog.org/p/Graphs1.swinb

Suggested improvements are welcome.

I think it is great that you are writing these tutorials and posting the code. Also the fact that you let people see your mistakes along the way is awesome; too many people are afraid to make mistakes in front of others.

First suggestion is for

As much as I would personally avoid that, if you want to go that route then I would suggest instead using generate and test.

Here are two examples of answers I have given related to the 8-queens problem that both rely on generate and test.

a. Understanding CLP(FD) Prolog code of N-queens problem
b. Hints to understand splendid program to solve Queens

The next suggestion is to add pictures. As much as they are hard to create, and also hard to get posted into certain sites, pictures can take a good tutorial and make it great. Remember beginners reading these tutorials will have a hard time just keeping the abstract concepts in their head, adding a picture will help to simplify many of the thoughts in their head, and also act as an anchor point for referring back to and validating if they are imagining the concept correctly. e.g Syntax diagram, Unification

1 Like

I’ve added the 8-puzzle, using the same example as Richard O’Keefe in The Craft of Prolog (p59 in the copy I have). I only realised once getting the answer his example is a bit of a cheat because it only takes four moves to reach the goal.

Ivan Bratko in the diagram on p242 of the third edition of Programming for Artificial Intelligence is even more obvious, setting up only two moves from victory.

Sadly, trying to solve the GGP puzzle at http://games.ggp.org/base/games/eightPuzzle/eightPuzzle.kif which takes a minimum of 30 moves cannot be done within the time limit allowed by the swish server.

I’ll probably add more puzzles in due course. The tutorial is at https://swish.swi-prolog.org/p/Graphs1.swinb

For initial states with solutions with four, five, and eighteen steps see:

https://github.com/LogtalkDotOrg/logtalk3/blob/9718581e6a5d5f807f3016e199e2c11fa1983eaf/examples/searching/eight_puzzle.lgt

1 Like

I’ve substantially rewritten this tutorial again, “backporting” stuff I’ve learnt from my game tutorial, adding iterative deepening to depth first and breadth first searches.

It’s still work in progress, and haven’t managed to solve the really tough puzzles I hope to yet. But it’s been very educational, and I’ve had “aha!” epiphanies on alpha-beta pruning and backward induction (topics I’ve managed to distinctions for in any various online courses on game theory in the past without comprehending at all).

https://swish.swi-prolog.org/p/Graphs1.swinb