Implement an AI-Powered Word Guessing Game using C#

During the trimester, weekly practical classes will re-enforce principles of the associated lecture topic. Of these, there will be five programming exercises whose solutions should be archived into a portfolio and submitted along with the main assignment at the end of the trimester. These exercises should be worked on in scheduled practical class time, and students can support/help each other provided that no actual code is exchanged between students, whether embedded in an email or attached as a separate file. In contrast verbal discussion and/or communication by free text grammatical social media is encouraged. In the portfolio, each successful exercise solution is worth three marks. For example if 4 exercises are specified for assessment but only 3 are successful, you will be awarded 3/5 th’s of 15% i.e 9/15 towards the final mark.

An inherent requirement of many computer games is to incorporate the ‘computer’ as an adversary (single player computer games). Usually the computer has to behave like a ‘real’ player and the extent to which this is achieved reflects the level of AI. Your assignment is to implement a game of ‘Guess The Word’ in which the computer always sets the word and you (the human player) has to guess the word - but in this case there is a ‘twist’ – the computer can cheat – it has access to a dictionary and is able to change the chosen word on the fly during the game so as to avoid matches proposed by the human player trying to guess the word. This should make the computer very difficult to beat.

1. Player one chooses a secret word, then writes out a number of dashes equal to the word length.

2. Player two begins guessing letters. Whenever he/she guesses a letter contained in the hidden word, player one reveals each instance of that letter in the word. Otherwise, the guess is wrong.

3. The game ends either when all the letters in the word have been revealed or when player two has run out of guesses.

Fundamental to the non-cheating game is that player one accurately represents the word he/she has initially chosen throughout the game. However in the cheating version player one (in this case the computer) isn’t committed to keeping a word, but rather maintains a list of possibilities on each turn within the constraints of the known letters player two has correctly guessed. In order to understand the algorithm for how this works one needs to understand the concept of ‘word families’. Basically the computer ‘remembers’ a word family on each turn. Consider for example, a small dictionary of only six words all of length 4:

Portfolio (15%)

ALLY BETA COOL DEAL ELSE GOOD

At the start, the word list is all the six words. Player two guesses a letter, lets say he/she guesses ‘E’. Player one (the computer) can now classify the following three word families from the word list:

1. _ _ _ _ no letters match, which include ALLY, COOL and GOOD

2. _ E _ _ includes BETA and DEAL

3. E _ _ E includes ELSE

Player one (the computer) now ‘chooses’ one of the word families that hopefully will reveal as little as possible about the possible word; there are various strategies to do this eg the largest family – which in this case is word family 1 (size of 3 words) which has no matches and player two is informed the guess of letter ‘E’ is wrong. Player one’s word list is now reduced (or now equates to) the chosen word family which is:

ALLY COOL GOOD

Now suppose player two guesses letter ‘O’. Player one’s families are now:

1. _ _ _ _ no letters match, which include ALLY

2. _ OO _ includes COOL and GOOD

The computer now chooses family 2 because it is the largest family (2 words), and informs player two the guess was correct with the match>

_ OO_

The computer’s word list is now reduced to>

COOL GOOD

Now suppose player two guesses letter ‘T’. In this case there are no letter matches and so the word family (word list) remains the same (and being the only family by default is the largest) and player two is informed the guess was wrong.

In any game scenario (dictionary, guesses) there are two possible final outcomes. Either player two reduces the word list down to one word and is able to guess the word and so wins (the computer then congratulates the player) or (and a more common outcome) player two will be completely stumped and will run out of guesses and loses. When this happens, the computer can pick any word from its current list and claim it is the chosen word all along. Player two in theory would have no way of knowing that player one was dodging guesses the whole time – it looks like player one simply picked an unusual word and stuck with it for the duration of the game. 

You may well find code on the internet or in textbooks that provide related solutions to this assignment. In order to encourage your own development of a solution rather than use of other software your implementation must conform to the following two requirements:

Main Assignment (85%)

1. Language must be C#

2. Application must be console based (a GUI interface would be an unnecessary distraction to the AI aspect of this work).

