How to speed up my engine

[lauriet]

Those are all good questions.

But behind the questions I think is this assumption: if you are getting 8 ply in 60 seconds on modern hardware very likely the problem is not the speed of the code but the algorithm. I suspect your branching factor is terrible (see https://chessprogramming.wikispaces.com ... ing+Factor).

--Jon

Branching factor is probably poor......it can take anything from 3 to 10 times longer to search the next ply, depending on the position.
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 ?

Laurie

[Dann Corbit]

Those are all good questions.

But behind the questions I think is this assumption: if you are getting 8 ply in 60 seconds on modern hardware very likely the problem is not the speed of the code but the algorithm. I suspect your branching factor is terrible (see https://chessprogramming.wikispaces.com ... ing+Factor).

--Jon

Branching factor is probably poor......it can take anything from 3 to 10 times longer to search the next ply, depending on the position.
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 ?

Laurie

The extremely small branching factors are due to:
1. Clever null move pruning (look at Stockfish code, for example).
2. Aggressive pruning algorithms like LMR (see https://chessprogramming.wikispaces.com/Reductions)
3. Other extreme pruning ideas (E.g. see Strelka listing in this link: https://chessprogramming.wikispaces.com/Razoring)

In order to prune well you will need very good move ordering. If you have bad move ordering, the fundamental technique of NULL MOVE pruning will give much less than SQRT(nodes) improvement. If your fail high on the pv node is less than 90%, then look into that.
(See https://chessprogramming.wikispaces.com/Move+Ordering)

[tttony]

Can you compile your program? and upload it?

Want to test it but my RAD studio does not like old pascal source and it wont let me compile because of the files dos and crt

[hgm]

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.

[lauriet]

Ill put a linux executable in the download on the web page.
Watch that space.



Laurie

[AndrewGrant]

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?

[hgm]

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.

[Sven]

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.

[Guenther]

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/

Guenther

[AndrewGrant]

Well if you take a look at uci.cpp you'll notice my abhorrent lack of UCI implementations. Aside from that, I am also searching for a new name for the engine because Ethereal is VERY bad for two reasons. 1) Because EtherealChess is already around, and 2) Ethereal makes people think of WireShark before it was WireShark.

I will release it as soon as I find a new name and figure out what I need to do to meet UCI standards. As of now, all my engine does is play 40/4 games with zero settings.

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."