Proving the correctness of the algorithm

[metax]

I'm not extending in diep by default upon GIVING a check of course. Too expensive. I extend upon walking away out of check.

Isn't this the same?

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value;

   if (check) depth++;
   
   while (mv = NextMove())
   {
       Do(mv);
       value = Search(-beta, -alpha, depth-1);
       Undo(mv);

       // .......
   }
}

or

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value, newDepth;
   
   while (mv = NextMove())
   {
       Do(mv);

       newDepth = depth - 1;
       if (mv.Check) newDepth++;

       value = Search(-beta, -alpha, newDepth);
       Undo(mv);

       // .......
   }
}

I cannot see any difference....

[Milos]

I'm not extending in diep by default upon GIVING a check of course. Too expensive. I extend upon walking away out of check.

Isn't this the same?

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value;

   if (check) depth++;
   
   while (mv = NextMove())
   {
       Do(mv);
       value = Search(-beta, -alpha, depth-1);
       Undo(mv);

       // .......
   }
}

or

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value, newDepth;
   
   while (mv = NextMove())
   {
       Do(mv);

       newDepth = depth - 1;
       if (mv.Check) newDepth++;

       value = Search(-beta, -alpha, newDepth);
       Undo(mv);

       // .......
   }
}

I cannot see any difference....

It's certainly not the same. In the first case you are increasing depth if you are in check, in the second case if your opponent opponent is.

[Sven]

I'm not extending in diep by default upon GIVING a check of course. Too expensive. I extend upon walking away out of check.

Isn't this the same?

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value;

   if (check) depth++;
   
   while (mv = NextMove())
   {
       Do(mv);
       value = Search(-beta, -alpha, depth-1);
       Undo(mv);

       // .......
   }
}

or

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value, newDepth;
   
   while (mv = NextMove())
   {
       Do(mv);

       newDepth = depth - 1;
       if (mv.Check) newDepth++;

       value = Search(-beta, -alpha, newDepth);
       Undo(mv);

       // .......
   }
}

I cannot see any difference....

If "if (check) ..." in the first version and "if (mv.Check) ..." in the second version both mean that the side to move is in check (where in the second version you write this as "the move 'mv' has given check") then these two versions are *nearly* identical. I say *nearly* because the difference is that the second version does not extend when in check at the root node (or the topmost node where Search() is called).

In Vincent's remark, "extending upon GIVING check" would mean, in my opinion, to extend if the side to move has at least one move that gives check, which is clearly different from being in check. At least that's what it sounds for me.

One sidenote: both of your algorithm variants may be better to read if you add a termination condition like "if (depth == 0) return QSearch(...);" above the while loop, and if you fix the "value = Search(...);" into "value = -Search(...);".

Sven

[diep]

I'm not extending in diep by default upon GIVING a check of course. Too expensive. I extend upon walking away out of check.

Isn't this the same?

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value;

   if (check) depth++;
   
   while (mv = NextMove())
   {
       Do(mv);
       value = Search(-beta, -alpha, depth-1);
       Undo(mv);

       // .......
   }
}

or

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value, newDepth;
   
   while (mv = NextMove())
   {
       Do(mv);

       newDepth = depth - 1;
       if (mv.Check) newDepth++;

       value = Search(-beta, -alpha, newDepth);
       Undo(mv);

       // .......
   }
}

I cannot see any difference....

Would you mind improving this code with hashtable cutoff, where you give it and hashtable store function call, nullmove and where you call qsearch and under what condition?

It really matters a lot.

Note we skip another discussion now. skewer checks?
You'll miss them.

Additionally you lose system time to detect whether a move is a check. For diep it's just incremental attacktable check whether i'm in check.

Vincent

[metax]

Would you mind improving this code with hashtable cutoff, where you give it and hashtable store function call, nullmove and where you call qsearch and under what condition?

There are a couple of errors and simplifications, but I just wanted to show the principle.

It really matters a lot.

Of course it matters for a real program. But the question is whether the change makes any difference.

skewer checks?
You'll miss them.

Not if "mv.Check" always contains true information on whether the move gives check.

Additionally you lose system time to detect whether a move is a check. For diep it's just incremental attacktable check whether i'm in check.

OK, then it will make a difference in nps.

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value;

   if (inCheck) depth++;


   // probe hash table
   // ...

   if &#40;depth <= 0&#41; return QSearch&#40;alpha, beta, 0&#41;;



   // try null move
   // ...


   GenerateMoves&#40;);
   
   while &#40;mv = NextMove&#40;))
   &#123;
       Do&#40;mv&#41;;
       value = -Search&#40;-beta, -alpha, depth-1&#41;;
       Undo&#40;mv&#41;;

       // .......
   &#125;
