WAC positions and iterative deepening

[Sven]

...

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.

Does that mean you do the following: if your PV from previous iteration is e4 e5 Nf3 Nc6, for instance, and you arrive at a node where White's first move was not e4 but Black can also move e5 now, then you search e5 first, even though you are not "in the PV"? And similarly, if White and Black played something different from e4 e5 and now White can play Nf3, you search Nf3 first, even if Black has - for instance - a pawn on g4?

If that is the case then I propose that you think about it again. You are turning the PV moves into something like killer moves, so I am not sure, but it is possible that this leads to worse move ordering than not doing it this way.

Sven

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

Does that mean you do the following: if your PV from previous iteration is e4 e5 Nf3 Nc6, for instance, and you arrive at a node where White's first move was not e4 but Black can also move e5 now, then you search e5 first, even though you are not "in the PV"? And similarly, if White and Black played something different from e4 e5 and now White can play Nf3, you search Nf3 first, even if Black has - for instance - a pawn on g4?

If that is the case then I propose that you think about it again. You are turning the PV moves into something like killer moves, so I am not sure, but it is possible that this leads to worse move ordering than not doing it this way.

Sven

In the remark that I have bolded, are you not referring to move transposition? I don't see how I can do the sort of thing you describe without a hash table. That's something I'm working on, but I'm not there yet.

I'll try to describe. After each iteration, there is a PV. At the next iteration, that PV gets searched first. And at the PV node I still do a moveGen, and from the generated list I know that the PV move must be there a second time, so I do an if then to make sure the PV move doesn't get searched twice.

Anyways, I don't know if that is clear. Right now I'm in an intermediate phase, so I suppose I have more worok to do in order to justify the ID/PV code I have written. It wouldn't surprise me at all that it would make no sense to leave the code as is, it might be better not to do ID at all.

All I'm trying to do is convince my self that give this progress of the phase of the program, the results I reached are not unexpected.

Here's the current code that shows the ID loop and how PV is being searched first.

http://fchess.pastebin.com/f5d8a02f6

[Daniel Shawul]

Unless I misunderstood, this is what you said you do

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?

I looked at your code and it looks like you are not doing it properly. Here is your ID. I

Code: Select all

#
for&#40; iPly = 1; iPly <= maxPly; iPly++ ) &#123;
#
 
#
                eval = alphaBeta&#40; gs, 1, alpha, beta, iPly>1 ? true &#58; false );
#
        &#125;

And inside alpha_beta you have the below code. Note that the boolean variable is set to true only for the first iteration only (it is false for the rest). So now it is not surprizing at all ID is not working for you. You can check if you have a pv move from previous iteration at every ply on a PV node. For that you need a boolean which indicates you are on a pv node. If you use PVS that will be where alpha + 1 != beta.

Code: Select all

