For EACH of the following search methods below, answer both of the following questions two questions:
EXPLAIN YOUR ANSWER - No credit will be given to a plain YES/NO answer without the corresponding explanation.
Let us consider the problem of search in a three-player game. You can assume that no alliances are allowed. We will call the players A, B, and C for convenience. The first change is that the evaluation function will return a list of three values indicating (say) the likelihood of winning for players A, B, and C, respectively.
Complete the following game tree by filling out the backed-up value triples (i.e. find correct values for the "??") for all remaining nodes, including the root:
to move A (?? ?? ??) / \ / \ B (?? ?? ??) (?? ?? ??) / \ / \ / \ / \ C (?? ?? ??) (?? ?? ??) (?? ?? ??) (?? ?? ??) / \ / \ / \ / \ / \ / \ / \ / \ A (+1 +2 +3) (+4 +2 +1) (+6 +1 +2) (+7 +4 -1) (+5 -1 -1) (-1 +5 +2) (+7 +7 -1) (+5 +4 +5)
- Problem 1: Remember that the search methods described in class assume the following things: - Each node in the search tree has a finite number of children. - No branch in the search tree contains the same node more than once. - The search tree may have branches that are infinitely long. - All costs are positive numbers. In fact you can assume for this HW that all costs are positive integer numbers. - Problem 2: The idea of the 3-player game described in this problem is that each player selects the move that MAXIMIZES his/her own gain (without worrying about minimizing the other players' gain). That is, player B selects the move with the highest 2nd component among all his/her options. - Problem 3: Notice that: - The problem statement tell you that BARTENDER uses backward chaining. - Note that BARTENDER tries to prove the conjectures/hypotheses in the order in which they appear in the list. That is, if BARTENDER is expected to serve Bond's Champagne then it recommends Bond's Champagne else if it is expected to serve Chateau...Red then it recommends Chateau...Red else if it is expected to serve Toe Lakes Rose then it recommends Toe Lakes Rose else if ... - For Part 2: Note that the working memory should INITIALLY consist of basic assertions, i.e. assertions that do NOT appear as the consequence of any of the rules. - Problem G: A perfectly legal answer to this question is to PROVE that no such procedure is possible.