Тут я кстати попробовал прикрутить хеширование к последней (ну ладно, крайней) модификации своей проги, той, где перебор с границами альфа-бета. И столкнулся вот с чем.

Во-первых, если в варианте с точными результатами (а не с границами) можно было оперировать таблицей внутри цикла ходов, то здесь это не проходит. Т.е. вызывается рекурсия (на каком-то уровне), и первое, что должно быть сделано (после усечения интервала альфа-бета в случае, когда new_depth<depth), это запись расклада в таблицу (конечно для ходов, когда на всех руках одинаковое кол-во карт), если этот расклад встретился впервые. После этого (для впервые встретившегося расклада) мы пробегаем по всем ходам, в результате чего получаем новое значение оценки альфа этого уровня, и его записываем в кеш.

А если же на этапе проверки "первичности" расклада выясняется, что такой расклад уже был (речь идёт конечно о транспонированных раскладах), это означает, что в таблицу некая оценка альфа уже была закеширована. И тогда нам уже нет смысла пробегать по всех ходам, чтобы её получить, мы её берём просто из кеша. Но здесь возникает вот какая штука. Если в прошлой версии программы, где шла работа с точными значениями, а не с оценками, нам кроме расклада и знания, чей сейчас ход, больше ничего нужно не было, и мы могли сразу взять закешированный ранее точный результат из таблицы, то в случае с оценками не так всё просто. Ведь здесь рекурсивная функция вызывается с параметрами. И если эти начальные параметры альфа и бета не кешировать вместе с раскладом, то всё считается неправильно. Поэтому ещё на этапе записи расклада в кеш (т.е. перед циклом ходов) туда же записываются и текущие альфа с бетой. А при проверке первичности/повторности расклада он считается повторным только в том случае, когда когда не только все карты совпадают, но и записанные в таблицу альфа и бета совпадают с теми альфой и бетой, которые на данный момент являются параметрами рекурсивной функции.

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

Да ... кэширование границ весьма трудно постигается умом. Я в свое время так и не смог разобраться, как это сделано у Словеснова. Там у него, как я понял, кэшируется только одно значение и устанавливается флаг, верхняя это граница, нижняя или точное значение. А если нужно закэшировать обе? Короче, не понял ...

Что касается взаимодействия закэшированных границ и передаваемых, то я тебе, кажется, давал эту ссылку:

https://askeplaat.wordpress.com/534-2/mtdf-algorithm/

Там в псевдокоде процедуры AlphaBetaWithMemory почти все расписано. Но есть и нюансы:

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

2. В псевдокоде не указано, в какой момент нужно записывать данные о транспозиции в кэш в случае обнаружения коллизии или того, что ячейка еще не заполнена (это можно рассматривать как вариант коллизии, кстати). Мы с Николаем на этом нагрелись. Записывали текущие границы и код транспозиции в ячейку сразу при обнаружении коллизии. А потом вызывался рекурсивный перебор, ячейка оказывалась переписана другой транспозицией, но мы корректировали по результатам перебора границы, а код транспозиции не трогали. И получалось, что мы кэшировали границы не к той транспозиции.
Потом Николай исправил это - код транспозиции записывался вместе со скорректированными границами уже после рекурсивного перебора.

Еще, кажется, я высылал тебе комментарии к этому псевдокоду. Что каждый оператор делает и зачем. Если нет - напиши, я вышлю еще раз. Если найду, конечно.

Там, на самом деле, не все так страшно. Посидеть полчасика/час и можно разобраться.

Насчёт комментариев я уже не помню, надо поднять литературку, т.е. переписку)

Сейчас я хотел озвучить некоторые эмпирические правила, которые я применил ещё на этапе формирования массива допустимых ходов, чтобы ещё до всяких рекурсий отсечь заведомо паразитные ходы. Это для игр на взятки.

Для играющего:

1. Если масть захода бьётся козырем вистующих или заведомо бьётся старшей картой масти (например синглетным тузом) вистующих, то заходим с самой маленькой, остальные ходы не рассматриваем.

2. Если масть играющего заведомо бьёт все карты вистующих в этой масти (например при структуре ТКДхх), то всегда заходим со старшей (кроме естессно, если мы не попадаем под случай №1, т.е. если её не убивают козырем).

Для вистующего:

1. Если масть захода бьётся козырем другого вистующего, то заходим с самой маленькой, остальные ходы не рассматриваем.

2. Если суммарно у вистующих в какой-то масти имеется минимум 2 карты старше самой старшей карты играющего, они никогда не пускают взятку.

3. Если вистующие могут взять взятку (при этом все дают в масть), а следующим ходом выйти в эту же масть и убить её козырем на другой руке, они никогда не пускают первую взятку.


А для мизеров не совсем понятно, как можно эмпирически что-то отсечь. Но я для них ввёл, если так можно сказать, проверку на "чистоту", которая производится каждые 3 хода (когда у всех равное кол-во карт). Для заходов вистующих и играющего эти проверки, конечно, различаются, и в целом занимают довольно объёмный код, т.к. нужно проверить все 4 масти и учесть много различных нюансов. Наверное это несколько увеличивает время работы программы для совсем уж немизерных рук, но для рук, близких к мизерным, ускорение очень существенное. Потому что если на некоторой глубине выясняется, что "моих больше нет", это отсекает сразу очень большую ветвь перебора.

Странные какие-то эвристики ...

1. Как это не рассматриваем? Коммуникационные приемы - они весьма коварные ... Иногда их не видишь, а они есть. Так что, начать перебор можно (и нужно) с фоски, но и остальные карты исключать ни в коем разе нельзя.

То же самое для вистующего.

2. Тоже, наверное, хотел написать: Начинаем рассмотрение вариантов с захода в старшую.

Остальные тоже как-то стремновато выглядят.

Т.е. ты хочешь сказать, что если вистующий вышел с туза (или в масть, которую второй вистующий бьёт козырем), то у нас есть варианты, что подкладывать? Я берусь утверждать, что вариантов, кроме младшей карты, у нас нет. Нет, ну играя вживую, мы конечно можем скинуть даму вместо семёрки в надежде, что не угадают снос, но в программе рассматривается абсолютно полная информация о раскладе, и снос известен.

Естественно, обратное неверно. Т.е. вистующие на нашего туза совсем не обязаны скидывать младшие, а порой должны ровно наоборот. А иногда даже и второго короля надо скинуть на наши ТДх.

Извини, не заметил, что ты имеешь в виду синглетного туза.

Да и не сходу - тоже. Первый ход втёмную делается вообще-то. Это из той же серии, когда профессор го считает, что мизер чистый, если зайти первым ходом воооон с того короля. Но ни одна программа вам этого не просчитает )

А теперь, внимание!!! Вопрос:

С какой целью в условиях этюда было акцентировано внимание на том, что это скачки?

Та-да-а-ам!!!

Ну, ладно. На открытых картах, когда очевидно, какой делать снос, играть и правда легче )

https://www.gambler.ru/php/protocol?gameno=...e=3&uin=1312691

Ну насчёт скачек, это очевидно, чтобы вскрылись до первого хода. Не сходу-то сообразить можно. Чтобы отдачи скорректировать) Но секунд за 10 я бы вряд ли додумался до этого. Другой вопрос, зачем снос-то от длинной?)