Correct strategy and Solution

Here we explain the strategy that prisoners would follow to give the right answers.Their strategy is based on process of elimination as shown in the kripke structures in section 2. For our solutions we assume that the prisoners are intelligent and rational enough to reason out the information available in order to deduce their conclusions.

There are two red and two blue hats. Prisoner C can see the colour of the hats that prisoners B and A are wearing. Prisoner B can see the colour of the hat that "A" is wearing.

The prisoners are able to make intelligent decisions by process of elimination of choices based on the knowledge they gain by looking at the person in front of them and the announcements they make. This is comparable to the table and the kripke structures in section 2.

If "C" sees "B" and "A" wearing the same colour of hat he knows that he has an opposite coloured hat on him.He is therefore eleminating four out of six choices.Out of the two choices available, he is able to eliminate the colour that he sees and is able to rightly announce his hat colour.

If he sees them wearing different colours then he does not know the right answer and therefore keeps quiet.In this process, two of the six choices get eliminated. Observing "C" being quiet, "B" realizes that the colour of his hat is different from the colour of the hat "A" is wearing and by eliminating the coilour that "A"is wearing he is able to rightly announce the colour of his own hat.

By rightly announcing the colour of their hats as in the above scenarios, prisoners help each other in saving their lives. In this process we also learn that being silent is also a kind of public announcement that helps others in gaining new knowledge.

But after "C" being quiet, if "B" also chooses to remain quiet, it means that "B" has seen some strange colour that he does not have in his list of elimination. With this available information "A" is unable to know the colour of his own hat. Hence he also chooses to keep quiet. Now that "A", "B" and "C" have been quiet, "D" also cannot announce the colour of his own hat. In this situation, all the three prisoners are executed.

Following the above strategy, we designed a game that was coded in Java. More description on playing this game is presented in section 4.

Conclusions and Scope for Improvements

Keeping in mind the scope of time,we considered a game with four prisoners and four hats of two different colours. This gave us a possibility to explore aspects of epistemic logics like common knowledge and public announcements. We could implement the kripke structures in different possible worlds. We used the semantic and syntactic representations as and when possible. We implemented this puzzle in form of a game that works like a charm. In our game the user is free to choose any colour of hat for each of the four prisoners.After the distribution of hats the prisoners analyse the scenario and deduce their conclusions to make public announcements. In principle it is sufficient that one of the prisoners give the right answer for all the three to be set free, but our game is able to show the knowledge that each prisoner posses at every stage and the analysis that he makes based on the new gained knowledge.

The complexity of this puzzle can be further increased to its variants with more number of hats, or more hats, more prisoners with a different situation such that they are not allowed to talk but can see each other etc. All these variants can be analysed on same lines as we did. With high complexity, a code like we wrote would be a better way of analysis than doing it in person.