Collecting the pv in Search

[theturk1234]

Hi guys,
I've been getting some weird pvs from my search function. Would any of you be able to tell what I'm doing wrong? Here's the code:
I'm using Bruce Moreland's method of collecting the pv:

Code: Select all

class LINE
{
public:
    int cmove = 0;// Number of moves in the line.
    Move argmove[20];  // The line for pvs of up to 20 moves long.
    int score = 0;
};
int Search::AlphaBeta(int alpha, int beta, int depth, LINE * pline, bool donullmove)
{
    if&#40;depth <= 1&#41;
    &#123;
        ++Nodes;
        pline->cmove = 0;
        return QuiescenceSearch&#40;alpha, beta, depth + 1&#41;;
    &#125;
    LINE line;

    //Null move pruning
    if&#40;&#40;Search&#58;&#58;Is_Mate&#40;) != -10000&#41; && &#40;donullmove&#41; && &#40;depth > 3&#41;)
    &#123;
        Search&#58;&#58;Current_Turn ^= 1;
        int Temp_Move = AlphaBeta&#40;-beta, -beta + 1, depth - 3, &line, false&#41;;
        if&#40;Temp_Move >= beta&#41;
            &#123;
                Search&#58;&#58;Current_Turn ^= 1;
                return beta;
            &#125;
    &#125;
    Search&#58;&#58;Current_Turn ^= 1;
    Generate_Moves&#40;false&#41;;
    Move move;
    if&#40;MoveStack.length&#40;) == 0&#41;
    &#123;
        alpha = Is_Mate&#40;);
        pline->score = alpha;
        pline->cmove = 0;
        return alpha;
	&#125;
	TTEntry* tt = TT.probe&#40;Get_Current_Hash_Key&#40;));
	if&#40;tt!= NULL&#41;
	&#123;
		if&#40;tt->nodetype == Alpha&#41; if&#40;tt->score <= alpha&#41; return alpha;
		if&#40;tt->nodetype == Beta&#41; if&#40;tt->score >= beta&#41; return beta;
		if&#40;tt->nodetype == Exact&#41; 
		&#123;
			if&#40;tt->depth > depth&#41;
			&#123;
				delete tt;
				return tt->score;
			&#125;
		&#125;
		delete tt;
	&#125;
	for&#40;int i = 0; i < MoveStack.length&#40;); i++)
    &#123;
        Nodes++;
        move.From = MoveStack&#91;i&#93;.From;
        move.To = MoveStack&#91;i&#93;.To;
        move.Move_Type = MoveStack&#91;i&#93;.Move_Type;
        Make_Move&#40;MoveStack&#91;i&#93;)
        int Score = -AlphaBeta&#40;-beta, -alpha, depth - 1, &line, &#40;donullmove ? false &#58; true&#41;);
        move.Undo_Move&#40;);
        if&#40;Score >= beta&#41;
        &#123;
            return beta;
        &#125;
        if&#40;Score > alpha&#41;
        &#123;
            pline->argmove&#91;0&#93; = move;
            pline->score = Score;
            memcpy&#40;pline->argmove + 1, line.argmove, line.cmove * sizeof&#40;Move&#41;);
            pline->cmove = line.cmove + 1;
            alpha = Score;
            NodeType node = Exact;
	         TT.save&#40;depth, Score, move, node, Get_Current_Hash_Key&#40;));
        &#125;

    &#125;
    NodeType node = Alpha;
    TT.save&#40;depth, move.Score, move, node, Get_Current_Hash_Key&#40;));
    return alpha;
&#125;

In the iterative deepening loop, I'm calling the search with:
LINE line;
int rootscore = AlphaBeta(alpha, beta, depth, &line, true);

I'm getting output like this:

Code: Select all

position startpos
go wtime 5000 btime 5000
info depth 1
info multipv 1 depth 1 seldepth 3 score cp 15 hashfull 0 pv g1f3 time 44 nodes
7012 nps 378000
info depth 2
info multipv 1 depth 2 seldepth 4 score cp -5 hashfull 0 pv a2a4 time 48 nodes
7072 nps 348000
info depth 3
info multipv 1 depth 3 seldepth 5 score cp 60 hashfull 0 pv e2e4 b8a6 b8a6 time
53 nodes 17932 nps 332000
info depth 4
info multipv 1 depth 4 seldepth 6 score cp 30 hashfull 0 pv e2e4 b8a6 b1a3 b8a6
b1a3 time 60 nodes 18599 nps 304000
info depth 5
info multipv 1 depth 5 seldepth 7 score cp 60 hashfull 2 pv e2e4 b8a6 b1a3 g8h6
b8a6 b1a3 g8h6 time 81 nodes 27465 nps 334000
info depth 6
info multipv 1 depth 6 seldepth 9 score cp 30 hashfull 4 pv e2e4 b8a6 b1a3 g8h6
g1h3 b8a6 b1a3 g8h6 g1h3 time 98 nodes 34267 nps 346000
info depth 7
bestmove e2e4

Are there any other problems with the search(not including the pv)?
Your comments are greatly appreciated!

David Cimbalista

[Edsel Apostol]

Why do you call

Code: Select all

delete tt;

after accessing the hash table?


This line

Code: Select all

int Temp_Move = AlphaBeta(-beta, -beta + 1, depth - 3, &line, false); 

should be -AlphaBeta instead.


And this line should be depth - 1 instead?

Code: Select all

return QuiescenceSearch(alpha, beta, depth + 1);

[theturk1234]

Hi Edsel,

1) Because I'm done with the TTEntry, so it has to be deleted or else it's a memory leak. I just realized, though, that if I call delete on it and then ask for a member, I'm going to get undefined behavior. Maybe I should use:

