Telecom Paris Dep. Informatique & Réseaux Nils Holzenberger ← Home page November 2024

Neuro-Symbolic Artificial Intelligence

with

Simon Coumes

and

Zacchary Sadeddine

➜            other AI courses

    The problem of the tower of Hanoi, but few know the the origin of the name (indispensable to shine during parties). The problem is to move a tower consisting of discs of decreasing sizes from one stack to another, touching one disc at a time and never placing a disc on a disc smaller than it. This problem, like that of the monkey, or card games, board games, is endowed with a finite state space, with an accessibility relation between the states.    

    This game has been used in psychology to study the human way of solving problems. In an experiment, subjects were asked to handle 25kg disks with handles, which required them to save actions and cooperate.     

    The tower of Hanoi is emblematic of a class of problems of which an optimal solution is an algorithm with central recursion. An algorithm like the one that tests whether an individual is an ancestor of another (see week 1) is recursive, but it is alateral recursion: the recursive call occurs at the end of the clause, when there is nothing else to perform. In traditional languages, lateral recursions are replaced by loops. The central recursion assumes instead a ‘descent’, then a ‘rise’ once the stopping condition (the bottom of the recursion) has been reached.
Example of algorithm with central recursion:

factorial(1, 1) :- !.
factorial(N, F) :-
    N1 is N - 1,
    factorial(N1, F1),
    F is F1 * N.

(Note that Prolog uses the expression is to force the arithmetic evaluation). Copy and paste this program and then test it by factorial(6, X).

This is a limited example, because in a language allowing the evaluation of arguments in situ, we would have a lateral recursion. For example, with the C language, we would have return N * fact (N-1).

Let us return to the Tower of Hanoi. The following program offers a central recursion resolution. A paraphrase can be: to move a stack, move the sub-stack (the stack minus its largest disc) on the intermediate stack, move its large disc toward the goal, and then move the sub-stack back to the large disc. You can test the program.

hanoi :-
    % 1 is the smallest disk and 5 the largest
    move([5,4,3,2,1], a, c, b).

move([ ], _, _, _).
move([D1|Stack], Start, Goal, Interm) :-
    move(Stack, Start, Interm, Goal), % this is a (central) recursive call
    write('move disk '), write(D1), write(' from '), write(Start), write(' to '), write(Goal), nl,
    move(Stack, Interm, Goal, Start). % yet another recursive call

This algorithm always finds an optimal solution. Try to implement it mentally to solve a problem with three discs (take coins), then four and finally five discs. Without training, the task requires a certain concentration! You must, like Prolog, maintain a stack of tasks in progress. Our ability to manage stacks is however more limited than Prolog.

Note: My first PhD student told me a technique that requires no memory (and thus no stack) and that produces the same result. You move the smallest disk every second move, always in the same direction (placing the stacks as a triangle may help); and in the remaining situations, you make the only lawful move. The direction of movement of the small disc depends on the parity of the number of discs. Yet another way to shine during parties!

    We can solve the Tower of Hanoi using a basic planning method as we used for the monkey problem. It has the advantage of being a general method of exploration rather than an ad hoc procedure. The first step is to represent the state of the system. Here, it will simply be a list of three lists [Ta, Tb, Tc] representing the contents of the three pegs. Next, we have to write the transition predicate between states.     
    The solution that follows uses a trick to avoid repeating the same thing six times, returning each time to the case where one moves from the stack a to the stack b. Note that the K variable ensures that the same permutation is used both times.

% State transition in the Tower of Hanoi puzzle
s([Ta,Tb,Tc], [Ta1,Tb1,Tc1]) :-
    permute(K, [Ta,Tb,Tc], [[D1|T1],T2,T3]), % as if source pole were a
    allowed(D1,T2), % checks that the move is legal
    permute(K, [Ta1,Tb1,Tc1], [T1,[D1|T2],T3]). % as if target pole were b - Note that K is the same

allowed(_,[]). % any disk can be put on an empty pole
allowed(D1,[D2|_]) :-
    D1 < D2. % checks that the disk beneath is larger
    
permute(1,[A,B,C],[A,B,C]). % Next time, let's write permute as a genuine prolog programme !
permute(2,[A,B,C],[A,C,B]).
permute(3,[A,B,C],[B,C,A]).
permute(4,[A,B,C],[B,A,C]).
permute(5,[A,B,C],[C,B,A]).
permute(6,[A,B,C],[C,A,B]). % Theory says that 3! = 6.

    The state to be reached is indicated by:

success([[],[],_]). % all disks in c

This program is designed to perform a search without central recursion. To do this, is uses a search procedure that performs one of the available actions as long as the goal has not been reached (as in the monkey program).

To avoid this problem, we can use an accumulator that will memorize the intermediary states. Have a look at the hanoi3 version that does exactly this.

Finally, the hanoi4 version implements a width-first strategy, instead of the depth-first strategy which is native in Prolog.

            

Back to the main page