Homework 3 -- due Tuesday March 25

1. [50 points] Answer the following questions from Russell and Norvig:
   1. [10 points] Question 6.2
   2. [10 points] Question 6.15
   3. [10 points] Question 7.8
   4. [10 points] Question 7.9
   5. [10 points] Question 7.12

2. [40 points] Do the following in Lisp.
   Do not forget to test your Lisp functions and submit both the functions and results on test cases using the IT Labs Submit Tool.
   You are to use the tic-tac-toe game agent available in the aima software.
   Look in search/test.lisp to see how to run a game, how to specify the agents playing in the game and the size of the board. For instance, to run the random-game-agent against the alpha-beta-ttt-agent on a game with n=4 and k=3 you need to do: (run-game (make-ttt-game :n 4 :k 3) :agents '(random-game-agent alpha-beta-ttt-agent))
   For your experiments use the alpha-beta-ttt-agent provided in the software and modify it as requested. Look in search/agents/ttt-agent.lisp for details on the agent.
   • study the effect of increasing the search depth used by the alpha-beta-ttt-agent. Try playing an alpha-beta agent which uses different depths, ranging from 1 to 3, against the alpha-beta-ttt-agent on a game with n=4 and k=3. Look at the moves played by the different agents to see what is the effect of changing the search depth.
     • Does the agent play better if the search depth is greater?
     • If you play the alpha-beta-ttt-agent against an agent with smaller depth (instead of playing the smaller depth agent against the alpha-beta-ttt-agent) do you get the same results?
   • change the evaluation function used by the alpha-beta-ttt-agent and see how this change affects the ability of the agent to win the game.
     • Play the alpha-beta-ttt-agent against an agent using your function on a game with n=4 and k=3.
     • Play your agent against the alpha-beta-ttt-agent.
3. [10 points] [Graduate Students only]
   1. Prove using resolution with refutation that D is entailed by the following set of propositions:
      1. ¬ A ⇒ ¬ B
      2. A ∧ C ⇒ D
      3. C
      4. B
   2. Prove using resolution with refutation that E is entailed by the following set of propositions:
      1. (C ∨ D) ⇒ ¬ A
      2. (D ∧ B) ⇒ A
      3. B ∨ D
      4. B ⇒ E ∨ A
      5. (A ∧ B) ⇒ (E ∨ C)
      6. A ∧ Z