&#125;

or

Code: Select all

int Search(int alpha, int beta, int depth)
{
   Move mv;
   int value, newDepth;

   // probe hash table
   // ...

   if &#40;depth <= 0&#41; return QSearch&#40;alpha, beta, depth&#41;;

   // try null move
   // ...

   GenerateMoves&#40;);


   while &#40;mv = NextMove&#40;))
   &#123;
       Do&#40;mv&#41;;

       newDepth = depth - 1;
       if &#40;mv.GivesCheck&#41; newDepth++; // mv.GivesCheck is a flag which indicates if a move delivers check

       value = Search&#40;-beta, -alpha, newDepth&#41;;
       Undo&#40;mv&#41;;

       // .......
   &#125;
&#125;

@Sven: Of course in the second variation you also test at the root if a move gives check....

[Sven]

@Sven: Of course in the second variation you also test at the root if a move gives check....

Yes, but you do not extend if the moving side at root is in check (so the previous move that led to the root node was giving check), which makes the difference I mentioned.

Version 1: You are at the root node and do a 2-ply search by calling Search(..., 2). If the moving side at the root node is in check then all successor nodes are searched with depth 2, otherwise all are searched with depth 1.

Version 2: You are at the root node and do a 2-ply search by calling Search(..., 2). It has no impact whether the moving side at the root node is in check. Instead, for each successor move that gives check 'newDepth' is set to 2, else to 1.

Sven

[metax]

Yes, but you do not extend if the moving side at root is in check (so the previous move that led to the root node was giving check), which makes the difference I mentioned.

Version 1: You are at the root node and do a 2-ply search by calling Search(..., 2). If the moving side at the root node is in check then all successor nodes are searched with depth 2, otherwise all are searched with depth 1.

Version 2: You are at the root node and do a 2-ply search by calling Search(..., 2). It has no impact whether the moving side at the root node is in check. Instead, for each successor move that gives check 'newDepth' is set to 2, else to 1.

Sven

There is no point in extending at the root if the side to move is in check. You will get exactly the same tree, only that the iteration reported if you extend is by one lower than if you don't extend at the root. The only difference might be that you don't have a one-ply search if you extend, so there might be differences in move ordering. Anyway, I consider extending at the root if in check as useless.

[Sven]

Yes, but you do not extend if the moving side at root is in check (so the previous move that led to the root node was giving check), which makes the difference I mentioned.

Version 1: You are at the root node and do a 2-ply search by calling Search(..., 2). If the moving side at the root node is in check then all successor nodes are searched with depth 2, otherwise all are searched with depth 1.

Version 2: You are at the root node and do a 2-ply search by calling Search(..., 2). It has no impact whether the moving side at the root node is in check. Instead, for each successor move that gives check 'newDepth' is set to 2, else to 1.

Sven

There is no point in extending at the root if the side to move is in check. You will get exactly the same tree, only that the iteration reported if you extend is by one lower than if you don't extend at the root. The only difference might be that you don't have a one-ply search if you extend, so there might be differences in move ordering. Anyway, I consider extending at the root if in check as useless.

What are you arguing about? Your initial question was whether version 1 and version 2 of Search() were different or not, and I answered they are different indeed, which is still true because version 1 *does* extend on check also at the root node while version 2 does not. Can you finally agree with me at that at least?

You are also still totally wrong in stating that both versions do search exactly the same tree. They do *not* if the side to move is in check at the root node, where version 1 searches exactly one ply deeper then version 2 in that case.

What can be discussed, of course, is whether extending at the root node when in check is *useful* or not. Here I am totally with you, it would not make much sense to do that - provided the "root node" we are talking about is really the root node of the whole search. And here we are again: an engine that has a separate search function only for the root node (many engines do have that for good reasons) will, with your version 2 of Search() [EDIT: applied to all full search nodes below the root], *miss* the check extension at all nodes of height 1 unless the root search function takes care about check extension there, too. But then everything becomes more complex and error-prone than necessary, where version 1 would simply fit.

Taking my last paragraph into account, I see no good reason to prefer version 2 over version 1.

Sven

[metax]

What are you arguing about? Your initial question was whether version 1 and version 2 of Search() were different or not, and I answered they are different indeed, which is still true because version 1 *does* extend on check also at the root node while version 2 does not. Can you finally agree with me at that at least?

I don't know... this isn't specified in the code I posted. This would be part of the RootSearch() function. If the root search function, however, does the same thing as the normal search function concerning the extensions, then you are right.

You are also still totally wrong in stating that both versions do search exactly the same tree. They do *not* if the side to move is in check at the root node, where version 1 searches exactly one ply deeper then version 2 in that case.

Well you'd have to speakl more precisely in this context. The following is true:

At a given reported fixed depth, the version which extends at the root if in check will search one ply deeper than a version which does not extend at the root if in check.
In a given time, they will search (almost) the same tree because extending at the root before searching any move does not affect the move decision nor the PV after a given time. However, it does affect the reported depth which will be by one lower after a given time in case you extend because you are searching all branches one ply deeper than reported. An iteration N in the version which extends at the root will correspond with ply N+1 in the version that does not extend (of course this is only valid if you are in check at the root). The only thing that would maybe affect the search tree is the fact that if you are in check and extend at the root, there will be no real iteration 1 search because in the reported iteration 1 you will actually be searching iteration 2.

What can be discussed, of course, is whether extending at the root node when in check is *useful* or not. Here I am totally with you, it would not make much sense to do that - provided the "root node" we are talking about is really the root node of the whole search. And here we are again: an engine that has a separate search function only for the root node (many engines do have that for good reasons) will, with your version 2 of Search() [EDIT: applied to all full search nodes below the root], *miss* the check extension at all nodes of height 1 unless the root search function takes care about check extension there, too. But then everything becomes more complex and error-prone than necessary, where version 1 would simply fit.

Taking my last paragraph into account, I see no good reason to prefer version 2 over version 1.

Sven

I also see no good reason to prefer v2 and I am using version 1. My point was, however, that the search trees of both versions, given that version1 does _not_ extend at the root if in check, and that version 2 takes care of extending checking moves at the root, would be exactly identical. The performance is another question.

Actually, as far as I know e.g. Stockfish uses the second version.

[Sven]

What are you arguing about? Your initial question was whether version 1 and version 2 of Search() were different or not, and I answered they are different indeed, which is still true because version 1 *does* extend on check also at the root node while version 2 does not. Can you finally agree with me at that at least?

I don't know... this isn't specified in the code I posted. This would be part of the RootSearch() function. If the root search function, however, does the same thing as the normal search function concerning the extensions, then you are right.

If "root node" is the topmost node being visited by the function Search() then this is specified in the code you posted.

But now it is becoming clear that you had much more in mind than you wrote in your initial post. You had a RootSearch() function in mind, and you were thinking about overall search behaviour when doing iterative deepening. Both was not part of your post I replied to, so how could I know what you wanted to compare?

You are also still totally wrong in stating that both versions do search exactly the same tree. They do *not* if the side to move is in check at the root node, where version 1 searches exactly one ply deeper then version 2 in that case.

Well you'd have to speakl more precisely in this context. The following is true:

At a given reported fixed depth, the version which extends at the root if in check will search one ply deeper than a version which does not extend at the root if in check.
In a given time, they will search (almost) the same tree because extending at the root before searching any move does not affect the move decision nor the PV after a given time. However, it does affect the reported depth which will be by one lower after a given time in case you extend because you are searching all branches one ply deeper than reported. An iteration N in the version which extends at the root will correspond with ply N+1 in the version that does not extend (of course this is only valid if you are in check at the root). The only thing that would maybe affect the search tree is the fact that if you are in check and extend at the root, there will be no real iteration 1 search because in the reported iteration 1 you will actually be searching iteration 2.

Correct. Your viewpoint is to look at the whole search, doing iterations. My viewpoint was only one single iteration.

What can be discussed, of course, is whether extending at the root node when in check is *useful* or not. Here I am totally with you, it would not make much sense to do that - provided the "root node" we are talking about is really the root node of the whole search. And here we are again: an engine that has a separate search function only for the root node (many engines do have that for good reasons) will, with your version 2 of Search() [EDIT: applied to all full search nodes below the root], *miss* the check extension at all nodes of height 1 unless the root search function takes care about check extension there, too. But then everything becomes more complex and error-prone than necessary, where version 1 would simply fit.

Taking my last paragraph into account, I see no good reason to prefer version 2 over version 1.

Sven

I also see no good reason to prefer v2 and I am using version 1. My point was, however, that the search trees of both versions, given that version1 does _not_ extend at the root if in check, and that version 2 takes care of extending checking moves at the root, would be exactly identical. The performance is another question.

Actually, as far as I know e.g. Stockfish uses the second version.

By "version 1 does _not_ extend at the root if in check" you certainly mean that you think of having a "version 1" RootSearch() function with that property, right? In this case I agree that both search trees would be identical.

It was not easy for me to get behind your ideas when you initially asked: "Isn't this the same? <code ...> I cannot see any difference." so I focussed upon comparing exactly these two pieces of code, nothing more.

Sven