PV extract from transposition table.

[Edsel Apostol]

Hi all,

I will be implementing a PV extracted from the transposition table. The

code seems to work but I'm not sure if it is correct. I will be posting it

here hoping that someone would point out the bugs in it or someone could

teach me a better implementation.

Code: Select all

void displaypv(int move, int w, int onmove, int depth){
    int x=0, c=onmove;
    static int pvt[MAXPLY];
    if(xboard) printf("%d %d %d %d ", depth, w, (gettime()-t1)/10, (int)nodes);
    else printf("%3d  %9d  %9d  %6d  %5d  ",depth,(int)(nodes-qnodes),(int)qnodes,(gettime()-t1),w);
    pvt[x]=move;
   while(TRUE){
        if(!domove(pvt[x++], c)){ pvt[--x]=0; break; };
        if(checkhash(&pvt[x], &w, 0) == EXACT){ c^=1; continue; }
        else{ pvt[x] = 0; break;}
    }
    while(x--){ undomove(c); c^=1;}
    for(x=0; pvt[x]; x++) printf("%s ", displaymove(pvt[x]));
    printf("\n");
    fflush(stdout);
}


Thanks in advance.

Edsel

[Volker Annuss]

Hi Edsel,

your while(TRUE) will run forever and there will be an overrun in pvt[x], when there is a repetition in your PV. So you must check for repetitions.

I wonder why the side to move is not updated in domove(). It is difficult for me to see, if it is updated correctly because it is flipped only after some conditions. The side to move must be part of the hash code. Is it?

Greetings,
Volker

[Edsel Apostol]

Hi Volker,

I wonder why the side to move is not updated in domove(). It is difficult for me to see, if it is updated correctly because it is flipped only after some conditions. The side to move must be part of the hash code. Is it?

I don't update my side to move in domove, instead I passed it in the domove routine as a parameter, that is why I flipped it every time the side to move changes. I will try to rewrite the entire program someday that would eliminate such bug-prone codes.

Anyway, thanks for pointing out to me the repetition bug, I have encountered it once before and I was wondering what was wrong with the code.

Do you have any suggestion for a much better implementation?

[smcracraft]

Hi all,

I will be implementing a PV extracted from the transposition table. The

code seems to work but I'm not sure if it is correct. I will be posting it

here hoping that someone would point out the bugs in it or someone could

teach me a better implementation.

Code: Select all

void displaypv(int move, int w, int onmove, int depth){
    int x=0, c=onmove;
    static int pvt[MAXPLY];
    if(xboard) printf("%d %d %d %d ", depth, w, (gettime()-t1)/10, (int)nodes);
    else printf("%3d  %9d  %9d  %6d  %5d  ",depth,(int)(nodes-qnodes),(int)qnodes,(gettime()-t1),w);
    pvt[x]=move;
   while(TRUE){
        if(!domove(pvt[x++], c)){ pvt[--x]=0; break; };
        if(checkhash(&pvt[x], &w, 0) == EXACT){ c^=1; continue; }
        else{ pvt[x] = 0; break;}
    }
    while(x--){ undomove(c); c^=1;}
    for(x=0; pvt[x]; x++) printf("%s ", displaymove(pvt[x]));
    printf("\n");
    fflush(stdout);
}


Thanks in advance.

Edsel

Hi - mine is:

movesinpv = 0;
while (retrieve(&length, &score, &flag, &hashmv, &threat)) {
if (legalmove2(bd,hashmv)) {
makemv(bd,hashmv);
movesinpv++;
if (movesinpv == 1) savebest(hashmv,score,SHOWMVNOTOK);
savemove(&pv[pvi],hashmv);
pvi++;
if (reps()==3) break;
} else break;
}

But a point - I do not use the hash table as the source for the storage
of my pv. For that, I use the triangular npv[][] array and then copy
over the npv[0][] to pv[0..n] so my pv is pv[0..n].

I maintain both the hash table but also the triangular array method.

The reason is that I never felt comfortable "walking the hash table"
for my pv - it struct me as dangerous and possibly inaccurate. While
the triangular array method is not perfect either, I do think it is
more reliable.

More detail for you here:

