which technic next to implement?

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
smatovic
Posts: 784
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

which technic next to implement?

Post by smatovic » Wed Mar 30, 2011 7:02 pm

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

Gian-Carlo Pascutto
Posts: 1138
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: which technic next to implement?

Post by Gian-Carlo Pascutto » Wed Mar 30, 2011 8:18 pm

SEE pruning in qsearch?

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

Dann Corbit
Posts: 9895
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: which technic next to implement?

Post by Dann Corbit » Wed Mar 30, 2011 9:19 pm

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

smatovic
Posts: 784
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: which technic next to implement?

Post by smatovic » Wed Mar 30, 2011 9:44 pm

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

Dann Corbit
Posts: 9895
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: which technic next to implement?

Post by Dann Corbit » Wed Mar 30, 2011 9:53 pm

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.

smatovic
Posts: 784
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: which technic next to implement?

Post by smatovic » Wed Mar 30, 2011 10:14 pm

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

Dann Corbit
Posts: 9895
Joined: Wed Mar 08, 2006 7:57 pm
Location: Redmond, WA USA
Contact:

Re: which technic next to implement?

Post by Dann Corbit » Wed Mar 30, 2011 10:19 pm

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.

bob
Posts: 20408
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: which technic next to implement?

Post by bob » Wed Mar 30, 2011 10:23 pm

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

smatovic
Posts: 784
Joined: Wed Mar 10, 2010 9:18 pm
Location: Hamburg, Germany
Full name: Srdja Matovic
Contact:

Re: which technic next to implement?

Post by smatovic » Wed Mar 30, 2011 10:36 pm

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

Gian-Carlo Pascutto
Posts: 1138
Joined: Sat Dec 13, 2008 6:00 pm
Contact:

Re: which technic next to implement?

Post by Gian-Carlo Pascutto » Thu Mar 31, 2011 5:32 am

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?

Post Reply