To discuss a strategy to play against Pacman, the ghosts send each other messages in English, encryped by a bijective mapping from the alphabet (a-z) to a permutation of the alphabet. Pacman intercepted an encrypted message of the ghosts, which is a string consisting of lower case letters (a-z) and spaces. Let this string be X, and assume no missing or extraneous spaces. Pacman decided to cast this problem as a search problem: he is searching for a mapping (equivalently, a length-26 sequence of letters) that maps the encrypted message X to a readable paragraph. Each search state is a mapping. Pacman assembled set W, a sufficiently large collection of English words that covers the ghosts’ vocabulary. But the ghosts make some typos in their messages. A) Goal test
i) Provide a reasonable goal test in terms of X and W that generally works despite that there are typos. Then, explain the rationale of your goal test in at most 2 sentences.
ii) Assume that the original message (before the ghosts encrypted it to X) does not have typos and contains all the letters in the alphabet. Is it guaranteed that you will find the correct mapping (the one that the ghosts are actually using) with your goal test? If so, explain your reasoning in 2 sentences; otherwise, give an example of a letter in the original message that is hard to get correct and explain your reasoning in 1-2 sentences.
iii) Describe a scenario that your goal test does not work, and explain why. You should complete your answer in no more than 3 sentences.
B) Recall that each search state is a mapping. For part (b), assume perfect goal test and that we are using tree search.
i) Give a start state and a set of legal actions such that DFS is guaranteed to reach a goal state. Explain in at most 4-5 sentences, why DFS is guaranteed to reach a goal state for your proposed start state and legal actions.
ii) What is the time complexity of running DFS on your proposed formulation of search?
iii) For your proposed start state and legal actions, is BFS guaranteed to reach a goal state?
C) Recall that Pacman is searching for a mapping that decodes the encrypted message X to a readable paragraph. Pacman found a 26 by 26 matrix [aij], where aij is the probability that the ith character is followed by the jth character in English words. He decided to formulate the search as follows: The start state is the mapping that maps a-z to itself (not decoding anything). A legal action is to swap two characters in the decoding mapping (the decoder). For example, from the start state, swapping a and b results in a decoder that maps the alphabet to "bacde...", which is a legal action. This decoder swaps only a’s and b’s and leaves everything else unchanged.
Help Pacman complete this search problem by completing the following:
• Provide a non-trivial cost function and a non-trivial heuristic.
• Discuss how the heuristic could meaningfully guide A* search.
• Explain whether the heuristic is admissible and/or consistent.