Unit 1 Lecture 3:Feb 04 Student A: From the text: "f(n) is an admissible heuristic- that is, provided that h(n) never overestimates the cost to reach the goal" Why does an admissible heuristic need to underestimate the cost of a node? It seems to me that it's more important how h(x) evaluates the cost of a node with respect to the cost of another node (predicting the optimal solution isn't the worst) rather than with respect to the actual cost (predicting that all costs are 5% greater than they actually are).? Student B Answers: We went over this a few times in class. If you overestimate the cost, you will skip certain paths that may be optimal and if you get the cost exactly right, you don't need to search, you just take the right path. Obviously you'd want an exact cost, but if you do that, the rest is irrelevant. CB Answers: My feeling is that Student A is asking a reasonable question, which I might put ``why do we care about absolute correctness (e.g. accurate path length) of a heuristic when really we're just making decisions and knowing relative goodness (this choice better than that) seems good enough?'' If you think about a-b search for game-playing, indeed it's not until you get into expected values that you care about the relative weighting of states (game positions). if A is better than B is better than C, it's OF if (ABC) are (1,2,3) or (1, 10 ,100). But in computing expected goodness you clearly need to be be more careful. Similarly with A*, the whole point of the admissible heuristic that approximates the TRUE path cost is to guarantee optimality. That is if you are guaranteeing to find the minimal cost path you gotta relate your measure to the path cost you're minimizing. Now it seems to me that ``true'' path cost may always be an approximation, so in a sense we should remember that these ``realistic'' path costs may actually be chosen for convenience and even with relative weightings of goodness in mind. Student C: Could we go over the pruning for a multiplayer game that does not involve chance? make tree like 0 123 1 123 -1 5 2 2 123 -1 5 2 545 0 (123) (421) 5 -1 -1 -1 5 2 7 7 -1 545 Key insights: Each player maximizes his own utility, the corresponding component in the utility vector. the entire vector is backed up, intact, since it representes the utility of the leaf node for all N players. Implement with rotating utility vector so the player to move is always first in the vector. As for alpha beta gamma etc. I don't see why that pruning idea should not work perfectly. Basically 0 knows some nodes won't be worth expanding since he can convince himself that 1 and (or?) 2 can force him to be in a worse situation than one he's already explored. Alliances are interesting question at this point ... term paper? May want to do sort of a ``diplomacy'' approach. Add Offer, Accept, Defect moves in to the tree. Might want constraints like tie-breaking in favor of current ally, maybe eating short-term pain for long-term good of the alliance, moves that could cause allies to defect, moving to guard against defection, weighing chances once third person eliminated, etc. How change evaluation function, especially to account for state (and history) of alliances. ------ The book's description of inference based agents was a little less clear than the one on circuit based agents. Could you talk about inference based agents (7.7 in RN), more specifically, how they work and a few examples of useful ones? Thanks. Justin Moore Good question, but it's unit 2 so we gotta be a bit patient.