Course:CPSC312-2017 Cluedo!

Cluedo Electronic Notebook

Authors: Sam Holdcroft, Katie Li-Wong, Nicholas Wu

What is the problem?

What is Cluedo?

Cluedo (Clue in North America) is a logic puzzle about trying to find out which cards are not held by your opponents. In a game of Cluedo there are 6 characters, 6 weapons and 9 rooms all represented on individual cards. At the start of the game, 3 cards (one from each type) are randomly selected and hidden away from all the players at the centre of the game board. The rest of the cards are then distributed to the players. When the game begins, players take it in turns to move round the board (which represents the 9 rooms) and ask each other questions to figure out which cards the players have. The aim is to work out which cards are hidden in the centre. If you know what cards every other player has, then by process of elimination, you can work out which cards are hidden in the centre.

A question takes the form of "Was it <character>, in the <room>, with the <weapon>". After a player asks a question, then the other players take it in turn to disprove their statement. If a player has a card to disprove this statement, then they must show it to the player who asked the initial statement, so the question asker now knows slightly more about the state of the game.

What are we going to do?

In the traditional board game, players are given a notepad on which to record all the information they receive. They can use the information they write down to work out what questions should be asked, and to eventually deduce the solution to the game. However, this can be tricky. Finding a good way to represent this data is hard, and the provided template is a table that is often too small to read - especially for any player who has vision impairments. Not only this, but in all the excitement of playing Cluedo, many players will accidentally ask questions they already know the answer to, only to have an opponent triumphantly exclaim "You asked me this last turn!"

We have decided to eliminate these problems though the creation of an electronic notepad, which will work to supplement a player as they compete against others in a game of Cluedo, rather than an actual small paper notepad. The program we create will feature a knowledge base that records who has what cards. Initially, this will just contain the cards dealt to whomever is using the program, but as the game progresses, the user will be able to input additional data as they uncover it. The user will then be able to make queries of the knowledge base to check which player has which card, and which cards are still suspects.

We decided we could take this a step further than a simple database however, so we will include functionality for the electronic notepad to suggest questions for the player to ask. The notepad will always suggest the most optimal questions, where all the suspects in the aforementioned (<character>, <weapon>, <room>) triple are still unknown; this should maximize the amount of information learned from each question. Not only that, but the notepad will be able to tell when it has enough information to work out the solution and should inform the user accordingly. It should also contain some basic error checking to make sure that the user does not try and enter a card that does not exist.

What is the something extra?

Overview

Most people are not programmers, and of those who are, very few are Prolog programmers. We felt it was reasonable to assume that the majority of people who play Cluedo are not familiar with Prolog, so the default interface is not ideal. To this end, we have decided to add a natural language interface to our program. It should be able to recognize simple sentences written in English and respond accordingly. We feel that our project would be idea for this kind of interface. Cluedo has a constrained vocabulary - so it should not be too difficult to create a dictionary that covers most phrases player could say. Some examples of what we'd like to parse is listed below.

Examples

Adding to the Knowledge Base (KB)

In order for the program to work as intended, the player must be able to update the KB with new information that is learned as the turns go by. The program should be able to parse this information and record it in a way that is usable when making a query. The program should also make sure that the player cannot add information about cards that do not exist in Cluedo, in order to reduce the number of errors encountered.

"I have Professor Plum": This should update the Knowledge Base to reflect that the user is in possession of the Professor Plum card.
"John has the Billiard Room": This should add the fact that John has the Billiard Room to the knowledge base.
"Peter has the Black Death": Program should respond to say that 'Black Death' is not a valid card in Cluedo.

Simple Queries

The player may wish to query the KB, so that they can deduce additional information based on how players are interacting with each other. To this end, the program must be able to recognize simple queries and search over the KB to find the answer.

"Who has Colonel Mustard?": This should respond with which player is in possession of the Colonel Mustard card, or inform the user that this information is not known.
"What cards does Susan have?": This should respond with a list of the cards that the KB has been told Susan possesses.
"What are the suspected characters?": This should tell the user which character cards could still be the solution.

Question Suggesting

The main feature of our project is the ability to suggest what question the user should ask next. In order to do this, the program needs to know what room the player is currently in.

"Im in the Library": This should inform the knowledge base that the user is in the library, so it should only suggest questions about the library.
"What is my next move?": This should suggest a question that the user should ask next. The question should be relevant to the room the player is in; if the player is standing in the Study then they may only ask questions about the Study. This query should also inform the user when the KB contains enough information to guess the solution to the whole game.

What did we learn from doing this?

Parsing natural language is hard! And the way our program is written in Prolog isn't very intuitive or user-friendly for people who don't know any Prolog.

Main Program

Our main program, to record information about a Cluedo game and make suggestions on what questions to ask, worked very well. This is partly due to Prolog's similarity to a database query program such as SQL. The parts of our program were:

The main function of the program is to look up terms in a database and return the result.
It also adds local facts to the database (notebook), to recommend the optimal questions and eventually devise the solution.
Recommending questions is simply looking for facts that were not defined in the database
A solution was found when there was only one possible question left to ask.

