Prove the following assertion: For every game tree, the utility obtained by MAX using minimax decisions against a suboptimal MIN
will never be lower than the utility obtained playing agains an optimal MIN. Can you come up with a game tree in which MAX can do still better using a suboptimal strategy against a suboptimal MIN?
1 answer:
Answer:
From the given diagram, consider a MIN node whose children are terminal nodes, if MIN plays
suboptimal. MIN will never be lower than the utility obtained playing against an optimal MIN
MIN will always select a move having minimax utility greater than or equal to the move that is
predicted by the minimax that is the MIN-played optimal value.
Then the MIN node's value is increased to MAX. This is done by induction.
One can do better than the minimax strategy, if the suboptimal play is predicted by MIN.
If MIN always falls for certain for certain kind of trap and losses, then setting up a trap guarantees a win.
Explanation:
See attached picture also.
You might be interested in
Answer:
Explanation:
Please see the attached picture for help.
Using the knowledge in computational language in C++ it is possible to write a code that cryptarithm is a mathematical puzzle where the goal is to find the correspondence between letters and digits
<h3>Writting the code:</h3><em>#include <bits/stdc++.h></em>
<em>using namespace std;</em>
<em>// chracter to digit mapping, and the inverse</em>
<em>// (if you want better performance: use array instead of unordered_map)</em>
<em>unordered_map<char, int> c2i;</em>
<em>unordered_map<int, char> i2c;</em>
<em>int ans = 0;</em>
<em>// limit: length of result</em>
<em>int limit = 0;</em>
<em>// digit: index of digit in a word, widx: index of a word in word list, sum: summation of all word[digit] </em>
<em>bool helper(vector<string>& words, string& result, int digit, int widx, int sum) { </em>
<em> if (digit == limit) {</em>
<em> ans += (sum == 0);</em>
<em> return sum == 0;</em>
<em> }</em>
<em> // if summation at digit position complete, validate it with result[digit].</em>
<em> if (widx == words.size()) {</em>
<em> if (c2i.count(result[digit]) == 0 && i2c.count(sum%10) == 0) {</em>
<em> if (sum%10 == 0 && digit+1 == limit) // Avoid leading zero in result</em>
<em> return false;</em>
<em> c2i[result[digit]] = sum % 10;</em>
<em> i2c[sum%10] = result[digit];</em>
<em> bool tmp = helper(words, result, digit+1, 0, sum/10);</em>
<em> c2i.erase(result[digit]);</em>
<em> i2c.erase(sum%10);</em>
<em> ans += tmp;</em>
<em> return tmp;</em>
<em> } else if (c2i.count(result[digit]) && c2i[result[digit]] == sum % 10){</em>
<em> if (digit + 1 == limit && 0 == c2i[result[digit]]) {</em>
<em> return false;</em>
<em> }</em>
<em> return helper(words, result, digit+1, 0, sum/10);</em>
<em> } else {</em>
<em> return false;</em>
<em> }</em>
<em> }</em>
<em> // if word[widx] length less than digit, ignore and go to next word</em>
<em> if (digit >= words[widx].length()) {</em>
<em> return helper(words, result, digit, widx+1, sum);</em>
<em> }</em>
<em> // if word[widx][digit] already mapped to a value</em>
<em> if (c2i.count(words[widx][digit])) {</em>
<em> if (digit+1 == words[widx].length() && words[widx].length() > 1 && c2i[words[widx][digit]] == 0) </em>
<em> return false;</em>
<em> return helper(words, result, digit, widx+1, sum+c2i[words[widx][digit]]);</em>
<em> }</em>
<em> // if word[widx][digit] not mapped to a value yet</em>
<em> for (int i = 0; i < 10; i++) {</em>
<em> if (digit+1 == words[widx].length() && i == 0 && words[widx].length() > 1) continue;</em>
<em> if (i2c.count(i)) continue;</em>
<em> c2i[words[widx][digit]] = i;</em>
<em> i2c[i] = words[widx][digit];</em>
<em> bool tmp = helper(words, result, digit, widx+1, sum+i);</em>
<em> c2i.erase(words[widx][digit]);</em>
<em> i2c.erase(i);</em>
<em> }</em>
<em> return false;</em>
<em>}</em>
<em>void isSolvable(vector<string>& words, string result) {</em>
<em> limit = result.length();</em>
<em> for (auto &w: words) </em>
<em> if (w.length() > limit) </em>
<em> return;</em>
<em> for (auto&w:words) </em>
<em> reverse(w.begin(), w.end());</em>
<em> reverse(result.begin(), result.end());</em>
<em> int aa = helper(words, result, 0, 0, 0);</em>
<em>}</em>
<em />
<em>int main()</em>
<em>{</em>
<em> ans = 0;</em>
<em> vector<string> words={"GREEN" , "BLUE"} ;</em>
<em> string result = "BLACK";</em>
<em> isSolvable(words, result);</em>
<em> cout << ans << "\n";</em>
<em> return 0;</em>
<em>}</em>
See more about C++ code at brainly.com/question/19705654
#SPJ1
