AI (CITS4211) Lab Sheet Two

Mind Games Forever

1. Refresh your knowledge of Java (some more), including using jars and interfaces along with javadoc documentation.
2. Provide a "hands-on" introduction to the agent model and agent function used in Russell and Norvig and throughout this unit.
3. Introduce the agent package used throughout this unit.
4. Start to think about search and search trees.

Preparatory Work

"Word Chess"

As an example, the following puzzles are due to A. J. Berghuis.¹

a) Change SICK to WELL in 4 moves. S I C K _ _ _ _ _ _ _ _ _ _ _ _ W E L L

b) Change SOFT to LOUD in 3 moves. S O F T _ _ _ _ _ _ _ _ L O U D

c) Change WEEK to YEAR in 3 moves. W E E K _ _ _ _ _ _ _ _ Y E A R

d) Change CENT to DIME in 4 moves. C E N T _ _ _ _ _ _ _ _ _ _ _ _ D I M E

Give these a go yourself (by hand) first to get the hang of it. You can find more examples at their "Word Chess" site.

Note that while the above examples can be solved using only letters found in the final word (since the optimal number of steps is less than or equal to the length of the word) this is not the case in general. In some cases it may be necessary to go via intermediate words containing letters that do not appear in either the start or finish words. For example, try DRY to WET in 6 moves. Your program should allow for this more general case.

Software Downloads

Notice that javadoc documentation for the above jars is also available from the unit web page.

Programming Tasks

1. Create a class WordPuzzle. The class should store a StringBuffer of uppercase letters. The class should also include an equals method, a toString method, and be cloneable. This class will later implement the Environment interface.

2. Create a class SnapShot that implements the interface Percept. SnapShot should contain a String representation of the word stored in WordPuzzle.

3. Add to WordPuzzle a method getPercept that returns a SnapShot.

4. Create a class Step containing the fields position and to. The first holds the position of the letter to change, the second holds the letter to change it to. Make this class implement the Action interface. The getCost method should return a value of 1.

5. Add to WordPuzzle a method update(Action step) that updates the contents of the puzzle according to the step passed. It should also print out the new value of the stored word. (If position is outside the word there should be no change to the word.) You should now make your WordPuzzle class implement the Environment interface.

6. Create a class WordSmith that implements the interface Agent. This will be your "intelligent" agent for solving word puzzles. Like most beings however it will start off without so much intelligence. For the moment implement the method getAction described in the interface so that for each call it returns a Step that cycles the characters of the string in turn. Thus if it starts with the string BOB, the sequence that it generates (on successive calls to getAction) will be:

   BOB
   BOC
   BOD
   . . .
   BOZ
   BOA
   BOB
   BPB
   BQB
   . . .
   BZB
   BAB
   . . .
   BNB
   BOB
   COB
   . . .
   ZOB
   AOB
   BOB
   

   Notice that this sequence includes all character strings that differ by one character from the initial sequence.

   Hint: You may find it easiest to convert the string to a character array, and use methods such as getNumericValue in the class Character. Clearly you will also have to remember some state information, such as the word you started with, and which character you are currently cycling.

7. You have now created your first agent! Create an executable class RunPuzzle that runs the agent as follows:
   1. Accept a start word and an end word (eg from the command line). Initialise the puzzle with the start word.
   2. Do the following loop while the word (percept) is not equal to the required end word:
      • get the percept from the word puzzle
      • pass it to your WordSmith agent
      • pass the action returned by the agent to the update method of the environment (puzzle).
   3. Halt once the end word is found and report a success.

   Run your program on a puzzle in which the start and end words differ by only one character. Check that it works as expected.

8. So far we are of course just cycling through strings, rather than valid words. You can check whether a string is a legal word using the open source Jazzy package that you downloaded earlier.

   The following code provides a demonstration of using the Jazzy package to check the validity of a word. (Note: Some problems have been noticed with uppercase words - you may need to convert to lowercase.)

   try {
     SpellDictionary dictionary = new SpellDictionaryHashMap(new File("egnlish.0"), null);
     SpellChecker spellCheck = new SpellChecker(dictionary);
     int result = spellCheck.checkSpelling(new StringWordTokenizer("HELLLO"));
     if (result == SpellChecker.SPELLCHECK_OK) System.out.println("Valid");
     else System.out.println("Invalid");
   } catch (Exception e) {
     e.printStackTrace();
   }
   

   Add some calls in your WordPuzzle game to ensure that only valid words are allowed. Change your agent function so that only valid steps are returned. Run your program to check that it works correctly.

9. Challenge

   Your agent should now be able to solve some very simple word puzzles.

   Start to think about how you could build a better solver.

   • What kind of search would be appropriate? What problems would you run into?

   • Do the nodes in this problem form a graph (a network of interconnected nodes) or a tree (a special kind of graph with, among other things, no cycles)? If a graph, can it be made into a tree by making use of the equals method? At what cost?

   • Recall that searches, or traversals, through nodes can be achieved using a depth-first search or a breadth-first search. The former can be achieved recursively (or using a Queue), the latter using a Queue.

     If a graph of nodes has cycles, which of these will (a) definitely terminate, (b) possibly terminate, or (c) definitely not terminate, for the cases where (i) a solution exists, and (ii) no solution exists? How will this be affected using the equals method as discussed above?

   • Which if any of the above searches will find the optimal (shortest) solution?

   Feel free to post your conjectures to help4211. We will continue to look at search in more detail as the unit progresses.

1. The examples shown are copyright AJBerguis and reproduced for educational purposes only.

Copyright © 2010, CSSE School of Computer Science & Sofware Engineering The University of Western Australia.