Assignment 1
Problem 1.
- Calculate the value assigned from the root node by using the minimax method, show the steps you followed.
- Use alpha-beta pruning to solve this problem (left to right). Show the steps you followed. How many nodes where visited? How many nodes are visited when you apply the algorithm right to left?
Problem 2.
Consider the following two player game (MAX and MIN). There is a stack of 6 tiles, three of value 1 and three of value 3 and whose value is hidden from the players. The game has the following development:
- First,each player gets 1 token from the
- Then the max player can, if he wants, take another
- Both players then show their chips.
If the sum of the values of the chips of both players is even, MAX wins. On the other hand, if the sum is odd, MIN wins. Suppose an agent plays the role of MAX and both players have gotten their first token. MAX got a 3 (and he knows it) and, obviously, he doesn’t know the value of MIN’s chip. Make the complete tree of the game and apply the algorithms seen in class to decide if in this situation it is convenient for MAX to take a second piece or not (indicate all the necessary information in the tree to be able to follow the development of the algorithm). What decision should max make?
Problem 3.
This is a classic problem, but a really nice one. We want to solve the Hanoi Tower problem:
“The Tower of Hanoi is a mathematical puzzle. It consists of three poles and a number of disks of different sizes which can slide onto any poles. The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape. The objective of the puzzle is to move all the disks from one pole (say ‘source pole’) to another pole (say ‘destination pole’) with the help of the third pole (say auxiliary pole).” Geeksforgeeks
- Youwill need to formulate and sketch the solution for this problem with 3
- Using either BFS or DFS (choose one), create the code for the solution for n disks (worst casescenario submit the pseudo-code).