Code: Select all

if(tt->depth > depth)
         {
            int score = tt->score;
            delete tt;
            return score;
         } 

It's better C++, anyway.

2) Right on! Got to fix that!
3) Well, it's not a mistake, I'm using the variable to determine the seldepth--I pass the current iterative deepening depth into the Quiescence search, then have the Quiescence search count up then add the iterative depth to the depth in the quiescence search to get the seldepth. Make sense?

Thanks for your help!
David Cimbalista[/i]

[ZirconiumX]

3) Well, it's not a mistake, I'm using the variable to determine the seldepth--I pass the current iterative deepening depth into the Quiescence search, then have the Quiescence search count up then add the iterative depth to the depth in the quiescence search to get the seldepth. Make sense?

I have a much easier way that makes much more sense.

I have a value called ply as a parameter to the search. Every time I make a move and call Alpha-beta, I call it with ply + 1. Then you can call Quies with ply as a parameter, too and at the top of every now, check if ply is greater than seldepth, and set seldepth to ply.

This also has the advantage of mate scoring being really simple.

[Edsel Apostol]

You're probably not implementing the hash table correctly. We usually don't delete any entry from the hash table. Can you post the functions TT.save() and TT.probe()?

[Sven]

1) Because I'm done with the TTEntry, so it has to be deleted or else it's a memory leak. I just realized, though, that if I call delete on it and then ask for a member, I'm going to get undefined behavior. Maybe I should use:

Code: Select all

if(tt->depth > depth)
         {
            int score = tt->score;
            delete tt;
            return score;
         }

It's better C++, anyway.

Agreed in general. However, "delete" is only necessary if "tt" points to an entry that you allocated by "new", thereby making a (redundant) copy of an existing TT entry. If that is the case then why do you return a copy, instead of simply returning a pointer to the original hash table entry?

3) Well, it's not a mistake, I'm using the variable to determine the seldepth--I pass the current iterative deepening depth into the Quiescence search, then have the Quiescence search count up then add the iterative depth to the depth in the quiescence search to get the seldepth. Make sense?

You are always calling QuiescenceSearch() from AlphaBeta() with depth=2, since the condition "depth <= 1" effectively means "depth == 1" (you never call AlphaBeta() with depth=0). So how do you think the iterative deepening depth gets passed into the Quiescence search? I'm afraid it isn't. I think the proposal of Matthew makes more sense and is also much more common.

There are some more issues regarding your TT handling:

- The stored depth of a TT entry is already sufficient if it is >= the current depth, you check "> depth".

