WAC positions and iterative deepening

[Fguy64]

OK, with my vanilla alphaBeta engine I have been testing WAC positions at a fixed depth ( no ID ) and qSearch turned off. What I do is find the minimum search depth that provides a correct solution

Then I test again using iterative deepening and searching PV first. Still no qSearch. And still fixed depth, no time control.

Primitive and unscientific I know, but that's the way it is for now. What I find more often than not is no improvement at all, in fact it is a little slower. Intuitively this doesn't seem out of line, as one would expect with tactical problems that PV is likely to change significantly as the search deepens, thus negating the advantage of iterative deepening.

Make sense?

[Aleks Peshkov]

No sense to explore chess game tree search without quiescence search.

[bob]

OK, with my vanilla alphaBeta engine I have been testing WAC positions at a fixed depth ( no ID ) and qSearch turned off. What I do is find the minimum search depth that provides a correct solution

Then I test again using iterative deepening and searching PV first. Still no qSearch. And still fixed depth, no time control.

Primitive and unscientific I know, but that's the way it is for now. What I find more often than not is no improvement at all, in fact it is a little slower. Intuitively this doesn't seem out of line, as one would expect with tactical problems that PV is likely to change significantly as the search deepens, thus negating the advantage of iterative deepening.

Make sense?

Do you have a working hash implementation? Killers? All of that is important as the idea behind iterative deepening is to use an N ply search to provide better move ordering for the N+1 ply search.

BTW, why no q-search? That is a very small amount of code to add and will greatly increase the accuracy of your search.

[Fguy64]

It's just a test of my alphaBeta. I have no HashTable Yet, I just want to make sure my ID is working as it should under the most basic of circumstances. I have qSearch in my program, I understand its benefits, it's just not a part of this test

[Fguy64]

I should add here that I am not complaining about the slowness. The issue is not what is the best way to do things, the issue is whether or not I should expect these results given what I have done. I am thinking yes, these results make sense, but I am not certain.

[jwes]

It's just a test of my alphaBeta. I have no HashTable Yet, I just want to make sure my ID is working as it should under the most basic of circumstances. I have qSearch in my program, I understand its benefits, it's just not a part of this test

You need some sort of memory of best moves, e.g. a hash table, before ID starts speeding up your search. The idea is that moves that cause cutoffs at one iteration should be tried first on the next iteration. To do this, you need to store the best move for many of the positions you search.

[Fguy64]

It's just a test of my alphaBeta. I have no HashTable Yet, I just want to make sure my ID is working as it should under the most basic of circumstances. I have qSearch in my program, I understand its benefits, it's just not a part of this test

You need some sort of memory of best moves, e.g. a hash table, before ID starts speeding up your search. The idea is that moves that cause cutoffs at one iteration should be tried first on the next iteration. To do this, you need to store the best move for many of the positions you search.

Well, I am collecting the principal variation from each iteration in a two dimensional array of moves, using the "triangular approach". And searching that PV first at the next iteration. Is that not what you are referring to?

It is my understanding that the benefit if ID and searching PV first comes from the hypothesis that a strong move in a n-ply search is probably a strong move in an n+1 ply search. But the rub is that when I am testing using tactical problems such as most of the WAC positions. Then PV is likely to change drastically later in the search, because of the tactical twist at the end of the combination. It is the "sting at the end of the scorpion's tail" effect which tends to negate a lot of the benefit of using ID. And i'd go further and suggest that whether use of a hash table has little effect on this particular aspect, that of the "point" of a combination appearing late in the search. PArticularly when the search is done at a fixed depth which is known to be just deep enough to "solve" the position.

OK I'm getting long winded here. Just trying to find out if my logic is valid

[Dann Corbit]

Iterative deepening is a big bonus if your move ordering is not very good. For instance, if you get a fail high on your first node only 80% of the time, then iterative deepening will give you a big speedup. If your move ordering is so good that you already get a fail high on your first move 95% of the time without iterative deepening, then you won't see much in the way of tangible benefits.

I have definitely seen programs for which iterative deepening gave improvements for WAC.

[jwes]

It's just a test of my alphaBeta. I have no HashTable Yet, I just want to make sure my ID is working as it should under the most basic of circumstances. I have qSearch in my program, I understand its benefits, it's just not a part of this test

You need some sort of memory of best moves, e.g. a hash table, before ID starts speeding up your search. The idea is that moves that cause cutoffs at one iteration should be tried first on the next iteration. To do this, you need to store the best move for many of the positions you search.

Well, I am collecting the principal variation from each iteration in a two dimensional array of moves, using the "triangular approach". And searching that PV first at the next iteration. Is that not what you are referring to?

It is my understanding that the benefit if ID and searching PV first comes from the hypothesis that a strong move in a n-ply search is probably a strong move in an n+1 ply search. But the rub is that when I am testing using tactical problems such as most of the WAC positions. Then PV is likely to change drastically later in the search, because of the tactical twist at the end of the combination. It is the "sting at the end of the scorpion's tail" effect which tends to negate a lot of the benefit of using ID. And i'd go further and suggest that whether use of a hash table has little effect on this particular aspect, that of the "point" of a combination appearing late in the search. PArticularly when the search is done at a fixed depth which is known to be just deep enough to "solve" the position.

OK I'm getting long winded here. Just trying to find out if my logic is valid

Searching the pv first does certainly help and probably not as much in tactical problems as in general positions, but it is only 10 or 20 positions while hash tables help in tens or hundreds of thousands of positions.

[Fguy64]

It's just a test of my alphaBeta. I have no HashTable Yet, I just want to make sure my ID is working as it should under the most basic of circumstances. I have qSearch in my program, I understand its benefits, it's just not a part of this test

You need some sort of memory of best moves, e.g. a hash table, before ID starts speeding up your search. The idea is that moves that cause cutoffs at one iteration should be tried first on the next iteration. To do this, you need to store the best move for many of the positions you search.

Well, I am collecting the principal variation from each iteration in a two dimensional array of moves, using the "triangular approach". And searching that PV first at the next iteration. Is that not what you are referring to?

It is my understanding that the benefit if ID and searching PV first comes from the hypothesis that a strong move in a n-ply search is probably a strong move in an n+1 ply search. But the rub is that when I am testing using tactical problems such as most of the WAC positions. Then PV is likely to change drastically later in the search, because of the tactical twist at the end of the combination. It is the "sting at the end of the scorpion's tail" effect which tends to negate a lot of the benefit of using ID. And i'd go further and suggest that whether use of a hash table has little effect on this particular aspect, that of the "point" of a combination appearing late in the search. PArticularly when the search is done at a fixed depth which is known to be just deep enough to "solve" the position.

OK I'm getting long winded here. Just trying to find out if my logic is valid

Searching the pv first does certainly help and probably not as much in tactical problems as in general positions, but it is only 10 or 20 positions while hash tables help in tens or hundreds of thousands of positions.

Thanks, that seems to at least lend some credence to what I was saying. I would like to clarify one point though. When you say that Hash tables help in many more thousands of positions, are you still talking about the move ordering aspect of ID and PV, or are you talking about transposition