Question about TT and PV

[selectany]

Hi all

I use TT in RootAlphaBeta and AlphaBeta search routines, and triangular array. The later is used to update and print PV, of course.

In process of iteration from depth = 2 to depth = n, I Print PV.

After first move hash table is filled. After second move I noticed that AlphaBeta search returns immediately, because of hash hit.
This result in shorter PV sequence with PrintPV routine.

Is that normal or I should continue searching for a bug ?

Here is an example PV. In depth 3 and 4 AlphaBeta routine returns immediately after hash hit.

depth 2 - f1g1 f8g8
depth 3 - f1g2
depth 4 - f1g2
depth 5 - f1g1 f8f7 g1h1 f7g8 h1g1
depth 6 - f1g1 f8f7 g1h1 f7g8 h1g1 g8f7

[Evert]

After first move hash table is filled. After second move I noticed that AlphaBeta search returns immediately, because of hash hit.
This result in shorter PV sequence with PrintPV routine.

Is that normal or I should continue searching for a bug ?

Yes, it's normal.
You can avoid the problem by not doing TT cutoffs in PV nodes, but only use it for move ordering.
A possible alternative to that is to try to find the rest of the PV in the transposition table and complete it that way.

[bob]

Hi all

I use TT in RootAlphaBeta and AlphaBeta search routines, and triangular array. The later is used to update and print PV, of course.

In process of iteration from depth = 2 to depth = n, I Print PV.

After first move hash table is filled. After second move I noticed that AlphaBeta search returns immediately, because of hash hit.
This result in shorter PV sequence with PrintPV routine.

Is that normal or I should continue searching for a bug ?

Here is an example PV. In depth 3 and 4 AlphaBeta routine returns immediately after hash hit.

depth 2 - f1g1 f8g8
depth 3 - f1g2
depth 4 - f1g2
depth 5 - f1g1 f8f7 g1h1 f7g8 h1g1
depth 6 - f1g1 f8f7 g1h1 f7g8 h1g1 g8f7

Are you checking the depth/draft of the hash entry? While this can happen here and there, it is pretty rare. The hit (above) at depth 3 probably should not happen since the TT entry should be one ply short on depth (we call that the TT draft) since we are now searching one ply deeper than when the entry was stored...

[selectany]

Hi all

I use TT in RootAlphaBeta and AlphaBeta search routines, and triangular array. The later is used to update and print PV, of course.

In process of iteration from depth = 2 to depth = n, I Print PV.

After first move hash table is filled. After second move I noticed that AlphaBeta search returns immediately, because of hash hit.
This result in shorter PV sequence with PrintPV routine.

Is that normal or I should continue searching for a bug ?

Here is an example PV. In depth 3 and 4 AlphaBeta routine returns immediately after hash hit.

depth 2 - f1g1 f8g8
depth 3 - f1g2
depth 4 - f1g2
depth 5 - f1g1 f8f7 g1h1 f7g8 h1g1
depth 6 - f1g1 f8f7 g1h1 f7g8 h1g1 g8f7

Are you checking the depth/draft of the hash entry? While this can happen here and there, it is pretty rare. The hit (above) at depth 3 probably should not happen since the TT entry should be one ply short on depth (we call that the TT draft) since we are now searching one ply deeper than when the entry was stored...

Hi

After debugging I found that problem arise after improving alpha from null-window search. The code below shows commented iScore and iAlpha for recursive call. I thought that is better to use scores returned from null-window search for a up bound (beta) in recursive call:

