Heyho,
want to upgrade my little engine Zeta Dva, i am satisfied with the nps-speed, but the engine searches too many nodes so it reaches in Blitz only depth from 7 to 11.
I read some papers about Null Move and Futility Pruning, but they seem not to be very handy...i mean some kind of instable. Any hint?
What i got working is:
- ID Framework
- PVS-AlphaBeta with SEE ordering (maybe i will switch back to MVV-LVA)
- Qsearch
- Transposition/Hash tables
- Simple Tablebased Evaluation
I did not manage to get Aspiration Windows to work.
--
Srdja
which technic next to implement?
Moderators: hgm, Rebel, chrisw
-
- Posts: 2661
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: which technic next to implement?
SEE pruning in qsearch?
If you still don't get more depth after that, spend a month fixing all bugs.
If you still don't get more depth after that, spend a month fixing all bugs.
-
- Posts: 12542
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: which technic next to implement?
What is your branching factor?smatovic wrote:Heyho,
want to upgrade my little engine Zeta Dva, i am satisfied with the nps-speed, but the engine searches too many nodes so it reaches in Blitz only depth from 7 to 11.
I read some papers about Null Move and Futility Pruning, but they seem not to be very handy...i mean some kind of instable. Any hint?
What i got working is:
- ID Framework
- PVS-AlphaBeta with SEE ordering (maybe i will switch back to MVV-LVA)
- Qsearch
- Transposition/Hash tables
- Simple Tablebased Evaluation
I did not manage to get Aspiration Windows to work.
--
Srdja
You don't have null move? If that is missing, you will not search deeply.
It will add 2-3 plies to your searches.
LMR will also increase the depth you can achieve.
Do null move first.
If you are nervous about zugzwang detection you can either use Omid's verified null move technique or Vincent's double null move idea.
See:
http://chessprogramming.wikispaces.com/ ... ve+Pruning
-
- Posts: 2661
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: which technic next to implement?
4x-6xWhat is your branching factor?
7 +0.02 1.5M 0:01.71 a1d1
6 +0.01 240088 0:00.30 d5c6
5 +0.08 61094 0:00.04 d5c6
4 +0.02 10803 0:00.01 a1d1
3 +0.08 1795 0:00.00 a1d1
2 +0.10 342 0:00.00 a1d1
1 +0.20 90 0:00.00 a1d1
No, not yetYou don't have null move?
Nice, that sounds like an good aim for the next weekendsIf that is missing, you will not search deeply.
It will add 2-3 plies to your searches.
Thanks for the hints, i guess that is what i was looking for.If you are nervous about zugzwang detection you can either use Omid's verified null move technique or Vincent's double null move idea.
--
Srdja
-
- Posts: 12542
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: which technic next to implement?
A branching factor of about 6 is what to expect from perfectly ordered alpha-beta. If you don't have any reductions, it is an amazing thing to have a branch factor less than 6 on average.smatovic wrote:4x-6xWhat is your branching factor?
7 +0.02 1.5M 0:01.71 a1d1
6 +0.01 240088 0:00.30 d5c6
5 +0.08 61094 0:00.04 d5c6
4 +0.02 10803 0:00.01 a1d1
3 +0.08 1795 0:00.00 a1d1
2 +0.10 342 0:00.00 a1d1
1 +0.20 90 0:00.00 a1d1
No, not yetYou don't have null move?
Nice, that sounds like an good aim for the next weekendsIf that is missing, you will not search deeply.
It will add 2-3 plies to your searches.
Thanks for the hints, i guess that is what i was looking for.If you are nervous about zugzwang detection you can either use Omid's verified null move technique or Vincent's double null move idea.
--
Srdja
Alpha beta (if perfectly ordered) gives you a search proportional to the square root of the nodes of pure mini-max which is about 36 to 38, depending on who you ask.
-
- Posts: 2661
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: which technic next to implement?
I would have to run more tests to calculate an real average branching factor...just took some snapshots of output.A branching factor of about 6 is what to expect from perfectly ordered alpha-beta. If you don't have any reductions, it is an amazing thing to have a branch factor less than 6 on average.
--
Srdja
-
- Posts: 12542
- Joined: Wed Mar 08, 2006 8:57 pm
- Location: Redmond, WA USA
Re: which technic next to implement?
At any rate, we are seeing what we expect.smatovic wrote:I would have to run more tests to calculate an real average branching factor...just took some snapshots of output.A branching factor of about 6 is what to expect from perfectly ordered alpha-beta. If you don't have any reductions, it is an amazing thing to have a branch factor less than 6 on average.
--
Srdja
The amazing search rates of engines today are based upon clever pruning techiques. One of the most important is null move pruning.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: which technic next to implement?
null-move is not much code. You can do this in 10-20-30 lines depending on how you implement it. It will result in a significant gain in depth, and maybe +100 Elo (or more, depending on engine maturity)...smatovic wrote:Heyho,
want to upgrade my little engine Zeta Dva, i am satisfied with the nps-speed, but the engine searches too many nodes so it reaches in Blitz only depth from 7 to 11.
I read some papers about Null Move and Futility Pruning, but they seem not to be very handy...i mean some kind of instable. Any hint?
What i got working is:
- ID Framework
- PVS-AlphaBeta with SEE ordering (maybe i will switch back to MVV-LVA)
- Qsearch
- Transposition/Hash tables
- Simple Tablebased Evaluation
I did not manage to get Aspiration Windows to work.
--
Srdja
LMR by itself is worth about the same, but it is more complicated overall...
-
- Posts: 2661
- Joined: Wed Mar 10, 2010 10:18 pm
- Location: Hamburg, Germany
- Full name: Srdja Matovic
Re: which technic next to implement?
hmm, and i guess thats the border where the real "magic" begins and mathematical correctness of algorithms is not so important anymore...i have read that every pruning technique has to "cooperate" with the others, like an concert with many musicians.The amazing search rates of engines today are based upon clever pruning techiques. One of the most important is null move pruning.
--
Srdja
-
- Posts: 1243
- Joined: Sat Dec 13, 2008 7:00 pm
Re: which technic next to implement?
Do you store and retrieve the best move from hash?smatovic wrote: - PVS-AlphaBeta with SEE ordering (maybe i will switch back to MVV-LVA)
[...]
- Transposition/Hash tables
I did not manage to get Aspiration Windows to work.
What exactly did not work about aspiration windows?