As of May 31, 2023, we have updated our Code of Conduct.

# Questions tagged [iddfs]

For questions related to the iterative deepening depth-first search (IDDFS) algorithm, which is an algorithm that runs a depth-first search (DFS) with progressively bigger depths.

6 questions
Filter by
Sorted by
Tagged with
1 vote
249 views

### Does iterative deepening depth-first search expand at most twice as many nodes as breadth-first search?

My understanding is that iterative deepening search is roughly equivalent to breadth-first search, except instead of keeping all visited nodes in memory, we regenerate nodes as needed, trading off ...
• 101
1 vote
342 views

### Why do iterative deepening search start from the root each iteration in the context of the minmax-algorithm?

Consider the graph below for an understanding on how IDS work. Now my question is: why do IDS start at the root every iteration, why not start at the previously searched depth in the context of minmax?...
• 11
217 views

### Beating iterative alpha beta search in Isolation Game

I'm having trouble beating an AI in Isolation game: https://en.wikipedia.org/wiki/Isolation_(board_game) with 3 queens on a 7x7 board. I tried applying alpha beta iteration with a scoring function on ...
• 697
1 vote
2k views

### What is the space complexity of iterative deepening search?

When using iterative deepening, is the space complexity, $O(d)$, where $b$ is the branching factor and $d$ the length of the optimal path (assuming that there is indeed one)?
165 views

### What are the common techniques one could use to deal with collisions in a transposition table?

Consider an iterative deepening search using a transposition table. Whenever the transposition table is full, what are common strategies applied to replace entries in the table? I'm aware of two ...
• 255
1 vote