Code: Select all

		if(iLegalMoves == 0) 
		{
			iScore = -AlphaBeta(pBoard, iDepth + iCheckExtension - PLY, -iBeta, -iAlpha, iPly + 1, E_COLOR(!eCol));
		}
		else
		{
			iScore = -AlphaBeta(pBoard, iDepth + iCheckExtension - PLY, -iAlpha - 1, -iAlpha, iPly + 1, E_COLOR(!eCol));
			if&#40;iScore > iAlpha && iScore < iBeta&#41;
			&#123;
				iScore = -AlphaBeta&#40;pBoard, iDepth + iCheckExtension - PLY, -iBeta, -/*iScore*/iAlpha, iPly + 1, E_COLOR&#40;!eCol&#41;);
			&#125;
		&#125;

But, after correction, PV is still shorter.

Yes I check depth/draft of the hash entry.

To be more precise, the test board was white King vs. black King. Computer is White:

1. e1f1 e8f8

Or:
------------------------------
Computer plays "e1f1" with PV:

depth 2 - e1f1 e8f8
depth 3 - e1f1 e8f8 f1g1
depth 4 - e1f1 e8f8 f1g1 f8g8
depth 5 - e1f1 e8f8 f1g2 f8g8 g2g1
depth 6 - e1f1 e8f8 f1g2 f8g7 g2g1 g7g8

Human response : "e8f8"

Computer plays "f1g1" with PV:

depth 2 - f1g1 f8g8
depth 3 - f1g2 f8g7
depth 4 - f1g2 f8g7
depth 5 - f1g1 f8f7 g1h1 f7g8 h1g1
depth 6 - f1g1 f8f7 g1h1 f7g8 h1g1 g8f7

As you can see the stored depth is greater and caused EXACT cut-off at "f8g7".

Here is code in EXACT case:

Code: Select all

...
		case EXACT:
			{
				if &#40;iHashScore < iBeta&#41;
				&#123;
					if &#40;cBestMove != 0&#41;
					&#123;
						UpdatePV&#40;iPly, cBestMove&#41;;
					&#125;
				&#125;
			&#125;
			return iHashScore;
...

May be this is one of those rare situations.

[bob]

Hi all

I use TT in RootAlphaBeta and AlphaBeta search routines, and triangular array. The later is used to update and print PV, of course.

In process of iteration from depth = 2 to depth = n, I Print PV.

After first move hash table is filled. After second move I noticed that AlphaBeta search returns immediately, because of hash hit.
This result in shorter PV sequence with PrintPV routine.

Is that normal or I should continue searching for a bug ?

Here is an example PV. In depth 3 and 4 AlphaBeta routine returns immediately after hash hit.

depth 2 - f1g1 f8g8
depth 3 - f1g2
depth 4 - f1g2
depth 5 - f1g1 f8f7 g1h1 f7g8 h1g1
depth 6 - f1g1 f8f7 g1h1 f7g8 h1g1 g8f7

Are you checking the depth/draft of the hash entry? While this can happen here and there, it is pretty rare. The hit (above) at depth 3 probably should not happen since the TT entry should be one ply short on depth (we call that the TT draft) since we are now searching one ply deeper than when the entry was stored...

Hi

After debugging I found that problem arise after improving alpha from null-window search. The code below shows commented iScore and iAlpha for recursive call. I thought that is better to use scores returned from null-window search for a up bound (beta) in recursive call:

Code: Select all

		if(iLegalMoves == 0) 
		{
			iScore = -AlphaBeta(pBoard, iDepth + iCheckExtension - PLY, -iBeta, -iAlpha, iPly + 1, E_COLOR(!eCol));
		}
		else
		{
			iScore = -AlphaBeta(pBoard, iDepth + iCheckExtension - PLY, -iAlpha - 1, -iAlpha, iPly + 1, E_COLOR(!eCol));
			if&#40;iScore > iAlpha && iScore < iBeta&#41;
			&#123;
				iScore = -AlphaBeta&#40;pBoard, iDepth + iCheckExtension - PLY, -iBeta, -/*iScore*/iAlpha, iPly + 1, E_COLOR&#40;!eCol&#41;);
			&#125;
		&#125;

But, after correction, PV is still shorter.

Yes I check depth/draft of the hash entry.

To be more precise, the test board was white King vs. black King. Computer is White:

1. e1f1 e8f8

Or:
------------------------------
Computer plays "e1f1" with PV:

depth 2 - e1f1 e8f8
depth 3 - e1f1 e8f8 f1g1
depth 4 - e1f1 e8f8 f1g1 f8g8
depth 5 - e1f1 e8f8 f1g2 f8g8 g2g1
depth 6 - e1f1 e8f8 f1g2 f8g7 g2g1 g7g8

Human response : "e8f8"

Computer plays "f1g1" with PV:

depth 2 - f1g1 f8g8
depth 3 - f1g2 f8g7
depth 4 - f1g2 f8g7
depth 5 - f1g1 f8f7 g1h1 f7g8 h1g1
depth 6 - f1g1 f8f7 g1h1 f7g8 h1g1 g8f7

That is perfectly normal. If you insist on fixing it, you can look at Crafty. I have a separate hash table to store the PV that goes with a hash entry, although only for positions where alpha != beta - 1. Then when I get an EXACT hit, I can recover the PV that goes with that hit and avoid a short PV. Costs nothing in speed...

As you can see the stored depth is greater and caused EXACT cut-off at "f8g7".

Here is code in EXACT case:

Code: Select all

...
		case EXACT:
			{
				if &#40;iHashScore < iBeta&#41;
				&#123;
					if &#40;cBestMove != 0&#41;
					&#123;
						UpdatePV&#40;iPly, cBestMove&#41;;
					&#125;
				&#125;
			&#125;
			return iHashScore;
...

May be this is one of those rare situations.

[selectany]

That is perfectly normal. If you insist on fixing it, you can look at Crafty. I have a separate hash table to store the PV that goes with a hash entry, although only for positions where alpha != beta - 1. Then when I get an EXACT hit, I can recover the PV that goes with that hit and avoid a short PV. Costs nothing in speed...

Yes, Crafty is the best chess programming manual for me.
I took many ideas from it.
Thanks