My Engine won't pick up PV's until depth >= 10

[ZirconiumX]

I have created an engine based on FirstChess (it was public domain), and attempted to add PV's using the Bruce Moreland approach - yet it doesn't pick them up till about depth 10 or so - it barely even searches until then

Magic 0.0 by Matthew Brades, Pham Hong Nguyen
d(isplay), Move( in LAN) quit( Magic)

e2e4
info depth 1
info score 0 nodes 1 nps 0 seldepth 0 pv
info depth 2
info score 0 nodes 2 nps 0 seldepth 0 pv
info depth 3
info score 0 nodes 3 nps 0 seldepth 0 pv
info depth 4
info score 0 nodes 4 nps 0 seldepth 0 pv
info depth 5
info score 0 nodes 5 nps 0 seldepth 0 pv
info depth 6
info score 0 nodes 6 nps 0 seldepth 0 pv
info depth 7
info score 0 nodes 7 nps 0 seldepth 0 pv
info depth 8
info score 0 nodes 8 nps 0 seldepth 0 pv
info depth 9
info score 0 nodes 9 nps 0 seldepth 0 pv
info depth 10
info score 0 nodes 10 nps 0 seldepth 0 pv
info depth 11
info score 50 nodes 33 nps 1 seldepth 0 pv b8c6
info depth 12
info score 0 nodes 191 nps 6 seldepth 0 pv b8c6 b1c3
info depth 13
info score 50 nodes 777 nps 20 seldepth 0 pv b8c6 b1c3 g8f6
info depth 14
info score 0 nodes 3371 nps 44 seldepth 0 pv b8c6 b1c3 g8f6 g1f3
info depth 15
info score 90 nodes 25762 nps 72 seldepth 10 pv b8c6 b1c3 g8f6 g1f3 f6e4
info depth 16
info score -10 nodes 92151 nps 79 seldepth 37 pv b8c6 b1c3 g8f6 g1e2 d7d6 e4e5
bestmove b8c6 ponder b1c3

ZIP file is here:
http://www.thelumpit.net/magic.zip

To compile, compile this.cpp.

Matthew:out

[John Major]

in srch.cpp you have

Code: Select all

if &#40;depth <= 0 || depth >= MAX_DEPTH&#41; &#123;
 ...search...

It should be <= MAX_DEPTH.

[John Major]

in srch.cpp you have

Code: Select all

if &#40;depth <= 0 || depth >= MAX_DEPTH&#41; &#123;
 ...search...

It should be <= MAX_DEPTH.

Sorry, you have

Code: Select all

	if &#40;depth <= 0 || depth <= MAX_DEPTH&#41; &#123;
		pline->cmove = 0;
		return Eval&#40;);
	&#125;

it should be >= MAX_DEPTH

[ZirconiumX]

...and now my QSearch is causing an explosion

