WAC positions and iterative deepening

[Dann Corbit]

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

It helps both ways. The hash table will store positions already visited giving a speedup (saving both evaluations and search). Also, a hash table hit that is already a pv node will give good move ordering and also prevent the need to perform the plies-K search for that node.

Consider a search where you are doing 12 plies deep.
In the previous search, you already did 11 plies, so a lot of the work for ID (and / or IID) will already have been accomplished. Because you already searched the position deeply, your hash table is populated with "what worked best last time" which should be a very good guide for "what will work best this time".

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

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

Move ordering. Except in blocked positions or endgames, transpositions do not play that big a role.

[Daniel Shawul]

I think you should test at fixed time rather than fixed depth. I don't really see how you can compare at fixed depth. Both should get same answers, say at depth 12, if doing ID does not screw up the search somehow, which I don't think will happen. Besides, you need the ID for time management so it is a no brainer. May be you should try using larger values of depth increment for the ID but i doubt that will work unless your branching factor is so low. Infact , what seemed to work for me was doing the opposite (three quarters of a ply increment). But i am not sure if that is due to better time management , sheer luck or some bug i have

[Fguy64]

I think you should test at fixed time rather than fixed depth. I don't really see how you can compare at fixed depth. Both should get same answers, say at depth 12, if doing ID does not screw up the search somehow, which I don't think will happen. Besides, you need the ID for time management so it is a no brainer. May be you should try using larger values of depth increment for the ID but i doubt that will work unless your branching factor is so low. Infact , what seemed to work for me was doing the opposite (three quarters of a ply increment). But i am not sure if that is due to better time management , sheer luck or some bug i have

I sort of see your point, I don't disagreem, but really in one sense I think it's kind of a non-issue. My program is not advanced at all, and this is just one simple test out of many possible tests. I'm not surprised there are other tests that are more useful, It's just "fix the depth, and compare the times taken to search", and the two tests find the same solution, the same PV, but ID with PV first takes a little longer that straight up negamax/alphaBeta. And so far I haven't seen any reason why this should not be the case.

If anyone thinks my results are not what they should be, I'm all ears. The relevant code can be viewed here.

http://fchess.pastebin.com/f5d8a02f6

[Daniel Shawul]

"fix the depth, and compare the times taken to search"

I understand now. In that case I think you should try larger depth.WAC test suites are relatively easy. Time to solution depths could be in milli seconds for most WAC postions, so low ID could slow you down. ID is more effective for longer time/larger fixed depth. This should give a clear win for ID even though you don't use transposition tables for cutoffs.

[Fguy64]

"fix the depth, and compare the times taken to search"

I understand now. In that case I think you should try larger depth.WAC test suites are relatively easy. Time to solution depths could be in milli seconds for most WAC postions, so low ID could slow you down. ID is more effective for longer time/larger fixed depth. This should give a clear win for ID even though you don't use transposition tables for cutoffs.

Thanks, Good idea, I'll give it a try, till now I'm just fixing the depth to the minimum required to clearly identify the optimal move. But I guess there is no reason why I shouldn't make the comparison at a higher depth, just to see how the two methods differ.

I'm dying to get a hash table implemented, just can't get my head around it. I've read all the pages I can find, slowly it is coming, I'll get there eventually touch wood.

[Uri Blass]

"fix the depth, and compare the times taken to search"

I understand now. In that case I think you should try larger depth.WAC test suites are relatively easy. Time to solution depths could be in milli seconds for most WAC postions, so low ID could slow you down. ID is more effective for longer time/larger fixed depth. This should give a clear win for ID even though you don't use transposition tables for cutoffs.

I understand that he does not use tranposition tables not only for cutoff but also not for better order of moves.

I see no reason that ID should help to get the same depth faster with no hash tables.

The only reason that ID may help to get faster at the same depth is because it helps the program to get a better order of moves but if the program does not get better order of moves then it only cost time because the program needs to search at smaller depth and needs to do additional work for it.

The target of ID is not to search faster at fixed depth.
Even in case that ID cause the program to be slightly slower with the same depth
In games you do not know the depth that you can practically get and
searching to fixed depth can cause you to have one of the following problems:
1)searching to depth that is smaller than the depth that you can get with ID.
2)searching to depth that it is too big not to lose on time.

I can add that the commercial program Junior(at least Junior9) does not use ID when it searches at fixed depth and I believe that it is often faster relative to the case that it gets the same depth in a normal game and not in analysis.

Uri

[MattieShoes]

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

I looked into this a while ago, and I found the main advantage is with move ordering, though the number of actual transpositions in many positions is very non-trivial, particularly in the endgame.

[Daniel Shawul]

"fix the depth, and compare the times taken to search"

I understand now. In that case I think you should try larger depth.WAC test suites are relatively easy. Time to solution depths could be in milli seconds for most WAC postions, so low ID could slow you down. ID is more effective for longer time/larger fixed depth. This should give a clear win for ID even though you don't use transposition tables for cutoffs.

I understand that he does not use tranposition tables not only for cutoff but also not for better order of moves.

I see no reason that ID should help to get the same depth faster with no hash tables.

The only reason that ID may help to get faster at the same depth is because it helps the program to get a better order of moves but if the program does not get better order of moves then it only cost time because the program needs to search at smaller depth and needs to do additional work for it.

The target of ID is not to search faster at fixed depth.
Even in case that ID cause the program to be slightly slower with the same depth
In games you do not know the depth that you can practically get and
searching to fixed depth can cause you to have one of the following problems:
1)searching to depth that is smaller than the depth that you can get with ID.
2)searching to depth that it is too big not to lose on time.

I can add that the commercial program Junior(at least Junior9) does not use ID when it searches at fixed depth and I believe that it is often faster relative to the case that it gets the same depth in a normal game and not in analysis.

Uri

He uses the PV from previous search for move ordering at PV nodes.
I guess that is also what TSCP does and I belive it works fine, otherwise
its only benefit would be a better time management as you said.

Junior has a low branching factor and probably does some good root move ordering before
it begins non-ID search. For a TSCP like engine, BF is somwhere close to 6
so it takes almost 6x as long to complete one more iteration. That is with plain alpha-beta.
I guess that move ordering on _PV nodes _will have more effect with the addition of PVS.

[Fguy64]

...

He uses the PV from previous search for move ordering at PV nodes.

I guess that is also what TSCP does and I belive it works fine, otherwise
its only benefit would be a better time management as you said.

Junior has a low branching factor and probably does some good root move ordering before
it begins non-ID search. For a TSCP like engine, BF is somwhere close to 6
so it takes almost 6x as long to complete one more iteration. That is with plain alpha-beta.
I guess that move ordering on _PV nodes _will have more effect with the addition of PVS.

Are you talking about me? Do I really use the PV from the previous search for move ordering at a PV node? The way I see it, at any node, if there is a PV move from the previous iteration, it gets searched first, after which a normal moveGen with normal MVV/LVA move ordering is done at that node. In other words, I'm not saving the PV node moveGen from a previous iteration, although the thought has crossed my mind, it seems that requires a HashTable no?

regards.