Transposition Table and upper bounds

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
3 answers Last reply
More about transposition table upper bounds
  1. 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
  2. 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
  3. 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
Ask a new question

Read More

PC gaming Computers Video Games