Want to know what savings to expect with pruning methods...

[voyagerOne]

Bumped.

I am hoping somebody can answer my questions...

Just need some advice/pointers.

Thanks.

[John Major]

Right now my engine can reach up to ply 8 (not including Q search) in about 20 seconds on avg.

The only saving features I have is:
MVV/LVA move ordering and killer.

My question is does 8 ply at 20 seconds sound right? Is it too slow?

Sounds right

What type of savings can I expect with each?
Transposition Tables

good speedup

PV-Search Pruning

moderate

Null Move

good

Aspiration windowing

moderate

futility

moderate

also Late Move Reductions (LMR), depends, moderate to very good

What do you guys recommend I should do next now?

- null move, easy to get quick results
- LMR, also quick results, but can weaken your engine
- TT, difficult to get right, worth it
- PVS, easy
- futility, initially easy, I'd skip this
- Aspiration windowing, difficult to get right, I'd skip this
- last but not least evaluation. I would do this first, it makes your engine play chess.

Thanks in advance!

[Sven]

Right now my engine can reach up to ply 8 (not including Q search) in about 20 seconds on avg.

The only saving features I have is:
MVV/LVA move ordering and killer.

My question is does 8 ply at 20 seconds sound right? Is it too slow?

You have reported a raw speed of about 2.5 Mnps on your machine. That means, 20 seconds * 2.5 = 50 Mnodes in 8 plies. That seems to be a lot of nodes. Take Fruit 2.1, for instance, it needs much less than 100,000 nodes to complete iteration 8 from the initial position. Stockfish 2.1 needs less than 10,000. My own engine KnockOut needs about 130,000 nodes for 8 plies. I think 1 million might be o.k. but 50 million is most probably too much, i.e. your engine seems to search too many nodes to get the same result as other engines.

So one of the first points is to improve your move ordering, in order to get a lower effective branching factor. I would start to analyze your qsearch first, since that takes the biggest amount of nodes. How do you order moves in qsearch?

What type of savings can I expect with each?
Transposition Tables
PV-Search Pruning
Null Move
Aspiration windowing
futility

What do you guys recommend I should do next now?

Since you already have an iterative-deepening search you will get a significant initial benefit from implementing a transposition table. Here the biggest advantage usually comes from searching the hash table move first to improve move ordering, while the "transpositions" themselves are usually not so frequent (depending on the position, of course - many pawn endings are counter-examples).

"Null move" should give a significant boost, too, for your engine. The changes to implement null move pruning are more or less "local" while implementing a transposition table requires much more work (including debugging - a lot can go wrong here) and affects your program infrastructure. In an early stage of engine development I would do the "difficult" things first, to avoid complex changes in later stages, but that is clearly a matter of taste.

PVS is quite cheap to implement, and will slightly reduce the tree size in most cases compared to plain alpha-beta search. Whether you use aspiration windows together with PVS or don't use them is a design decision.

From the list you gave above, futility pruning would be the last one for me. Its implementation may also interact with your evaluation function due to the futility margins that depend on properties of the evaluation. Most probably it is far from being a "+200 ELO" improvement for your engine.

Btw, how does your evaluation function look like at the moment? Considering your high NPS I would assume it is a very simple eval only, like "material + PST". Improving the evaluation can sometimes also help to reduce the tree size, by finding refutations of positionally bad moves quicker. And it helps to let your engine play better chess, of course.

Good luck for your development!

Sven

[John Major]

What do you guys recommend I should do next now?

- null move, easy to get quick results
- LMR, also quick results, but can weaken your engine
- TT, difficult to get right, worth it
- PVS, easy
- futility, initially easy, I'd skip this
- Aspiration windowing, difficult to get right, I'd skip this
- last but not least evaluation. I would do this first, it makes your engine play chess.

I forgot to mention that LMR works best with a TT so that you have good move ordering with a hash move.

[voyagerOne]

Hi Sven,
Thanks for the informative feedback, I really appreciate it!

You have reported a raw speed of about 2.5 Mnps on your machine. That means, 20 seconds * 2.5 = 50 Mnodes in 8 plies. That seems to be a lot of nodes. Take Fruit 2.1, for instance, it needs much less than 100,000 nodes to complete iteration 8 from the initial position. Stockfish 2.1 needs less than 10,000. My own engine KnockOut needs about 130,000 nodes for 8 plies. I think 1 million might be o.k. but 50 million is most probably too much, i.e. your engine seems to search too many nodes to get the same result as other engines.

I believe you are implying that I have pruning features in my engine. The only pruning I have is alpha/beta. Correct me if I am wrong but I believe there is no way to get nodes below 100k at depth 8 just using alpha/beta and move ordering...otherwise I seriously did something wrong.

So one of the first points is to improve your move ordering, in order to get a lower effective branching factor. I would start to analyze your qsearch first, since that takes the biggest amount of nodes. How do you order moves in qsearch?

