Tom Barth's Prolog Project

Description of the Problem

A famous book came out about twenty years ago that was called "Six Degrees of Separation". Its conceit was that everyone on the planet is separated from everyone else on the planet by at most 6 people, with separation here meaning knowing someone personally. For example, I have a friend whose business partner knows his Congressman, who in turn knows President Obama. Thus, I am 4 degrees separated from the President.

Shortly after the book came out, some college students at Albright College came up with an offshoot of the book. They called it "Six Degrees of Kevin Bacon" after the eponymous actor. The idea here was that Bacon was such a prolific actor that any other actor could be linked back to him via roles in movies in a chain consisting of no more than six links. For example, Robert DeNiro was in "Goodfellas" with Joe Pesci, who was in "My Cousin Vinny" with Marisa Tormei, who was in "The Wrestler" with Mickey Rourke, who was in "Diner" with Kevin Bacon. So, DeNiro is separated from Bacon by 4 links.

This prolog program captures a small part of the "Six Degrees of Kevin Bacon" game. We have a limited number of movies in the data base, and a recursive rule that allows the actors to be chained together. If you start with Kevin Bacon, you should be able to link to any other actor listed in the data base, though not necessarily in less than six moves, due to only one Kevin Bacon movie being listed.

Description of the Database

The data base is rather simple. It consists of a number of facts listing two stars and the name of the movie they played together in; these facts are called 'stars'. There is also a recursive rule, called 'path', that enables you to forward chain from one actor in a fact to another. This enables you to play the '6 Degrees of Kevin Bacon' game in a limited fashion, plus interrogate the data base to see who stars in a particular movie.

The Code

The code as a prolog file (ready for compilation)

%% The following prolog program is a variation of the
%% Six Degrees of Kevin Bacon parlor game. Clearly, it
%% is a vast oversimplification in that it has limited
%% the cast to 2 stars and requires that they be chained
%% together in the order they are entered in the data base,
%% with only forward chaining currently working properly,
%% but it could be expanded in the future to incorporate
%% those and other changes for completeness.
%%
%% Late Note: Backward chaining now working via 'backchain'
%% command; can now trail back to Kevin Bacon from another actor.
%%
%%
%%	Author:  Tom Barth
%%	Date:	 9/29/2010
%%	Class:	 MAT 385
%%
%%
%%
%%	First, we enter a sampling of movies and their stars.
%%
%%
stars(bacon,rourke,'Diner').
stars(rourke,tomei,'The Wrestler').
stars(tomei,pesci,'My Cousin Vinny').
stars(pesci,deNiro,'Casino').
stars(deNiro,brando,'The Godfather II').
stars(brando,pacino,'The Godfather').
stars(pacino,keaton,'The Godfather').
stars(keaton,allen,'Annie Hall').
stars(deNiro,foster,'Taxi Driver').
stars(foster,mcGillis,'The Accused').
stars(mcGillis,ford,'Witness').
stars(ford,r2d2,'Star Wars').
stars(keaton,alda,'Hannah and Her Sisters').
stars(alda,newman,'The Sting').
stars(newman,redford,'Butch Cassidy and the Sundance Kid').

%%	Below is the recursive method of chaining the stars together.
%%
path(A,B) :- stars(A,B,_).
path(A,B) :- stars(A,C,_),
path(C,B).

backchain(X,Y) :- stars(Y,X,_).
backchain(X,Y) :- stars(Y,Z,_),
path(Z,X).

%%  findall(X,path(bacon,X), Z).
%%
%%	The above findall statement will list the chain of actors
%%	from Kevin Bacon to the desired actor (represented by 'X').
%%
%%
%%	Other items of interest include: finding out who stars in a
%%	particular movie by entering: stars(X,Y,'MOVIE NAME'). and
%%	determining if 2 actors can be linked together by entering:
%%	path(A,B), where A and B are the particular actors interesting
%%	you at the moment.
%%
%%
%%	Other features were attempted to be added but haven't worked
%%	out just yet due to the author's inexperience with prolog.
%%

== Example Output ==

% c:/users/tom/documents/prolog/bacon compiled 0.00 sec, 148 bytes
1 ?-  [bacon].
% bacon compiled 0.00 sec, 136 bytes
true.

2 ?- %see who stars in 'Butch Cassidy and the Sundance Kid'
|    c
|
Action (h for help) ? break
% Break level 1
[1] 2 ?- stars(X,Y,'Butch Cassidy and the Sundance Kid').
X = newman,
Y = redford.

[1] 3 ?- %% can we link Kevin Bacon to Harrison Ford?
|
Action (h for help) ? break
% Break level 2
[2] 3 ?- path(bacon,ford).
true .

[2] 4 ?- path(redford, bacon).
false.

[2] 5 ?- %% What is the chain from Kevin Bacon?
|
Action (h for help) ? break
% Break level 3
[3] 5 ?- findall(X,path(bacon,X), Z).
Z = [rourke, tomei, pesci, deNiro, brando, foster, pacino, keaton, allen|...].

[3] 6 ?- findall(Y,path(brando,Y), Z).
Z = [pacino, keaton, allen, alda, newman, redford].

I prefer this format for the output (ael):

See who stars in 'Butch Cassidy and the Sundance Kid':

1 ?- stars(X,Y,'Butch Cassidy and the Sundance Kid').
X = newman,
Y = redford.

Can we link Kevin Bacon to Harrison Ford?

2 ?- path(bacon,ford).
true .
3 ?- path(redford, bacon).
fail.

What is the chain from Kevin Bacon?

4 ?- findall(X,path(bacon,X), Z).
Z = [rourke, tomei, pesci, deNiro, brando, foster, pacino, keaton, allen|...].
5 ?- findall(Y,path(brando,Y), Z).
Z = [pacino, keaton, allen, alda, newman, redford].