Collecting PV in a PVS search ?

[mar]

pvLine is a std::list, I set the bestmove as first element and attach childPV by "splice" ( change of a pointer ).
It avoid data copying. Each pvline change is just:set a new bestmove and "link" the already calculated child.

Right, you think you avoid copying but you have 1 dynamic allocation per element added.
Also since std::list is a doubly-linked list, assuming you compile for x64, the node itself consumes 24 bytes instead of 4 (and in fact even more as heap allocated objects require some bookkeeping, say 8 extra bytes plus padding if necessary).
You also have no guarantee the nodes are allocated close to each other.
Plus you need to link when adding a new element.

So I don't believe this is faster than copying a very small chunk of data,
have you measured it if you claim it's faster?

[hgm]

PV updates happen so infrequently, that the effect on total speed will be negligible however you do it. Another thing to keep in mind is that the average length of updated PVs is very small, perhaps only 2 moves. Longer PVs only occur in nodes close to the root, which make up a negligible fraction of the tree. For such short PVs copying the data is probably faster than adjusting the links.

Having a linked list would also make it very cumbersome to hash the PV (such as Crafty does).

[elcabesa]

So I don't believe this is faster than copying a very small chunk of data,
have you measured it if you claim it's faster?

no I haven't measured, and i don't claim that it's faster
I only claim it's fast enough for my engine and that it's a quite simple code

[MahmoudUthman]

Thank you all .

Well, a stack in a linear array seems better; it avoids 2-d addressing, and is more compact.

Code: Select all

typedef int Move;

Move pv[MAXPLY*MAXPLY];
int pvPtr;

int
Search ()
{
  int myPV = pvPtr;
  pv[pvPtr++] = INVALID; // initialize empty PV

  for(ALL_MOVES)
  {
    ...

    if(score > alpha) {
      if(score >= beta) break; // cutoff
      int p = pvPtr; // PV of daughter was left here
      pvPtr = myPV; // pop previous PV
      pv[pvPtr++] = move; // new PV move
      while((pv[pvPtr++] = pv[p++]) != INVALID) ; // append PV of daughter to it
    }
  }

  pvPtr = myPV; // pop PV (but leave it above stack top)
}

I tried this , and I can't get it completely right , this is it :

Code: Select all

int myPV = pvPtr;
	hpv[pvPtr++] = Move(); // initialize empty PV 
	for (Move move; (move = MP.Next()).M != 0; )
	{
		PrincipalVariation localPV;

		++i;
		Position::MakeMove(move);
		if (i > 1) value = -searchNonPV(-(alpha + 1), depth - 1, true);
		if (i == 1 || (value > alpha && (value < beta))) value = -searchPV(-beta, -alpha, depth - 1,localPV);
		Position::UnMakeMove(move);
		if (value > bestValue)
		{
			bestValue = value;
			if (value > alpha)
			{
				mBest = move;
				bound = Bound::Exact;
				if (value < beta)
				{
					alpha = value;
					pv.Concat(move, localPV);

					int p = pvPtr; // PV of daughter was left here 
					pvPtr = myPV; // pop previous PV 
					hpv[pvPtr++] = move; // new PV move 
					while ((hpv[pvPtr++] = hpv[p++]).M != 0); // append PV of daughter to it 
				}
				else
				{
					bound = Bound::Lower;
					if (NOTCaptureOrPromotion(move)) UpdateKillersAndHistory(move, depth, QuietsSearched, QuietCount);
					break; // Fail high
				}
			}
		}
		if (NOTCaptureOrPromotion(move) && (move.M != mBest.M) && (QuietCount < 64))
			QuietsSearched[QuietCount++] = move;
	}
	pvPtr = myPV; // pop PV (but leave it above stack top)

the other method I found in one of Sven's replies , the result is the second one :

Code: Select all

position startpos
go wtime 10000
info depth 1 score cp 61 nodes 23 time 0 pv e2e3
info depth 1 score cp 61 nodes 23 time 1 pv e2e3

info depth 2 score cp 0 nodes 94 time 3 pv e2e3 g8f6
info depth 2 score cp 0 nodes 94 time 5 pv e2e3 g8f6

