Please write the program in C++ . Visual representation of the input : ( Root )
ID: 3603140 • Letter: P
Question
Please write the program in C++.
Visual representation of the input:
( Root ) Max
/ |
( ) ( ) ( ) Min
/ | / | / |
3 12 8 2 4 6 14 5 2
Visual representation of the MiniMax algorithm:
( 3 ) Max
/ |
( 3 ) ( 2 ) ( 2 ) Min
/ | / | / |
3 12 8 2 4 6 14 5 2
And so the output should be 3, because 3 will be the max return value after the minimax tree program finished running.
So basically we prompt a message asking the user to input a tree(nested list), and the user enters the nested list specified above. To go more into detail of what can be done:
The input minimax tree could be any height or have any degree of nesting. Therefore you could either, write a recursive operator >> to read a minimax tree into a Node, or read the nested list as a string and then parse the string to build the tree. So the tree then would look with the above input like so:
Once it goes through and evaluates the minimax tree, the output then will be 3.
If you have any questions, let me know. Thanks.
p.s. IF YOU can do the problem above in PYTHON, then if you can please add comments and proper indention.
MAX 3 A a1 3 MIN b1 di d. 3 12 8 4 14 5 2 Figure 5.2 A two-ply game tree. The nodes are "MAX nodes," in which it is MAX's turn to move, and the nodes are "MIN nodes." The terminal nodes show the utility values for MAX; the other nodes are labeled with their minimax values. MAX's best move at the root is a1, because it leads to the state with the highest minimax value, and MIN's best reply is bi, because it leads to the state with the lowest minimax value.Explanation / Answer
#include<bits/stdc++.h>
using namespace std;
int minimax(int depth, int nodeIndex, bool isMax,
int scores[], int h)
{
// Terminating condition. i.e leaf node is reached
if (depth == h)
return scores[nodeIndex];
// If current move is maximizer, find the maximum attainable
// value
if (isMax)
return max(minimax(depth+1, nodeIndex*2, false, scores, h),
minimax(depth+1, nodeIndex*2 + 1, false, scores, h));
// Else (If current move is Minimizer), find the minimum
// attainable value
else
return min(minimax(depth+1, nodeIndex*2, true, scores, h),
minimax(depth+1, nodeIndex*2 + 1, true, scores, h));
}
// A utility function to find Log n in base 2
int log2(int n)
{
return (n==1)? 0 : 1 + log2(n/2);
}
// Driver code
int main()
{
// The number of elements in scores must be
// a power of 2.
int scores[] = {3, 12, 8, 2, 4, 6, 14, 15, 2};
int n = sizeof(scores)/sizeof(scores[0]);
int h = log2(n);
int res = minimax(0, 0, true, scores, h);
cout << "The optimal value is : " << res << endl;
return 0;
}