http://www.seanet.com/~brucemo/topics/pv.htm

What do you all think? I would suggest you a) try both b) pick the
one that gives the better result for your program specifically.

Stuart

[diepeveen]

Hi all,

I will be implementing a PV extracted from the transposition table. The

code seems to work but I'm not sure if it is correct. I will be posting it

here hoping that someone would point out the bugs in it or someone could

teach me a better implementation.
<snip>

Edsel, in general it's a good idea to let others fix your bugs.
Note that Diep is getting mainline out of hashtable too (except for
the first move which i have in a variable in the root, as i prefer to
take '0 risks' with that move, even if it is a risk of 1 in a trillion if
not less).

Vincent

[Edsel Apostol]

Hi all,

I have not implemented pv extract as I have posted here, instead I used

the one just like Fruit. The only reason I want to derive the pv from the

transposition table in the first place is that I want to display the principal

variation even if there is a cut-off from the transposition table in pv nodes.

I had overcome this problem by not letting a cut-off from the

transposition table in pv nodes, I just use the bestmove retrieved for

move ordering. It would search a little bit more nodes but I would not

have to device any more complex method to retrieve and display the full

pv. I have learned this idea from Glaurung and Fruit.

Edsel.

[smcracraft]

Hi all,

I have not implemented pv extract as I have posted here, instead I used

the one just like Fruit. The only reason I want to derive the pv from the

transposition table in the first place is that I want to display the principal

variation even if there is a cut-off from the transposition table in pv nodes.

I had overcome this problem by not letting a cut-off from the

transposition table in pv nodes, I just use the bestmove retrieved for

move ordering. It would search a little bit more nodes but I would not

have to device any more complex method to retrieve and display the full

pv. I have learned this idea from Glaurung and Fruit.

Edsel.

My program attempts to solve the issue of pv printouts this way.

When it comes time to printout the pv, I compare the backed-up
triangular array pv withe the pv from walking the hash table.

Since I know the evaluation backed up by the search, I compare
the final quiescence for the terminal node in each of the two
outcomes. If both are the same as the backed up one, then fine,
I pick the longer of the two pvs.

If one is the same and the other isn't, I pick the one that is the
same and print out its pv.

If the neither is the same, that is the real problem. In that case,
I take the longer one.

Certainly this points out a pathology in the search, whether it be
cutoff, or in hash, or in triangular array that may not be known at
present - so I chose the above to bandaid it.

In my program, I save the pv for use by the temporal difference
learning engine so I have to have something decent to use
for every move to be learned from.

Stuart

[smcracraft]

Another point I'd like to add was seen after the above post.

I had been having an engine-crashing bug for a long-time, cropping
up every N games. The cause was an intentional ASSERT that
if an unmove was made of a non-existant piece (the proverbial ghost),
the engine would exit.

This bug had been there for almost 1 1/2 years since the program's
inception in mid-2004.

Well, the problem turned out to be in the walk-the-pv show-the-pv
function. This function based on its mode-flag compares the pv
from the hash table with the pv from the triangular array and sees
the evaluation at the end of each and if it matches the evaluation
returned by search(). The one that matches is used as the pv. If
neither matches, the longer one is used.

In either case, that pv is stuffed into yet another location which is
then used by the search() to search the pv first at each ply.

The bug resulted from a routine called legalmove2() that determines
if the move retrieved from the hash table is legal in the current board
position. I had omitted a check that if the hash move did not include
a captured piece but there was piece at the to destination well, the
move would get made anyway.

The end result is that when unmaking, a ghost piece would be created
and the ASSERT would get triggered.

The fix was to include the above check.

I am still not happy with my showpv() pv-walker and having to
break ties between triangular pv arrays and walking the hash table
but weird things happen at cutoffs that I don't understand and it
affects the pv.

I save the pv for each move made on the physical board during the
game for use by the temporal difference learning engine and it does
result in good learning so the PV at least is accurate enough for that
which I think is more exacting than other typical uses of the PV other
than improving the search()'s efficiency by PV-searching first always.

Anyway, just thought I'd share that. Feels good to fix an old bug. I
am sure there are a lot more in my program.

Stuart