#
int alphaBeta( GameState gs, int ply, int alpha, int beta, boolean pvs ) {
#
 
#
        if( !think || (ply>iPly && !qs) ) return evaluate(gs);
#
        if( ply > iPly ) return qSearch( gs, 0, alpha, beta );
#
               
#
'''''''''''''
        if&#40; pvs && ply<iPly ) &#123;
#
       
#
                pvm = PV&#91;1&#93;&#91;ply&#93;;
#
                p0 = posn&#91;pvm & 63&#93;; p1 = posn&#91;&#40;pvm>>6&#41; & 63&#93;;
#
                gs1 = makeMove&#40; gs, pvm );
#
                count++;
#
               
#
                eval = -alphaBeta&#40; gs1, ply+1, -beta, -alpha, pvs );
#
               
#
                unmakeMove&#40; gs1, pvm, p0, p1 );
#
               
#
                if&#40; eval >= beta ) &#123;
#
                        if&#40; ply == 1 ) &#123;
#
                                PV&#91;1&#93;&#91;1&#93; = pvm;
#
                                for&#40; int j=2; j<=iPly; j++ ) &#123;
#
                                        PV&#91;1&#93;&#91;j&#93; = 0;
#
                                &#125;
#
                        &#125;
#
                        return beta;
#
                &#125;
#
                if&#40; eval > alpha ) &#123;
#
                        alpha = eval;
#
                        PV&#91;ply&#93;&#91;ply&#93; = pvm;
#
                        for&#40; int j=ply+1; j<=iPly; j++ ) &#123;
#
                                PV&#91;ply&#93;&#91;j&#93; = PV&#91;ply+1&#93;&#91;j&#93;;
#
                        &#125;
#
                &#125;
#
        &#125;
#
       
#
       
#
        moveGen&#40; gs, ply );

May I alos suggest that you generate the moves once, sort them, pick the better move and recurse to the next ply later. Because the way you are doing it, lot of code is duplicated.

Cheers

[Fguy64]

...

Note that the boolean variable is set to true only for the first iteration only (it is false for the rest). So now it is not surprizing at all ID is not working for you. You can check if you have a pv move from previous iteration at every ply on a PV node. For that you need a boolean which indicates you are on a pv node. If you use PVS that will be where alpha + 1 != beta.
...

uhh, I don't follow that remark at all. As I see it, it's the exact opposite. Why would I set the boolean to true for the first iteration only. Cause that is the only iteration for which there is not a previous PV.

The condition is iPly>1 ? true : false. That says send true for every iteration but the first one.

Am I missing your point?

[Daniel Shawul]

My mistake. It is difficult to go through someone else's code and spot a problem. I won't try it again You should make sure you search the pv first at every ply (which I am still confused whether you do it or not??). If you do not , all you do with the ID is waste time so it is not surprizing that it is slower. And you do not need a hash table for that.

[Fguy64]

My mistake. It is difficult to go through someone else's code and spot a problem. I won't try it again You should make sure you search the pv first at every ply (which I am still confused whether you do it or not??). If you do not , all you do with the ID is waste time so it is not surprizing that it is slower. And you do not need a hash table for that.

I appreciate your efforts, it helped. Yes reading someone else's code is not the easiest. Especially since following chess programming conventions is not something I'm known for.

Refer back to the alphaBeta code you quoted above That code deals with searching PV first at every ply. The line of code.

if( pvs && ply<iPly ) {

says that for every ply exept the last one there is a PV move to play, if ply == iPly that is the l;ast ply and we are essentially doing a 1-ply search on the final PV position. if ply > iPly the evaluate() or qSearch() is called.

[Sven]

Hi Fred,

it is nice that you publish part of your engine source code, not everyone does this.

Also, as you already know there are quite a lot of people in this forum who are willing to help others solving their programming issues.

To improve quality of these support activities I suggest that you think about offering your source code (the part you are willing to publish) in a different way: just put an archive of source files for download on your page, so it is a lot easier for us to browse through your code with our own favourite editor or development environment, even if we can't do a build.

Regarding the current version that you have published, I do not even see the ID code that successively calls alphaBeta for the root node, nor do I see your various class declarations. Maybe I missed something, I don't know. But incomplete code leads to incomplete support

EDIT: found the ID code, function getMove() at the very top . Nevertheless, I would like to see more to understand better.

Sven

[Fguy64]

Thanks Sven, I appreciate and welcome the assistance.

OK the complete source code is available at http://fchess.uuuq.com/fchess2/fchess2.zip This zip file contains two engine files. Engine.java is the version that includes iterative deepening and searching PV first. Engine.java.1 is the version that is not ID. PV is collected, but for display purposes only. The two engine classes differ in the methods getMove() and alphaBeta() that I linked to above.

I have also posted applets for the two versions.

http://fchess.uuuq.com/fchess2/fchess2.htm is the version without iterative deepening.
http://fchess.uuuq.com/fchess2/fchess2a.htm is the version with iterative deepening.

If you actually run the program, you will see there is a drop down list with various testing options. I have used test4, which is alphaBeta with material eval only and no qSearch. I use this option only to eliminate the effects of Q so that I can focus on what is happening in my alphaBeta search. What I do is fix the depth of the search to the minimum required to offer a clear solution, and compare time/leaf nodes.

Finally, I'll repeat that the issue is that for testing of WAC positions, most, but not all, of the positions take a little longer to solve using ID with PV searched first. In all cases the same PV is found for both versions.

5rk1/1ppb3p/p1pb4/6q1/3P1p1r/2P1R2P/PP1BQ1P1/5RKN w - - 0 1 Rg3, depth=6 is a position that is solved significantly quicker with ID, 2br2k1/2q3rn/p2NppQ1/2p1P3/Pp5R/4P3/1P3PPP/3R2K1 w - - 0 1 Rxh7 depth=10 is a position that is slower with ID.

hope that clarifies the situation. Let me know if I can offer more clarification

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

Anyways, I did a little more testing, and I found that when I fix the depth to be a couple of plies longer than that which is needed to solve the position, then the balance is shifted in favor of ID, which is as you suggested (I think).

[Daniel Shawul]

That is great. I never measured how much ID gives me interms of ELO but it always made sense to me with higher branching factor, and ofcourse for better time management. I plan to use different ID depth increments for endgame and may also for the last iteration when we have too little time to complete it.
regards,
Daniel