Consider the following Minimax Tree. If we evaluate children from left-to-right using alpha-beta pruning with a given set of values for nodes A through I, some of the nodes may be pruned. That is, we may never need to evaluate the node because of what we have seen in prior search.
In this homework, you’ll write two programs, specifically tailored for this particular tree. (In other words, your programs will work only for trees having the precise format shown above.)
• The first program will be called MINIMAX and will perform straight minimaxing. It’ll take as input the values of the nodes A through I and will output the move of the Max player as one of “L” (left), “M” (middle), or “R” (right).
• The second program will be called ALPHABETA and will perform alpha-beta pruning. It’ll take as input the values of the nodes A through I and will output the move of the Max player as one of “L” (left), “M” (middle), or “R” (right). Additionally, it’ll output, in alphabetical order and separated by blanks, the names of the nodes (if any) that are pruned.
TEST DATA FOR MINIMAX
1. Tree #1: A=5 B=3 C=1 D=2 E=5 F=4 G=1 H=3 I=3
2. Tree #2: ...
The node values for this tree are not known at this stage; they will be manually entered by your TA when your submission is being evaluated. Thus, your program should be prepared to input 9 values (domain: Z), separated by blanks, from the keyboard.
TEST DATA FOR ALPHABETA
1. Tree #1: A=5 B=3 C=1 D=2 E=5 F=4 G=1 H=3 I=3 2. Tree #2: A=5 B=2 C=2 D=5 E=1 F=3 G=2 H=4 I=2
3. Tree #3: A=1 B=3 C=4 D=1 E=4 F=1 G=3 H=5 I=3
4. Tree #4: ...
