Improve my chess engine (mainly nps and branching factor)

[adityapande]

Hi all,

I recently wrote a chess engine ( https://github.com/pandeaditya/Conqueror ) and it plays well but in a 5 minute game per side it generally plays at depths 4 to 10, a queit depth of upto 10 moves (checks and captures included).
I have already implemented alphabeta pruning, legal move generator, quiescent search, dedicated move_gen() for checks, iterative deepening , MVV/LVA move ordering, c++ std based map transposition tables and null moves.
My program has a move_gen() which checks mates (check and stale) and insufficient material etc also. I have a mobility based evaluation function for which I take into account the number of legal moves available to a side to get the mobility score for a position.
I am getting a speed of upto 30 knps and about 80-85% of the nodes are quiet nodes ( i.e number of calls to QS() function / total calls to QS() or alphabeta() ).
Also I get around 1e5 to 3e5 total nodes at depth 6 in middle/endgame. Is it too much? Please suggest improvements to my design.
I am using bitvectors + piece coordinates hybrid board rep but no bit magic as of now.
I played it against many engines but most engines play at a higher depth than mine so my engine is at best able to draw with the likes of Hermann, Taktix, etc
Regards,
Aditya Pande[/url]

[ZirconiumX]

Hi all,

I recently wrote a chess engine (https://github.com/pandeaditya/Conqueror) and it plays well but in a 5 minute game per side it generally plays at depths 4 to 10, a queit depth of upto 10 moves (checks and captures included).
I have already implemented alphabeta pruning, legal move generator, quiescent search, dedicated move_gen() for checks, iterative deepening , MVV/LVA move ordering, c++ std based map transposition tables and null moves.
My program has a move_gen() which checks mates (check and stale) and insufficient material etc also. I have a mobility based evaluation function for which I take into account the number of legal moves available to a side to get the mobility score for a position.
I am getting a speed of upto 30 knps and about 80-85% of the nodes are quiet nodes ( i.e number of calls to QS() function / total calls to QS() or alphabeta() ).
Also I get around 1e5 to 3e5 total nodes at depth 6 in middle/endgame. Is it too much? Please suggest improvements to my design.
I am using bitvectors + piece coordinates hybrid board rep but no bit magic as of now.
I played it against many engines but most engines play at a higher depth than mine so my engine is at best able to draw with the likes of Hermann, Taktix, etc
Regards,
Aditya Pande

Late move reductions, and possibly futility pruning would be good next steps, IMHO.

Matthew:out

[adityapande]

Late move reductions, and possibly futility pruning would be good next steps, IMHO.

Matthew:out

I read about these 2 techniques but I find them very artificial depth gain as we are effectively searching depth-1 only in each case. At least the ideas seem to be a lot lossy...

[Henk]

Late move reductions, and possibly futility pruning would be good next steps, IMHO.

Matthew:out

I read about these 2 techniques but I find them very artificial depth gain as we are effectively searching depth-1 only in each case. At least the ideas seem to be a lot lossy...

Yes and if you reduce too much with LMR you get the "Best move almost never changes problem" or severe depth/ply inflation. I don't know the answer to your question. I would like to hear good answers too.

[adityapande]

Late move reductions, and possibly futility pruning would be good next steps, IMHO.

Matthew:out

I read about these 2 techniques but I find them very artificial depth gain as we are effectively searching depth-1 only in each case. At least the ideas seem to be a lot lossy...

Yes and if you reduce too much with LMR you get the "Best move almost never changes problem" or severe depth/ply inflation. I don't know the answer to your question. I would like to hear good answers too.

I have also faced the "Best move almost never changes problem" when I implemented Aspiration search with iterative deepening. It reduced the playing strength significantly and I had to take the aspiration search out. Maybe later I will be able to fix the bug arising due to setting of evaluation scores somewhere on repeated aspiration search (after falling out of window). It still strangely uses the old evaluation with the failing alpha, beta

[Henk]

But adding futility pruning/razoring and LMR will help a bit.

[ZirconiumX]

Late move reductions, and possibly futility pruning would be good next steps, IMHO.

Matthew:out

I read about these 2 techniques but I find them very artificial depth gain as we are effectively searching depth-1 only in each case. At least the ideas seem to be a lot lossy...

Not entirely sure what you mean.

LMR may be artificial, but it definitely works well. If a move is pointless, why waste time searching it to full depth?

Also, you haven't mentioned PVS, which is a definite must have.

Matthew:out

[Angrim]

The first thing that really stuck out from your description is that it sounds like you are generating fully legal moves. Most people don't bother checking if a move is into check until it is time to use it, they just make a list of mostly legal moves, and then before they go to actually evaluate each move they do a quick check to see if it was an illegal move or not. Then just skip the illegal moves. Since around half of all moves generated are pruned and never used, this can speed your search up a bit.
And in general, your search could use a lot more speed. With modern hardware it is easy to get 1mil nps on a single core, so something is seriously slow in your code to be getting 30k nps. I'd recommend looking into code profiling to find out where it is spending most of it's time.

[tpetzke]

Welcome at chess programming. If your engine is able to draw Hermann it is already quiet strong. Good job !

I read about these 2 techniques but I find them very artificial depth gain as we are effectively searching depth-1 only in each case. At least the ideas seem to be a lot lossy...

but they really work. Look, you also gain additional plies of search by reducing probably poor moves, so the reduction is relative considering the higher overall depth.

But LMR is a technique that I would recommend to implement later because it is risky if your move ordering is bad. The biggest gains come from improving move ordering. Measure how often you get a cutoff with the 1st move if there is a cutoff. You want that number to be at least 90%. If you are below that don't bother with anything else. First fix this.

If you don't have null move yet, you should look at it.

30.000 moves for depth 6 are ok for an early engine version. I looked at iCE 0.1 and it took 70.000 nodes to reach depth 6. If you move up the ladder this number will drop.

A speed of 30.000 nps seems really slow. Have you profiled your engine and looked where it spends its time. With any decent HW you should have at least 500k nps especially if your eval is not very complex already.

[Bloodbane]

"c++ std based map transposition tables"

That is probably slowing you down quite a bit since inserting stuff into a std::map is very slow. Most people(i.e. everyone) just new or malloc a part of memory just for the TT and avoid the overhead of std::map. CPW-Engine should have a perfectly good example on this.