Альфа-бета-таблицы поиска и транспонирования

Question

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

В литературе, которую я до сих пор читал, говорится, что вам нужно хранить тип позиции, оценку и некоторую другую информацию. Почему вы должны хранить тип? Разве вы не можете просто использовать счет, если запись в таблице из предыдущего поиска стала глубже?

Эта страница показывает некоторый пример кода для этого, но я не могу понять, почему поиск AB возвращает бета, когда альфа> = бета. Разве вы не должны возвращать альфа?

Answer 1

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

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