CSci 356 - Homework 2

Due: Wednesday, Feb.19, 2025

This assignment is worth 50 points. For full credit:

Reading: AI:FCA, Ch. 1 Section 1.2, Ch. 3 Sections 1 - 7.

Written Part (25 points).

  1. (15 points) These historical AI systems are all introduced in Chapter 1 of the textbook; some were developed before the term "artificial intelligence" was coined!
     
    Pick three of the systems listed below to research and write one to three paragraphs about each, expanding on the text's descriptions. Be sure to include the year the program was developed (or the paper describing it was published), the goals of the system or problem it was intended to solve, and if you can find out, the programming language used to develop the system:
     
    • Terry Winograd's SHRDLU
    • Samuel's 1952 checkers program
    • Wang's logic theorem prover
    • Warren and Pereira's CHAT-80
    • McCulloch and Pitt's formal neuron model (not a program, more a descriptive model)
    • The perceptron neural model of Rosenblatt
     
  2. (10 points) Winograd schemas have been proposed as an alternative to the sorts of questions typically used in the Turing Test. An example of Winograd schemas and an interaction with the version of ChatGPT released in 2022 appears in Example 1.2 in Chapter 1 of the textbook. For this problem:
    •  give the two main properties of Winograd schemas
    • come up with three statement/question pairs of your own that might be posed to ChatGPT
    Extra credit if you use your schemas with an LLM like ChatGPT and provide the transcript.

Programming Problem (25 points - 5 points each).

Here we'll experiment with and modify the search problem examples described in Chapter 3 of aipython.pdf; here's a quick breakdown of each section:

For each problem, you'll run the Python code with ipython as before: ipython -i program.py where you'll replace program.py with the actual file name.

  1. Run the program searchGeneric.py as described in Sec. 3.1 then run each executable line of code from lines 61-68 interactively as suggested in the paragraph just above those lines of code. That is, you'll create two objects of type Searcher, then run the search method repeatedly until no more solutions are found. Grab a screenshot of your results.
     
  2. Run the program searchGUI.py then interactive execute SearcherGUI(Searcher, searchExample.simp_delivery_graph) at the iPython prompt. You'll get a graphics window showing the graph for the robot delivery problem. Press the Step button repeatedly to see the nodes explored by the DFS algorithm used by Searcher.

    The matplotlib window that displays the graph has a Disk icon that opens a dialog box to save the currently displayed image as a PNG file. Use this to produce two files: one image showing an intermediate step where the goal state has not yet been reached, and one showing the solution.
     
  3. The Searcher class can be easily modified to run the BFS algorithm instead of the DFS algorithm. To do this, change the code in the method add_to_frontier so that it uses queue discipline (first-in, first-out) rather than the stack discipline it currently uses (last-in, first-out) when add new path nodes.

    Now re-run the examples from Problem 1, show the results, and discuss whether BFS or DFS performs better here. Granted, it is a very small example.
     
  4. The class AStarSearcher is implemented in this same Python file. Again, there are example runs commented out in the section from lines 160 to 175. Run these as we did in Problem 1. Produce a screenshot for each run of AStarSearcher; be sure to call the search method until it no longer returns new results.
     
  5. Attempt AIPython Exercise 3.2; document the comparison to A* requested (number of paths expanded, path found by each)

Deliverables.

Written part:

Programming part: