Three-prisoners Puzzle

From Wikipedia:

Three prisoners, A, B and C, are in separate cells and sentenced to death. The governor has selected one of them at random to be pardoned. The warden knows which one is pardoned, but is not allowed to tell. Prisoner A begs the warden to let him know the identity of one of the others who is going to be executed. "If B is to be pardoned, give me C's name. If C is to be pardoned, give me B's name. And if I'm to be pardoned, flip a coin to decide whether to name B or C."

The warden tells A that B is to be executed. Prisoner A is pleased because he believes that his probability of surviving has gone up from 1/3 to 1/2, as it is now between him and C. Prisoner A secretly tells C the news, who is also pleased, because he reasons that A still has a chance of 1/3 to be the pardoned one, but his chance has gone up to 2/3. What is the correct answer?

Code

We use the predicates safe/1 and tell_executed/1:

safe(i) means that prisoner i is not going to be executed, with i in {a,b,c}.
tell_executed(i) means that the warden tells A that i is going to be executed, with i in {b,c}.

:- use_module(library(pita)). :- if(current_predicate(use_rendering/1)). :- use_rendering(c3). :- endif. :- pita. :- begin_lpad. safe(a):1/3; safe(b):1/3; safe(c):1/3. % a, b and c are safe with probability 1/3 tell_executed(b):1/2; tell_executed(c):1/2:- safe(a). % the jailer says that b will be executed with probability 1/2 or c will be % executed with probability 1/2 if a is safe tell_executed(A):- select(B, [b,c], [A]), safe(B). % the jailer says that A will be executed with certainty if there is a prisoner % B in {b,c} different from A that is safe tell:- tell_executed(_). % the jailers speaks if there is a prisoner for which he says that he will be % executed :- end_lpad.

What is the probability that A is not executed before the warden has spoken?

prob(safe(a),Prob).

What is the probability that A is not executed after the warden has spoken?

prob(safe(a),tell,Prob).

As you can see, the probability of A being safe is the same before and after the warden communication.

What is the probability that C is not executed before the warden and A have spoken?

prob(safe(c),Prob).

What is the probability that C is not executed after the warden has said B to A?

prob(safe(c),tell_executed(b),Prob).

As you can see, the probability of C being safe increases from 1/2 to 2/3.

Note that if you change the probability distribution of selecting B or C when A is safe, the probability of A being safe after the communication does not change, while the one of C being safe changes. You can try it by modifying the second clause and rerunning the queries.

You can also visualize these values with:

prob(safe(a),Prob),bar(Prob,C).

prob(safe(a),tell,Prob),bar(Prob,C).

prob(safe(c),Prob),bar(Prob,C).

prob(safe(c),tell_executed(b),Prob),bar(Prob,C).

The problem is also explained in this nice video:

References

[1] Wikipedia

[2] Peter D. Grunwald and Joseph Y. Halpern. "Updating Probabilities." Journal of Artificial Intelligence Research 19 (2003): 243-278.