Как учесть историю позиции в таблицах транспонирования

В настоящее время я разрабатываю решатель для карточной игры на основе трюка под названием Skat в идеальной информационной ситуации. Хотя большинство людей могут не знать игру, пожалуйста, потерпите меня; моя проблема носит общий характер.

Краткое введение в Скат:
По сути, каждый игрок поочередно разыгрывает одну карту, и каждые три карты создают уловку. Каждая карта имеет определенную ценность. Счет, достигнутый игроком, является результатом сложения стоимости каждой карты, содержащейся в трюках, которые выиграл соответствующий игрок. Я пропустил некоторые вещи, которые не важны для моей проблемы, например, кто играет против кого или когда я выигрываю трюк.
Мы должны помнить, что есть текущий счет, и кто играл во что раньше, когда исследует определенную позицию (-> ее историю), имеет отношение к этому счету.

Я написал альфа-бета-алгоритм на Java, который, кажется, работает нормально, но он слишком медленный. Первое улучшение, которое кажется наиболее перспективным, - это использование таблицы транспозиции. Я читал, что при поиске дерева в игре Skat вы встретите множество позиций, которые уже были исследованы.
И вот тут возникает моя проблема: если я найду позицию, которая уже была исследована ранее, ходы, ведущие к этой позиции, были другими. При этом, в общем, оценка (и альфа, или бета) тоже будет другой.
Это приводит к моему вопросу: как я могу определить ценность позиции, если я знаю ценность той же позиции, но с другой историей?
Другими словами: как я могу отделить поддерево от его пути к корню, чтобы его можно было применить к новому пути?
Моим первым импульсом было то, что это просто невозможно, потому что на альфа или бета могли повлиять другие пути, которые могут быть неприменимы к текущей позиции, но...

Кажется, уже есть решение
... что я, кажется, не понимаю. В основной диссертации Себастьяна Купфершмида о решателе Skat я нашел этот фрагмент кода (может быть, C-ish / псевдокод?):

def ab_tt(p, alpha, beta):
    if p isa Leaf:
        return 0

    if hash.lookup(p, val, flag):
        if flag == VALID:
            return val
        elif flag == LBOUND:
            alpha = max(alpha, val)
        elif flag == UBOUND:
            beta = min(beta, val)
        if alpha >= beta:
            return val

    if p isa MAX_Node:
        res = alpha
    else:
        res = beta

    for q in succ(p):
        if p isa MAX_Node:
            succVal = t(q) + ab_tt(q, res - t(q), beta - t(q))
            res = max(res, succVal)
            if res >= beta:
                hash.add(p, res, LBOUND)
                return res
        elif p isa MIN_Node:
            succVal = t(q) + ab_tt(q, alpha - t(q), res - t(q))
            res = min(res, succVal)
            if res <= alpha:
                hash.add(p, res, UBOUND)
                return res
    hash.add(p, res, VALID)
    return res

Это должно быть довольно очевидно. succ(p) это функция, которая возвращает каждое возможное движение в текущей позиции. t(q) это то, что я считаю текущим результатом соответствующей позиции (очки, достигнутые до сих пор декларатором). Поскольку я не люблю копировать вещи, не понимая этого, это должно быть просто помощью для тех, кто хотел бы помочь мне. Конечно, я немного подумал над этим кодом, но я не могу обдумать одну вещь: вычитая текущий счет из альфа / бета перед повторным вызовом функции [например, ab_tt(q, res - t(q), beta - t(q)) ], похоже, что происходит какое-то разделение. Но какая именно выгода, если мы сохраним значение позиции в таблице транспонирования, не выполняя здесь тоже самое вычитание? Если мы нашли ранее исследованную позицию, то почему мы можем просто вернуть ее значение (если VALID) или использовать связанное значение для альфа или бета? На мой взгляд, как сохранение, так и извлечение значений из таблицы транспонирования не будет учитывать конкретную историю этих позиций. Или это будет?

Литература:
Английские источники почти не содержат информации об искусственном интеллекте в скат-играх, но я нашел этот: Игрок- скат на основе симуляции Монте-Карло от Kupferschmid, Helmert. К сожалению, вся статья, и особенно разработка таблиц транспонирования, довольно компактна.

Редактировать:

Чтобы каждый мог лучше представить себе, как развивается счет в игре "Скат" до тех пор, пока не будут разыграны все карты, вот пример. Ход игры отображается в нижней таблице, один трюк на линию. Фактическое количество очков после каждого трюка находится на левой стороне, где +X - это оценка заявителя (-Y - это оценка защищающейся команды, что не имеет значения для альфа-бета). Как я уже сказал, победитель трюка (декларатор или команда защиты) добавляет ценность каждой карты в этом трюке к своему счету.

Значения карты:

Rank    J   A   10  K   Q   9   8   7
Value   2   11  10  4   3   0   0   0
Источник

1 ответ

Решение

Я решил проблему. Вместо того, чтобы делать странные вычитания при каждом рекурсивном вызове, как подсказывает ссылка в моем вопросе, я вычитаю текущий результат из полученного значения альфа-бета только при сохранении позиции в таблице транспозиции:

Для точных значений (позиция не была сокращена):

transpo.put(hash, new int[] { TT_VALID, bestVal - node.getScore()});

Если узел вызвал бета-обрезание:

transpo.put(hash, new int[] { TT_LBOUND, bestVal - node.getScore()});

Если узел вызвал альфа-обрезание:

transpo.put(hash, new int[] { TT_UBOUND, bestVal - node.getScore()});

Куда:

  • transpo это HashMap<Long, int[]>
  • hash это long значение, представляющее эту позицию
  • bestVal является либо точным значением, либо значением, вызвавшим сокращение
  • TT_VALID, TT_LBOUND а также TT_UBOUND простые константы, описывающие тип записи таблицы транспозиции

Тем не менее, это не сработало само по себе. После публикации того же вопроса на gamedev.net, пользователь по имени Альваро дал мне решающий совет:
При сохранении точных результатов (TT_VALID), Я должен только хранить позиции, которые улучшили альфа.

Источник
Другие вопросы по тегам