Search instability or bug?

[stegemma]

[...]
I assume you don't do lazy eval either?

You could just dump the two trees and see where they differ, since they should not.

No lazy eval. I've seen that it fail sometime low sometime high but only when val is negative. I've think to go back and restart from a simpler approach, just to understand how to handle correctly the alfabeta window.

First step:

Code: Select all

val = -AlfaBeta(-valok, valInfinity, iDepth - 1);

This will never fail and it always get back the expected val. The call appears more logic to me and can be explained this way: "i already know that the value is valok, so it can't be more than this".

Now i can say: "ok, so the opponent can't reach a value lower than valok" but i need a +1, because comparing with beta is not simmetric (it use val>beta to cut the node and <= to don't cut):

Code: Select all

val = -AlfaBeta(-valok, -valok+1, iDepth - 1);

Even this one doesn't never fail.

And now why not -1/+1, as you suggested?

Code: Select all

val = -AlfaBeta(-valok-1, -valok+1, iDepth - 1);

No failing again! So i've missed something in the previous try... ah, ok... i've wrote valok+1 instead of -valok+1, sorry

But if this were the error... lets try again:

Code: Select all

val = -AlfaBeta(-valok, -valok, iDepth - 1);

This apparently never fail but the node count is so low (equal to the ply depth!) that it only prove that you were right, saying that we can't distinguish between a true returned value and fail high/low. It is very interesting: we get the expected value but... it is wrong! This must applyed to the first calls of this message: if we use the true value and we get back that value, we are not sure that it is good. -1/+1 should be the more secure approach. Now it is too late... i should read all of this posts and try again tomorrow (i'm sure to have missed some important detail).

I'm happy, i can bury my old alfagemma and experiment with alfabeta, now.

Many thanks to all of you.

[stegemma]

I'm trying to understand why it still fails on -val-1 to val+1.

Why are you inverting the sign of alpha but not beta? It should be -val-1, -ival for a null window or -val-x, -val+x for an aspiration window.

Sorry i've read this post too late, now i've solved. In fact, i was using the bad sign for beta. Now i can experiment some idea about alfabeta.

Thanks.

[elpapa]

Sorry i've read this post too late, now i've solved. In fact, i was using the bad sign for beta. Now i can experiment some idea about alfabeta.

Thanks.

I'm glad you solved it. Alphabeta, though basically very simple, can really mess with your head sometimes.

[stegemma]

Sorry i've read this post too late, now i've solved. In fact, i was using the bad sign for beta. Now i can experiment some idea about alfabeta.

Thanks.

I'm glad you solved it. Alphabeta, though basically very simple, can really mess with your head sometimes.

Oh yes!

Now i'm trying an alfabeta binary search. I set a min/max value to +/- a rook value, compute v = (min+max)/2 and then try the window [-v-1, -v+1]; if i get back v, i stop, if not, i set min/max properly to v, depending if a fail high/low and loop again.

This seems to give about -30% of the nodes, compared to a full search, using a middle-game test position but the returned value are a little different from the expected one.

There's a lot to experiment with aspiration/null windows...

[stegemma]

This is the actual code, still just for test:

Code: Select all

