Monday, December 9, 2013

Solving Logic Riddles using AI Programming

Consider three persons, Caesar, Brutus, and Cassius. One is a king, another is a bureaucrat, and the third is a spy. The king never lies, whereas the bureaucrat always lies. The spy either lies or tells the truth. Caesar claims that Cassius is a bureaucrat, Brutus claims that Caesar is a king, Cassius claims that he is a spy.

Who is who?

The solution, by hand

Let's start by solving this without computer assistance. Cassius cannot be a king: he is asserting that he is a spy, so if he were king, he would be lying - which is impossible for the king to do. Likewise, Brutus cannot be king, since he claims Caesar is, and so would be lying. So Caesar is the king. Brutus is then telling the truth, so he cannot be a bureaucrat (the Bureaucrat always lies). So Brutus must be a spy, and, by exclusion, Cassius is a bureaucrat (which is consistent, since Cassius is lying when asserting he is a spy). To summarize, there is a unique solution, which is:

Caesar: king.
Brutus: spy.
Cassius: bureaucrat.

The solution, AI programming

How would you encode information about this problem in such a way as to let the computer solve it? Sure, in this case the solution was easy to obtain, but if you had 100+ rules and a lot more people it would not be easy to solve the problem by hand (think of the problem as an equation with values true/false). Logic programming, as the name suggest, provides an intuitive and natural way to express logical riddles (among other things). The following in Prolog:

First, tell the computer Caesar, Brutus, and Cassius are persons:

person(caesar).
person(brutus).
person(cassius).

Next, we would like to assign King, Liar (Bureaucrat is too long to type), and spy to these persons:

assign(K,L,S) :-
person(K), % king is a person
person(L), % liar is a person
person(S), % spy is a person
king(K,L,S), % constraints for king (to be defined later)
liar(K,L,S),  % constraints for liar
spy(K,L,S), % constraints for spy
different(K,L,S). % king, liar, and spy must be different people

We must thus defined the constraints imposed by virtue of being King, Liar, and Spy:

king(K,L,S) :- says(K,K,L,S). % Whatever King says is true
liar(K,L,S) :- \+ says(L,K,L,S). % Whatever Liar says is false (think of "\+" as "not true")
spy(_,_,_). % Anybody can be a spy

Now onto the claims that each of them make:

says(caesar,K,L,S) :- L = cassius. % Caesar says Cassius is Liar
says(brutus,K,L,S) :- K = caesar. % Brutus says Caesar is King
says(cassius,K,L,S) :- S = cassius. % Cassius says he himself is Spy

Finally, we define what "different" means:

different(X,Y,Z) :- X \= Y, X \= Z, Y \= Z. % Not the same: X,Y,Z 

Now we may query Prolog to obtain all solutions:

?- assign(K,L,S).
K = caesar, <--- Caesar is King
L = cassius, <--- Liar is Cassius
S = brutus ; <--- Spy is Brutus
false. <---- This means there are no more solutions

An interesting change

To see that this really works, consider what would happen if we don't require that there must be a unique King, Liar, and Spy. For example, one person could then be both King and Spy. This is effectively done by removing the requirement that they are all different: either remove different(K,L,S) from assign(K,L,S), or define it trivially as different(_,_,_), meaning there are no constraints).

Before executing the query, let's make some observations: a person cannot both the king and liar, assuming that person makes at least one claim. Since everybody makes a claim here, nobody can be both king and liar. So at least two people must be assigned the properties {king, liar, spy}. Clearly anybody can in principle be both king and spy, or liar and spy, since spy adds no new constraints. Furthermore, our original solution should still be part of the new solution set, since we've only removed one constraint.

How many solutions do you count? This problem is clearly more difficult than the previous one. Our query will reveal all solutions:

?- assign(K,L,S).
Solution 1:
K = S, S = caesar, <--- Caesar is both king and spy
L = cassius  <--- Cassius is liar

Solution 2 (This is the original solution):
K = caesar,
L = cassius,
S = brutus 

Solution 3:
K = S, S = cassius, <--- Cassius is king and spy
L = caesar <--- Caesar is Liar

Solution 4:
K = S, S = cassius, <--- As above, Cassius is king and spy
L = brutus <--- This time Brutus is the liar (instead of Caesar)

false. <--- No more solutions.

There is an asymmetry of solutions: when Cassius is both king and spy (solution 3 and 4), the liar can be Caesar or Brutus. But when Caesar is king and spy (solution 1), only Cassius can be a liar, not Brutus. This is because Brutus asserts that Caesar is king, and liars are never allowed to tell the truth.

No comments:

Post a Comment