How to speed up my engine

[hgm]

Search over ALL captures adds an extra overhead that you don't need. For example, you can discard losing captures in the quiescence search because you will surely stand pat in the next ply.

No. You mix up losing captures and futile captures. Good captures can be futile, and bad captures can be non-futile.

[hgm]

Previously I was not counting a node if depth=0 and it jump to qsearch. Was this incorrect ?

You should not count calls of routines that defer processing of the node to other routines as extra nodes. If you have separate routines Search(depth) and QSearch(), and at the top of Search() you have "if(depth == 0) return QSearch();" that call to Search() should not be counted as a node, but the call to QSearch() of course will have to be counted. A 'node' of the search tree is supposed to be a position, and having the position handled by a different routine will not make it a different position.

[asanjuan]

Search over ALL captures adds an extra overhead that you don't need. For example, you can discard losing captures in the quiescence search because you will surely stand pat in the next ply.

No. You mix up losing captures and futile captures. Good captures can be futile, and bad captures can be non-futile.

Good point.
The problem is the recapture in the next ply.

Anyway, skipping moves with SEE <0 saves you to search (and evaluate, generate moves... blah, blah...) over the winning captures in the next ply (that is very likely to happen).

At the end, SEE saves you precious time. This is what I was trying to point.

[flok]

Search over ALL captures adds an extra overhead that you don't need. For example, you can discard losing captures in the quiescence search because you will surely stand pat in the next ply. Check that you are doing well the stand pat.

I suggest you to implement a SEE function and discard moves where SEE < 0
The one described in the wiki is pretty good. Rhetoric has this function adapted. You should see a speedup.

This see, am I supposed to do something like:

int see(someting)
{
doMove()
generateMoveList()
see()
undoMove()
}

Or is it enough to just check which of the opponent with the lowest eval can re-catch and so on (swap colors) until all of them are evaluated?
Because this step of generating a list of moves can be rather cpu-intensive.

[Sven]

Search over ALL captures adds an extra overhead that you don't need. For example, you can discard losing captures in the quiescence search because you will surely stand pat in the next ply. Check that you are doing well the stand pat.

I suggest you to implement a SEE function and discard moves where SEE < 0
The one described in the wiki is pretty good. Rhetoric has this function adapted. You should see a speedup.

This see, am I supposed to do something like:

int see(someting)
{
doMove()
generateMoveList()
see()
undoMove()
}

Or is it enough to just check which of the opponent with the lowest eval can re-catch and so on (swap colors) until all of them are evaluated?
Because this step of generating a list of moves can be rather cpu-intensive.

No doMove()/undoMove() and no generateMoveList() is required for SEE. You just determine the piece values of all attackers and defenders of the given target square, and work through that list. Always "capture" with the least-valued attacker resp. defender and update the score of the capture sequence. Also make use of "stand pat" similar to QS, i.e. if capturing a piece scores worse than not capturing then you choose not to capture, of course.

Smarter SEE implementations also take care about hidden (discovered) attacks coming into play in the middle of a capture sequence.

[Sven]

Nodes: 2668831
Qnodes: 1523297
BetaCuts: 1521133
NullMove Cuts: 318
Search Depth: 7
Max Qsearch depth: 11
Eval Hash Hits: 980109
time used: 96

Even if I ignore the topic whether your node counting for Q-search is correct or not (others have already commented about it - I think your previous version was counting correctly at least), I suggest to double check your search again since your number of Qnodes is much too low. The ratio (Qnodes / (Nodes + Qnodes)) is about 35%, usually it is between 80% and 90%, so something might go wrong with your quiescence search.

So I guess my NPS is 27800.....does this sound right ?

From the numbers above NPS would be calculated as:

Total nodes = Nodes + Qnodes = 2668831 + 1523297 = 4192128
NPS = Total nodes / Time = 4192128 / 96 = 43668

If I change Qnodes based on the assumption that you currently count each Q-search node twice then I get:

NPS = (2668831 + (1523297 / 2)) / 96 = 35734

Not much of a difference, though.

Recently I sent you a couple of comments via PM, maybe you have not noticed these yet. The problems with your Q-search implementation which I reported there might explain the unusually low ratio of Q-search nodes, and the way how you do move legality checking is definitely one obvious explanation of the very low NPS.

[flok]

Thanks!

I once implemented a version of SEE which did do a do/undo-move etc. Dog slow and no improvements at all.
The version I hacked in this evening (only 1 extra check) is visibly faster.
This night I'll run a test to see what gain it gives.

[lauriet]

Previously I was not counting a node if depth=0 and it jump to qsearch. Was this incorrect ?

You should not count calls of routines that defer processing of the node to other routines as extra nodes. If you have separate routines Search(depth) and QSearch(), and at the top of Search() you have "if(depth == 0) return QSearch();" that call to Search() should not be counted as a node, but the call to QSearch() of course will have to be counted. A 'node' of the search tree is supposed to be a position, and having the position handled by a different routine will not make it a different position.

I have modified the accounting and inc(nodes) is now done after the call to qsearch so they are not counted twice.Here is a typical report:

Nodes: 954050
Qnodes: 92311
BetaCuts: 815918
NullMove cuts: 55
Depth: 7
Eval Hash hits: 1058053.

If a null move causes a betacut both are incremented.

Thnks for the correction
Laurie

[lauriet]

So I guess that is 954040/60 = 15900 NPS

A bit less than Deep Blue !


Laurie

[lauriet]

Can anyone disable their transposition table and post the before and after information
e.g. How many extra ply it is worth.

Does Nodes go up........what about all the nodes it bypasses because of the TT entry ? Does that men nodes go down ? But now its searching new nodes....so do nodes go up ?
Do you assume that nodes go down because of the TT and then they go up because of the extra search.....does this mean the node count is not as significant


Laurie.