info depth 1
info score 50 nodes 43 nps 43 pv b8c6
info depth 2
info score -20000 nodes 96 nps 48 pv b8c6
info depth 3
info score -20000 nodes 97 nps 48 pv b8c6
info depth 4
info score -20000 nodes 98 nps 49 pv b8c6
info depth 5
info score -20000 nodes 99 nps 49 pv b8c6
info depth 6
info score -20000 nodes 100 nps 50 pv b8c6
info depth 7
info score -20000 nodes 101 nps 50 pv b8c6
info depth 8
info score -20000 nodes 102 nps 51 pv b8c6
info depth 9
info score -20000 nodes 103 nps 51 pv b8c6
info depth 10
info score -20000 nodes 105 nps 52 pv
info depth 11
info score -2470 nodes 109 nps 54 pv
info depth 12
info score -2315 nodes 111 nps 55 pv
info depth 13
info score -2315 nodes 113 nps 56 pv
info depth 14
info score -2315 nodes 115 nps 57 pv
info depth 15
info score -2315 nodes 117 nps 58 pv
info depth 16
info score -2315 nodes 119 nps 59 pv
info depth 17
info score -2315 nodes 121 nps 60 pv
info depth 18
info score -2315 nodes 123 nps 61 pv
info depth 19
info score -2315 nodes 125 nps 62 pv
info depth 20
info score -2315 nodes 127 nps 63 pv
info depth 21
info score -2315 nodes 129 nps 64 pv
info depth 22
info score -2315 nodes 131 nps 65 pv
info depth 23
info score -2315 nodes 133 nps 66 pv
info depth 24
info score -2315 nodes 135 nps 67 pv
info depth 25
info score -2315 nodes 137 nps 68 pv
info depth 26
info score -2315 nodes 139 nps 69 pv
info depth 27
info score -2315 nodes 141 nps 70 pv
info depth 28
info score -2315 nodes 143 nps 71 pv
info depth 29
info score -2315 nodes 145 nps 72 pv
info depth 30
info score -2315 nodes 147 nps 73 pv
info depth 31
info score -2315 nodes 149 nps 74 pv
info depth 32
info score -2315 nodes 151 nps 75 pv
info depth 33
info score -2315 nodes 153 nps 76 pv
info depth 34
info score -2315 nodes 155 nps 77 pv
info depth 35
info score -2315 nodes 157 nps 78 pv
info depth 36
info score -2315 nodes 159 nps 79 pv
info depth 37
info score -2315 nodes 161 nps 80 pv
info depth 38
info score -2315 nodes 163 nps 81 pv
info depth 39
info score -2315 nodes 165 nps 82 pv
info depth 40
info score -2315 nodes 167 nps 83 pv
info depth 41
info score -2315 nodes 169 nps 84 pv
info depth 42
info score -2315 nodes 171 nps 85 pv
info depth 43
info score -2315 nodes 173 nps 86 pv
info depth 44
info score -2315 nodes 175 nps 87 pv
info depth 45
info score -2315 nodes 177 nps 88 pv
info depth 46
info score -2315 nodes 179 nps 89 pv
info depth 47
info score -2315 nodes 181 nps 90 pv
info depth 48
info score -2315 nodes 183 nps 91 pv
info depth 49
info score -2315 nodes 185 nps 92 pv
info depth 50
info score -2315 nodes 187 nps 93 pv
info depth 51
info score -2315 nodes 189 nps 94 pv
info depth 52
info score -2315 nodes 191 nps 95 pv
info depth 53
info score -2315 nodes 193 nps 96 pv
info depth 54
info score -2315 nodes 195 nps 97 pv
info depth 55
info score -2315 nodes 197 nps 98 pv
info depth 56
info score -2315 nodes 199 nps 99 pv
info depth 57
info score -2315 nodes 201 nps 100 pv
info depth 58
info score -2315 nodes 203 nps 101 pv
info depth 59
info score -2315 nodes 205 nps 102 pv
info depth 60
info score -2315 nodes 207 nps 103 pv
info depth 61
info score -2315 nodes 209 nps 104 pv
info depth 62
info score -2315 nodes 211 nps 105 pv
info depth 63
info score -2315 nodes 213 nps 106 pv
info depth 64
info score -2315 nodes 215 nps 107 pv
info depth 65
info score -2315 nodes 217 nps 108 pv
info depth 66
info score -2315 nodes 219 nps 109 pv
info depth 67
info score -2315 nodes 221 nps 110 pv
info depth 68
info score -2315 nodes 223 nps 111 pv
info depth 69
info score -2315 nodes 225 nps 112 pv
info depth 70
info score -2315 nodes 227 nps 113 pv
info depth 71
info score -2315 nodes 229 nps 114 pv
info depth 72
info score -2315 nodes 231 nps 115 pv
info depth 73
info score -2315 nodes 233 nps 116 pv
info depth 74
info score -2315 nodes 235 nps 117 pv
info depth 75
info score -2315 nodes 237 nps 118 pv
info depth 76
info score -2315 nodes 239 nps 119 pv
info depth 77
info score -2315 nodes 241 nps 120 pv
info depth 78
info score -2315 nodes 243 nps 121 pv
info depth 79
info score -2315 nodes 245 nps 122 pv
info depth 80
info score -2315 nodes 247 nps 123 pv
info depth 81
info score -2315 nodes 249 nps 124 pv
info depth 82
info score -2315 nodes 251 nps 125 pv
info depth 83
info score -2315 nodes 253 nps 126 pv
info depth 84
info score -2315 nodes 255 nps 127 pv
info depth 85
info score -2315 nodes 257 nps 128 pv
info depth 86
info score -2315 nodes 259 nps 129 pv
info depth 87

Code: Select all