info depth 3 score cp 56 nodes 541 time 7 pv e2e3 e7e6 b1c3
info depth 3 score cp 56 nodes 541 time 10 pv e2e3 e7e6 b1c3

info depth 4 score cp 0 nodes 2286 time 13 pv b1c3 e7e6 e2e3
info depth 4 score cp 0 nodes 2286 time 16 pv b1c3 e7e6 e2e3 d7d5

info depth 5 score cp 54 nodes 5658 time 21 pv b1c3 g8f6 g1f3 d7d6 d2d3
info depth 5 score cp 54 nodes 5658 time 23 pv b1c3 g8f6 g1f3 d7d6 d2d3

info depth 6 score cp 0 nodes 24685 time 43 pv b1c3 b8c6 d2d4 d7d5 g1f3 g8f6
info depth 6 score cp 0 nodes 24685 time 45 pv b1c3 d7d6 b1c3 g8f6 b1c3 e4d3 g1f3 g8f6

info depth 7 score cp 54 nodes 45626 time 64 pv b1c3 g8f6 g1f3 b8c6 e2e3 e7e6
info depth 7 score cp 54 nodes 45626 time 67 pv b1c3 g8f6 g1f3 b8c6 e2e3 e7e6 f8b4 a2a3

info depth 8 score cp 5 nodes 91993 time 106 pv b1c3 g8f6 g1f3 b8c6 e2e4 e7e6 f1b5 f8b4
info depth 8 score cp 5 nodes 91993 time 109 pv b1c3 g8f6 g1f3 b8c6 e2e4 e7e6 f1b5 f8b4 f8b4 a2a3

info depth 9 score cp 51 nodes 170399 time 170 pv b1c3 g8f6 g1f3 e7e6 e2e4 f8b4 e4e5 f6d5 f1c4
info depth 9 score cp 51 nodes 170399 time 175 pv b1c3 g8f6 g1f3 e7e6 e2e4 f8b4 e4e5 f6d5 f1c4

what am I doing wrong ?

[hgm]

The second method is suspect: at 6 ply it gives a PV of length 8, while the final two moves are not captures (so not from QS). And b1c3 is played three times!

[MahmoudUthman]

The second method is suspect: at 6 ply it gives a PV of length 8, while the final two moves are not captures (so not from QS). And b1c3 is played three times!

sorry I meant that the second method/second line is the one you provided so I must have done something wrong , by the way I have a dedicated function for the root search so in All I do there is this :

Code: Select all

std::string PVString()
{
	std::string res = "";
	for(auto tpr=pvPtr; hpv[tpr].Move16!=0;tpr++)
	{
		res += ' ' + Parser::MoveToAlgebraicNotation(hpv[tpr]);
	}
	return res;
}

Root
{
if (abs(alpha) >= Value_Mate_In_Max_Ply)//optimize this section
		{
			auto MateIn = (Value_Mate - abs(alpha)) / 2;
			std::cout << "info depth " << d << " score mate " << (alpha >= 0 ? MateIn + 1 : -MateIn) << " nodes " << TotalNodeCount << " time " << TimeManager::Elapsed() << " pv " << Parser::MoveToAlgebraicNotation(BestMove) + PVString() << std::endl;
			break;
		}
		else std::cout << "info depth " << d << " score cp " << (alpha * 100 / PawnValueEg) << " nodes " << TotalNodeCount << " time " << TimeManager::Elapsed()<<" pv " <<Parser::MoveToAlgebraicNotation(BestMove)+PVString() << std::endl;
}

and I'm not collecting Qsearch PVS yet.

[hgm]

The code you show for it looks OK. But there could be problems if you would ever return from the Search routine without resetting pvPtr to the value it had on entry. That you sometimes get an extra long PV suggests that at some point you returned to the root with pvPtr != 0. That would also explain how you can get a duplicat move: the extra moves are not at the end, but at the start of the PV, where there remained left-overs from the PV of a previous iteration.

[Rein Halbersma]

i did it this way

http://vajoletchess.blogspot.it/2013/11 ... cipal.html

today I use a std::list instead of a std::Vector because it's faster, You can find the new code in vajolet, but it's very similar to the one explained in the blog.

