Когда альфа-бета-поиск с памятью возвращает значения отсечки?

Я реализовал альфа-бета-поиск с таблицей транспонирования.

Есть ли у меня правильные идеи о хранении отсечек в таблице?

В частности, правильна ли моя схема возврата отсечений при попадании в таблицу? (И, соответственно, их сохранения.) Моя реализация, похоже, конфликтует с этот, но интуитивно он кажется мне правильным.

Кроме того, мой алгоритм никогда не сохраняет запись с флагом at_most. Когда мне следует сохранять эти записи?

Вот мой (упрощенный) код, демонстрирующий основные идеи:

int ab(board *b, int alpha, int beta, int ply) {
    evaluation *stored = tt_get(b);
    if (entryExists(stored) && stored->depth >= ply) {
        if (stored->type == at_least) { // lower-bound
            if (stored->score >= beta) return beta;
        } else if (stored->type == at_most) { // upper bound
            if (stored->score <= alpha) return alpha;
        } else { // exact
            if (stored->score >= beta) return beta; // respect fail-hard cutoff
            if (stored->score < alpha) return alpha; // alpha cutoff
            return stored->score;
        }
    }   

    if (ply == 0) return quiesce(b, alpha, beta, ply);

    int num_children = 0;
    move chosen_move = no_move;
    move *moves = board_moves(b, &num_children);

    int localbest = NEG_INFINITY;
    for (int i = 0; i < num_children; i++) {
        apply(b, moves[i]);
        int score = -ab(b, -beta, -alpha, ply - 1);
        unapply(b, moves[i]);
        if (score >= beta) {
            tt_put(b, (evaluation){moves[i], score, at_least, ply});
            return beta; // fail-hard
        }
        if (score >= localbest) {
            localbest = score;
            chosen_move = moves[i];
            if (score > alpha) alpha = score;
        }
    }
    tt_put(b, (evaluation){chosen_move, alpha, exact, ply});
    return alpha;
}

artificial-intelligence algorithm chess minimax alpha-beta-pruning
person dylhunn    schedule 16.06.2016    source источник
comment
Я думаю, что это ошибка - не очень хороший вопрос. Вам необходимо предоставить минимальный воспроизводимый пример   -  person Idos    schedule 17.06.2016
comment
@Idos Достаточно честно. Я отредактировал вопрос - у меня нет конкретной проблемы, но я хочу проверить, правильно ли я понимаю этот сложный алгоритм.   -  person dylhunn    schedule 17.06.2016
comment
Тоже здесь не уместно. Оно очень расплывчато и широко. Если у вас на самом деле нет есть проблемы, на которую вы можете указать, то это не по теме, извините...   -  person Idos    schedule 17.06.2016
comment
@Idos Отредактировано снова с конкретным вопросом.   -  person dylhunn    schedule 17.06.2016

Ответы (1)


arrow_upward
2
arrow_downward

Моя реализация, кажется, конфликтует с этой

Код для поиска таблицы транспонирования кажется мне правильным. Примерно то же самое, что и в википедии.

// Code on Wikipedia rewritten using your notation / variable names
if (entryExists(stored) && stored->depth >= ply)
{
  if (stored->type == at_least)
    alpha = max(alpha, stored->score);
  else if (stored->type == at_most)
    beta = min(beta, stored->score);
  else if (stored->type == exact)
    return stored->score;

  if (alpha >= beta)
    return stored->score;
}

Это эквивалентно (проверка if (alpha >= beta) была перемещена внутри каждого типа узла):

if (entryExists(stored) && stored->depth >= ply)
{
  if (stored->type == at_least)
  {
    alpha = max(alpha, stored->score);
    if (alpha >= beta)  return stored->score;
  }
  else if (stored->type == at_most)
  {
    beta = min(beta, stored->score);
    if (alpha >= beta)  return stored->score;
  }
  else if (stored->type == exact)
    return stored->score;
}

и это можно изменить в:

if (entryExists(stored) && stored->depth >= ply)
{
  if (stored->type == at_least)
  {
    // if (max(alpha, stored->score) >= beta) ...
    if (stored->score >= beta)  return stored->score;
  }
  else if (stored->type == at_most)
  {
    // if (min(beta, stored->score) <= alpha) ...
    if (stored->score <= alpha)  return stored->score;
  }
  else if (stored->type == exact)
    return stored->score;
}

Оставшееся отличие заключается в том, что Википедия использует оптимизацию fail-soft, в то время как ваш код представляет собой классическую альфа-версию. бета-обрезка (fail-hard). Fail-soft — это небольшое улучшение, но оно не меняет ключевых моментов алгоритмов.

мой алгоритм никогда не сохраняет запись с флагом at_most. Когда я должен хранить эти записи?

Существует ошибка в том, как вы храните тип узла exact/at_most. Здесь вы предполагаете, что узел всегда имеет тип exact:

tt_put(b, (evaluation){chosen_move, alpha, exact, ply});

на самом деле это может быть узел at_most:

if (alpha <= initial_alpha)
{
  // Here we haven't a best move.
  tt_put(b, (evaluation){no_move, initial_alpha, at_most, ply});
}
else
   tt_put(b, (evaluation){chosen_move, alpha, exact, ply});
person manlio    schedule 30.06.2016