Ну вот ... Пока я тут соловьем изливался, написал коротко и по существу

Насчет скорострельности - это к Николаю. У него все же более продвинутый инструмент.

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

Так вот, несмотря на то, что писался этот прототип лет 10 назад и на Delphi, время обсчета весьма запутанного расклада около 6 секунд.

	Север  Q  10  10 9 8 7  K J 10 8
Запад  A K  A Q 9  K Q J  A 9		Восток  J 10 7  K J 8 7  A  Q 7
	Снос  9 8  -  -  -

Скачки. W на первой руке играет 7БК.

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

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

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

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

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

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

Именно так я и делаю)

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

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

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

Отключил у себя хеш, проверил этот расклад без него. Да, у меня считается около 30 секунд.. Любопытно, первый ход надо делать в 9 черв, я бы сходу и не сообразил наверное. А почему снос - две карты от длинной?

Тут не в том дело, что для противоположной стороны не рассматривается ...

Еще раз попробую ...

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

А вот нижняя границы оценки не передается на следующий уровень. Ты ее каждый раз рассчитываешь заново. Сначала даешь какое-то малое значение, а потом потихоньку уточняешь. И потом, при передаче хода сопернику именно эта оценка нижней границы АЛЬФА передается на следующий уровень как БЕТА.

Получается, что на каждом уровне рекурсии ты эту АЛЬФУ создаешь заново, теряя всю информацию о ранее полученной оценке.

А в альфа-бета отсечении эта оценка сквозная. Она передается из ветви в ветвь дополнительным параметром АЛЬФА, корректируясь в сторону увеличения. Таким образом, уже с самого начала мы имеем все более узкий диапазон оценок границ. И БЕТА в каждой ветви уже с самого начала, с самого первого варианта хода имеет более низкие значения, что увеличивает число отсечений.

Отключил у себя хеш, проверил этот расклад без него. Да, у меня считается около 30 секунд.. Любопытно, первый ход надо делать в 9 черв, я бы сходу и не сообразил наверное. А почему снос - две карты от длинной?

Потому что это этюд

Ну заторговался человек Хотя, кто его заторговал - не ясно

Вот понятно теперь, как альфа-отсечение влияет? Еще в несколько раз сокращает время.

Я бы на твоем месте не занимался сейчас подбором размера кэша, а сделал бы нормальный алгоритм отсечений. Тому как при увеличении числа отсечений средняя глубина перебора резко изменится, уменьшится число обращений к кэшу, уменьшится число коллизий.

Это сообщение отредактировал Pochemuk - 11/05/2018, 16:56

Я понял. Попробую ещё раз подумать)

Вот-вот ... подумай.

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

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

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

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