Илья, можно через личку? )

michael.dukhin@yandex.ru

Дополнение к описанию.

Хеш-таблица представляет собой динамический массив, каждым элементом которого является также динамический массив. Для одиночных раскладов её первая размерность устанавливается 2000000, вторая размерность - ноль (т.е. изначально она памяти не занимает). Данные в таблицу заносятся, когда номер хода кратен трём (т.е. на столе нет выхоженных карт), начиная с 3-го и до 24-го хода. 27-й ход (когда у всех по одной карте) заносить бессмысленно. Сначала расклад транспонируется по достоинству карт и по мастям (с учётом козыря), потом с помощью хеш-функции высчитывается ключ (максимально случайно в диапазоне от 0 до 2000000), и размерность ячейки таблицы с этим номером расширяется до 28, чтобы записать в неё расклад (максимальное число карт: 27 + чей ход). Каждая такая (любая из 28-ми) ячейка - размером 1 байт (8 бит), хотя это, я понимаю, расточительно. Для конкретной карты ведь достаточно 5 бит (+ ещё 1 бит для определения козырь/нет), но я пока не знаю, как это сделать без ущерба для всего остального (во встроенных инструментах среды программирования есть только переменные размером 1 байт, если хочется чего-то другого, надо формировать новый класс переменных, я этим не заморачивался). На самом деле, размерность устанавливается не 28, а 29. Одна ячейка резервируется под кэш, чтобы туда записать результат расклада, т.е. кол-во взяток, которое получается. Таблица работает по принципу цепочек, т.е. когда происходит коллизия, размер соотв. ячейки увеличивается ещё на 29. Т.е. в одну ячейку может быть записано несколько раскладов. Коллизии редки (меньше 1%), если таблица заполнена процентов на 10, но когда она заполняется наполовину и больше, коллизии могут достигать 50% и более. Как ни странно, это мало влияет на скорость расчёта (я экспериментировал с различными размерами).

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

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

Если выбирается "посчитать все расклады для S", размер таблицы устанавливается в 10 раз больше, т.е. 20000000. И она обнуляется всегда, когда задаётся новый расклад. Иначе будет занимать много оперативки. 20 млн и так многовато, но у меня на компе с оперативкой 2 гига считается без проблем.

Илья, можно через личку? )

michael.dukhin@yandex.ru

Написал)

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

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

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

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

Интуитивно как раз понятно, что ничего не надо пересчитывать с нуля ...

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

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

Либо использовать мультитэйбл, при котором затирание малокарточных концовок многокарточными не происходит.

Напрягает меня здесь много чего.

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

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

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

Еще раз изложу суть альфа-бета отсечений:

1. Оценка хода меньше ранее полученной нижней границы (или равна ей). Пока что это ничего не значит, но просто вносит вклад в оценку позиции. Особенно для отсечений с амортизацией отказов.
2. Оценка хода лежит строго внутри границ. Это точное значение для данной позиции.
3. Оценка хода лежит выше верхней границы (или равна ей). Можно произвести отсечку (прекращение перебора ходов в данной позиции), т.к. противник не позволит развиваться игре так, чтобы эта позиция возникла - ему выгоднее получить позиции с лучшими результатами.

Т.е. вся работа ведется не с точными значениями, как в классическом минимаксном переборе, а с оценками и границами оценок. Границы в ходе перебора постепенно уточняются и сужаются. В конце концов они стянутся в точку - верхняя станет равна нижней.
При этом если текущая оценка больше или равна этой общей границы, то производится немедленная отсечка. А если меньше, то отсечка будет произведена на более высоком рекурсивном уровне при возврате.
За счет этого достигается значительное сокращение дерева перебора.

Привет, Андрей) Да, я конечно открывал ссылки, которые ты мне присылал. Но обо всём по порядку)

Почему я не использовал классическую альфа-бету? Рассказываю. Когда я решил этим всем заняться, в первую очередь меня интересовала удобная визуализация раскладов и розыгрышей, с чего я, собственно, и начал. Ну то есть, вот карты, их можно двигать и делать ходы согласно правилам. Но как-то немного глупо их двигать просто так, поэтому я решил прикрутить что-то типа решателя, не имея на тот момент представления обо всех этих алгоритмах. Конечно гуглил, но не сразу въезжал, что к чему. И организовал я решение на основе классического минимакса. При этом долго думал, как же его сделать. Получалось, что только с помощью 30-кратного вложенного цикла. Который можно заменить рекурсивной процедурой, которая выглядит красиво, но нужно очень чётко представлять границы итераций, что для опытного программера, наверное, плёвое дело, а я только спустя время разобрался во всех нюансах. Ну и вот, в минимаксе используются точные значения. А чтобы использовать вместо него альфа-бету, нужно менять всю идеологию основной рекурсии, что мне делать очень не хотелось (но придётся, как я понимаю). И я прикрутил к уже реализованному минимаксу отсечения, которые строго говоря нельзя назвать альфа-бетой, но которые по сути выполняют ту же функцию. Сразу скажу, что я оперировал в качестве результата полным кол-вом взяток, которые берёт разыгрывающий, а не кол-вом взяток, которые получаются из хвоста розыгрыша. Но это на самом деле не принципиально, потому что в любой момент розыгрыша я знаю, сколько уже взяток он взял, они фиксируются в глобальной переменной.

