Internal Iterative Deepening

[AndrewShort]

something I've been meaning to ask for a long time...

I presently have implemented iterative deepening (ID) with aspiration windows (pv of previous iteration is tried first, but otherwise hash best move is tried first if I'm not following the pv anymore). That works great.

I also have PVS implemented, and although I've been tempted to remove it from time to time, I still have it in there, I just can't seem to let go of it.

Now I want to implement Internal Iterative Deepening (IID). My understanding is if you don't have a hash best move, then do a cheap shallow search, e.g. Depth - 2, to try to get a best move that way, and if you do, sort that first. Seems simple in principle. Presumably, the cost of the shallow search is offet by the benefit of better move ordering.

My VB code for IID looks like this:

Code: Select all

'if no best move from hash, do a cheap shallow search to see if I can get a best move that way
        If uiBestMove = 0 AndAlso iDepth > 2 AndAlso Not (fINNULLMOVE) Then
            iVal = -iAlphaBeta(iDepth - 1 - 2, -iBeta, -iAlpha, tLocalPV)
            If tLocalPV.iMoveCnt > 0 Then
                uiBestMove = tLocalPV.aPVmoves(0)
            End If
        End If

This code is before I generate/sort the moves of a node. When I sort the moves, I pass the "best move" to the sort routine. fINNULLMOVE is False during a shallow null move search - idea is if I'm already doing a shallow null move search, no point in doing a shallow IID search as well. The iDepth > 2 is so that I only bother doing the shallow search at least 2 ply before the horizon. The shallow search is 2 ply less than it otherwise would be.

This seems to help dramatically in some cases - I still need to further test, but I want to make sure I'm being smart about when/how to use IID. For example, should I use iDepth > 5 instead? Also, in googling around, I saw someone explain that this should only be used on PV nodes, but I don't understand that statement - a PV node is a node whose score is > Alpha (it won't fail low) - how could you know the node is a PV node unless you've tried a few moves to get a score > Alpha first? And you don't want to try the children moves until you've sorted them. I must be misunderstanding what is meant by a PV Node....

thanks for any clarification you can give me

[Zach Wegner]

This seems to help dramatically in some cases - I still need to further test, but I want to make sure I'm being smart about when/how to use IID. For example, should I use iDepth > 5 instead? Also, in googling around, I saw someone explain that this should only be used on PV nodes, but I don't understand that statement - a PV node is a node whose score is > Alpha (it won't fail low) - how could you know the node is a PV node unless you've tried a few moves to get a score > Alpha first? And you don't want to try the children moves until you've sorted them. I must be misunderstanding what is meant by a PV Node....

Yes, a PV node is simply a node in PVS that has beta>alpha+1. There are really two things meant by PV nodes: that the final score returned is >alpha and <beta, as you say, and a node in PVS with an open window. Every node that returns score>alpha and score<beta will be in an open window though.

Anyways, I use IID on CUT nodes as well. It helps for me. And for clarification, CUT here means that the ply distance from the node to the closest PV node is odd. I.e. each child of a PV node after the first is a CUT node, and each child of those is ALL, and so on.

[pedrox]

something I've been meaning to ask for a long time...

I presently have implemented iterative deepening (ID) with aspiration windows (pv of previous iteration is tried first, but otherwise hash best move is tried first if I'm not following the pv anymore). That works great.

In the management of moves, I ordered first the move of the hash and second the first move of the pv of the previous iteration (I think that the majority of programs with hash tables not bonus for pv).

I think it is useless to make an IID with bonus for pv as the first or second move.

Is anyone disagree?

[hgm]

Micro-Max does IID in every node at all depths. It is its only device for move ordering; the best move of the previous iteration is tried first; after that, all moves are tried in board-scan order. (Even that first move is retried... But that usually gives a hash hit on an already cached hash entry, so the cost is near zero.)

A hash move merely substitutes for early iterations of the IID process. If the requested depth equals 9, and there was a hash hit on a d=5 entry, IID starts with d=6 and the hash move, in stead of with d = -1. (If the hash hit would have had a depth >= 9, the IID loop would terminate immediately, without doing any iterations, and the hash score would be returned.)

Note that uMax starts IID with d = -1, i.e. it still does an iteration before d = 0. (The latter is QS and considers only captures.) This iteration also considers only captures, but no replies are searched, so the 'best' move (which will then be used to start QS) is the move that captures the highest piece (i.e. MVV). This is enough to prevent QS explosion due to rampaging Queens.

The fact that the d=0 iteration searches only captures, makes that captures are searched before normal moves if it is already apparent at QS level that they are a cut move. Searching captures at d=1 is identical to searching captures at d=0: both need a reply at QS level, and the replies from the d=1 search are hash hits on the entries filled by the d=0 search. So effectively the d=0 plus d=1 iteration are like a d=1 that searches all captures before all non-captures.

[Harald Johnsen]

Code: Select all

'if no best move from hash, do a cheap shallow search to see if I can get a best move that way
        If uiBestMove = 0 AndAlso iDepth > 2 AndAlso Not (fINNULLMOVE) Then
            iVal = iAlphaBeta(iDepth - 2, iAlpha, iBeta, tLocalPV)
            If tLocalPV.iMoveCnt > 0 Then
                uiBestMove = tLocalPV.aPVmoves(0)
            End If
        End If

I've corrected your code : you were reducing depth by 3, and your were searching with wrong bounds.

HJ.

[AndrewShort]

Code: Select all

'if no best move from hash, do a cheap shallow search to see if I can get a best move that way
        If uiBestMove = 0 AndAlso iDepth > 2 AndAlso Not (fINNULLMOVE) Then
            iVal = iAlphaBeta(iDepth - 2, iAlpha, iBeta, tLocalPV)
            If tLocalPV.iMoveCnt > 0 Then
                uiBestMove = tLocalPV.aPVmoves(0)
            End If
        End If

I've corrected your code : you were reducing depth by 3, and your were searching with wrong bounds.

HJ.

wow, that was a good catch. I was doing negamax, but I forgot that you only do that after MakeMove() or MakeNullMove(), since it's the other player's turn. In my IID, I'm simply doing it before I generate moves, so I shouldn't be doing negamax. Good catch! Copy and Paste within my code has caused me so many bugs over the years...

[bob]

something I've been meaning to ask for a long time...

I presently have implemented iterative deepening (ID) with aspiration windows (pv of previous iteration is tried first, but otherwise hash best move is tried first if I'm not following the pv anymore). That works great.

In the management of moves, I ordered first the move of the hash and second the first move of the pv of the previous iteration (I think that the majority of programs with hash tables not bonus for pv).

If these are not the _same_ move you have an issue. Simplest solution is to take the PV and "stuff" it into the hash table after an iteration ends, in case some of the deeper nodes was overwritten by later searching. Once you do that, you can remove the "PV" move part of your ordering. Since it only applies to N nodes where N = iteration depth, it will not be needed.

I think it is useless to make an IID with bonus for pv as the first or second move.

Is anyone disagree?

IID is used when you are searching a PV node (beta - alpha > 1) and you discover you have no hash table move. IID helps significantly when that happens. Most common case is where iteration N fails high, but you run out of time trying to get a true score and play the move anyway. At even plies you have no "best move" from the hash table, and IID helps significantly there.

[Zach Wegner]

I've corrected your code : you were reducing depth by 3, and your were searching with wrong bounds.

What's wrong with reducing by 3?

[AndrewShort]

Code: Select all

'if no best move from hash, do a cheap shallow search to see if I can get a best move that way
        If uiBestMove = 0 AndAlso iDepth > 2 AndAlso Not (fINNULLMOVE) Then
            iVal = iAlphaBeta(iDepth - 2, iAlpha, iBeta, tLocalPV)
            If tLocalPV.iMoveCnt > 0 Then
                uiBestMove = tLocalPV.aPVmoves(0)
            End If
        End If

I've corrected your code : you were reducing depth by 3, and your were searching with wrong bounds.

HJ.

wow, that was a good catch. I was doing negamax, but I forgot that you only do that after MakeMove() or MakeNullMove(), since it's the other player's turn. In my IID, I'm simply doing it before I generate moves, so I shouldn't be doing negamax. Good catch! Copy and Paste within my code has caused me so many bugs over the years...

To generally avoid zero alpha-beta windows (which null move and PVS use), I changed it to this:

Code: Select all

'if no best move from hash, do a cheap shallow search to see if I can get a best move that way
        If uiBestMove = 0 AndAlso iDepth > 2 AndAlso (iBeta-iAlpha > 1) Then
            iVal = iAlphaBeta(iDepth - 2, iAlpha, iBeta, tLocalPV)
            If tLocalPV.iMoveCnt > 0 Then
                uiBestMove = tLocalPV.aPVmoves(0)
            End If
        End If

[Harald Johnsen]

I've corrected your code : you were reducing depth by 3, and your were searching with wrong bounds.

What's wrong with reducing by 3?

It's not wrong, but in his first post he is talking about reducing by two and there is three in the code

HJ.