typedef int vtype;
// for(...any move at root...){
val = -AlfaBeta(-valInfinity, valInfinity, iDepth - 1);  ncf = nodescount - ncf;   ntf += ncf;
vtype valok = val;
vtype vmin = -valRook;
vtype vmax = valRook;			
for (vtype v = 0; vmax - vmin >= valPawn;)
{
   val = -AlfaBeta(-v - 1, -v + 1, iDepth - 1);
   if (val == v) break;
   if (val > vmax) vmax = valInfinity;
   else if &#40;val < vmin&#41; vmin = -valInfinity;
   else if &#40;val > v&#41; vmin = v; else vmax = v;
   v = &#40;vmin + vmax&#41; / 2;
&#125;
val = -AlfaBeta&#40;-vmin - 1, -vmax + 1, iDepth - 1&#41;;

Of course this an overnight work and it can be improved a lot.

[stegemma]

In another night of test, I've try to use a pivot value equal to the last iteration value for any move and a binary windowed search:

Code: Select all

uint64_t nc1, nc2 = 0;
uint64_t ncf = nodescount;  val = -AlfaBeta(-valInfinity, valInfinity, iDepth - 1);  ncf = nodescount - ncf;   ntf += ncf;
vtype valok = val;
sfout.Push("#--- valok = " + clsString(valok));
vtype vmin = pLoopMove->alfavalue - valKnight;
vtype vmax = pLoopMove->alfavalue + valKnight;
uint64_t nck = nodescount;
for (vtype pivot = pLoopMove->alfavalue; vmax - vmin >= valPawn && !bTimeExpired;)
{
	val = -AlfaBeta(-pivot - 1, -pivot + 1, iDepth - 1);
	if (bTimeExpired) break;
	sfout.Push("# " + clsString(vmin) + "..." + clsString(vmax) + " : " + clsString(pivot) + " -> " + clsString(val));
	if (val == pivot) break;
	else if (val > pivot)
	{
		vmin = pivot - 1;  if (val>vmax) vmax = valInfinity - 1;
	}
	else if &#40;val < pivot&#41;
	&#123;
		vmax = pivot + 1; if &#40;val<vmin&#41; vmin = -valInfinity + 1;
	&#125;
	pivot = &#40;vmin + vmax&#41; / 2;
&#125;
if (!bTimeExpired&#41;
&#123;
	val = -AlfaBeta&#40;-vmax, -vmin, iDepth - 1&#41;;
	sfout.Push&#40;"# end&#58; " + clsString&#40;vmin&#41; + "..." + clsString&#40;vmax&#41; + " -> " + clsString&#40;val&#41;);
	nck = nodescount - nck;		ntk += nck;
	double perc = double&#40;nck&#41;*100.0 / double&#40;ncf&#41;;
	sfout.Push&#40;"# ok " + GetUserMove&#40;pLoopMove&#41; + "&#58; valok " + clsString&#40;valok&#41; + " val " + clsString&#40;val&#41; + " "
		+ clsString&#40;ncf&#41; + "-" + clsString&#40;nck&#41; + "=" + clsString&#40;double&#40;ncf&#41; - double&#40;nck&#41;) + " " + clsString&#40;perc, 2&#41; + "%");
&#125;
sfout.Push&#40;"#-------");

I would try again, to find a way (if any) to get some interesting result... for now, I've found a way to slow down my search

Here's my output:

Code: Select all

#--- valok = 1000
# -3000...3000 : 0 -> 1
# -1...3000 : 1499 -> 1498
# -1...1500 : 749 -> 750
# end: 748...1500 -> 1000
# ok g2g4: valok 1000 val 1000 36945-90298=-53353 244.41%
#-------
#--- valok = 1000
# -3000...3000 : 0 -> 1
# -1...3000 : 1499 -> 1498
# -1...1500 : 749 -> 750
# end: 748...1500 -> 1000
# ok d2d3: valok 1000 val 1000 53798-122675=-68877 228.03%
#-------
#--- valok = 0
# -3000...3000 : 0 -> 0
# end: -3000...3000 -> 0
# ok b1a3: valok 0 val 0 42276-79162=-36886 187.25%
#-------
#--- valok = 0
# -3000...3000 : 0 -> 0
# end: -3000...3000 -> 0
# ok f2f3: valok 0 val 0 37285-69219=-31934 185.65%
#-------
#--- valok = 0
# -3000...3000 : 0 -> 0
# end: -3000...3000 -> 0
# ok f2f4: valok 0 val 0 67479-130880=-63401 193.96%
#-------
#--- valok = 1000
# -3000...3000 : 0 -> 1
# -1...3000 : 1499 -> 1498
# -1...1500 : 749 -> 750
# end: 748...1500 -> 1000
# ok h2h3: valok 1000 val 1000 43291-99953=-56662 230.89%
#-------
#--- valok = 1000
# -3000...3000 : 0 -> 1
# -1...3000 : 1499 -> 1498
# -1...1500 : 749 -> 750
# end: 748...1500 -> 1000
# ok a2a3: valok 1000 val 1000 43013-98763=-55750 229.61%

I like the fact that I get the correct value from the last AlfaBeta call and that the binary search gives the expected converting values.

(NB: sfout.Push() is my asynchronous thread-safe std::cout buffered output while clsString is obviously my string class)