Теперь о том, как это работает (пошагово). Мы проверили ход первой картой, например, разыгрывающего (не важно, это может быть самый первый ход или где-то в глубине розыгрыша), рассмотрели все ответы на него и получили, например, 6 взяток. Проверяем ход второй картой и, например, видим, что какой-то ответ вистующих даёт те же 6 взяток. Всё, дальнейшие ответы не рассматриваем. В реализации это выглядит так: на некоторой глубине рекурсии (когда мы по ней поднимаемся) мы рассмотрели все варианты ответов на некий ход ВИСТУЮЩЕГО и получили результат для разыгрывающего, например, 6. Перед тем, как перейти к рассмотрению следующего хода ВИСТУЮЩЕГО и ответов на него, мы производим проверку, а нужно ли это делать? Т.е. мы проверяем ход РАЗЫГРЫВАЮЩЕГО, который был сделан перед этим . И если это был не корневой ход, то мы сравниваем сравниваем результат хода ВИСТУЮЩЕГО на текущей глубине рекурсии с результатом предыдущих ходов РАЗЫГРЫВАЮЩЕГО на предыдущей глубине, они все записаны в массив глобальных переменных. И если мы видим, что этот результат был 6 или больше, мы следующие ходы ВИСТУЮЩЕГО на текущей глубине рекурсии не рассматриваем, а моментально перескакиваем на предыдущую глубину, где ходил РАЗЫГРЫВАЮЩИЙ, и уже начинаем рассматривать следующий его ход. Причём мы можем перескочить сразу на несколько уровней вверх, т.к. вистующие могут делать до 4-х ходов подряд, и мы естественно изначально проверяем это. Т.е. на той "глубокой" глубине, где ходил вистующий, мы проверяем, а когда же последний раз ходил разыгрывающий, а это может быть один ход назад, два, три или четыре. Всё это, конечно, касается и противоположной стороны, т.е. вистующий и разыгрывающий меняются местами, только разыгрывающий максимум может сделать не 4 хода подряд, а 2.

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

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

Кстати, насчёт мультитейбла. Ну я его сделал (дело 10 минут). На массиве раскладов скорость возросла примерно процентов на 7. Но коллизии всё равно есть. Причём их даже больше, но это я связываю с тем, что вместо одной таблицы на 2 млн ячеек я сделал 8 таблиц по 300 000 ячеек (точнее, переменная, описывающая таблицу, осталась одна, я просто ввёл для неё ещё одну размерность). З00 тыщ судя по всему маловато даже для раскладов с одинаковым кол-вом карт.

У меня пока всё)

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

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

Вот теперь я начал понимать твой алгоритм. И могу сказать, что это совсем не алгоритм альфа-бета отсечений. Чем-то похожий, но не он.

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

В результате, перед анализом первого варианта хода мы должны дать нижней границе экстремально малое значение (например, 0 оставшихся взяток или даже "минус бесконечность" в зависимости от реализации).

И получается, что при таком допущении отсечение при разборе первого варианта хода работать не будет (условие отсечения никогда или почти никогда выполняться не будет). Поэтому и приходится, как ты пишешь "рассматривать все ответы на него".

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

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

В алгоритме альфа-бета отсечений происходит почти то же самое, но и еще кое что:
На каждый уровень рекурсии приходит не только оценка верхней границы БЕТА, но и оценка нижней границы АЛЬФА, полученная ранее из анализа параллельных ветвей.
Таким образом, у нас нет необходимости давать нижней границе фиктивное низкое значение перед переборм вариантов. Мы уже имеем вполне конкретное рабочее значение. И при передачи хода противнику (уже в первом варианте нашего хода) эта АЛЬФА станет для него вполне конкретной оценкой верхней границы результата соперника БЕТОЙ. Реальной, а не завышенной, как у тебя!!!

В результате уже при разборе первого варианта ходов отсечений будет гораздо больше.

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

Немножко лирического отступления:

Давным давно, в далекой, далекой галактике когда мобилы были большими, я переписывался со Словесновым. По поводу того, почему у меня так медленно считает. Ну и он мне указал на мою ошибку - она была именно такой :)

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

Можно и так, но это неудобно при кэшировании ...

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

Это потому что все таблицы одинакового размера. А этого не нужно.

Для 9-карточных концовок с избытком хватит таблицы из нескольких сот ячеек.
Для 2-карточных концовок, вообще, достаточно 2-3 десятков ячеек.
А самые большие таблицы нужны для 5-6-7-карточных концовок, наверное. Там уже счет пойдет на десятки и сотни тысяч. Вот сэкономленный объем и надо им отдать.