1. Read the file dictionary.txt (Official Scrabble Player's Dictionary, 2ndEd containing over 120,000 words).

2. Prompt the user for a word length, re-prompting as necessary until a number is entered such that there's at least one word that's exactly that long.

3. Prompt the user for a number of guesses, which must be an integer greater than zero.

4. Prompt the user for whether to display a running total of the number of words remaining in the word list (ruins the illusion of a fair game but useful for testing).

5. Play a game of Guess The Word using the following algorithm:

Construct a list of all words in the English language whose length matches the input length.

Print out how many guesses the user has remaining, along with any letters the player has guessed and the current blanked-out version of the word. If the user chose earlier to see the number of words remaining, print that out too.

Prompt the user for a single letter guess, re-prompting until the user enters a letter that hasn't been guessed yet. Make sure that the input is exactly one character long and that it's a letter of the alphabet.

Partition the words in the dictionary into groups by word family.

Find the most common “word family” in the remaining words, remove all words from the word list that aren't in that family, and report the position of the letters (if any) to the user. If the word family doesn't contain any copies of the letter, subtract a remaining guess from the user.

If the player has run out of guesses, pick a word from the word list and display it as the word that the computer initially “chose.”
If the player correctly guesses the word, congratulate accordingly.

6. Ask if the user wants to play again and loop accordingly.

You might want to spend a bit of time thinking about the design of your program rather than plunging straight in with the coding.

1. How are you going to implement the word list and the word families (think arrays, or lists, or variations of this?

2. Both frequency and letter position must be considered in construction of the word families.

3. How will you pattern match between the partially guessed word and words in a word family?

Program requirements

4. To achieve a really good mark, you need to optimise the Guess the Word algorithm (step 5 in the above code development). Currently it is by no means optimal – for example picking the largest family is not always the best way to cause the human to lose. Perhaps the algorithm can be improved by weighting the word families by some other metric not based on largest size (or size at all). Perhaps you might consider having the computer “look ahead” a step or two by considering what actions it might take in the future (eg a minimax strategy). Perhaps the number of guesses left could be used in some way to improve the algorithm. You are encouraged to explore any technique you can think of to improve the algorithm. Be aware that there are many ways of optimising the Guess the Word algorithm and no one solution will define a single definitive ‘answer’ to this assignment.

5. I suggest that you implement the assignment in its basic form, and when you have a working solution explore strategies to improve the algorithm.

6. When the user specifies a word length, you will need to check that there are indeed words of that length in the dictionary. The longest word in the dictionary has length 29, but there are no words of length 27 or 26. Be sure to take this into account when checking if a word length is valid.

Structure your submission with a folder named after your sid e.g. ‘sid1234567’ This folder should itself contain two folders, one called ‘Portfolio’ and the other main assignment folder called ‘WordFamilies’ or similar. The portfolio should contain one folder per assessed exercise, each containing two files, the C# source code (.cs) and the C# executable (.exe). The main assignment folder should contain;

1. Source (.cs) and compiled code (.exe) files, and any other relevant files to run the program (eg example .txt files).

2. A pdf or word file document report to include:

a) 600 word evaluation of the game development and attributes (for example, discussion of classes and/or data structure(s); strengths and limitations of the implementation).

b) A copy of the source code content reproduced in the word/pdf file as Appendix 1, suitably formatted.

c) Instructions for running the program in an Appendix 2.

The main assignment mark will be an amalgamation of four equally weighted components. See the separate mark scheme/ mark sheet for details on how this assignment will be marked. Note that evenif your main assignment program is not fully functional (or even will not compile) you can still get credit for the program design, coding and evaluation. Feedback will be available in 2 ways a) via an email sent to each student which will contain personalised content, and b) via e-vision accessible by students listing percentage, grade and outcome (subject to assessment board rules).

If you are unfortunate enough to require a reassessment (normally as second attempt but possibly as a first attempt), you should re-submit the Word Families main assignment by the standard due date for Trimester 1 2020-21 resubmissions, and your mark out of 100% will be calculated on this new main assignment only (usually the system will cap this at 40%). Note there will be NO portfolio component to submit or considered irrespective of how well they were undertaken at the first attempt. You are encouraged to explore a different approach to achieving a solution to the main assignment compared to the first attempt.