Move ordering help

[Sven]

Also, if I add PVS

Code: Select all

        val = -alphabeta(-alpha-1, -alpha, depth-1+ext, true, check);
        if (&#40;val > alpha&#41; && &#40;val < beta&#41;)
        &#123;
            stats->pvsresearch++;
            val = -alphabeta&#40; -beta, -alpha, depth-1+ext, true, check&#41;;
        &#125;

Then the node count increases, rather than an expected decrease.
[...]
So the problem could well be the PVS implementation... sorry.

As far as I can see from your previous posts you are using fail-hard alpha-beta. So I am not sure whether your re-search condition "val > alpha && val < beta" is correct, IMO it should be "val > alpha" only. But it is possible that this is only redundant code since "val > alpha" after null-window search should mean "val == alpha+1".

Sven

[Sven]

Also, if I add PVS

Code: Select all

        val = -alphabeta(-alpha-1, -alpha, depth-1+ext, true, check);
        if (&#40;val > alpha&#41; && &#40;val < beta&#41;)
        &#123;
            stats->pvsresearch++;
            val = -alphabeta&#40; -beta, -alpha, depth-1+ext, true, check&#41;;
        &#125;

Then the node count increases, rather than an expected decrease.
[...]
So the problem could well be the PVS implementation... sorry.

As far as I can see from your previous posts you are using fail-hard alpha-beta. So I am not sure whether your re-search condition "val > alpha && val < beta" is correct, IMO it should be "val > alpha" only. But it is possible that this is only redundant code since "val > alpha" after null-window search should mean "val == alpha+1".

Sven

I think the "&& val < beta" is OK, sorry for confusing you. There was a discussion last year where that has been asked already, see the "PVS" thread in this forum that just popped up again today.

Sven

[Sven]

Also, if I add PVS

Code: Select all

    int played=0;

    for&#40;uint i = 0; i < mlist.getcount&#40;game.getply&#40;)); ++i&#41;
    &#123;
        picknext&#40;i,mlist&#41;;

        if &#40;makemove&#40;game,mat,his,list&#91;i&#93;))
        &#123;
            takemove&#40;game,mat,his&#41;;
            continue;
        &#125;

        check = incheck&#40;game,mat,game.getside&#40;));
        ext = 0;
        if&#40;check&#41;
        &#123;
            stats->checkext++;
            ext = 1;
        &#125;

        if &#40;played==0 && opt->pvs&#41;
        &#123;
            stats->pvssearch++;
            val = -alphabeta&#40;-alpha-1, -alpha, depth-1+ext, true, check&#41;;
            if (&#40;val > alpha&#41; && &#40;val < beta&#41;)
            &#123;
                stats->pvsresearch++;
                val = -alphabeta&#40; -beta, -alpha, depth-1+ext, true, check&#41;;
            &#125;
        &#125;

        takemove&#40;game,mat,his&#41;;
        if&#40;status->stopped == STOPPED&#41;
        &#123;
            return 0;
        &#125;

        played++;

        from = FROM&#40;list&#91;i&#93;);

        if &#40;val > alpha&#41;
        &#123;
            // ..etc

This PVS implementation is flawed IMO. You do a zero-width search and possibly a re-search if played == 0, i.e. for the first move? That does not make sense for me. Can you explain whether this is a bug or a feature?

And what about your search for played > 0, then?

Sven

[Richard Allbert]

Hi Sven,

Thanks for the move ordering tips... I'll try them out.

Regarding PVS.. you are correct, but I seem to have deleted a couple of lines by mistake, when editing some other things out.

Code: Select all

if (opt->pvs)
     {
        if( played == 0)
        {
         val = -alphabeta( -beta, -alpha, depth-1+ext, true, check);
        }
        else
        {
         val = -alphabeta(-alpha-1, -alpha, depth-1+ext, true, check);
         stats->pvssearch++;
         if (val > alpha)
         {
            stats->pvsresearch++;
            val = -alphabeta( -beta, -alpha, depth-1+ext, true, check);
         }
        }
     }
     else
     {
       val = -alphabeta( -beta, -alpha, depth-1+ext, true, check);
     }

     takemove(game,mat,his);
     if(status->stopped == STOPPED) { return 0;}

     played++;

Sorry.

Anyhow, I was looking at the PVS, and thinking... I should really do root move ordering for this to have a positive effect, shouldn't I?

Thanks

Richard[/code]

[Sven]

Regarding PVS.. you are correct, but I seem to have deleted a couple of lines by mistake, when editing some other things out.

Looks better now

Sven

[Harald]

Quick side topic. Do you still have your chess program available for Atari ST ? If so I wouldn't mind checking it out.

I can offer the source and TOS Program of my first chess program
"HLSchach" on the Atari ST. This program was never publicly released
for a good reason. It looked nice but was extremely slow. In a few minutes
it could only reach ply 4 to 6. The move ordering for the alpha beta
algorithm was just awful. The language of the program is C. I can not
promise that the last version I found in my "old Atari" folder works
without problems.

Send me an email address to get it (400kB zip).

Harald