Nice. 
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.
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 usingportray/1. =/2succeeds 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:
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).