Code: Select all

std::copy(childPV.begin(),childPV.end(),back_inserter(PV)); 

Would be better to write

Code: Select all

PV.insert(PV.end(), childPV.begin(),childPV.end()); 

Since that would allocate the required memory in one go.

[MahmoudUthman]

The code you show for it looks OK. But there could be problems if you would ever return from the Search routine without resetting pvPtr to the value it had on entry. That you sometimes get an extra long PV suggests that at some point you returned to the root with pvPtr != 0. That would also explain how you can get a duplicat move: the extra moves are not at the end, but at the start of the PV, where there remained left-overs from the PV of a previous iteration.

I checked It always return 0 at the root , I was forgetting to set pv[pvptr+1] to invalid at the very beginning of the search so it was being skipped in case of an early return but now things got somewhat strange , here's an example :

Code: Select all

position startpos
depth 19
info depth 1 score cp 61 nodes 23 time 0 pv e2e3
info depth 1 score cp 61 nodes 23 time 1 pv e2e3

info depth 2 score cp 0 nodes 94 time 3 pv e2e3 g8f6
info depth 2 score cp 0 nodes 94 time 5 pv e2e3 g8f6

info depth 3 score cp 56 nodes 541 time 8 pv e2e3 e7e6 b1c3
info depth 3 score cp 56 nodes 541 time 11 pv e2e3 e7e6 b1c3

info depth 4 score cp 0 nodes 2286 time 14 pv b1c3 e7e6 e2e3
info depth 4 score cp 0 nodes 2286 time 16 pv b1c3 e7e6 e2e3

info depth 5 score cp 54 nodes 5658 time 21 pv b1c3 g8f6 g1f3 d7d6 d2d3
info depth 5 score cp 54 nodes 5658 time 23 pv b1c3 g8f6 g1f3 d7d6 d2d3

info depth 6 score cp 0 nodes 24685 time 39 pv b1c3 b8c6 d2d4 d7d5 g1f3 g8f6
info depth 6 score cp 0 nodes 24685 time 41 pv b1c3 d7d6 b1c3 g8f6

info depth 7 score cp 54 nodes 45626 time 57 pv b1c3 g8f6 g1f3 b8c6 e2e3 e7e6
info depth 7 score cp 54 nodes 45626 time 60 pv b1c3 g8f6 g1f3 b8c6 e2e3 e7e6

info depth 8 score cp 5 nodes 91993 time 96 pv b1c3 g8f6 g1f3 b8c6 e2e4 e7e6 f1b5 f8b4
info depth 8 score cp 5 nodes 91993 time 99 pv b1c3 g8f6 g1f3 b8c6 e2e4 e7e6 f1b5 f8b4

info depth 9 score cp 51 nodes 170399 time 155 pv b1c3 g8f6 g1f3 e7e6 e2e4 f8b4 e4e5 f6d5 f1c4
info depth 9 score cp 51 nodes 170399 time 158 pv b1c3 g8f6 g1f3 e7e6 e2e4 f8b4 e4e5 f6d5 f1c4

info depth 10 score cp 27 nodes 542522 time 388 pv e2e4 g8f6 e4e5 f6d5 d2d4 e7e6 c2c4 f8b4 c1d2 b4d2 b1d2 d5f4
info depth 10 score cp 27 nodes 542522 time 392 pv e2e4 g8f6 e4e5 f6d5 d2d4 e7e6 c2c4 f8b4 c1d2 b4d2 b1d2 d5f4

info depth 11 score cp 51 nodes 788276 time 571 pv e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 f1c4 f8b4 e1g1 e8g8 c3d5
info depth 11 score cp 51 nodes 788276 time 574 pv e2e4 e7e5 g1f3 g8f6 b1c3 b8c6 f1c4 f8b4 e1g1 e8g8 c3d5

info depth 12 score cp 24 nodes 1037959 time 765 pv e2e4 e7e5 g1f3 b8c6 d2d4 e5d4 f1d3 g8f6 c2c3 f8d6 c3d4 e8g8
info depth 12 score cp 24 nodes 1037959 time 769 pv e2e4 e7e5 g1f3 b8c6 d2d4 e5d4 f1d3 g8f6 c2c3 f8d6 c3d4 e8g8

