Wednesday, May 9, 2012
Seats in 571 for Fall
Monday, May 7, 2012
Common errors on the final: One last mail before grades
*CORRECTED* Re: Final Cumulatives
Folks:Attached please find the final cumulatives (with the marks from take-home final also put in).The total is calculated with 20% weightage for the final. So the maximum points one could have got on cumulative was106.6.The current cumulative totals are shown.The students at the top of each of the sections are guaranteed an A+. They (i.e., these two student)are welcome to suggest grade cutoffs for the rest of the classin their respective sections. (The suggestion will only be non-binding of course; however I find that the students tend to have a better idea of thecomparative ease/difficulty of the courses--and so it is reasonable to consider their input on the grade cutoffs)The final letter grades will be posted sometime tonight.regardsRao
Final Cumulatives
Monday, April 30, 2012
Homework 3 Grading
--
Kartik Talamadupula
Re: CSE471: Where to Turn In Final
yes. If I am not in my office, you can turn it in at the main office and ask them to put it in my mailbox (they will put a stamp and put it in my mailbox).
RaoOn Mon, Apr 30, 2012 at 3:47 PM, Kevin Wong <kkwong5@asu.edu> wrote:
Hello,Will the take-home final exam be turned in at your office?Thank you
Re: CSE471: Where to Turn In Final
Hello,Will the take-home final exam be turned in at your office?Thank you
Sunday, April 29, 2012
Missing image in part G of homework 3 Re: CSE 471: Homework 3 solution
Hi,In the solution for part G of homework 3, the image cannot be displayed. Can you check this, please?Thank you--
Phien Pham
Saturday, April 28, 2012
Reminder about the "NO CONSULTATIONS WITH OTHER STUDENTS" clause of the take-home
Friday, April 27, 2012
Final Exam released..
Thanks for all the ballot stuffing ;-)
Thursday, April 26, 2012
Heads up on Final Exam release..
Wednesday, April 25, 2012
Cumulatives with homework 3 grades
Monday, April 23, 2012
Fwd: course evaluations
From: James Collofello <JAMES.COLLOFELLO@asu.edu>
Date: Mon, Apr 9, 2012 at 9:20 AM
Subject: course evaluations
To: "DL.WG.FSE.Faculty" <DL.WG.FSE.Faculty@mainex1.asu.edu>
Colleagues,
I sent the message below to all of our students. Please reinforce this messaging with your students.
Engineering Students,
As this semester comes to an end, you will soon be receiving requests to complete engineering course evaluations. We are committed to continuously improving the educational experience of our students. Your course evaluations provide important input to this process which is reviewed by Program Chairs and School Directors as they evaluate curriculum. Your course evaluations are also an important component in faculty performance evaluations impacting decisions regarding reappointment, tenure, promotion and merit. Please complete your evaluations.
James S. Collofello
Associate Dean of Academic and Student Affairs
Professor of Computer Science and Engineering
School of Computing Informatics and Decision Systems Engineering
Ira A. Fulton Schools of Engineering
Arizona State University
Agenda for tomorrow's class---is in your hands..
Sunday, April 22, 2012
Saturday, April 21, 2012
Re: Question related to previous lecture.
From: William Cushing <william.cushing@gmail.com>
Date: Fri, Apr 20, 2012 at 11:25 PM
Subject: Re: Question related to previous lecture.
To: Subbarao Kambhampati <rao@asu.edu>
Cc: Juan Guzman <jcguzma1@asu.edu>
Well I suppose Rao CC'd me since I know a bit about games. So here's info...but perhaps more than you wanted...
Opponent modeling is (very, very, ...) hard; an opponent can figure out that you've figured them out (or just get worried about the possibility) and suddenly change their style of play (for example, play randomly for a spell).
Last time I checked the case of Poker, which is perhaps as much as 5 years ago (or more!), the state-of-the-art had shifted back to not using opponent modeling, partially because of this sort of issue,
and partially because the state-of-the-art in finding the optimal line of play had advanced.
Specifically the advance that I'm aware of is to use state abstraction in order to produce a smaller, simpler game.
One that can be brute-force solved for the optimal strategy.
In that instance, it beat the then reigning approach based on opponent modeling.
One thing to keep in mind about Poker is that `bluffing' is a part of optimal play---in the Nash sense---and is something that two infinitely computationally powerful and rational agents would do to one another.
In *real-life* poker, the people who make the money are the people who ``play the odds''.
It is only in popular culture that we imagine Poker to be a game largely about opponent modeling.
In truth it is a fantastic exercise in relatively complicated statistical theory---and self-control.
The practical variant is of course investing in the stock market.
The most interesting work in opponent modeling that I'm aware of is for Rock Paper Scissors.
Here the Nash strategy is easy to compute, so, in a tournament setting, if you want to win the tournament, you *have* to be better at opponent modeling than everyone else is.
That is, the Nash player(s) for RPS will place in the dead-middle of a tournament.
Those who attempt to win will make profit off of each other; half will place above average, and half below.
The winner of the year I looked at in detail is called Iocaine (a reference to Princess Bride, and descriptive of its algorithm).
You may have seen the relevant Star Trek episode concerning Data playing against a grand master of a made-up game (Stratagus?).
(The lesson is that the only way to lose is to try to win.)
--
Final word on opponent modeling: No one really wants to play in such lopsided settings.
Either the stronger player is teaching, in which case the point is far from trying to punish the student as much as possible for making mistakes,
or a handicap is imposed---which is still a form of teaching, in that the stronger player isn't going to be upset by losing (but they also aren't going to make any hasty or kind moves).
Kasparov against a not-chess-genius 10-year-old at a two-rook and queen handicap, for example, could be excused for taking 10 minutes to think.
Some like to look at a handicap as a challenge in opponent modeling; how can you provoke the weaker player into mistakes, working towards getting rid of their material advantage?
But the better way is just to play normally, and let the mistakes happen naturally, if they do.
If they don't, then play another game, and reduce the handicap :).
Long story short, even when you far outclass your opponent in domain knowledge or raw computational ability, in almost all situations (but not tournament-RPS) it still makes sense to pretend that you don't.
-Will
P.S. Oh, and regarding Deep Blue, basically IBM hired every grandmaster they could get their hands on, especially those with the most experience playing Kasparov, and they collaborated on extensive study of all of his games ever recorded (something such masters of course had already spent years of their life doing), largely to produce what is known as an ``opening book'' geared especially towards playing Kasparov, that is, one containing the greatest pertinent details on every game he has ever played (and has since been analyzed to death). I think little about the hardware or algorithms was very specifically targeted at Kasparov; after all, how can you? He wouldn't be best if he had blind spots that anyone else can identify. Recently much that was mysterious about Deep Blue is no longer `classified', but still much about the whole affair is hush-hush. Whether or not that opening book helped at all is debatable, obviously the games were not repeats of past games. From what I understand, the modern assessment is that Kasparov was defeated by his own humanity; the final games he lost in frustration, that is, it seems he should have been able to force a win if not for the unusual stress he had no experience in dealing with. (The type of stress is hilarious: he couldn't stare-down Deep Blue; his inability to intimidate the opponent befuddled him, or so the story goes. The poor technician tasked with implementing the computer's moves on the physical board describes his fear and trepidation upon approaching Kasparov quite colorfully.)
Modern chess-playing software is largely held to have surpassed Deep Blue, without resorting to special hardware, nor with any concerns about possibly being opponent-specific.
I don't know what the current reigning champ is, but for a spell I know Fritz was used as a study tool by most grandmasters (read: "Is stronger than.").
Opponent modeling is done a lot of time (and for games like Poker, it is pretty much de rigueur. )It may be less critical in chess where, at least at the grand master level, "optimal opponent" is a reasonable assumption.I don't off hand know whether Deep Blue did opponent modeling to any extent--the classic reference onDeep Blue is this paper:RaoOn Fri, Apr 20, 2012 at 5:02 PM, Juan Guzman <jcguzma1@asu.edu> wrote:
I had this thought during class, but I wasn't sure if it was necessarily relevant to the lecture.
Do agents like deep blue always assume an optimal opponent such as Kasparov? It seems to me that one would be able to deduce the expertise level of an opponent using the existing information of the game tree and analyzing the opponent's moves. Like the example you gave in class, If Kasparov would take 10 minutes to make a move against a 5 year old, we would consider it silly; If deep blue saw that the opponent kept making moves that were highly in its favor (mistakes) could we use that information to make the agent execute moves more suited to the situation? Rather than assuming that it's playing against a grand master and using min max, we can calculate the possibility of the opponent making an arbitrary (non optimal) move and make "bolder" moves as a result? Or does deep blue already make optimal moves regardless of the skill level of opponents?- Juan
Sent from my mobile device
Friday, April 20, 2012
Re: Question related to previous lecture.
I had this thought during class, but I wasn't sure if it was necessarily relevant to the lecture.
Do agents like deep blue always assume an optimal opponent such as Kasparov? It seems to me that one would be able to deduce the expertise level of an opponent using the existing information of the game tree and analyzing the opponent's moves. Like the example you gave in class, If Kasparov would take 10 minutes to make a move against a 5 year old, we would consider it silly; If deep blue saw that the opponent kept making moves that were highly in its favor (mistakes) could we use that information to make the agent execute moves more suited to the situation? Rather than assuming that it's playing against a grand master and using min max, we can calculate the possibility of the opponent making an arbitrary (non optimal) move and make "bolder" moves as a result? Or does deep blue already make optimal moves regardless of the skill level of opponents?- Juan
Sent from my mobile device
Thursday, April 19, 2012
*Mandatory* Interactive Review Question (Must answer as a comment on the BLOG)
=============
If you need to refresh the memory, the class notes page at http://rakaposhi.eas.asu.edu/cse471 has description of what was covered in each of the lectures.
A cool Java applet for Chess that shows the computer "thinking" its moves using min-max and alpha-beta & Quiescence search
Office hours 2-3pm today..
Monday, April 16, 2012
Bayes Net Project Answers and Stats
Undergrad:
max 64.5
min 42
avg 56.5
stddev ~7.2
Grad:
max 67.5
min 41.5
avg 61
std dev ~7
--
Check marks are one point, slashes are half points, and x's are no points.
Plus and Minus are for exceptional answers.
Showing the screenshots is worth a point, except for part 3, which is worth two points, and part 2, which is worth no points.
Every `interesting' number in a CPT is worth a point.
Short answer questions are one point each.
The following is a detailed breakdown and meant only as a reference, not gospel --- it may contain errors since I wrote it from memory.
--
Question 1:
The correct numbers are straightforward, very few lost points.
1 point for the diagram, 10 more for the CPTs, 5 for the calculations, 2 for the short answers.
Intuition:
Our belief in inferior plutonium should increase if we see that the slushies are liquified, as a possible cause of that is core meltdown, and in turn, a possible cause of core meltdown is inferior plutonium.
Of course if we directly observe a core meltdown then our belief should only be that much stronger in inferior plutonium.
At that point the state of the slushies is irrelevant, since slushie liquification is just a poor man's test for predicting whether core meltdown occurred.
Interestingly, if we know that a core meltdown has occurred and the water is poor quality, then we already have a good explanation for the core meltdown and so our belief should be somewhat lessened in the possible fault with the plutonium.
(For two things to both have gone wrong at the same time is harder to believe then just one thing going wrong!)
D-SEP: Regarding irrelevence of slushies once we know core meltdown: The formal test is to cut every path between the two nodes (with or without evidence depending on the type of path).
There is just one path connecting IP and SL, going through CM, and the configuration is not -> CM <-. Then knowing CM cuts that, and thus all, paths between IP and SL and we have that they are D-separated.
--
Question 2:
All but a handful got this wrong, so, a little theory first.
There are two key words: "perfect" and "exhaustive".
For a cause to be perfect it gives its effects with 100% probability, or, in propositional logic, a forward implication.
For causes to be exhaustive means that the effect occurs with 0% probability in the absence of all causes. In propositional logic, one could write a backwards implication (the converse), or the inverse.
So, encoding 1 (effects+converses):
(LW or IP) <=> CM
CM <=> GD
CM <=> SL
Or encoding 2 (effects+inverses):
(LW or IP) => CM
CM => GD
CM => SL
not (LW or IP) => not CM
not CM => not GD
not CM => not SL
There were 6 possible points for the encoding, 3 points for the calculations, and 2 points for the short answers.
Interpretation:
1) If SL, since causes are exhaustive, a cause had to be true, and there is only one: Core meltdown. Again there must be a cause, but, there are two possible causes. In the lack of any further evidence the best we can do is count those situations where IP is true versus false and infer the appropriate ratio, i.e., the best we can do is compute the probability. Assuming you didn't change the priors, then, the number is 0.52.
2) As before, but now we have additional evidence ruling out bad water as a cause. Left with only one possible explanation, again by the assumption of "exhaustive", it must be that the plutonium was bad. So the probability is 1.0.
3) The probability is 0, because there is no possible world in which IP holds given the evidence. This query is special though, because the probability of any and all queries given the evidence ~GD and SL is 0.
By exhaustive causes and SL, CM must be true. By perfect causes, then GD must also be true. But since ~GD is given, there cannot be any world satisfying any property.
Relation to Propositional Logic:
1) We could count possible worlds even in propositional logic, but, not in a `weighted' way (otherwise we are just doing straight up probabilistic propositional calculus already).
One can get the tool to tell you what the right numbers are by giving priors on IP and LW that are fair coin flips.
2) Exactly the same as in the probabilistic case, formally: SL => CM and SL gives CM; CM => (LW or IP) and CM gives (LW or IP), finally (LW or IP) and ~LW gives IP.
3) Given a contradiction, we can infer anything we like, the opposite of the Bayes Net situation. (In the net, IP either true or false is probability 0. In the propositional encoding, one could infer that it is simultaneously true and false.)
One could of course still get points for shorter answers, I am just being verbose. It was very unlikely to get points for either interpretation or relation to propositional logic if your encoding was wrong to begin with.
As a total freebie the CPTs were given 10 points for this question, where one was even permitted to change the priors around somewhat on IP and LW.
--
Question 3:
2 points is for giving GD just the parent CM, LW the parent CM, and IP the parents LW and CM.
1.5 points is for extra edges.
Less is for downright wrong networks.
In the ideal network there are 11 probabilities that need to be assessed, and there are 11 points awarded if your network includes those values in the right places (duplicated however many times needed by redundant parents).
Note that you can use the original network as an oracle for more than just values --- you can also test conditional independence assumptions in order to figure out that GD does not need SL as a parent, yet, IP does need LW as a parent.
1 point if you said this network was worse than the original, or implied it well enough.
1 point if you demonstrated that your network reproduced the right values.
--
Question 4:
part a) 1 point for the diagram; 5 more points for the `interesting' numbers, i.e., the CPTs that are new/different.
part b) 1 point for the diagram; 8 more points for the differing numbers.
I was kind here regarding rounding---not that there was a choice since only one student noticed that one needed to provide 8 digits of precision to do the question justice.
(In general throughout the assignment any answer rounded consistently was acceptable.)
--
I was not kind regarding simple oversights, like swapping two numbers; the tool+assignment are too easy to use and complete and anyways there were tons of freebie points.
-Will
Latest cumulatives (with the project 3 as well as the at home version of the test 2 included)
Sunday, April 15, 2012
Applets URL corrected for homework 3
Saturday, April 14, 2012
Thinking Cap: A Post-Easter Resurrection..
Thursday, April 12, 2012
Next topic: Search in perfect information games: Chapter 5.1--5.3
Tuesday, April 10, 2012
Last homework-cum-micro-mini-project released
My mis-statement in class about the standard resolution refutation proof error
Grading for your homework 2
Monday, April 9, 2012
Current Grade Book (with test 2 and homework 2 scores)
Saturday, April 7, 2012
An easter egg in the form of Test 2 do-over..
Wednesday, April 4, 2012
Availability tomorrow
Some errata corrected in the Spring Field problem solution
Part B.[4pt] Given your network above, which of the following (conditional) independences hold? Briefly justify your answer in each case:
- Independence of inferior-quality plutonium and low-quality heavy water in Springfield nuclear plant
Given no evidence at all, they are independent of each other.
- Independence of inferior-quality plutonium and low-quality heavy water in Springfield nuclear plant, given watery slurpees over at Apu's.
Using D-SEP, we can see that once SL is given, IP and LH are not independent (the "common-effect" case; since neither CM nor any of its descendants can be in the evidence for IP and LH to be independent)
- Independence of low-quality heavy-water and wateryness of slurpees at Apu's, given core-meltdown
Using D-Sep again, LH is indepedent of SL given CM (since the only path from LH to SL goes through CM, and it is an inter-causal path, and it gets blocked once CM is known). Another way of seeing this is that CM is the markov blanket of SL, and so given CM, SL is independent of everything else.
Tuesday, April 3, 2012
Cleaned up most of the UTF-8 error chars in the springfield bayesnet example
Forgot to tell you about the Turing award for PAC...
Re: Review for Thursday
If you cannot make those times work for you, let me know and we can arrange to meet individually at another time.
-Will
Monday, April 2, 2012
Project 2 Grading
Tuesday, March 27, 2012
Geo-centric model and limit of Occam's razor.
Re: Project 3 bn/bif question
Hi,Quick question: In the project when it is asking for .bn, is it refering to the .bif text since that is the first option under the edit toolbar command? Or is it just copying only the probabilities section that the .bif text shows at the bottom? I'm confused since I cannot seem to find any "bn" reference in the applet.Thanks,
--
Ivan ZhouGraduate StudentGraduate Professional Student Association (GPSA) Assembly MemberEta Kappa Nu (HKN) Active MemberSchool of Computing, Informatics and Decision Systems EngineeringIra A. Fulton School of EngineeringArizona State University
Monday, March 26, 2012
Project 3 submission instructions..
Sunday, March 18, 2012
Re: Dawkins' rant on coin-toss superstitions
Hello Professor,I read this after the last class. What a coincidence! Couldn't resist sharing it with you.Thanks,
Srinath
Saturday, March 17, 2012
textbook writeup on D-Sep condition
Homework 2 will be due on 3/29
Tuesday, March 13, 2012
Grading for your project 1
Friday, March 9, 2012
Project 3 released; Due 3/27
Thursday, March 8, 2012
A worked out example on variable elimination
Monday, March 5, 2012
Office hours tomorrow from 2:30--3:30pm (instead of 1-2pm)
Project 2: Extra Credit
Project 2: Submission Instructions
Flip-flopping--from a cognitive, social and effectiveness stand points..
Rao
Tuesday, February 28, 2012
Thinking Cap: Why don't we talk of independence assertions in Propositional Logic..
Rao
Monday, February 27, 2012
Project 2 FAQs
Sunday, February 26, 2012
Re: Questions on Project 2
1. Does the planner jar you gave us support in preconditions? I seam to get error on the ones that is available in http://planning.cis.strath.ac.uk/competition/domains.html (UMTranslog-2)
Here is my code:
:precondition (and (at ?p) (or (connected ?h ?p) (connected ?p ?h)))
Output:
Exception while parsing domain robby!
edu.asu.sapa.parsing.ParseException: Encountered "(" at line 13, column 29.
Was expecting:
")" ...
at edu.asu.sapa.parsing.PDDL21Parser.generateParseException(PDDL21Parser.java:4230)
at edu.asu.sapa.parsing.PDDL21Parser.jj_consume_token(PDDL21Parser.java:4109)
at edu.asu.sapa.parsing.PDDL21Parser.AllIConditions(PDDL21Parser.java:1063)
at edu.asu.sapa.parsing.PDDL21Parser.InstantAct(PDDL21Parser.java:1139)
at edu.asu.sapa.parsing.PDDL21Parser.Action(PDDL21Parser.java:843)
at edu.asu.sapa.parsing.PDDL21Parser.ActionList(PDDL21Parser.java:835)
at edu.asu.sapa.parsing.PDDL21Parser.parse_domain_pddl(PDDL21Parser.java:62)
at edu.asu.sapa.Planner.main(Planner.java:73)
It works if I change to and instead of or.
2. Is there a way to give or in the parameters? For example Report needs to take in room and hallway. Currently I solved it using two actions report-room and report-hallway. I feel there should be a better way.
I checked the tutorials you had attached in the bottom of the project description. I couldn't find direct answer to my question there which is why I am mailing you.
Regards,
Srijith Ravikumar
Saturday, February 25, 2012
Homework 2 problems
Friday, February 24, 2012
Project 2: Tutorial
Thursday, February 23, 2012
Readings for next topic: Chapters 13 and 14 in 3e
Wednesday, February 22, 2012
Project 2 Preview available; Due March 8th; in class
Undergraduate research opportunity with my group..
A list of recent publications from the group can be found at http://rakaposhi.eas.asu.edu/papers.html
Tuesday, February 21, 2012
Thinking Cap 2: Search, Theorem Proving and SAT
In particular, given a heuristics h2 which is more informed than h2 (in that forall nodes n, h2(n) >= h1(n)), we can only show that the "interior f-contour" nodes expanded by search with h1 are also expanded by h2.
Specifically, consider a node n' such that f2(n') = g(n') + h2(n') < f* (where f*, the optimal cost of the goal node, is the same for both heuristics). So, n' will clearly be expanded by the search with h2. Since h1 <= h2, clearly f1(n') is also less than f*, and so search with h1 also expands node n'. This shows that the number of nodes on the interior f-contours for h1 can not be fewer than the nodes on the interior f-contours for h1. (An interior f-contour is the set of equi-f-value nodes with f-values less than f*)
The tricky part is that this subsumption doesn't necessrily hold for nodes that are on the "f* contour"--i.e. nodes that have
f1 or f2 equal to f*. Based on the tie-breaking strategy, a subset of these nodes will likely be expanded before the search terminates. If the subset expanded by h2 is more than that expanded by h1, search with h2 can do more expansions even though it is more informed.
See if you can think of possible reasons why this could happen. [hint: there is a slide in the informed search lecture--with annotation "advanced"--that gives the insights needed, if you are having trouble..]
Re: Anonymous feedback opportunity
Folks:
Here is a mr. poll link where you can give anonymous text-based feedback on the course.
<Removed from Blog; see email for link>
I encourage you to participate in it.
Rao
Anonymous feedback opportunity
<Link Removed from blog; see email for the link>
Exam solutions video (just 46MB!) and doc available online
Test 1 grades..
office hours change for today: will be available 2:30--3:30
Thursday, February 16, 2012
Homework Grading Rubric
The maximum homework scores are 65 and 64. After that are a handful of mid-50s. The median score is something like 43.
The mean is 39ish, the mean excluding the lowest scores is 41ish. The vast majority of the class scored in the mid 30s to mid 40s.
(The minimums are several 0s, of course, and among actual assignments are several sub-20 scores such as 6 and 12, as I recall.)
So a mid 40 is something like a B or B+. Low 50s and higher is definitely an A; I think there are about 7 such scores.
--
As I'm sure you can tell I began the grading in `reviewer' mode, i.e., how I would review a submission to an international conference or journal on artificial intelligence.
This is a mistake which was fortunately halted before total catastrophe ensued. Please
don't take my comments personally, indeed, feel free to entirely ignore them. Note that the grading is consistent and fair, at least, as well as can be expected
from a human being. In particular the drastic change in the level of commentary between the first and second halves means little besides a drastic change
in the level of commentary --- the grading itself was just as `harsh'.
It is worth noting that at least one (if not several) student(s) got a perfect (or above perfect) score on any given question (not the same students each time).
Also, the entire class average would likely go up by 10 or even 15 points had all the assignments been in fact complete.
The following is a break-down of how the final judgments were converted into points. This varies a little from question to question,
but the general idea is that correctness is worth a point and justification is worth a point, and that each question no matter
how large or how small was worth 2. Except question 1, where its 8 sub-questions are only worth 1 each.
--
All rounding is rounding up; all sub-scores are truncated to the maximum possible where scoring over maximum was possible.
Question 1: 8 possible points.
0/3 of a point for no example,
1/3 of a point for a flawed example,
2/3 of a point for a dubious example,
3/3 of a point for a fine example.
For any agent whatsoever in any domain, say X, a fine example consists of:
X with faulty/good sensors, with/without multiple agents, and with faulty/good effectors.
Other idioms are more appropriate for certain domains. For driving, for example, one might say:
Driving (not) in a blizzard, (not) on a closed course, and (not) drunk.
For poker:
Poker with(out) Extra-sensory perception, with(out) opponent's families as hostages, and drunk/sober. (Or dealer/not-dealer.)
Question 2: 6 possible points.
1/4 of a point for a incorrect answer with faulty explanation.
2/4 of a point for a correct answer with faulty explanation, or, for an incorrect answer with a good explanation.
3/4 of a point for a correct answer with a dubious explanation, and in some cases perhaps even for an incorrect answer (with fantastic explanation).
4/4 of a point for a correct answer with correct explanation.
The correct answers are that accessibility and determinism depend on the agent design, respectively due to sensor and motor/effector quality, while staticness is an environmental
parameter usually independent from agent design. (But there are exceptions.)
Questions 3 through 6: 22 possible points.
These are summed and rounded in one group. There are three possible marks in three possible positions:
A leading +/- indicates that the answer provided was deemed technically correct/incorrect. (X for not committing to a single clear answer.)
The following +/- indicates that the explanation provided was deemed adequate/inadequate. (X for not giving any explanation at all, or in some cases, an explanation worse than nothing at all.)
Each of those is worth a point.
Optionally a trailing +/- is a positive or negative half-point, modifying the score for the explanation.
All combinations are possible. In particular one could give an interesting explanation for a wrong answer and receive as much as 1.5 out of 2 points.
It is also possible to score 2.5 out of 2 points, which is the point of summing all of the questions together before rounding and truncating to the maximum score.
As the score "- - -" would be worse than no answer, these are first altered to "- - X", removing the negative modifier.
Most of the time the trailing modifiers cancel out or nearly so.
In theory one could have scored 2.5 points on questions 3 and 4, 10 points on 5.1 and 5.2, and another 2.5 points on question 6, which I may have neglected to truncate to the maximum score
which should be possible on the entire set: 2+2+8+8+2 = 22. If you have a sub-score above 22 on that part, you might want to avoid bringing my attention to it ;).
Question 7: 8 points total.
7.1 used the scale above. The correct answer to 7.1 is of course DFS, because of its vastly superior space-complexity and no loss of quality under these ideal-for-DFS conditions.
The other 3 parts were marked using +/- letter grades with the following meaning, as I recall:
A+ = 2.5
A- to A = 2
B+ = 1.5
C+ to B = 1
D to C = 0.5
X = 0.
The order these are listed in is 7.2.1, 7.2.3, and 7.2.2. A+ on 7.2 was for drawing the tree to depth 3 proper (and getting everything else right).
The correct answers to 7.2.1 and .3 are virtually the same; a barren sub-tree is effectively a special case of a highly non-uniform goal distribution at the leaves. The grading was
looking for non-uniformity as the reason to prefer iterative-broadening over DFS in 7.2.1, and the grading was looking for an appropriate connection to barrenness being made in
the answer to 7.2.3. Many answers were extremely difficult to parse or understand. Using specific examples greatly benefited those students who did so.
It was also a good observation to note that: if the left-most goal is halfway through the leaves in such a way that it is found at the cutoff b'=b/2 then IBDFS has a huge (astronomical for, say, b=100)
advantage. Note the solution guide suggests that the 3.1 etc. nodes are good for IBDFS --- this is incorrect. b'=b is the worst-case for IBDFS. For b=3 and d=3 there are actually
only 4 possible leftmost goals for which IBDFS would perform better than DFS, and so, `on average' it likely would not perform better except of course that we have little idea what
`on average' means except that it *isn't* a straight average over the leaves of the tree treating each as having equal likelihood of being the leftmost goal.
Questions 8-12: 32 possible points.
2 points per question mark plus 2 more for "Is the manhattan distance heuristic admissible." which I think was missing a question mark.
+ means full credit, i.e., 2.
- means partial credit, i.e., 1.
x means no credit.
These were all pretty straightforward.
-Will
Further notes on what was considered correct/incorrect:
Question 8 (2 points): There were quite a few similar strategies for attempting to prove question 8 using simpler arguments than the standard of "consider any other path at the time A* returns".
Virtually no one got points for this question.
Question 3 (2 points): In order of difficulty: partial-accessibility, complete inaccessibility, full accessibility. With partial-accessibility one has the option of designing the agent to pre-plan for contingencies, or re-plan when
the unexpected happens. With no sensors, neither is possible, so neither need be implemented. Not implementing is of course easier than implementing.
Question 4 (2 points): Detail is not always helpful. Up to a point a better model can help an agent improve its performance --- but a model of the entire universe at nanometer resolution is too far. There are two points: the computational burden
of too much detail, also, the more precise your model the more likely it is that it is inaccurate, perhaps gravely so. (In learning theory this is called *overfitting*, and deliberate simplification of a model to avoid such is called regularization. In planning
one would say abstraction rather than regularization.)
Question 5.2: There was a lot of confusion on this question. One point in particular is that the solution guide uses a very strict notion of what it means
to achieve a goal -- ruling out stochastic achievement almost as a matter of definition. It also isn't very clear that A2 isn't meant to be doubly handicapped.
Question 6 (2 points): IDDFS is a complete algorithm and so cannot possibly be performing infinitely more work than DFS --- the conclusion doesn't make sense.
The actual ratio is the ratio between the sum of the integers from 1 to D (which is D choose 2) by just D, which is (D+1)/2. (Where D=d+1, the number of vertices in the single path that is the entire search tree.)
EC (4 points): The ratio (b+1)/(b-1) stems from an average-case analysis, which involves much more annoying algebra than the far easier worst-case analysis.
I think that everyone who made a serious attempt got at least 1 point? Elegant psuedo-proofs got 2.
Tuesday, February 14, 2012
Re: [CSE471] Instructions for your Project-1 CODE
Hi all:I have created a link on Blackboard so that you can submit your Project-1 *code* (your report should be submitted before class, and in hard-copy). Please name your file as <first_name>_<last_name>.lisp.And as a reminder: the "early" deadline is 4:30pm, 2/14; and the extended one is exactly one week later.Please let me know if you have any question.Thanks,Tuan