Parallelizing Master Mind in Prolog. Document type: Tech Note Author: Thomas Sjöland, LPSLAB, SICS, Kista, Stockholm, Sweden. Project: Gigalips Date: 87 01 28 Abstract For the purpose of studying the process of parallelizing Prolog programs we now and then try to parallelize and run programs which solve "real" problems, but which are no bigger than to be manageable. The idea is of course to achieve some information which will make it easier for us to isolate the important issues in a practical parallel Prolog system. I spent some time with a program for solving the Master Mind problem, including a simulated user. This note describes how the program was conceived and completed in a sequential Prolog system with the focus of the feasibility of parallelizing the program. After having initiated some bugfixes in ANLWAM, we tried to run these programs on the Balance 8000 to get some figures on speed-up etc. We tried to implement the algorithms in GHC also. About the problem. Game playing is a traditional task for AI-programs. The solutions involve more or less intricate search heuristics in order to reduce a search space. In all interactive games the procedure is similar. Given some information, i.e. a board with pieces on it, the algorithm tries to find a sensible thing to do which will improve the situation so as to lead to the goal as quickly as possible. Here we do NOT consider the problem of finding an optimal strategy for Master Mind. We only want a "real" program with some possible parallelism to use as a starting point for a discussion on the methodology of parallel logic programming. About Possible Parallelism. The possible parallelism in this class of programs is restricted by some different factors: 1) We do NOT search for DIFFERENT solutions on the top level. Out of the many proposals which perhaps a parallel subsystem can give, ONE shall be chosen and presented to the user to give information for further processing. This means that unrestricted OR-parallelism won't do. We need to collect the solutions and analyze them before proceeding in the game. A 'bagof' or one-solution metapredicate will most often occur in a deterministic top-level predicate here. Unfortunately 'one-solution' did not work in ANLWAM at the time of this study, so only the solution based on bagof was testable. 2) We want to avoid producing redundant parallelism. An ignorant program will be likely to produce the same computation many times. In sequential Prolog this is often the case too, but it can be avoided by techniques like "lemma generation" etc. There is sometimes a formulation of the algorithm that utilizes parallel search, which can be considered "wasteful" of resources since many processors perform work which is later being discarded. This parallelism can be considered as trading power for time, and is appropriate if you have enough resources. We could call it "the rich mans parallelism" as opposed to "blind parallelism" where anything which can be done in parallel is done so, regardless of whether it produces much redundant work, and resources are swamped with needless computations. Our Suggested Algorithms. Shapiro [1] presents a program to solve this problem but these versions were not directly based on his proposal since it includes use of assert/retract, which are difficult to use in a parallel system. The basic idea of our first algorithm is the same, but it is coded using an accumulating parameter instead of assert. The First Algorithm. The first algorithm for our particular solution can be described abstractly as follows: 1)- Arbitrarily generate a previously untried combination of pegs (numbers). 2)- Check whether the combination suggested is "compatible" with the answers given by the user to the earlier guesses. If not, iterate from step (1). (The first time every guess is "compatible"). 3)- Present this solution to the user, and input answers. 4)- If the last guess was not the correct one, iterate from step (1). 5)- Stop. The First Approach to Implement the First Algorithm. The generation phase (1) and the test phase (2) could be parallelized, if only the relation "previously untried" could be managed globally for all tests. This seemingly trivial thing turns out to be rather difficult with some formulations, which are working smoothly in a sequential system, since the different branches executing in or-parallel have no means of "knowing" what goes on in the other ones, and therefore tend to redo work already performed by others. On the other hand we do not want to wait for termination of the earlier branches before trying other solutions, since that leads to a sequentialized execution. Searching in parallel for the "leftmost" solution (i.e. the first solution that would come given a standard sequential search) will speed up the search, but most of the computation will have to be reiterated in the next guessing step unless the other processors will store its computed results for later fast retreival. Concluding this argument one could say that the first algorithm argues the need for the meta-primitive "leftmost_solution". The parallelism thus produced could be considered as "look-ahead parallelism". The Version of the First Algorithm With Explicit Search Space. In order to allow the use of the meta primitive "any_solution" instead of only "leftmost_solution", we can reformulate the algorithm to one where the whole search space is stored in a term. An untried combination can be found using "pick", and in principle "pick" represents the predicate where the parallelism is generated. The execution penalty in Quintus Prolog for such a version was a 2.5 minutes initialization time (can be discarded if the search space is an axiom, though this demands a huge code space), and a 3-fold decrease in run-time performance compared to the first approach, (due probably to a higher rate of "deep backtracking" in this version). Unfortunately, the memory requirements of this version were too much for the current ANLWAM so we could not verify the claim that it is runnable in parallel. Actually, we doubt it, since it seems that the number of choice points grows in an unbounded way. There is also a lot of redundant search going on, since the branches do not communicate information about which parts of the search space have already been discarded by other processors searching in a different way. This kind of redundancy is often handled by 'cut' or by 'if-then-else' in sequential Prolog, but we must be more explicit in our coding to avoid it in a parallel environment. The algorithm, though correct, and executable in a sequential system, is therefore not usable for parallelization. Trying to Use Lazy Evaluation to Improve On the Previous Approach. In order to reduce the need for initiating, and storing the whole search space, we considered the use of a "lazy" scheme (before properly understanding the redundancy issue discussed above). The list describing the search space, could be the elements produced so far followed by a term corresponding to a lambda-expression describing the way to compute the rest of the list. Unfortunately, we need to keep the elements produced so far (but not checked) in the branches to the right (according to the second version of the algorithm), we reach a situation where we in the worst case will have to not only store the whole search space, but also generate it lazily, which is probably more time-consuming than generating it from the start. Trying to avoid this by storing another lambda-expression for calculating the parts of the search space, which have been discarded in the current branch leads to much reexecution, and its worst case can also demand a lot of space to store the term containing the search space (a mixture of elements and lambda expressions), most likely much bigger than storing the search space itself (!). The algorithm would still search redundantly, as described above. These considerations make the approach unfeasible for our purpose. Summation So Far. The worst problem with the algorithms proposed so far is the need for reiteration of the tests in large parts of the search space, since or-parallel execution does not in itself communicate to the current branch any information about the parts of the search space that has been discarded by other branches. Even if such information was communicated, an algorithm which prunes the search space in larger units (given below), performs much better. A More Practical Algorithm. A suggestion for parallel execution which is more reasonable uses a strictly controlled parallelism. Roland Karlsson suggested this method. - The search space is divided into N parts for the N processors. The search for a compatible combination is performed in parallel by N processors performing the first algorithm in sequential mode in its unique part of the search space. If we keep track of how far each of the processors have proceeded in its computation at the point in time when the first solution is found it could be possible to proceed without recomputation in each of the processors. If that can be achieved, we have an algorithm where the redundant computation is avoided completely. We could even let the other processors continue searching for other possible alternatives, while a solution is presented to the user and the system waits for answers. One remaining problem is to keep all processors busy. When one of the processors runs out of work we could let the algorithm reschedule the division of the search space so that all processors have useful work to perform at all times. This scheme has the problem that the scheduling of parallel work has to be explicitly coded in the algorithm, something we in principle would like to avoid, since it reduces the major advantage of logic programming, namely that the exact control strategy used should not be significant for the semantics. But often you need to violate this idea also in sequential Prolog. More problematic might be the need for much global control information making the program less readable declaratively. Our implementation of this version is not as sophisticated as is outlined above. It simply uses 'bagof' to get suggestions from all 8 subparts of the search space and then chooses its guess from those. A More Abstract Algorithm. There is also another algorithm, which is more "abstract" in the sense that it operates on the set of possible combinations directly instead of on individual elements of the search space. It can be outlined as follows: 1)- generate a term containing the whole search space. 2)- choose one element from the given space (term). 3)- present the chosen element to the user and read the answer 4)- if it was correct, stop else generate the subset of the given set which contains those combinations which are compatible with the latest given answer, i.e. map(compatible(Answer,Space),Subspace). 5)- iterate from step (2) with the given Space replaced by SubSpace. We have here the same space requirement problems as in version 2. We also need to use "bagof" instead of "any_solution", but we will not reiterate tests unnecessarily. This algorithm will only be appropriate when we have a system with a large number of parallel processors, and it always demands memory space at least enough to store the whole search space in a term. A Better Algorithm. An improvement ought to be possible for many cases if the algorithm was using the available information already in step (1) in order to generate a compatible combination instead of blindly generating a member from the search space and testing in a later step. Still we need to code a way to communicate which parts of the search space have been already discarded by the other branches. An outline of such an algorithm is: 1)- Generate a query describing the restrictions on the solution. 2)- Produce a solution by executing the query, possibly in a breadth first and-parallel mode. 3)- Present the produced solution to the user and request an answer. 4)- If not finished, reiterate from step (1) with a more restrictive query. Even though 'metalevel reasoning' is used since we produce queries which are applied, this program is perfectly appropriate for parallel execution (in step 2). We will reiterate some work, but we will NOT produce ALL elements in the search space for later checking. In order to avoid unnecessary tests over overlapping parts of the environment, you need to formulate the query so that the earlier tested parts will not occur in the search for a new combination. This can be rather difficult, so this demand must be relaxed. On the other hand we will avoid the "blind" generation of the whole search space that the other methods have, since the information provided by the answer is enough to prune the search tree significantly. The algorithm of this category presented here is one given by Ciepielewski and Overbeek, using a simple constraint scheme testing the condition for each individual peg rather than first producing a guess and then testing it in its whole. This showed to be the most important optimization, for total execution time. (A similar, but cleaner, approach was implemented in SICStus Prolog using 'freeze' by Carlsson, and was said to give similar performance). To improve this algorithm, we would like to avoid starting from the whole search space again, but only consider the unpruned parts in the next guess. this seemed somewhat tricky to code cleanly, without destroying the efficiency. Default Guesses. In order to quickly reduce the search space a human guesser often uses default guesses for the first two cases in this game in order to span all colours quickly. It was suggested to me that this would always give fewer guesses. I added this to one version of the 'better' algorithm and it did reduce the number of guesses for the test example from 7 to 6. Further improvements. In order to improve the algorithm further, we would like to have it try a combination based on some more reasonable choice function than random. With reasonable we mean one for which the search space will be reasonably (approximately equally much) pruned regardless of the answer given by the user. It has also been argued that an algorithm which only chooses guesses which are possible candidates to be the secret code is probably not optimal [Knuth] [Rada]. About Imperative Implementations. We want to point out that there exists imperative algorithms utilising monitors for generating unique elements from the search space and controlling the activities of several test automata working in parallel. These are in nature very far from the idiom of programming marketed as "declarative programming" and are therefore considered unnatural in our logic programming framework, but of course they would be very natural in for instance a system for parallel object oriented programming (computation expressed as communicating automata). Also many other optimizations regarding representation of the search space and the like could lead to drastically better algorithms in more low level languages (with probably a larger effort spent on debugging). This is indicated by folklore knowledge about parallel implementations of imperative game-playing algorithms. The elegance of parallel logic programming seems to us to be an overwhelming advantage, but of course, the execution penalty imposed by using Prolog, must be considered seriously. Conclusions. Parallelizing a Prolog program is not so simple as a naive look at the problem might imply. An algorithm which works nicely in sequential mode will sometimes have a dreadful behaviour in parallel, (regardless of the problems with a non-logical formulation), and the trivial parallelization of a logically correct program which lacks control for the parallel search might swamp the system with unnecessary work. The need for annotations and powerful metaprimitives seems obvious for a practical system. The studied algorithms have radically different performance in sequential Prolog ranging within a factor of 100. This is sometimes not so obvious to a naive programmer, since the declarative content of the programs is the same. Thinking about what the system does is still necessary. A parallel Prolog system will probably tend to emphasize this drawback rather than the opposite, so therefore much attention must be given to the control issues. Acknowledgements: The results presented here evolved partly through discussions with Dr. Seif Haridi, Dr. Andrzej Ciepielewski and Roland Karlsson, all colleagues at SICS. The work of the Gigalips project on parallelizing logic programs and the latest ANLWAM-system (parallel Prolog on a multiprocessor) was also necessary. This includes work by Ross Overbeek with colleagues at ANL, Dr. D.H.D. Warren and Kish Shen at Manchester University and Mats Carlsson at SICS. For trying out the algorithms sequentially I used Quintus Prolog on a SUN/3 computer, which makes me indepted to the whole Quintus staff. General discussions on problems of parallel search in Prolog with Dr. Khayri Mohamed-Ali, Bogdan Hausman, Dan Sahlin, Lennart E. Fahlen at SICS, Prof. Sten-]ke T{rnlund at UPMAIL and Dr. Kazunori Ueda from ICOT have also helped a great deal. References: [1] Ehud Shapiro & Leon Sterling, The Art of Prolog, MIT Press ISBN 0-262-69105-1, 1986 [2] Hausman & Ciepielewski, Performance Evaluation of a Storage Model for OR-parallel Execution of Logic Programs. SICS 86003 Research Report ISSN 0283-3638, 1986 [3] Kazunori Ueda, Guarded Horn Clauses, Ph.D. thesis. Univ. of Tokyo 1986 [4] ANLWAM A Parallel Implementation of the Warren Abstract Machine, Butler, Lusk, Olson, Overbeek (ANL Internal Report) 1986 [5] Quintus Prolog User's Guide and Reference Manual version 6. 1986 [6] OR-parallel Execution of Prolog on a Multi-Sequential Machine. Khayri A. M. Ali, SICS R86006 Research Report ISSN 0283-3638, 1986 [7] Ehud Shapiro, Playing Mastermind Logically, SIGART Newsletter 85 pp 28-29, 1983 [8] David Powers, Playing Mastermind More Logically or Writing PROLOG More Efficiently SIGART Newsletter 89, pp 28-32, 1984 [9] Roy Rada, Mastermind in SIGART SIGART Newsletter, 1984 [10] Donald Knuth, The Computer as MasterMind Jr. Recr. Math., 1-6, 1976 ---------------------------------------------------------------------------- Appendix 0: mastermind program 0 ---------------------------------------------------------------------------- /* Master Mind 0. The first algorithm, the first approach. */ run :- write('Master Mind, algorithm 1, approach 1. Thomas Sjoeland 87 01 19'), nl, code(C), write(code(C)), nl, statistics(runtime,_), loop(B), statistics(runtime,T), write(exectime(T)), nl. code([5,4,3,5,7]). loop(B) :- loop([],B). loop(Board,Board) :- finished(Board), !. loop(Inboard,Outboard) :- leftmost_solution(guess(G,Inboard)), answer(G,Answer), loop([[G,Answer]|Inboard],Outboard). finished([[_,[5,0,0]]|_]). /* A parallel search for solutions can be applied here, if we can guarantee that we do not miss any part of the solution set, i.e. that left_most_solution produces the solution that we would obtain first from an ordinary sequential Prolog execution. */ leftmost_solution(P) :- P, !. guess(G,Inboard) :- (Inboard=[[Last,_]|_] -> true ; Last=[0,1,1,1,1]), next_solution(Last,G0,8), guess0(G0,G), compatible(G,Inboard). :- parallel guess0/2. guess0(G,G). guess0(G,G1) :- next_solution(G,G0,8), guess0(G0,G1). :- compile(seqlib). ---------------------------------------------------------------------------- Appendix 1: mastermind program 1 ---------------------------------------------------------------------------- /* Master Mind 1. The first algorithm, the second approach. */ run :- write('Master Mind, Alg 1, expl. search-sp, Thomas Sjoeland 87 01 19'), nl, code(C), write(code(C)), nl, loop(B). code([5,4,3,5,7]). loop(B) :- statistics(runtime,_), generate_search_space(Search_space), statistics(runtime,T), write(generationtime(T)),nl, loop(Search_space,[],B), statistics(runtime,T0), write(searchtime(T0)),nl. loop(_,Board,Board) :- finished(Board), !. loop(Search_space,Inboard,Outboard) :- any_solution(guess(Search_space,New_search_space,G,Inboard)), answer(G,Answer), loop(New_search_space,[[G,Answer]|Inboard],Outboard). finished([[_,[5,0,0]]|_]). generate_search_space(S) :- bagof(X,generate_element([1,1,1,1,1],X),S). :- parallel generate_element/2. generate_element(G,G). generate_element(G,G0) :- next_solution(G,G1,8), generate_element(G1,G0). /* A parallel search for solutions can be applied, if we can guarantee that we do not miss any part of the solution set. */ any_solution(P) :- P, !. guess(Search_space,New_search_space,G,Inboard) :- ppick(G,Search_space,New_search_space), compatible(G,Inboard). :- parallel ppick/3. ppick(X,[X|T],T). ppick(X,[H|T],[H|R]) :- ppick(X,T,R). :- compile(seqlib). ---------------------------------------------------------------------------- Appendix 2: mastermind program 2 ---------------------------------------------------------------------------- /* Master Mind 2. The first algorithm, the practical approach. */ run :- write('Master Mind, practical algorithm. Thomas Sjoeland 87 01 19'), nl, code(C), write(code(C)), nl, statistics(runtime,_), loop(B), statistics(runtime,T), write(exectime(T)), nl. code([5,4,3,5,7]). loop(B) :- loop([],B, [[1,1,1,1,1],[1,1,1,1,2],[1,1,1,1,3],[1,1,1,1,4], [1,1,1,1,5],[1,1,1,1,6],[1,1,1,1,7],[1,1,1,1,8]]). loop(Board,Board,_) :- finished(Board), !. loop(Inboard,Outboard,Last) :- bagof(Guess,suggest(Last,Guess,Inboard),Guesses), pick_a_guess(G,Guesses,Lastguesses),!, answer(G,Answer), loop([[G,Answer]|Inboard],Outboard,Lastguesses). finished([[_,[5,0,0]]|_]). pick_a_guess(G,Guesses,Lastguesses) :- increment_guesses(I,G,Guesses,Lastguesses). increment_guesses(I,G,[G|T],[H|T]) :- G=[_,_,_,_,I], next_solution(G,H,I). increment_guesses(I,G,[H|T],[H|R]) :- increment_guesses(I,G,T,R). /* A parallel search for solutions can be applied here, if we can guarantee that we do not miss any part of the solution set. */ :- parallel suggest/3. suggest([Last|_],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). suggest([_,Last|_],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). suggest([_,_,Last|_],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). suggest([_,_,_,Last|_],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). suggest([_,_,_,_,Last|_],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). suggest([_,_,_,_,_,Last|_],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). suggest([_,_,_,_,_,_,Last|_],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). suggest([_,_,_,_,_,_,_,Last],G,Inboard) :- Last=[_,_,_,_,I], leftmost_solution(guess(Last,G,Inboard,I)). leftmost_solution(P) :- P, !. guess(Last,G,Inboard,I) :- guess0(Last,G,I), compatible(G,Inboard). guess(_,[],_,_). guess0(G,G,_). guess0(G,G1,I) :- next_solution(G,G0,I), guess0(G0,G1,I). :- compile(seqlib). ---------------------------------------------------------------------------- Appendix 3: mastermind program 3 ---------------------------------------------------------------------------- /* Master Mind 3. The "Abstract" algorithm. */ run :- write('Master Mind, Abstract Algorithm, Thomas Sjoeland 87 01 23'), nl, code(C), write(code(C)), nl, statistics(runtime,_), loop(B), statistics(runtime,T), write(exectime(T)), nl. code([5,4,3,5,7]). loop(B) :- generate_search_space(Search_space), write(start),nl, loop(Search_space,[],B). loop(_,Board,Board) :- finished(Board), !. loop(Sp,Inboard,Outboard) :- pick_a_solution(G,Sp,T_sp), answer(G,Answer), map_compatible([G,Answer],T_sp,New_sp), /* len(New_sp,L), write(size(L)), nl, */ loop(New_sp,[[G,Answer]|Inboard],Outboard). finished([[_,[5,0,0]]|_]). generate_search_space(S) :- bagof(X,generate_element([1,1,1,1,1],X),S). :- parallel generate_element/2. generate_element(G,G). generate_element(G,G0) :- next_solution(G,G1,8), generate_element(G1,G0). /* A parallel search for solutions can be applied, if we can guarantee that we do not miss any part of the solution set. map_compatible(Answer,[G|T],Out) :- (compatible(G,[Answer]) -> Out=[G|R] ; Out=R), map_compatible(Answer,T,R). map_compatible(_,[],[]). */ /* To run in an OR-parallel system, we need to reformulate this as a bagof call collecting all members of the search space that are compatible. */ map_compatible(Answer,L,Out) :- bagof(G,(ppick(G,L,_),compatible(G,[Answer])),Out). pick_a_solution(G,Sp,T_sp) :- any_solution(ppick(X,Sp,T_sp)). any_solution(P) :- P, !. :- parallel ppick/3. ppick(X,[X|T],T). ppick(X,[H|T],[H|R]) :- pick(X,T,R). :- compile(seqlib). ---------------------------------------------------------------------------- Appendix 4: mastermind program 4 ---------------------------------------------------------------------------- /* master4, A version written by Overbeek & Ciepielewski. */ run :- write('Master Mind, Overbeek & Ciepielewski (adapted by TS)'), nl, code(C), write(code(C)), nl, statistics(runtime,_), loop(B), statistics(runtime,T), write(exectime(T)), nl. code([5,4,3,5,7]). loop(B) :- loop([],B). loop(Board,Board) :- finished(Board), !. loop(Inboard,Outboard) :- G=[_,_,_,_,_], any_solution(guess(Inboard,G)), answer(G,Answer), loop([[G,Answer]|Inboard],Outboard). finished([[_,[5,0,0]]|_]). any_solution(G) :- G, !. guess(L,[P1,P2,P3,P4,P5]) :- pick(P1), test(L,[P1]), pick(P2), test(L,[P1,P2]), pick(P3), test(L,[P1,P2,P3]), pick(P4), test(L,[P1,P2,P3,P4]), pick(P5), test(L,[P1,P2,P3,P4,P5]). /* Parallel search is induced whereever 'pick' occurs. */ :- parallel pick/1. pick(1). pick(2). pick(3). pick(4). pick(5). pick(6). pick(7). pick(8). test([],Choice). test([H|T],Choice) :- check_compatible(H,Choice), test(T,Choice). inexact(Tried,Choice,Inexact) :- inexact(Tried,Choice,Inexact,0). inexact([],_,N,N). inexact([Ht|Tt],Choice,N,I) :- delete(Ht,Choice,New_Choice) -> (J is (I + 1), inexact(Tt,New_Choice,N,J)); (inexact(Tt,Choice,N,I)). delete(X,[X|Y],Y). delete(X,[X1|Y],[X1|Z]) :- delete(X,Y,Z). exact(Choice,Tried,Exact) :- exact(Choice,Tried,Exact,0). exact([],_,N,N). exact([H|T],[H|T2],N,I) :- J is (I + 1), exact(T,T2,N,J). exact([H1|T1],[H2|T2],N,I) :- H1 \== H2, exact(T1,T2,N,I). check_compatible([Tried,[B,C,_]],Pchoice) :- length(Pchoice,L), Choices_Left is (5 - L), exact(Pchoice,Tried,E), E =< B, B =< E + Choices_Left, inexact(Tried,Pchoice,I), S is (B + C), I =< S, S =< I + Choices_Left. :- compile(seqlib). ---------------------------------------------------------------------------- Appendix 5: mastermind program 5 ---------------------------------------------------------------------------- /* master5, A version by Overbeek & Ciepielewski, (with default guesses). */ run :- write('Master Mind 5, Overbeek & Ciepielewski, defaults included.'), nl, code(C), write(code(C)), nl, statistics(runtime,_), loop(B), statistics(runtime,T), write(exectime(T)), nl. code([5,4,3,5,7]). loop(B) :- loop([],B). loop(Board,Board) :- finished(Board), !. loop(Inboard,Outboard) :- G=[_,_,_,_,_], any_solution(guess(Inboard,G)), answer(G,Answer), loop([[G,Answer]|Inboard],Outboard). finished([[_,[5,0,0]]|_]). any_solution(G) :- G, !. /* To start by using default guesses (idea by Dan Sahlin), should prune the search space. */ guess(L,[P1,P2,P3,P4,P5]) :- L=[_,_|_], pick(P1), test(L,[P1]), pick(P2), test(L,[P1,P2]), pick(P3), test(L,[P1,P2,P3]), pick(P4), test(L,[P1,P2,P3,P4]), pick(P5), test(L,[P1,P2,P3,P4,P5]). guess([],[1,2,3,4,4]). guess([_],[5,5,6,7,8]). :- parallel pick/1. pick(1). pick(2). pick(3). pick(4). pick(5). pick(6). pick(7). pick(8). test([],Choice). test([H|T],Choice) :- check_compatible(H,Choice), test(T,Choice). inexact(Tried,Choice,Inexact) :- inexact(Tried,Choice,Inexact,0). inexact([],_,N,N). inexact([Ht|Tt],Choice,N,I) :- delete(Ht,Choice,New_Choice) -> (J is (I + 1), inexact(Tt,New_Choice,N,J)); (inexact(Tt,Choice,N,I)). delete(X,[X|Y],Y). delete(X,[X1|Y],[X1|Z]) :- delete(X,Y,Z). exact(Choice,Tried,Exact) :- exact(Choice,Tried,Exact,0). exact([],_,N,N). exact([H|T],[H|T2],N,I) :- J is (I + 1), exact(T,T2,N,J). exact([H1|T1],[H2|T2],N,I) :- H1 \== H2, exact(T1,T2,N,I). check_compatible([Tried,[B,C,_]],Pchoice) :- length(Pchoice,L), Choices_Left is (5 - L), exact(Pchoice,Tried,E), E =< B, B =< E + Choices_Left, inexact(Tried,Pchoice,I), S is (B + C), I =< S, S =< I + Choices_Left. :- compile(seqlib). ---------------------------------------------------------------------------- Appendix 6: mastermind program 6 ---------------------------------------------------------------------------- /* master6, TS 87 01 26 */ run :- write('Master Mind, Better pruning, Thomas Sjoeland 87 01 26'), nl, code(C), write(code(C)), nl, statistics(runtime,_), loop(B), statistics(runtime,T), write(exectime(T)), nl. code([5,4,3,5,7]). :- compile(seqlib). loop(B) :- loop([],B). loop(Board,Board) :- finished(Board), !. loop(Inboard,Outboard) :- G=[_,_,_,_,_], any_solution(guess(Inboard,G)), answer(G,Answer), loop([[G,Answer]|Inboard],Outboard). finished([[_,[5,0,0]]|_]). /* A parallel search for solutions can be applied here, if we can guarantee that we do not miss any part of the solution set. */ any_solution(P) :- P, !. guess([],Guess) :- fill_in(Guess). guess([[L,[B,W,E]]|R],Guess) :- insert_n_exact_matches(B,L,Guess), insert_n_inexact_matches(W,L,Guess), insert_n_non_matches(E,L,Guess), guess(R,Guess). fill_in([]). fill_in([H|T]) :- var(H), pick(H,[1,2,3,4,5,6,7,8],_), fill_in(T). fill_in([H|T]) :- nonvar(H), fill_in(T). insert_n_exact_matches(N,L,Guess) :- select_n_positions(N,L,Guess,Ln,Ln). insert_n_inexact_matches(N,L,Guess) :- select_n_positions(N,L,Guess,Ln,Gn), all_unique_members(Gn,L), nomatch(Gn,Ln). insert_n_non_matches(N,L,Guess) :- setdiff([1,2,3,4,5,6,7,8],L,Nonmatches), select_n_positions(N,L,Guess,_,Gn), all_members(Gn,Nonmatches). nomatch([],[]). nomatch([H|T],[G|S]) :- \+ H=G, nomatch(T,S). all_unique_members([],_). all_unique_members([H|T],L) :- pick(H,L,R), all_unique_members(T,R). all_members([],_). all_members([H|T],L) :- pick(H,L,_), all_members(T,L). :- parallel select_n_positions/5. select_n_positions(0,_,_,[],[]). select_n_positions(I,[H|T],[G|S],[H|R],[G|Q]) :- I>0, I1 is I-1, select_n_positions(I1,T,S,R,Q). select_n_positions(I,[_|T],[_|S],R,Q) :- I>0, len(T,L), L>=I, select_n_positions(I,T,S,R,Q). setdiff([],_,[]). setdiff([H|T],L,R) :- pick(H,L,_),!, setdiff(T,L,R). setdiff([H|T],L,[H|R]) :- setdiff(T,L,R). /* not used ... index(X,[X|T],1). index(X,[_|T],I) :- index(X,T,I1), I is I1+1. exact_match(X,L,G,I) :- index(X,L,I), index(X,G,I). non_match(X,L,G) :- member(X,[1,2,3,4,5,6,7,8]), \+ member(X,L), member(X,G). inexact_match(X,L,G) :- index(X,L,I), index(X,G,J), index(Y,L,J), \+ X=Y. */ ---------------------------------------------------------------------------- Appendix 7: mastermind program 7 ---------------------------------------------------------------------------- /* master7, Sicstus version by Mats Carlsson: Clean separation between generate and test. The use of delayed unification with the reversed test-generate sequence gives an efficient program despite the clear logic. The predicates echeck and icheck have mode declarations to give delay semantics. */ cputime(S) :- statistics(runtime,[_,S]). time_solution(Code) :- cputime(S), solve_body(Code,_,[]), cputime(E), T is (E - S), write([time,T]), nl. solve_body(Code,X,L) :- one_only(solution(Code,L,Y)), ask(Code,Y,[B,C]), continue(Code,X,Y,L,B,C). one_only(G) :- call(G), !. continue(Code,Answer,Answer,_,B,_) :- length(Code,B), !. continue(Code,Answer,Tried,L,B,C) :- solve_body(Code,Answer,[[B,C,Tried]|L]). solution(Code,L,Choice) :- length(Code,N), test(L,Choice,N), % HERE generate(L,N,Choice). generate([],N,Choice) :- genfirst(N,Choice). generate([[_,_,Tried]|_],N,Choice) :- gennext(N,Tried,Choice). genfirst(0,[]) :- !. genfirst(N,[Q|Qs]) :- pick(Q), N1 is N-1, genfirst(N1,Qs). gennext(N,[A|As],[A|Qs]) :- N1 is N-1, gennext(N1,As,Qs). gennext(N,[A|As],[Q|Qs]) :- pick(Q), A@0, Ex1 is Ex-1. echeck(_,_,Ex,Ex,N) :- Ex0, Inex1 is Inex-1. icheck(_,Bs,Bs,Inex,Inex,N) :- Inex