Stack Overflow
Stack Overflow

Questions tagged [iterative-deepening]

82 questions
48
votes
3 answers

Iterative deepening vs depth-first search

I keep reading about iterative deepening, but I don't understand how it differs from depth-first search. I understood that depth-first search keeps going deeper and deeper. In iterative deepening you establish a value of a level, if there is no…
bb2
  • 2,872
  • 7
  • 37
  • 45
29
votes
5 answers

Difference between Breadth First Search, and Iterative deepening

I understand BFS, and DFS, but for the life of me cannot figure out the difference between iterative deepening and BFS. Apparently Iterative deepening has the same memory usage as DFS, but I am unable to see how this is possible, as it just keeps…
theraven
  • 4,825
  • 3
  • 20
  • 20
9
votes
1 answer

prolog depth first iterative deepening

I am trying to implement a depth first iterative deepening search of a state space graph. I have a graph with three vertices and their are two activating edges and two inhibition edges. Each node has a binary value, collectively this is the state of…
user27815
  • 4,767
  • 14
  • 28
9
votes
2 answers

Chess: high branching factor

I'm trying to develop a simple chess engine, but I'm struggling with its performance. I've implemented Negamax with alpha-beta pruning and iterative deepening (without any additional heuristics), but I'm unable to get reasonable search time beyond…
Matis
  • 503
  • 5
  • 17
7
votes
4 answers

How to use call_with_depth_limit/3

I'm trying to use call_with_depth_limit/3 in SWI-Prolog to implement iterative deepening and either I don't understand how it works or it's misbehaving. I have an example where the following happens: ?- call_with_depth_limit(mygoal, 29,…
Joan
  • 99
  • 4
7
votes
2 answers

How to implement iterative deepening with alpha beta pruning

I'm writing a program to play Dots and Boxes and I want to increase my time efficiency by ordering the moves I consider in alphaBeta based on their heuristic values in a iterative deepening scheme. Essentially, I want to go into the search tree,…
A. Romer
  • 73
  • 1
  • 1
  • 7
5
votes
1 answer

How to implement a transposition table for connect 4?

I'm making a connect 4 AI in python, and I'm using minimax with iterative deepening and alpha beta pruning for this. For greater depths it's still quite slow, so I wanted to implement a transposition table. After reading up on it I think i get the…
Tr33hugger
  • 51
  • 3
5
votes
1 answer

How to improve performance using Transposition Table in Game Playing?

I have implemented iterative deepening with alpha-beta pruning in my game and I also added a Transposition Table to store already evaluated boards. Right now, I am doing the following: When running iterative deepening, at depth = 0 it evaluates and…
Raj
  • 1,928
  • 3
  • 29
  • 53
5
votes
1 answer

CLIPS LHS binding variables

I'm trying to write a CLIPS program which use the Iterative Deepening algorithm to solve a planning problem. For this same reason I would like to keep a low branching factor. In the following code ?s is the variable which represent the level of the…
beppe95
  • 151
  • 6
5
votes
1 answer

Iterative deepening in common lisp

I've written an iterative deepening algorithm, it works except when I add cycle checking, the algorithm returns a deeper solution than it should. But when I don't check for cycles it does work correctly, but it takes too long. Can anyone please spot…
turingcomplete
  • 2,128
  • 3
  • 16
  • 25
4
votes
1 answer

How to find list of shortest length from an infinite set (Prolog)

I have a Prolog function path(A,B,Path) that yields all the valid paths on a board from A to B. The output of this function looks like this: ?- path(0,2,Path). Path = [0, 1, 2] ; Path = [0, 3, 2] ; Path = [0, 1, 4, 2] ; Path = [0, 3, 4, 2] ; Path =…
Ryan Erdmann
  • 1,786
  • 10
  • 11
4
votes
1 answer

Iterative Deepening A* Star Explanation

Can somebody explain about Iterative Deepening A*? I still don't understand how it works. Iterative deepening search w/ Depth First Search, and If still not found the solution; increase the Depth++ until found solution. If Iterative deepening using…
yudayyy
  • 260
  • 2
  • 9
  • 20
3
votes
2 answers

Minimax/ Alpha beta pruning Move Ordering?

I've read (for example, http://radagast.se/othello/Help/order.html) that searching on the best moves at each level first (which can be found using iterative deepening) makes the search go much faster. How would one go about searching on the best…
weeb
  • 1,939
  • 4
  • 18
  • 29
3
votes
2 answers

Block world problem search runs out of stack space

I have the following code: move(state(on(X, NewX), OldY, Z), state(NewX, on(X, OldY), Z)). move(state(on(X, NewX), Y, OldZ), state(NewX, Y, on(X, OldZ))). move(state(OldX, on(Y, NewY), Z), state(on(Y, OldX), NewY, Z)). move(state(X, on(Y, NewY),…
Mystery
  • 152
  • 5
3
votes
4 answers

Artificial Intelligence: Time Complexity of IDA* Search

I am studying informed search algorithms, and for Iterative Deepening A* Search, I know that the space complexity is O(d), where d is the depth of the shallowest goal node. I have tried to find out what its time complexity is, but I haven't been…
ceno980
  • 2,003
  • 1
  • 19
  • 37
1
2 3 4 5 6