At the depth ply if there is a capture... my Qsearch will only look at all the captures on that particular square. I do not have check extension yet.

Btw, how does your evaluation function look like at the moment? Considering your high NPS I would assume it is a very simple eval only, like "material + PST". Improving the evaluation can sometimes also help to reduce the tree size, by finding refutations of positionally bad moves quicker. And it helps to let your engine play better chess, of course.

My evaluation has material +PST, mobility, isolated pawns, and king's pawn shelter.

[asanjuan]

50 Mnodes for 8 ply sounds too much for me. Maybe you are not counting the nodes very well. Maybe your conter++ is in the wrong place (only a suggestion).

I recently done some tests with my engine, and at the end, I had to rewrite the entire search, doing everything from the begining, starting with the plain alfa-beta.
In my case, i was searching some moves twice. So try to run perft tests to verify you are not searching more branches than what is needed.

This is what i found as good improvements in alfa-beta (apart of what you said):
- a correct quiescence search pruning bad captures (can use see<0 or a more simple routine to detect bad captures at one level. This is what i do.)
- killer moves for move ordering. Very good impact in nodes visited. the best i saw.
- history heuristic whith piece-to table. improves a bit your "killer" hits.
- Good implementation of transposition table. Is very easy to make a disastrous implementation of your TT and it isn't an evident test to ensure your code is ok. Btw, It is also very easy to build a good one.

If at this moment everyting is ok, try to change your alfa-beta to PVS or negascout, it worked very well for me.
If you have a working PVS, try futility. it helped me a lot.

After that i began to work with null move and lmr stuff.
I've done all this things, and given my slow engine, i surprisingly saw my engine reaching 90% at 1 second at WAC.
It was only a collateral effect of reducing the number of bugs.

Good luck with your engine.

[voyagerOne]

Thanks Alberto for your response. Are you able to give me any numbers?

What are your nodes at 8ply for just just alpha/beta and move ordering,history and killers...compared to when you added TT, null moves, and pvs.?

Thanks in advance!

[Sven]

You have reported a raw speed of about 2.5 Mnps on your machine. That means, 20 seconds * 2.5 = 50 Mnodes in 8 plies. That seems to be a lot of nodes. Take Fruit 2.1, for instance, it needs much less than 100,000 nodes to complete iteration 8 from the initial position. Stockfish 2.1 needs less than 10,000. My own engine KnockOut needs about 130,000 nodes for 8 plies. I think 1 million might be o.k. but 50 million is most probably too much, i.e. your engine seems to search too many nodes to get the same result as other engines.

I believe you are implying that I have pruning features in my engine. The only pruning I have is alpha/beta. Correct me if I am wrong but I believe there is no way to get nodes below 100k at depth 8 just using alpha/beta and move ordering...otherwise I seriously did something wrong.

Not below 100k but far below 50M. I think you might be able to reach <2Mnodes for 8 plies (initial position) with all you have now, just with a better move ordering. And after adding TT + NullMove it should be possible to get far below 1Mnodes. (Of course it is not the goal to optimize an engine's behaviour especially for the initial position, it is just an example.)

For instance, reducing the effective branching factor from 8 to 5 would have the potential to reduce the tree size of an 8-ply search to (5/8) ^ (8-1) = 3.7% of the original size. 50Mnodes * 3.7% = 1.85Mnodes.

So one of the first points is to improve your move ordering, in order to get a lower effective branching factor. I would start to analyze your qsearch first, since that takes the biggest amount of nodes. How do you order moves in qsearch?

At the depth ply if there is a capture... my Qsearch will only look at all the captures on that particular square. I do not have check extension yet.

What I intended to ask was, in which order does your Qsearch look at all the captures? My experience has been that changing the move ordering in the quiescence search can have a very significant impact (positive or negative) on the overall tree size.

Sven

[voyagerOne]

Not below 100k but far below 50M. I think you might be able to reach <2Mnodes for 8 plies (initial position) with all you have now, just with a better move ordering.

You are pretty close...the node count of my engine is 2.7M.

By the way, I average around 8-10 seconds (mid-game) at depth 8. Not 20...I thought it was 20 for some reason.

What I intended to ask was, in which order does your Qsearch look at all the captures?

MVV/LVA.

Thanks for all your input Sven.

[smatovic]

What do you guys recommend I should do next now?

1) check perft results
http://chessprogramming.wikispaces.com/Perft+Results

I had some problems with CastleMoves/Rights and En Passant Moves.

2) Setup some test positions
http://chessprogramming.wikispaces.com/Test-Positions

For a quick look how good your improvements are.

3) TT-Tables

To get a PV-Move in a Iterative Deepening Framework,
to get a suggested best move in PVS,
as an option -> to update alphabeta bounds.

4) Iterative Deepening Framework

5) PVS

6) Null Move

7) LMR

--
Srdja