The concept of iterative deepening make sense but when i went to implement it there was one detail i couldn't get a concise answer to on other websites. Currently I have a 6 ply basic alpha-beta search followed by a quiescence search. I use iterative deepening. Starting at ply 2, then 4 then 6 (for some reason iterative deepening from depths 2, 3, 4, 5, 6 was slower than going in increments of 2). My question is this:
At each new iteration, do I only take the best move from the previous shallower search and bump that to the top of the move list for the next deeper search and then using standard move ordering techniques for the remainder. Or, am i supposed to be getting the value for each move from the previous search, sorting them in order of which is best and then using that as the order for the entire movelist for the deeper search.
Everything I read only talks about searching the best move from the previous depth first. But shouldn't I be searching the 2nd best move next, then the third best etc..?
Iterative Deepening
-
H.G.Muller
- Posts: 190
- Joined: Sun Jul 14, 2013 10:00 am
- Real Name: H.G. Muller
Re: Iterative Deepening
It would probably be faster to search the second-best move second. The problem is that alpha-beta in general does not tell you what the second-best move is. Doing extra search work to figure that out usually more than offsets the advantage. Some engines count the number of nodes the search of each move in the root requires, under the assumption that if a move is very close in score to the best move found so far, it will be hard to refute it (and thus require many nodes). They then sort the non-PV moves in the current iteration by node count of the previous iteration.
If the previous iteration had a PV change, you will have more than one move for which you have an exact score, and you could make use of that. In some of my engines every move that beats alpha is immediately put in front of the move list, so that it will be searched first if no better move is found amongst the remaining once, but could end up second or third if one or two other moves later beat it. That way the sensible moves tend to end up in front of the move list.
If the previous iteration had a PV change, you will have more than one move for which you have an exact score, and you could make use of that. In some of my engines every move that beats alpha is immediately put in front of the move list, so that it will be searched first if no better move is found amongst the remaining once, but could end up second or third if one or two other moves later beat it. That way the sensible moves tend to end up in front of the move list.
Re: Iterative Deepening
Thank you for taking the time to respond. This is my first chess engine and i must say, watching it find a tough mate in 5 with under promotions etc... has been like a religious experience for me. I'm still a newbie so i apologize if i don't use the correct terminology (i had to look up what PV meant in your post). I haven't even finished a proper eval function with heuristics yet. So right now most nodes unless they lose/win material have value zero. You offered some interesting ideas which I will have to come back to later. But for now I just want to create a basic engine with a 6 ply basic search (which i really want to get to 8) followed by a quiescence search. I wasn't even going to add the iterative deepening just yet but I figured any half decent engine has to have this.
So, if you were in my shoes is it sufficient to just take the best move from the previous depth and move it to the top of the move list for the next depth? Will that give me enough benefits to make it worthwhile. Do many engines do this? Or is that far too simplistic. It does seem to give me a slight speed up.
So, if you were in my shoes is it sufficient to just take the best move from the previous depth and move it to the top of the move list for the next depth? Will that give me enough benefits to make it worthwhile. Do many engines do this? Or is that far too simplistic. It does seem to give me a slight speed up.