All of this takes advantage of prologs ability to quickly search for information. We chose a triple format for storing the data of who has which cards, we used prop(P, has, C) to show that the player P is holding the card C. By using this kind of Subject Relation Value triple we were able to not only query which cards a player is holding, but also who is holding which cards.

Cluedo is a closed environment. This means we can define what all of the possible cards are, which allows us to use negation as we are accounting for all the possibilities. If we want to check if a card could be part of the solution to the game then we only need to check if there is not a prop(P,has,C) where C is the card we're looking for. We know that we have complete knowledge of the 'world' so far, there is no missing data.

Overall, we felt that Prolog was an excellent choice our project.

Extension

The extension is where we found the most problems - English is a very tricky language that has a lot of grammatical rules. It's very hard to model all of these rules, so we ended up making simplifications. For instance, in the query "Which cards does john have?" we ignored both the which and the have, despite the fact that these do both have meaning in real English. But we decided that it would be fine to create a more simplistic model of the language, as Cluedo has only a very limited vocabulary and it's possible to infer the meaning of the whole sentence from just a few words. The above query could be simplified down to "cards does john" (and it is simplified to this in our program), and whilst this makes no sense in real English, and this can only really mean one thing in the context of a game of Cluedo. It was this kind of situation where using difference lists really paid off, it is very simple (and computationally quick) to remove a word from the start and the end of a list using this technique.

The other problem we had was words being used in multiple instances to mean different things - the contextual information was often just as important as the individual word. For instance the 'has' relationship means two different things depending on the context. In the context of "Who has the study" it is a call to loop up which player is in possession of the 'study' card. But in the sentence "John has the study" it is instead an assignment operator - it is an instruction to record the fact that the player 'John' is in possession of the card 'study'. We solved this by flagging the 'has' query depending on the initial word. When the first word was 'Who' then has was actually replaced with the word 'query_has' to differentiate it from other instances. This was made very easy due to the use of difference lists.

Overall we were very proud of our interface. It is able to understand a wide variety of commands and provide an appropriate response. We do feel that the Prolog interface is not the best use for our program, it's a little cumbersome to type ask("<question>", A) and then to read what the answer is. If we were to continue developing this, we would like to make a UI element to plug the program into. Preferable made in a different language (such as Java, or maybe a web based interface), it would be though this the users would interact. This interface would read in commands from the user, then pass them to our program to parse them and return an answer. This answer would then be displayed to the user in a much cleaner manner.

However, we feel Prolog was the best choice for the actual parsing of natural language. In particular, difference lists made it very easy to separate commands down to singe atoms that could be parsed for meaning.

User's Guide to Using the Cluedo Notebook Program

Welcome to the e-notebook for Cluedo! The following is a guide on how it can be used to help you (potentially) win your game of Cluedo.

Steps to follow:

At the start of the game, once you have been dealt your cards, please tell the e-notebook which cards you have. You can do so by typing in: ask("I have the <card>",A).

Don't forget to hit enter. Then hit the semi-colon ";" button until you're told either true or false. It will return with A=p1, which is you, and false. Capitalization and question marks within the quotation marks are optional. Make sure that you replace <card> with whichever cards you have been given, if you receive the 'dagger' card then <card> should be replaced by the word 'dagger'. You must do so for every card that you've received. So the game should start with you typing in the specified ask command once for each card.

Make sure that as you go along, you add additional information that you find out from other players to your e-notebook. You can do so by typing in: ask("Bob has the <card>",A). Bob should be replaced by the player's name and <card> should be replaced by whichever card they have.
If it's your turn and you'd like a suggestion for what you should do next, you can get help from your e-notebook. You need to first tell the notebook which room you're in. You can do so by typing in: ask("I am in the <room>", A). This will return true. You can then ask what you should do next: ask("what is my next move?",A). It'll either tell you that you can ask a question and give you the question to ask, or tell you that it has a solution for you and provide you with the solution, or it'll give you an error. You will only get an error if you add information that is incorrect! So only tell the program something that you are positive about.

Summary of Queries to Ask the Notebook/Additional Notes

You should always be following the format of: ask(S, A). where S is your question in quotation marks and A is as is. As you play, you can ask the following questions as well:

ask("who has the library",A).

Should return with A=answer or false if no one has it.

ask("which cards does p1 have", A).

p1 can be substituted with other names.
Should return with A=card or false if p1 has no cards.

ask("what <rooms/weapons/characters> does p1 have", A).

Replace <rooms/weapons/characters> with just 1 of the 3, and it'll tell you that A=answers, or false if p1 has no cards.
Note: In general, if you try to add a card that does not exist or has already been added, the program will just tell you false.

Code

All code is issued under a license.

Project Code

All of our code can be found on our GitHub repository, where it is available under a Attribution-ShareAlike 4.0 International license.

Testing Code

We also have our testing code available on this repository. However in order to run this some configuration may be required.