How to speed up my engine

[Guenther]

...

Also, excuse my lack of information here (self taught) what do you mean by " but it was not statically linked vs. libstdc++-6.dll at least."

It complained about this missing dll. Even when I added manually the right version, it started complaing about more dlls.
All those are part of GCC/MingW runtime libraries, AFAIK you need to add them during compilation via some switch
otherwise the exe won't run on other machines without GCC/MingW installed already.
IIRC it was: -static-libgcc.

I am sure others can help more, because I haven't compiled anything since
several years and I never had used GCC/MingW ;)

(BTW this was on Win7 64bit Ultimate)

[lauriet]

BTW do you consider your program released?

https://github.com/AndyGrant/Ethereal

I ask because I found 2 compiled versions of Etheral in an old folder
of your master branch.
Also the readme file sounds as if you consider Ethereal open to the public ?

I downloaded the newer one for testing (V2) but it was not statically linked vs. libstdc++-6.dll at least.

I am also asking because I am rebuilding the RWBC chronology of XB/UCI chess programs and Ethereal is still unknown.

Another thing, I guess you and your program are not related to this?
(the naming similarity is probably no big matter because I believe that was a standalone program
and had no XB/UCI interface - otherwise we would know it already)

https://sourceforge.net/projects/etherealchess/




Im confused here......ethereal is not my program ???

[lauriet]

In the worst case, you may have to search all of the captures. But there are some things you can do to improve that. You should be ordering your moves in some form as to search 'best' captures first. You should also be using some sort of standing pat, as well as delta pruning. Do you have these things or are you looking for other things to add?

Yes i look at besr catures first and do have a stand pat score but do not have any delta pruning.

Laurie

[lauriet]

It escaped me that you did not have a hash table. This could very well explain all the difference with Fairy-Max. It is really worth a lot in terms of branching factor to have the cut-move of the previous iteration listed in the hash table, so that you can almost alwars start with the cut move. In addition engines without hash table typically start to play like an idiot in Pawn endings, so that it will give you a lot of Elo too.

So your first priority should be to add a hash table.

Thanks.......this was the sort of thing i was looking for........and will head in this direction

Laurie

[lauriet]

No i cant swear that i have no bugs.......can anyone?

My first suspicion goes exactly into that direction. See my other comments below.

No transposition table.
In check, scans out from the king looking for attackers.
Quiescense has its own move gen that only gives captures.....no checks. Moves are ordered via captured - capturing.
Eval has pst, mobility, pawn structure, king safety, 2 rook/knight/bishop reward.
havent done any profiling yet......i will look into this.

Nothing from this list seems to indicate any kind of severe problem so far. But ...

branchinf factor is probably very poor as it can take 7 times longer to search the next ply.
nps is maybe about 1000-2000 per second.

An EBF of 7 is definitely too much, considering also that you have implemented null-move and obviously also regular move ordering stuff. Part of your problem is here. And nps, do you really mean 1000-2000 nodes per second, or 1000-2000 kNodes per second?
- In the former case I would say: yes, there are bugs, and you need to find and fix them first before you change *anything*. That would be roughly a factor of 1000 away from what's reasonable today. Here I would suggest to use profiling to find the bottleneck.
- In the latter case I'd propose to concentrate on finding the exact reason for the bad EBF only. Maybe transposition table is already the key here, but I would not start implementing a complex task like that until I am reasonably sure about having excluded other sources of the problem.

I would also do another check: disable all of your evaluation features except material and PST, and look how your engine performs. The first observation should be: much faster. A second observation *might* be that it also helps to get a much better EBF; in this case an explanation for your bad EBF might be a severe problem within your positional evaluation. Then re-enable your features again step by step to see their influence on performance and on EBF. Use identical test scenarios of course. Maybe you find one feature that kills your search.[/quote


I think MAYBE I was counting nodes wrong...so I have modified the engine to inc nodes when i enter search. Qnodes when I enter qsearch,
In an early middle game position I have:

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

I would like to post the screen shot but cant figure that out.
So I guess my NPS is 27800.....does this sound right ?
Previously I was not counting a node if depth=0 and it jump to qsearch. Was this incorrect ?


Laurie

[Dann Corbit]

I have read that the best engines do less than 2.......how is that possible. Does it mean it only looks at 2 moves in any position ?

No, it just lies about the depth. For every next depth on average it just searches one new move of every position. But it always searches a new move at the end of the PV. So the depth there just means the PV length.

I am pretty sure that the question was about branching factor and not pv length.

A branching factor of 2 does not mean that 2 nodes are searched, but that only twice as many nodes on average are searched on each succeeding iteration.

Using pure alpha beta, with ideal move ordering the branching factor will be 6 and the search will still be game theoretically perfect. Null move, LMR, etc. perform risky pruning but it works out well in practice though the outcome is no longer guaranteed.

[lauriet]

My engine reports 208629 nodes for 5 ply and then 735601 for 6 ply.

Does that mean the BF is (735601 - 208629)/208629 = 2.53 ???


Laurie.

[Dann Corbit]

My engine reports 208629 nodes for 5 ply and then 735601 for 6 ply.

Does that mean the BF is (735601 - 208629)/208629 = 2.53 ???


Laurie.

That is an estimate for a single location. You should average over many plies and positions to get a really good idea.

My calculation would be 735601/208629=3.5259 (three and a half times as many nodes for ply 6 as ply 5).

I guess that the time for ply 5 to ply 6 will have very nearly the same ratio

[Guenther]

BTW do you consider your program released?

https://github.com/AndyGrant/Ethereal

...

Im confused here......ethereal is not my program ???

Sorry, I did not want to hijack your thread, but this was Andrews' first post in TalkChess and he practically 'announced' his program in his signature.
I answered to his post only, which you can see best in Threadview.
(Mod: Would it be difficult to split this thread branch into a new one about Ethereal?)

[asanjuan]

The null move uses R=2 no matter what.
LMR (R=1) is based on the move ordering so it reduces moves that are < 0 based on PST.

Quiescence could be an issue.....I search ALL captures, good or bad. Can I improve this ??


Laurie.

Yes.

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.

In my opinion, the starting point BEFORE introduce null move an lmr is to have a clean alpha - beta with a good quiescence search and a good move ordering.

Add a hash table at this point.

Compile some stats. You should see that 95% of the beta cutoffs are made by the first move, and that in average, 98% of the cutoffs are made within the 3 first moves searched.

Test it, as much as you can, and then, when you are pretty sure that everyting is ok, then adapt that alpha-beta to a PVS. You should see a small speedup.

Then, introduce null move and lmr. The gain must be huge.

I followed these steps when I made a rewrite of Rhetoric. I think is the most logical way to speedup your engine.

I forgot to ask if you have implemented and tested a perft function. Sometimes the basics fail and some branches can be searched more than once.

Hope it helps.