Page 1 of 2

which technic next to implement?

Posted: Wed Mar 30, 2011 7:02 pm
by smatovic
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

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 8:18 pm
by Gian-Carlo Pascutto
SEE pruning in qsearch?

If you still don't get more depth after that, spend a month fixing all bugs.

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 9:19 pm
by Dann Corbit
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
What is your branching factor?

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

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 9:44 pm
by smatovic
What is your branching factor?
4x-6x

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
You don't have null move?
No, not yet ;)
If that is missing, you will not search deeply.
It will add 2-3 plies to your searches.
Nice, that sounds like an good aim for the next weekends :)
If you are nervous about zugzwang detection you can either use Omid's verified null move technique or Vincent's double null move idea.
Thanks for the hints, i guess that is what i was looking for.

--
Srdja

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 9:53 pm
by Dann Corbit
smatovic wrote:
What is your branching factor?
4x-6x

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
You don't have null move?
No, not yet ;)
If that is missing, you will not search deeply.
It will add 2-3 plies to your searches.
Nice, that sounds like an good aim for the next weekends :)
If you are nervous about zugzwang detection you can either use Omid's verified null move technique or Vincent's double null move idea.
Thanks for the hints, i guess that is what i was looking for.

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

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.

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 10:14 pm
by smatovic
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.
I would have to run more tests to calculate an real average branching factor...just took some snapshots of output.

--
Srdja

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 10:19 pm
by Dann Corbit
smatovic wrote:
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.
I would have to run more tests to calculate an real average branching factor...just took some snapshots of output.

--
Srdja
At any rate, we are seeing what we expect.
The amazing search rates of engines today are based upon clever pruning techiques. One of the most important is null move pruning.

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 10:23 pm
by bob
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
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)...

LMR by itself is worth about the same, but it is more complicated overall...

Re: which technic next to implement?

Posted: Wed Mar 30, 2011 10:36 pm
by smatovic
The amazing search rates of engines today are based upon clever pruning techiques. One of the most important is null move pruning.
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.

--
Srdja

Re: which technic next to implement?

Posted: Thu Mar 31, 2011 5:32 am
by Gian-Carlo Pascutto
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.
Do you store and retrieve the best move from hash?

What exactly did not work about aspiration windows?