- You return alpha resp. beta if you find a lower-bound resp. higher-bound entry for which the current score matches, even if the TT entry has insufficient depth. In my opinion this is not correct, as far as I know TT entries with insufficient depth should always be ignored.

- You always overwrite TT entries that you have already stored with type "Exact" (within the move loop), replacing its type by "Alpha" at the end of AlphaBeta(). It would be better to only call TT.save() once per node, whenever you return from AlphaBeta(). For this purpose you would need to save the information whether the node type is "Exact" or "Alpha" somehow.

EDIT: Regarding PV handling I see two other points.

- At some points you explicitly set pline->cmove (the PV length) to 0 before returning, at other points you don't. I propose that you cross-check the proper setting of the PV length, it might be inconsistent.

- The maximum PV size is limited to 20 but when copying a subtree PV into the current PV you do not check the size, so once your engine starts searching beyond 20 plies it will produce unexpected results. It would make sense to only copy min("subtree PV length", 20-1) plies.

[Sven]

Also I do not understand your handling of the current turn. Obviously you switch the turn in MakeMove() and UndoMove(). But why do you also switch it unconditionally between the null move pruning code and Generate_Moves()? Looks like a bug to me. I would expect this:

Code: Select all

    //Null move pruning
    // NOTE: the condition below is not sufficient. You need to:
    // 1) also exclude null move when being in check (IsMate() does not look like checking this), and
    // 2) also exclude null move in endgames with very few non-pawn pieces of the moving side, due to zugzwang problem
    if((Search::Is_Mate() != -10000) && (donullmove) && (depth > 3))
    {
        Search::Current_Turn ^= 1; // make null move => NOTE: hash key update missing here!!
        int Temp_Move = -AlphaBeta(-beta, -beta + 1, depth - 3, &line, false); // NOTE: I would rename Temp_Move since it is a score, not a move
        Search::Current_Turn ^= 1; // unmake null move
        if(Temp_Move >= beta)
            {
                // NOTE: what about setting an empty PV here?
                // NOTE: what about storing something in the TT here?
                return beta;
            }
    }
    Generate_Moves(false);
    ...

Please consider also my comments marked with NOTE in the code snippet above.

[Sven]

I wrote:

- At some points you explicitly set pline->cmove (the PV length) to 0 before returning, at other points you don't. I propose that you cross-check the proper setting of the PV length, it might be inconsistent.

Now I see that you use the C++11 "In-class member initializers" feature for your LINE class which is equivalent to an explicit constructor setting cmove and score to 0. So your setting of the PV length seems to be consistent at least at those places which I had doubts about initially.

But you should still be careful with your local instance "line" allocated on the stack of AlphaBeta() since you reuse that instance several times. For instance, in the move loop you do the recursive call with "&line" - what if one subtree stores a non-empty PV there but the next one doesn't (and also does not set pline->cmove to 0), does "line" now still contain the non-empty PV of the previous subtree? I'm afraid it does ... Even the first subtree in the move loop can "suffer" from a non-empty PV left by the null-move search if there was no beta cutoff.

So I would always allocate a PV instance as local as possible, and never reuse it, unless you perfectly take care about the correct state of a "global" (i.e., function-wide) PV instance.

[Sven]

It's me again ... Please take a look at the value of the "donullmove" parameter in the recursive AlphaBeta() call within your move loop. There you pass "false" if the current node was called with "true" (in fact the expression "(donullmove ? false : true)" is the same as simply "!donullmove"). That disallows null moves every second ply even if you never made any previous null move on the current move path from the root. I would expect that you only pass "false" directly after making the null move, i.e. outside the move loop. So the recursive call within the move loop should always pass "true" here, in my opinion.

[tttony]

Apart from the points of Edsel Apostol and Sven Schüle

I will point out some things that are not right, according to https://chessprogramming.wikispaces.com/

Quiescence should be executed when depth == 0, but if you use null move, then should be depth <= 0

Inside Score >= beta you should save it into tt

Code: Select all

if(Score >= beta)
{
    TT.save(depth, beta, move, Beta, Get_Current_Hash_Key()); 
    return beta;
}