Description
● Problem Statement
Assume that there are two teams and they are team attacker and team defender. Therefore, at a state of the game
one agent in each team is left alive respectively. Here, the defender is given a lifeline called HP which will be
assigned randomly. Furthermore, the attacker agent will try to give maximum negative HP to the defender agent
to decrease his(d) chances of survival in the game. On the other hand, the defender agent will try to protect
himself by receiving the lowest negative HP possible from the attacker agent. Furthermore, the attacker can
have a choice from a number of bullets from his gun and the optimal moves will cost a certain maximum
negative HP (chosen from randomly assigned values within the range of minimum and maximum negative HP).
Here, are the following things you need to do using Alpha-Beta Pruning algorithm:
❖ Sample Input 1:
1. Enter your student id:
17301106
2. Minimum and Maximum value for the range of negative HP:
1 30
Note: Here, the second input is a space separated single line input string.
❖ Sample Input 1 Explanation:
Ex. 1 (17301106)
(Use 1st digit of your bracu student id)
# Number of turns for the attacker agent
[Assume that both of them will get equal number of
chances]
Ex. 60 (17301106)
(Use last 2 digits of your bracu student id in reverse)
# Initial lifeline (HP) for the defender at initial state
of the game
Ex. 3 (17301106)
(Use semester code-3rd digit of your bracu student id)
# Number of bullets from which the final choice has
to be made by the attacker.
Ex. 1 (1 30) # Minimum value for the range of negative HP
values
Ex. 30 (1 30) # Maximum value for the range of negative HP
values
❖ Sample Output 1:
1. Depth and Branches ratio is 2:3
2. Terminal States (leaf node values) are 19,22,9,2,26,16,16,27,16.
3. Left life(HP) of the defender after maximum damage caused by the attacker is 44
4. After Alpha-Beta Pruning Leaf Node Comparisons 7
1
❖ Sample Output 1 Explanation:
(Application of Alpha-Beta Pruning Algorithm)
MAX – Level 0 Attacker’s Turn / Initial Start MAX utility/Best Choice
MIN – Level 1 Defender’s Turn 3 branches
Leaf Nodes – Level 2 Terminal state 3^2=9 Leaf Nodes(Random States)
[19, 22, 9, 2, 26, 16, 16, 27, 16]
(Left lifeline/HP)
Left Life = (60 – 16) = 44
So, Left life(HP) of the defender after maximum damage caused by the attacker is 44
Hint:
1. Apply Alpha-Beta Pruning algorithm for sample output line 3 and line 4
2. Formula: Left life HP=Initial life HP-MAX negative HP
Note:
Terminal nodes are randomly generated values within the given range of negative HP (sample output line 2).
❖ Sample Input 2:
1. Enter your student id:
20201003
2. Minimum and Maximum value for the range of negative HP:
5 20
❖ Sample Output 2:
1. Depth and Branches ratio is 4:2
2. Terminal States(Leaf Nodes) are 18,13,5,12,10,5,13,7,17,8,6,8,5,11,13,18.
3. Left life(HP) of the defender after maximum damage caused by the attacker is 22
4. After Alpha-Beta Pruning Leaf Node Comparisons 13
2
