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.
Questions tagged [iddfs]
6 questions
3
votes
1 answer
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 strategies:
Replace the oldest entry whenever a new…
ihavenoidea
- 255
- 2
- 11
1
vote
2 answers
When should the iterative deepening search and the depth-limited search be used?
When should the iterative deepening search (IDS), also called iterative deepening depth-first search (IDDFS), and the depth-limited search be used?
Iram Shah
- 315
- 2
- 5
- 14
1
vote
0 answers
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 memory for time.
The $(i+1)$th layer of a tree has…
xojfqa
- 101
- 4
1
vote
2 answers
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?
What is the intuition behind it?
steward
- 11
- 1
1
vote
1 answer
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)?
user42125
0
votes
0 answers
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 the state. I tried 3 scoring functions:
(0.75/#…
user8714896
- 717
- 1
- 4
- 21