Homework 3 -- due Tuesday March 9

Written questions

1. [15 points] Assume that generating the children of a node in a game tree takes time c. You are considering using one of two evaluation functions, e1 or e2. For any node n, it takes time t1 to evaluate e1(n) and time t2 to evaluate e2(n). Assume the branching factor in the tree is b and t1 < t2.
   1. under what conditions the time neded to search to depth d using e1 will be the same as the time to search to depth d-1 using e2?
   2. how does this change if you use α-β pruning [look at how the complexity of α-β pruning differs from the complexity of min-max with a depth bound].
   3. is it more important to have an evaluation function that is quick to evaluate for min-max or for min-max with α-β pruning?
2. [10 points] If a game is not a zero-sum game, should minimax be used? explain why or why not and give an example of a game tree to support your answer.
3. [15 points] Can α-β pruning can be extended to multi-player games? If yes, how? if not, why not? This is an open question. If you search the literature for answers, do not forget to cite the sources you consulted.
4. [15 points] Show in detail how to solve the following crypto-arithmetic problem I + DID = TOO.
   You have to use backracking search with the minimum remaining value heuristics to select the variable and the least-constraining value heuristics (if needed) to chose the value. Show the search tree explored by the backtracking algorithm.
5. [10 points] Given a constraint satisfaction problem with (1) a finite number of variables and (2) a finite domain for each variable
   1. how does the number of variables affect the size of the search space?
   2. how does the size of the domains affect the size of the search space?
   Explain your reasoning.

Lisp questions

For these questions we will use the constraint satisfaction software in AIMA (in search/agorithms/csp.lisp). There are two algorithms implemented, csp-backtracking-search and csp-forward-checking-search. In search/test-search.lisp there are two examples on how to call these functions. Look at search/domains/nqueens.lisp to see how to create a CPS problem.

1. [20 points] Use the the AIMA csp-backtracking-search function to solve the map-coloring problem shown in the textbook in Figure 6.1.
   Since in this software values of CSP variables have to be integers use the following code to specify the three colors:
   (setf *colors* '(1 2 3))
   Use this representation of the map which is modeled after the one used in AIMA for routing problems. Each sublist is a region, followed by a list of its neighbors.
   (setf *australia* '((sa (wa nt q nsw v)) (wa (nt sa)) (nt (q sa wa)) (q (nsw sa nt)) (nsw (v sa q)) (v (sa nsw)) (t)))
   You will have to write yourself a function to return the list of regions in the map and a function to check if two regions are neighbors in the map.
   
2. [5 points] Repeat the same problem on the Australia map this time using 4 colors. Is the solution different? Do you need 4 colors or are 3 enough?
3. [5 points] Can us use just 2 colors to color the Australian map?
4. [5 points] Repeat the same problem for the USA map defined here:
   (setf *usa* '( (al (ms tn ga fl)) (ak) (az (ca nv ut nm)) (ar (tx ok mo tn ms la)) (ca (or nv az)) (co (wy ne ks ok nm ut)) (ct (ny ma ri)) (de (pa nj md)) (dc (va md)) (fl (al ga)) (ga (al tn nc sc fl)) (hi) (id (mt wy ut nv or wa)) (il (wi in ky mo ia)) (in (mi oh ky il)) (ia (mn wi il mo ne sd)) (ks (ne mo ok co)) (ky (il in oh wv va tn mo)) (la (tx ar ms)) (me (nh)) (md (pa de dc va wv)) (ma (ny vt nh ri ct)) (mi (wi in oh)) (mn (wi ia sd nd)) (ms (la ar tn al)) (mo (ia il ky tn ar ok ks ne)) (mt (nd sd wy id)) (ne (sd ia mo ks co wy)) (nv (ca or id ut az)) (nh (me ma vt)) (nj (de pa ny)) (nm (az co ok tx)) (ny (vt ma ct nj pa)) (nc (sc ga tn va)) (nd (mn sd mt)) (oh (pa wv ky in mi)) (ok (ks mo ar tx nm co)) (or (wa id nv ca)) (pa (ny nj de md wv oh)) (ri (ma ct)) (sc (nc ga)) (sd (nd mn ia ne wy mt)) (tn (ky va nc ga al ms ar mo)) (tx (nm ok ar la)) (ut (az nv id wy co)) (vt (nh ma ny)) (va (nc tn ky wv md dc)) (wa (id or)) (wv (pa md va ky oh)) (wi (mi il ia mn)) (wy (mt sd ne co ut id))))