Transposition Table and upper bounds

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

The transposition table normally stores (in addition to other things) a
'best move found' and an indentifier indicating whether the entry is an
upper bound, lower bound, or an exact score.

When I am ordering moves, I use the move found in the TT first. It
seems, though, that in the case of upper bounds, the move stored isn't
very good and actually slows down the search by trying it first. Does
anyone know: is the 'best move found' on upper bounds not useful? Or
does this indicate that I have some other bug?

Thanks!
-Greg

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

MageOfMaple@gmail.com writes:

> When I am ordering moves, I use the move found in the TT first. It
> seems, though, that in the case of upper bounds, the move stored isn't
> very good and actually slows down the search by trying it first. Does
> anyone know: is the 'best move found' on upper bounds not useful?

At nodes where the search fails low, it makes no sense to talk about
the 'best move found'. The only thing you know is that no move is
good enough to produce a score bigger than alpha. There is no way to
guess which move is best.

In other words, the behaviour you observe is exactly what you should
expect to see. You shouldn't store a move in the hash table except
for lower bounds and exact scores.

> Or does this indicate that I have some other bug?

Not at all.

--
Tord Romstad

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

* Tord Kallqvist Romstad <romstad@math.uio.no> (2005-09-21) schrieb:

> MageOfMaple@gmail.com writes:
>
>> When I am ordering moves, I use the move found in the TT first. It
>> seems, though, that in the case of upper bounds, the move stored isn't
>> very good and actually slows down the search by trying it first. Does
>> anyone know: is the 'best move found' on upper bounds not useful?
>
> At nodes where the search fails low, it makes no sense to talk about
> the 'best move found'. The only thing you know is that no move is
> good enough to produce a score bigger than alpha. There is no way to
> guess which move is best.

Well, no move being better than alpha does not mean there is nor best
move.

When I iterate through all the moves I always try to update a maximum
value initialized with -INFINTE. I also try to maximize alpha of course.

> In other words, the behaviour you observe is exactly what you should
> expect to see. You shouldn't store a move in the hash table except
> for lower bounds and exact scores.

On other values of alpha and beta this position might as well have an
exact value or fail high. And it is always better to try the best move
first, because if alpha can be increased the best move will increase it
most, yielding a smaller search window for further searches.

And if alpha can't be increased, i.e. on fail low, the order of moves
search simply doesn't matter.

mfg, simon .... l

 

[Guest]

Archived from groups: rec.games.chess.computer (More info?)

Simon Krahnke <overlord@gmx.li> writes:

> * Tord Kallqvist Romstad <romstad@math.uio.no> (2005-09-21) schrieb:
>
> > At nodes where the search fails low, it makes no sense to talk about
> > the 'best move found'. The only thing you know is that no move is
> > good enough to produce a score bigger than alpha. There is no way to
> > guess which move is best.
>
> Well, no move being better than alpha does not mean there is nor best
> move.
>
> When I iterate through all the moves I always try to update a maximum
> value initialized with -INFINTE.

I suppose you mean something like this:

int search(int alpha, int beta, int depth) {
move_t move, best_move;
int value, best_value;

if(depth == 0) return qsearch(alpha, beta);

best_value = -INFINITE;
while((move = pick_move()) && alpha < beta) {
make_move(move);
value = -search(-beta, -alpha, depth - 1);
unmake_move(move);
if(value > best_value) {
best_value = value;
best_move = move;
if(value > alpha) alpha = value;
}
}
return best_value;
}

However, as long as best_value remains below alpha, you have no idea
which moves are better than other moves. The values returned for each
move is nothing more than an _upper bound_ for the true value of that
move. If best_value is less than or equal to alpha at the end of the
move loop, it is perfectly possible that best_move is actually the
_worst_ of all moves at this node. Storing best_move in the
transposition table in this case is highly dubious, and will most
likely hurt your move ordering.

At nodes where you get a beta cutoff, you also cannot be sure that
best_move is really the best move, but at least you know that it is
better than all the other moves which were actually searched. The
only case in which you really know the best move is at nodes with an
exact score, i.e. when alpha < best_value < beta at the end of the
move loop.

--
Tord Romstad