info depth 13 score cp 56 nodes 1699055 time 1268 pv e2e4 d7d5 e4d5 g8f6 g1f3 e7e6 d5e6 c8e6 d2d4 b8c6 c2c3 f8d6 f1b5
info depth 13 score cp 56 nodes 1699055 time 1272 pv e2e4 d7d5 e4d5 g8f6 g1f3 e7e6 d5e6 c8e6 d2d4 b8c6 c2c3 f8d6 f1b5

info depth 14 score cp 31 nodes 2432983 time 1786 pv e2e4 e7e5 g1f3 g8f6 f3e5 b8c6 d2d4 c6e5 d4e5 f6e4 d1d4 e4c5 f1c4 f8e7
info depth 14 score cp 31 nodes 2432983 time 1790 pv e2e4 e7e5 g1f3 g8f6 f3e5 b8c6 d2d4 c6e5 d4e5 f6e4 d1d4 e4c5 f1c4 f8e7

info depth 15 score cp 44 nodes 3305586 time 2454 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 f3g5 d7d5 e4d5 c6a5 d2d3 h7h6 g5f3 f8d6 e1g1
info depth 15 score cp 44 nodes 3305586 time 2459 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 f3g5 d7d5 e4d5 c6a5 d2d3 h7h6 g5f3 f8d6 e1g1

info depth 16 score cp 28 nodes 4851008 time 3525 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 d2d4 e5d4 f3g5 d7d5 e4d5 f8b4 c2c3 d8e7 e1f1 c6e5 c4b5 c7c6 c3b4
info depth 16 score cp 28 nodes 4851008 time 3530 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 d2d4 e5d4 f3g5 d7d5 e4d5 f8b4 c2c3 d8e7 e1f1 c6e5 c4b5 c7c6 c3b4

info depth 17 score cp 29 nodes 6351332 time 4598 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 d2d4 e5d4 f3g5 d7d5 e4d5 c6e5 d1d4 f8b4 c2c3 b4d6 c1f4 f6h5
info depth 17 score cp 29 nodes 6351332 time 4603 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 d2d4 e5d4 f3g5 d7d5 e4d5 c6e5 d1d4 f8b4 c2c3 b4d6 c1f4 f6h5

info depth 18 score cp 17 nodes 14914737 time 10638 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 f3g5 d7d5 e4d5 c6a5 c4b5 c7c6 d5c6 b7c6 b5e2 f8c5 e1g1 h7h6 g5f3
info depth 18 score cp 17 nodes 14914737 time 10643 pv e2e4

info depth 19 score cp 24 nodes 17814559 time 12816 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 f3g5 d7d5 e4d5 c6a5 d2d3 h7h6 g5f3 f8d6 b1d2 a5c4 d2c4 e8g8 e1g1
info depth 19 score cp 24 nodes 17814559 time 12821 pv e2e4 e7e5 g1f3 b8c6 f1c4 g8f6 f3g5 d7d5 e4d5 c6a5 d2d3 h7h6 g5f3 f8d6 b1d2 a5c4 d2c4 e8g8 e1g1

bestmove e2e4

All PVs are ok except at depth 6 and depth 18 the first is completely wrong and the second is empty -"the first move is parsed at the root and not collected through this method"- which is strange .

this is my code

Code: Select all

