1 Overview

In this homework you will simulate a Pokemon battle where a Pikachu is fighting against a Blastoise. For that problem I simplified the Pokemon fighting procedures given in ^[1]. In the simplified procedure, there are two attributes of each Pokemon: HP and PP.

• HP (Health Points): Total health of a Pokemon. May be decreased after attack of the opponent. No defense mechanism is included.
• PP (Power Points): Total ability to do an attack. Each Pokemon starts with a total of 100 PP and it decreases according to each attacks PP values. If Skip attack is used, +100 PP is obtained.

1

BLG336E Homework-1

Also for an attack there are four different attributes:

• PP: To do an attack, PP value of the selected attack should be decreased from Pokemons own PP. If this value is greater than the Pokemons PP, attack cannot be used.
• Accuracy: Accuracy of an attack. If it is not an attack with 100% accuracy, multiple nodes should be created in the graph.
• Damage: Damage of the attack.
• FirstUsage: The first level of the graph where the attack may be used.

To simulate the graph you should create a graph. Some important rules for creating the graph are given below.

• The HPs of Pikachu and Blastoise are 273 and 361 respectively. Attack properties of them are given in text files.
• A node is a leaf node, if one of the competitors are knocked-out or the level limit of the tree is reached. No children of a leaf node is allowed.
• In the simulation, it is taught that Pokemons are not using a decision mechanism to select an attack. Thus, for a list of attacks, it is equally likely to select one of them.

The graphs first three levels are given in the figure below.

Figure 1: First three layers of the match

2

2 Graph Implementation (40 pts.)

Implement the code which creates a graph according to the rules given in the Overview section. You should create the graph according to the max-level value given in the graph. Your code here should output the last layers node information. An example run is given below:

g++ main . cpp o project1./ project1 part1 2P HP:243 P PP:90 B HP:321 B PP:90 PROB:0.1111P HP:233 P PP:90 B HP:321 B PP:80 PROB:0.1111P HP:213 P PP:90 B HP:321 B PP:75 PROB:0.1111P HP:243 P PP:85 B HP:311 B PP:90 PROB:0.0762P HP:233 P PP:85 B HP:311 B PP:80 PROB:0.0762P HP:213 P PP:85 B HP:311 B PP:75 PROB:0.0762P HP:243 P PP:85 B HP:361 B PP:90 PROB:0.0326P HP:233 P PP:85 B HP:361 B PP:80 PROB:0.0326P HP:213 P PP:85 B HP:361 B PP:75 PROB:0.0326P HP:243 P PP:80 B HP:301 B PP:90 PROB:0.0792P HP:233 P PP:80 B HP:301 B PP:80 PROB:0.0792P HP:213 P PP:80 B HP:301 B PP:75 PROB:0.0792P HP:243 P PP:80 B HP:361 B PP:90 PROB:0.0198P HP:233 P PP:80 B HP:361 B PP:80 PROB:0.0198P HP:213 P PP:80 B HP:361 B PP:75 PROB:0.0198

1

3

5

7

9

11

13

15

17

3 BFS-DFS Implementation (40 pts.)

Using the graph generated by the functions in the previous part, implement BFS and DFS algorithms to traverse the graph. Run both BFS and DFS algorithms and print node count and running time. Analyze the results. Your code should be run by ./project1 part2 <max-level> dfs or ./project1 part2 <max-level> bfs commands.

4 Probability of the Easiest Path (20 pts.)

For both Pikachu and Blastoise, find out the probability of the easiest action sequence (containing minimum number of levels) to win the battle. Select one of the algorithms in the previous part to solve the problem. An example output is given below.

./ project1 part3 pikachuPikachu used x . It s <effective /noneffective >.Blastoise used y . It s <effective /noneffective >.. . .Level count : Probability :

1

3

5

7

3

[1] https://www.math.miami.edu/~jam/azure/pokedex