PV Search and Transposition Table

[Cheney]

I have worked out the kinks in my TT implementation and it seems to be working fine, until ...

My last version of the AB search (without TT) I had implemented PV Search, which also worked. I based this from CPW (http://chessprogramming.wikispaces.com/ ... ion+Search)

I created a new AB search which uses the TT and PV Search and bad moves happened. I tried to implement a separate zwSearch like in CPW but that was worse. I did not have the zwSearch examine the TT.

From debugging, it is clear to me that a TT entry is being used somehow when the smaller window is used but I am having trouble identifying where and why.

So before I dig deeper into what the TT is doing, I decided to modify the search process. Instead of of the search calling iteself with alpha-1,alpha I have it call the previous version of AB search which does not have a TT check. Yes, it works but I do not believe it is the correct path.

Is the a correct implementation or should the PVSearch with the window of alpha-1,alpha still check the TT for entries?

Also, in the CPW link, the zwSearch shows this: score = -zwSearch(1-beta, depth - 1). I am expecting 1-beta as a type-o.

Thank you

[syzygy]

So before I dig deeper into what the TT is doing, I decided to modify the search process. Instead of of the search calling iteself with alpha-1,alpha I have it call the previous version of AB search which does not have a TT check. Yes, it works but I do not believe it is the correct path.

I don't know how precise you are when typing this, but if your search is calling itself with "alpha-1,alpha", then you have some signs wrong.

If the engine starts to play silly moves, you probably have a bug like this. Either in the parameters you're passing recursively, or where you are checking against bounds.

Also, in the CPW link, the zwSearch shows this: score = -zwSearch(1-beta, depth - 1). I am expecting 1-beta as a type-o.

You might want to take same time to thoroughly study how alpha-beta works until you can comfortably reason about it. Otherwise you're not understanding what you're doing.

The 1-beta is correct. In a zero window search, the (alpha, beta) window has become (alpha, alpha+1) or alternatively (beta-1, beta). The recursive invocation is with parameters (-beta, -alpha), so either (-alpha-1,-alpha) or (-beta,-beta+1) = (-beta, 1-beta). If you're only passing beta, that means the recursive invocation passes 1-beta.

[Cheney]

but if your search is calling itself with "alpha-1,alpha"

That is my type-o , sorry. The search is passing -alpha-1,-alpha.

As for the 1-beta, I think I get it now, I was not looking at it through algebraic eyes. I only tested the zwSearch and am sure I had something wrong in its implementation. I am not using that now.

I have reviewed and wrote various sample AB methods to learn about it. What I have has been working well and bug free. It is integrating the TT and PVS into one AB method. Both on their own in their own AB search reduce nodes a fair amount, but together is the issue. I'll review it again.

I will admit, once stepping into a new iteration of AB with the zero window, I was not following it correctly and still need to wrap my mind around that specific piece. For example, in this part of the code:

Code: Select all

if ( score > alpha ) // in fail-soft ... && score < beta ) is common
  score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search

... if I am passing -alpha-1,-alpha, when is score > alpha and score < beta if I called with alpha was 10? Wouldn't the window then be -11,-10? I"ll have to look a little harder at that piece to confirm just what it is doing.

[Sven]

For example, in this part of the code:

Code: Select all

if ( score > alpha ) // in fail-soft ... && score < beta ) is common
  score = -pvSearch&#40;-beta, -alpha, depth - 1&#41;; // re-search

... if I am passing -alpha-1,-alpha, when is score > alpha and score < beta if I called with alpha was 10? Wouldn't the window then be -11,-10? I"ll have to look a little harder at that piece to confirm just what it is doing.

"score > alpha && score < beta" obviously can only happen with a non-zero window but not for beta == alpha+1. The fail-soft variant that adds "score < beta" to the re-search condition does not apply if you are already within the zero-window search. Moreover, the whole re-search does not apply there since its "full window" is already the zero window and you cannot make it any larger. That's why the zwSearch() function in CPW does not need the whole re-search part.

Sven

[Cheney]

Thank you

I believe where I found why bad moves appear.

Code: Select all

            if (depth == 0)
            {
                PVSorting = false;
                value=QuiescenceSearch(board, ply, alpha, beta);
                //value = Evaluation.Evaluate(board);
                TransTable.SetTTEntry(board.HashKey, depth, value, false, ZobristHashEntry.Exact);
                return value;
            }

It appears, under certain circumstances, setting the TT at this point in this fashion is taking the last move of any move list and making it the best. I removed this line of code and the bad moves are gone and less nodes are searched.

However, I believe this happens based on the PVSearch and qSearch. For some reason, my mind is not wrapped around this yet and I think I need to put it on paper .

The PV search shrinks the window. Eventually qSearch is called with that minimal window. If the stand pat < beta and < alpha and there are either no capture moves or no capture moves to increase alpha, then the minimal window's alpha (originally -alpha-1) is returned. Back in the main search, this value > alpha and will kick off a full window search.

What I was seeing when I had the bad moves was all the move scores were increasing by 1 and overwriting the TT.