//nothing changed here
searchNonPV()
{
}
//SearcgPV()
{
hpv[pvPtr].M = 0; // initialize empty PV 
//Early returns through pruning,TT ,3fold , ...etc.
...
//
int myPV = pvPtr++;
	for (Move move; (move = MP.Next()).M != 0; )
	{
		PrincipalVariation localPV;
		i++;
		Position::MakeMove(move);
		if (i > 1) value = -searchNonPV(-(alpha + 1), depth - 1, true);
		if (i == 1 || (value > alpha && (value < beta))) value = -searchPV(-beta, -alpha, depth - 1,localPV);
		Position::UnMakeMove(move);
		if (value > bestValue)
		{
			bestValue = value;
			if (value > alpha)
			{
				mBest = move;
				bound = Bound::Exact;
				if (value < beta)
				{
					alpha = value;
					pv.Concat(move, localPV);

					int p = pvPtr; // PV of daughter was left here 
					pvPtr = myPV; // pop previous PV 
					hpv[pvPtr++] = move; // new PV move 
					int count = 0;
					while ((hpv[pvPtr++] = hpv[p++]).M != 0)  count++; // append PV of daughter to it 					
				}
				else
				{
					mBest = move;
					bound = Bound::Lower;
					//irrelevant code
					break; // Fail high
				}
			}
		}
		//irrelevant code
	}
	pvPtr = myPV; // pop PV (but leave it above stack top)

	if (i == 0) return InCheck ? -Value_Mate + ply : Value_Draw;
       //irrelevant code
	return bestValue;
}
std::string PVString()
{
	std::string res = "";
	for(auto tpr=pvPtr; hpv[tpr].Move16!=0;tpr++)
		res += ' ' + Parser::MoveToAlgebraicNotation(hpv[tpr]);
	return res;
}
IDSearch(size_t maxdepth)
{
	Move BestMove;;
	int value;

	//GenerateRootMoves
	//irrelevant code

	for (size_t d = 1; (d <= maxdepth); d++)
	{
		int alpha = -Value_Infinite, beta = Value_Infinite;
		PrincipalVariation bestPVL;
		for (size_t i = 0; i < NMoves; i++)
		{
			PrincipalVariation localPV;
			Position::MakeMove(RootMoves[i].move);
			if (i > 0) value = -searchNonPV(-(alpha + 1), d - 1, true);
			if (i == 0 || (value > alpha)) value = -searchPV(-beta, -alpha, d - 1, localPV);
		        Position::UnMakeMove(RootMoves[i].move);

			if (value > alpha)
			{
				alpha = value;
				BestMove = RootMoves[i].move;
				RootMoves[i].Score = value;

				bestPVL.Concat(RootMoves[i].move, localPV);
			}
			else RootMoves[i].Score = -Value_Infinite;//by what should they be ordered ?

			
		}
		
		if (abs(alpha) >= Value_Mate_In_Max_Ply)//optimize this section
		{
			auto MateIn = (Value_Mate - abs(alpha)) / 2;
			std::cout << "info depth " << d << " score mate " << (alpha >= 0 ? MateIn + 1 : -MateIn) << " nodes " << TotalNodeCount << " time " << TimeManager::Elapsed() <<bestPVL.ToString() << std::endl;
			break;
		}
		else std::cout << "info depth " << d << " score cp " << (alpha * 100 / PawnValueEg) << " nodes " << TotalNodeCount << " time " << TimeManager::Elapsed() << bestPVL.ToString() << std::endl;
		
		if (abs(alpha) >= Value_Mate_In_Max_Ply)//optimize this section
		{
			auto MateIn = (Value_Mate - abs(alpha)) / 2;
			std::cout << "info depth " << d << " score mate " << (alpha >= 0 ? MateIn + 1 : -MateIn) << " nodes " << TotalNodeCount << " time " << TimeManager::Elapsed() << " pv " << Parser::MoveToAlgebraicNotation(BestMove) + PVString() << std::endl;
			break;
		}
		else std::cout << "info depth " << d << " score cp " << (alpha * 100 / PawnValueEg) << " nodes " << TotalNodeCount << " time " << TimeManager::Elapsed()<<" pv " <<Parser::MoveToAlgebraicNotation(BestMove)+PVString() << std::endl;
		std::cout<<std::endl;

		//irrelevant code
		if (TimeManager::Stop()) break;
	}

	return BestMove;
}

I can't figure out what I'm doing wrong so far ?

[hgm]

You do not collect the PV in the usual way in the root at the time a new PV move is found. Instead you do it at the end of the iteration, where you combine the best move with the PV left on the PV stack, which must have been put there by the latest PV daughter.

But it is not guaranteed that this PV daughter will also be the one responsible for the best move. In the face of search instability a NonPV pilot search can fail high, trigger a PV re-search, which then fails low after all. But it would produce a PV, overwriting the PV of the earlier best-move daughter.

A PV node that fails high can return an empty PV, if alpha was not increased before the cutoff occurs.