Extensions/Reductions

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Extensions/Reductions

Post by metax » Mon Sep 28, 2009 2:29 pm

The only extensions I have implemented in my engine right now are check extensions and singular move extensions (which should be insignificant because they do not take away much performance). I experimented with recapture extensions, but they seemed to decrease the performance a lot while not really providing a strength increase. I allow up to 8 extensions in a subtree.

Currently I do not have any reductions.

The question is whether this makes sense because according to many statements I read, too much extensions take much performance but do not increase playing strength.
Reductions make the search tree smaller but I think it is dangerous to reduce the wrong moves.

What is the best compromise in your opinion?

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

Re: Extensions/Reductions

Post by bob » Mon Sep 28, 2009 5:27 pm

metax wrote:The only extensions I have implemented in my engine right now are check extensions and singular move extensions (which should be insignificant because they do not take away much performance). I experimented with recapture extensions, but they seemed to decrease the performance a lot while not really providing a strength increase. I allow up to 8 extensions in a subtree.

Currently I do not have any reductions.

The question is whether this makes sense because according to many statements I read, too much extensions take much performance but do not increase playing strength.
Reductions make the search tree smaller but I think it is dangerous to reduce the wrong moves.

What is the best compromise in your opinion?
This is an easy one. Extend the moves that lead to unclear positions so that the search can clear them up and give the static evaluation a position to evaluate that has no dynamic considerations that make this a difficult task. Reduce the moves that lead to uninteresting positions that will not affect the final search result.

:)

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Extensions/Reductions

Post by metax » Mon Sep 28, 2009 6:02 pm

bob wrote:This is an easy one. Extend the moves that lead to unclear positions so that the search can clear them up and give the static evaluation a position to evaluate that has no dynamic considerations that make this a difficult task. Reduce the moves that lead to uninteresting positions that will not affect the final search result.

:)
That seems to be pretty obvious. But

- what would you say if you had to give a brief description of positions which have dynamic considerations?
- how would you define uninteresting positions? You could take positions with a very big material difference which are unlikely to become balanced - but what if there is a sacrifice leading to material win or even to mate?

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

Re: Extensions/Reductions

Post by bob » Mon Sep 28, 2009 7:27 pm

metax wrote:
bob wrote:This is an easy one. Extend the moves that lead to unclear positions so that the search can clear them up and give the static evaluation a position to evaluate that has no dynamic considerations that make this a difficult task. Reduce the moves that lead to uninteresting positions that will not affect the final search result.

:)
That seems to be pretty obvious. But

- what would you say if you had to give a brief description of positions which have dynamic considerations?
1. One side is in check.

2. one side has material hanging.

3. both sides have material hanging

4. one side has some sort of tactical threat (potential fork, skewer, etc.

5. both sides have a tactical threat

6. one side has a king that is dangerously exposed

7. both sides have an exposed king.

Etc. Some extensions are used to help. For example extend checks to resolve the attack/threat before doing the static evaluation. Ditto for pushing passed pawns. The q-search handles captures, although not very well. Etc.



- how would you define uninteresting positions? You could take positions with a very big material difference which are unlikely to become balanced - but what if there is a sacrifice leading to material win or even to mate?
1. way behind in material or the opponent is in an overwhelming position with too many tactical threats to consider playing into this position.

2. completely lost position (KP vs K but side with pawn can force a promotion based on simple endgame rules).

3. pointless moves. Such as Nb3-a1, where the king is castled at h1/g1 and retreating the knight is not necessary to save material.

As a human, we can categorize most moves as pointless and not even consider them. In a program, we can't do this with as much accuracy, so we reduce them instead of throwing them out completely.

adieguez

Re: Extensions/Reductions

Post by adieguez » Mon Sep 28, 2009 10:51 pm

metax wrote:.
Reductions make the search tree smaller but I think it is dangerous to reduce the wrong moves.
It doesn't seem dangerous at least for me. As I see it, don't reduce the hash move and killers, and then for the rest you can even reduce randomly and is hard to make the program weaker.

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

Re: Extensions/Reductions

Post by Dann Corbit » Mon Sep 28, 2009 11:01 pm

adieguez wrote:
metax wrote:.
Reductions make the search tree smaller but I think it is dangerous to reduce the wrong moves.
It doesn't seem dangerous at least for me. As I see it, don't reduce the hash move and killers, and then for the rest you can even reduce randomly and is hard to make the program weaker.
You can make the program weaker if your reductions are inverted.
Imagine (for instance) if we reduce when an exchange shows a huge loss, since other alternatives are probably better. But if we goofed up the color, we may trim the opposite moves of those that we wanted to trim (e.g. we trim the good exchanges instead). Then this will make our program weaker, I am almost sure.

I guess that random reductions will have very little effect, but inverted reductions will have a bad one.

adieguez

Re: Extensions/Reductions

Post by adieguez » Mon Sep 28, 2009 11:08 pm

I have an even better attemp, reduce by increments of 5 ply :)
Dann Corbit wrote:
adieguez wrote:
metax wrote:.
Reductions make the search tree smaller but I think it is dangerous to reduce the wrong moves.
It doesn't seem dangerous at least for me. As I see it, don't reduce the hash move and killers, and then for the rest you can even reduce randomly and is hard to make the program weaker.
You can make the program weaker if your reductions are inverted.
Imagine (for instance) if we reduce when an exchange shows a huge loss, since other alternatives are probably better. But if we goofed up the color, we may trim the opposite moves of those that we wanted to trim (e.g. we trim the good exchanges instead). Then this will make our program weaker, I am almost sure.

I guess that random reductions will have very little effect, but inverted reductions will have a bad one.

User avatar
Eelco de Groot
Posts: 4245
Joined: Sun Mar 12, 2006 1:40 am
Location: Groningen

Re: Extensions/Reductions

Post by Eelco de Groot » Tue Sep 29, 2009 12:51 am

adieguez wrote:I have an even better attemp, reduce by increments of 5 ply :)
If you allow consecutive nullmove reductions with an Reduction factor of five plies, you do that all the time. I still think this is possible, Ancalagon does this, that is whenever a searchdepth of at least ten is reached which is not that often. Maybe Rybka does this too, at least in null window searches. But it makes Zugzwang positions a bit hard 8-)

Eelco
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan

adieguez

Re: Extensions/Reductions

Post by adieguez » Tue Sep 29, 2009 1:07 am

Eelco de Groot wrote:
adieguez wrote:I have an even better attemp, reduce by increments of 5 ply :)
If you allow consecutive nullmove reductions with an Reduction factor of five plies, you do that all the time. I still think this is possible, Ancalagon does this, that is whenever a searchdepth of at least ten is reached which is not that often. Maybe Rybka does this too, at least in null window searches. But it makes Zugzwang positions a bit hard 8-)

Eelco
Actually I have not yet tested any 5 ply reductions, maybe I should not have too much asumptions or else my proggy will never get near the top. Anyway, other requirement would be to fix amyan slowness. Do you know how fast amyan can be if I do a pure material eval? well, it is SLOWER yet than several other programs in their normal form. Maybe I will go bitboard, I am not sure. The wiki mentioned in another thread looks usefull.

metax
Posts: 344
Joined: Wed Sep 23, 2009 3:56 pm
Location: Germany

Re: Extensions/Reductions

Post by metax » Mon Oct 05, 2009 6:11 pm

I still have a dumb question... :)

If you extend a subtree because of check or anything else and you see that a reduction has been done before... do you extend two plies then? Probably not, but I just wanted to be sure...

Post Reply