Artificial Intelligence Question posted in
ChatGBT is becoming a world-wide phenomena, try it out here.

some doubts about a Prolog program that use a moves graph to move blocks on 3 stack – Artificial Intelligence

I am studying Prolog using Ivan Bratko book: Programming for Artificial Intelligence and I am finding some problems trying to understand how work an exercise that use graphs to decide how to move blocks and to arrange them in an order.

This is an image related to what the program have to do:

enter image description here

As you can see in the previous image the blocks A,B,C can be moved using a number of admissible moves that are:

  • A block can be moved only if it is at the top of the stack
  • A block can be moved on the ground (on a void stack)
  • A block can be moved over another block (at the top of another stack that contains some others blocks)

So these admissible moves induce a graph of the possible transitions between one state and another state in the graph, something like this:

enter image description here

So, as you can se in the previous graph I can represent a situation using a list of 3 sublist.

Each sublist represent a stack where I can put the blocks according to the previous constraints

So for example the situation of the central node of the previous graph can be represented by:

[[A], [B], [C]]

Because each stack contain a single block

The situation represented by the node at the top left where I stacked one below the other blocks
C,A,B can be represented by:

[[C,A,B], [], []]

because all the blocks are in a single stack (the first one)

Now, I have to write a predicate s(Situation1, Situation2) that is TRUE if Situation1 and Situation1 are two representations of the world of blocks (like the previous) and there is a legal move allowed between Situazion1 and Situazion2.

So I could represent this thing in the following using a series of facts like (this thing is shown on the slides of my teacher and not on the Bratko book:

s([[A|RA],B,C],[RA,[A|B],C]).
s([[A|RA],B,C],[RA,B,[A|C]]).
…

I interpret it in this way: I have 2 stacks:

Situation1 = [A|RA], B, C] where RA is the rest of the first stack without the block A (in this case it is void because this is the situation in which I have one block in each stacks)

Situation2 = [RA,[A|B],C] that is another situation with the first stack that is void (RA), the second stack that is the old second stack with the A block on the top and the third stack that contains only the C block

So it represents a legal transition…so I could declare a series of facts that represents explicitly all the possibles transitions.

But this is not good idea (I can have many transitions to encode in facts) so on the Bratko book implement programmatically the s(Situation1, Situation2) predicate in this way:

/* BASE CASE: If I delete X from List and X is the HEAD of List, NewList is
              the Tail of List
*/
del(X, [X|Tail], Tail).

/* GENERAL CASE: If the head of List is not X then the program have to delete
                 X in the Tail of List
*/
del(X, [Y|Tail], [Y|Tail1]) :- del(X, Tail, Tail1).


s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-

                                 del([Top1|Stack1], Stacks, Stacks1),
                                 del(Stack1, Stacks1, OtherStacks).


goal(Situation) :- member([a,b,c], Situation).

solve(N,[N]) :- goal(N).

The del/3 predicate it is very simple (simply delete an X item from a list) and there is not much interesting.

I have some problem to understand how work the s/2 predicate that calculate legal moves.

On the book say:

The successor relation can be programmed according to the following rule: Situation2 is a SUCCESSOR of Situation1 if there are two stacks:
Stack1 and Stack2 in Situation1 and the top block of Stack1 can be
moved on Stack2

Intuitively this is not difficult to me because it appear clear that a move is legal if I can take a block by the top of one of the 3 stack and I can put it on the top of another stack (also a void stack, that corresponds to the situation in which I put a block on the ground)

But I am finding many difficult to understand the previous code of s/2 predicate when it write:

s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-

                                 del([Top1|Stack1], Stacks, Stacks1),
                                 del(Stack1, Stacks1, OtherStacks).

I have some difficult to understand how read it and what exactly do when use del/3 predicate and also what exactly represent Stacks, Stack1, Stack2, Stacks1 variable

Tags:

2

Answers


  1. 0

    after correcting the singleton in s/2, obtaining

    s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-
    del([Top1|Stack1], Stacks, Stacks1),
    del(Stack2, Stacks1, OtherStacks).

    I get on test

    ?- s([[a,b,c],[],[]],R).
R = [[b, c], [a], []] .
    Login or Signup to reply.
  2. 0

    you ask, what does the following mean:

    s(Stacks, [Stack1, [Top1|Stack2] | OtherStacks]) :-
                             del([Top1|Stack1], Stacks, Stacks1),
                             del(Stack1, Stacks1, OtherStacks).

    we can read it thus: s/2 of course is a “step” (or “move”, or “successor”) relationship. We have Stacks list of stacks, to begin with. The 2nd param is our result, of moving one block somehow among them.

    Since del is a backtracking predicate, so will be s. So, it will produce results one by one. Here the declarative reading will be helpful. 🙂

    We read the body thus: there is A = [Top1|Stack1] among the Stacks, which turn into Stacks1 with A removed from them. If we had three Stacks, we’ll have two Stacks1, and another stack A, of which the first – Top1 – element is obviously, the top block on that stack (and Stack1 is the stump, the rest of that stack). IOW, we pick some stack A among the three stacks, and the rest are Stacks1. The top block on A is Top1.

    On to the next line. 🙂 If we were to delete the stump Stack1 from the two Stacks1, we’d get OtherStacks. That’s just nonsense, we know that the stump is not among the Stacks1. So that’s obviously an error (a “typo”).

    How are we to correct it? Our goal is to place the Top1 on one of the stacks in Stacks1, so let’s do just that:

        del(A,Stacks1,B), Result = [ Stack1 ,         % a stump
                                 [Top1 | A] |     % move the top block
                                 B].

    which is our 2nd argument, up to renaming of the variables: A = Stack2, B = OtherStacks. So, the correct second line is

                             %   del(Stack1, Stacks1, OtherStacks).   % ERROR
                             del(Stack2, Stacks1, OtherStacks).   % CORRECT

    just as in CapelliC’s answer.

    CapelliC is right, the naming is just horrible, 🙂 it’s very easy to mis-type. A, B, C is much better.

    Login or Signup to reply.
Please signup or login to give your own answer.

Back To Top
Search