Page 1 of 1
Implementing pvs
Posted: Sun Jan 13, 2013 4:41 am
by CDaley11
I have a quick question about PVS implementation. Basically here's how I've been trying to implement it (I've turned off all other optimizations besides move ordering, and alpha-beta cutoffs in order to be sure that it is working)
Code: Select all
// Inside the evaluation function
for (EACH_MOVE) {
makeMove();
toggleTurn();
if ( IS_FIRST_MOVE ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
} else {
temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
if ( temp > alpha ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
}
}
toggleTurn();
unmakeMove();
// Check for alpha and beta cutoffs
// ....
}
But I've been getting some really weird results. It does significantly speed up my program, but now my program will sometimes play horrendous moves. Losing a queen to a pawn for example.
Re: Implementing pvs
Posted: Sun Jan 13, 2013 6:43 am
by lucasart
CDaley11 wrote:I have a quick question about PVS implementation. Basically here's how I've been trying to implement it (I've turned off all other optimizations besides move ordering, and alpha-beta cutoffs in order to be sure that it is working)
Code: Select all
// Inside the evaluation function
for (EACH_MOVE) {
makeMove();
toggleTurn();
if ( IS_FIRST_MOVE ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
} else {
temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
if ( temp > alpha ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
}
}
toggleTurn();
unmakeMove();
// Check for alpha and beta cutoffs
// ....
}
But I've been getting some really weird results. It does significantly speed up my program, but now my program will sometimes play horrendous moves. Losing a queen to a pawn for example.
No idea what else you're doing wrong, but your PVS implementation is correct. Now there are two things in your code comment that worry me:
- what do you mean by "inside the evaluation function" ? Surely you mean the *search* function ?
- what do you mean by "alpha and beta cutoffs" ? What is an "alpha cutoff" ?
Re: Implementing pvs
Posted: Sun Jan 13, 2013 6:55 am
by lucasart
lucasart wrote:CDaley11 wrote:I have a quick question about PVS implementation. Basically here's how I've been trying to implement it (I've turned off all other optimizations besides move ordering, and alpha-beta cutoffs in order to be sure that it is working)
Code: Select all
// Inside the evaluation function
for (EACH_MOVE) {
makeMove();
toggleTurn();
if ( IS_FIRST_MOVE ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
} else {
temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
if ( temp > alpha ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
}
}
toggleTurn();
unmakeMove();
// Check for alpha and beta cutoffs
// ....
}
But I've been getting some really weird results. It does significantly speed up my program, but now my program will sometimes play horrendous moves. Losing a queen to a pawn for example.
No idea what else you're doing wrong, but your PVS implementation is correct. Now there are two things in your code comment that worry me:
- what do you mean by "inside the evaluation function" ? Surely you mean the *search* function ?
- what do you mean by "alpha and beta cutoffs" ? What is an "alpha cutoff" ?
There is however, one important inefficiency in the above code. Not a bug, but an inefficiency.
- at non PV node, when searching a move that isn't the first one
- you do not fail low, as expected. So you do a re-search with the full window. But the full window *is* the zero window at non PV nodes. So you are wasting time by doing the same search twice.
A hacky way to fix your code is as follows:
Code: Select all
if ( IS_FIRST_MOVE ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
} else {
temp = -searchToDepth( depth - 1, -alpha - 1, -alpha );
if ( temp > alpha && temp < beta ) {
temp = -searchToDepth( depth - 1, -beta, -alpha );
}
}
"temp < beta" is a hack that ensures you don't do the re-search in the useless case where beta=alpha+1 (it ensures that beta > alpha+1 in order to re-search).
Re: Implementing pvs
Posted: Sun Jan 13, 2013 8:08 pm
by CDaley11
Thanks for your help and identifying some inefficient code. I found out that using a transposition table with the pvs was throwing it off, I think it's because my table doesn't distinguish between nodes that returned an exact evaluation and nodes that only produced a cutoff.