int Quies(int alpha, int beta)
{
	int score, moves;
	move_t mB[200];
	
	nodes++;	
		
	score = Eval();
	if (score >= beta)
		return beta;
	if (score > alpha)
		alpha = score;
		
	if ((nodes & 1023) == 0) {
		timedOut();
		if (abortFlag)
			return Eval();
	}
	
	moves = QGen(side, mB);
	if (moves == 0)
		return alpha;
	
	for &#40;int i = 0; i < moves; i++) &#123;
		if (!MakeMove&#40;mB&#91;i&#93;)) &#123;
			TakeBack&#40;);
			continue;
		&#125;
		score = -Quies&#40;-beta, -alpha&#41;;
		TakeBack&#40;);
		if &#40;score >= beta&#41;
			return beta;
			
		if &#40;score > alpha&#41;
			alpha = score;
	&#125;
	return alpha;
&#125;

Matthew:out

[hgm]

...and now my QSearch is causing an explosion

Not really. As you can see you hardly search any nodes. It is just that you let it print like mad. In a bit of a suspicious way, I might add. As it seems to take only 2 nodes to search 74 ply deep. While one would think that this should take 74 nodes at least...

[John Major]

...and now my QSearch is causing an explosion

Some observations:

Your null move

Code: Select all

score = -AlphaBeta(depth - 1 - R, 1 - alpha, 0 - alpha, &line);

causes assert(beta > alpha) on top of AlphaBeta() to fail. It should be something like this:

Code: Select all

score = -AlphaBeta(depth - 1 - R, -beta, -beta + 1, &line);

You only want to know if the score is above beta. Missing is that you don't want two consecutive null moves.


Your futility pruning must do take back before returning alpha. f_prune is not initialised.

Your Think() must stop if depth > MAX_DEPTH, otherwise you get this endless nonsense output.

The general advice is to make the program as simple as possible and take it from there step by step. Only add features when you have time to debug them.

Always initialize your variables. Use loads of asserts.

[Sven]

...and now my QSearch is causing an explosion

Hi Matthew,

currently I have no important comment on your QSearch, it does not look as if it could do much harm. But I strongly suggest that you fix all compiler warnings, since I know that some of them point to bugs. I have compiled the code you published via the link above using VS2010 Express, and got a lot of warnings that are definitely bugs.

Mainly these are making trouble (but you should better fix ALL warnings):

Code: Select all

// tran.cpp (this warning appears many times in zobristKey() and
// lets that function effectively return complete random,
// which makes your hash table code do the same
if (side == BLACK)
    key ^ blackToMove;
// must be: key ^= blackToMove;
// same at many other places

// srch.cpp (this one does actually not do any harm but the line is
// simply useless, and in other cases such code could really screw you up)
seldepth == 0;

// eval.cpp (unitialized variables, this bug lets you practically never
// identify an endgame
int	IsEnding()
{
    int wpawn, wknight, wbishop, wrook, wqueen, bpawn, bknight, bbishop, brook, bqueen;
    for &#40;int i = 0; i < 64; i++) &#123;
        if &#40;color&#91;i&#93; == WHITE&#41; &#123;
            if &#40;piece&#91;i&#93; == PAWN&#41;
                wpawn++;
            if &#40;piece&#91;i&#93; == KNIGHT&#41;
                wknight++;
...

There is even more. Have you run your program in a debugger, and compiled it without /NDEBUG? If you didn't than you definitely should, I can assure you that you will see a lot of surprises Please set a breakpoint on each line that contains "assert(false)".

One other issue that is very important to fix is that in AlphaBeta(), the variables score and f_prune are not initialized but used within this condition:

Code: Select all

if &#40;score + VALUE_BISHOP <= alpha && 
    depth == 1 && 
    f_prune && 
    !IsInCheck&#40;side&#41; && 
    i < moves - 1&#41;
    return alpha;

This leads to an immediate return of AlphaBeta() through this branch, or the next one (for depth == 2) which is similar. While I can't tell exactly what the meaning of that piece of code is (it seems to be futility pruning, but then you would not want to RETURN to the parent node, just to SKIP the current move!), I am sure that the missing values for 'score' and 'f_prune' cause your tree to be very small (AlphaBeta() seems to always return after expanding just the first move one ply deep - I did not add your QSearch code yet). 'score' will be set after having searched the first move, or (which is a bad side effect, you should use a local score variable there!) in the block for null move if that one is entered, but it will in general not be set when dealing with the first move.

I think there is considerable work to be done. But this is also part of the fun

EDIT: some of my points are now also covered by another post as I have just seen.


Sven

[Sven]

Your futility pruning must do take back before returning alpha. f_prune is not initialised.

Why should it even return? I guess it should only skip the current move (after calling TakeBack which I initially missed).
Also, the semantics of the variable 'score' must be clarified. It is used at too many places, keeping its value from something that happened some time before, and therefore participates in screwing it up. My proposal to Matthew is therefore to make such variables as local as possible.

Sven

[John Major]

Your futility pruning must do take back before returning alpha. f_prune is not initialised.

Why should it even return? I guess it should only skip the current move (after calling TakeBack which I initially missed).

Sven

True, I had overlooked that.

I also got compile errors/warnings with g++ in Linux. Had to include string.h in srch.cpp. 'Key' in zobristKey() is used uninitialized.

There is a divide by zero bug in Think().

Null move tests if score >= beta of course, not > as I said.

[Sven]

I also got compile errors/warnings with g++ in Linux. Had to include string.h in srch.cpp.

Under VS2010Express I did not get errors, only warnings. But it was necessary to compile "this.cpp" which #include-s all other .cpp files.

'Key' in zobristKey() is used uninitialized.

That is due to the "x ^ y" instead of "x ^= y" kind of bugs in that routine which I mentioned.

There is a divide by zero bug in Think().

Yes, the NPS argument for printf() is not robust against the case that the elapsed time is zero (because an iteration was very fast).

Sven