Question

1. What do we mean when we say to solve a two-player strategy game in a a. ultra weak sense b. weak sense c. strong sense

2. Compare Depth-First Iterative Deepening method with Depth-First Search and Breadth- First Search. What are the pros and cons for each of these methods

Answer 1

1. Two Player Strategy Game:

Ultra-Weak:

Ultra weak sense can be a strategy in which we can prove that the player in the game can win, lose or draw from the beginning.

Weak:
From the start of the game in weak sense a procedure is provided by which we can make sure a player win or end the match with draw no matter how many turns of the 2nd player are left.

Strong:
In strong sense we can find a sequence of a steps to find exact moves for a player from any position to secure perfect win no matter how much mistakes you have made.

2. BFS vs DFS:

IDS:
   We use iterator in this.
   Only works in complete path (no infinite path)
   Time Complexity O(b^d)
   Space Complexity O(bd)
IDS does give optimal solution

Advantages:

IDS uses less memory as compare to BFS
IDS is more feasible than BFS because of the right amount of memory propotion

Disadvantages:

IDS takes a little longer time to complete because of visiting same nodes so many times.

BFS:
IN BFS we go from root then to left and then to right
It should be complete.
Time complexity of BFS is O(b^(d+1)) e.g b+ b^2 +b^3 +...+b^d+ (b^d+a -b) because we are traversing level by level.
Expanding each node.
Space complexity will be same as time complexity
Yes we can get optimal solution via BFS.

Advantages:

BFS is better than IDS for finding shortest path.
BFS used for testing a graph to check is it Bipartitie.

Disadvantages:

BFS uses more memory.

BFS is inflexible as compare to IDS

IF YOU HAVE ANY QUERY PLEASE COMMENT DOWN BELOW
PLEASE GIVE A THUMBS UP