Главная В клубе 1166 Войти
Здравствуйте, гость Правила · Помощь

»  Оценка карты играющего при заданном сносе, Определение результата игры для мизера и игры на взятки Подписаться | Сообщить другу | Версия для печати
      » 11/05/2018, 13:21,  Pochemuk 
Кутруповезет (11 мая 2018, 12:46)
То, что здесь описано, это как раз алгоритм бета-отсечения - когда рассматривается ход вистующих. А вот альфа-отсечение - когда рассматривается ход играющего - у вас не описано. Если его действительно в вашей программе нет, то его можно добавить без изменения всей идеологии, и это должно дать не меньшее ускорение.

Ну вот ... Пока я тут соловьем изливался, написал коротко и по существу smile.gif
      » 11/05/2018, 13:59,  Pochemuk 
Фрэд (10 мая 2018, 18:31)
Да, я понимаю, что вот это вот всё немного "через одно место", но эффективность налицо. Например, расклады, которые простым минимаксом (без хеша и отсечений) считались несколько часов, с помощью этой приблуды стали считаться 1 минуту. Расклад, который считался 7 минут, стал считаться 5 секунд. А какую эффективность даёт классическая альфа-бета, примерно такую же или выше?

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

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

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

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

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

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

Другие расклады не просите просчитать и засечь. У меня там вообще никакого интерфейса нет. Расклад приходится заменять прямо в исходниках, потом перекомпилировать. А у меня и Delphi сейчас не установлен.
      » 11/05/2018, 16:08,  Фрэд 
Кутруповезет (11 мая 2018, 12:46)
Фрэд (10 мая 2018, 18:31)

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

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

Почему же, всё ровно тоже самое (только наоборот) рассматривается и для противоположной стороны.
      » 11/05/2018, 16:14,  Фрэд 
Pochemuk (11 мая 2018, 13:20)
Фрэд (10 мая 2018, 18:31)
Сразу скажу, что я оперировал в качестве результата полным кол-вом взяток, которые берёт разыгрывающий, а не кол-вом взяток, которые получаются из хвоста розыгрыша. Но это на самом деле не принципиально, потому что в любой момент розыгрыша я знаю, сколько уже взяток он взял, они фиксируются в глобальной переменной.

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

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

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

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

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

Для 9-карточных концовок с избытком хватит таблицы из нескольких сот ячеек.
Для 2-карточных концовок, вообще, достаточно 2-3 десятков ячеек.
А самые большие таблицы нужны для 5-6-7-карточных концовок, наверное. Там уже счет пойдет на десятки и сотни тысяч. Вот сэкономленный объем и надо им отдать.
Я ещё вчера изменил размеры таблицы, сделал их разными. Коллизии уменьшились, но не намного. Я могу вывести на экран их число для разных таблиц, посмотрю, где их больше всего.
      » 11/05/2018, 16:29,  Фрэд 
Pochemuk (11 мая 2018, 13:59)
У меня же сейчас есть только прототип - реализация альфа-бета перебора без кэширования. Но там применена одна хиленькая эвристика лучшего хода - сначала рассматриваются берущие ходы, а потом отдающие.

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

Отключил у себя хеш, проверил этот расклад без него. Да, у меня считается около 30 секунд.. Любопытно, первый ход надо делать в 9 черв, я бы сходу и не сообразил наверное. А почему снос - две карты от длинной?
      » 11/05/2018, 16:48,  Pochemuk 
Фрэд (11 мая 2018, 16:08)
То, что здесь описано, это как раз алгоритм бета-отсечения - когда рассматривается ход вистующих. А вот альфа-отсечение - когда рассматривается ход играющего - у вас не описано. Если его действительно в вашей программе нет, то его можно добавить без изменения всей идеологии, и это должно дать не меньшее ускорение. [/QUOTE]
Почему же, всё ровно тоже самое (только наоборот) рассматривается и для противоположной стороны.

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

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

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

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

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

А в альфа-бета отсечении эта оценка сквозная. Она передается из ветви в ветвь дополнительным параметром АЛЬФА, корректируясь в сторону увеличения. Таким образом, уже с самого начала мы имеем все более узкий диапазон оценок границ. И БЕТА в каждой ветви уже с самого начала, с самого первого варианта хода имеет более низкие значения, что увеличивает число отсечений.
      » 11/05/2018, 16:54,  Pochemuk 
Фрэд (11 мая 2018, 16:29)
Pochemuk (11 мая 2018, 13:59)
У меня же сейчас есть только прототип - реализация альфа-бета перебора без кэширования. Но там применена одна хиленькая эвристика лучшего хода - сначала рассматриваются берущие ходы, а потом отдающие.

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

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

Потому что это этюд smile.gif

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

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

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

Это сообщение отредактировал Pochemuk - 11/05/2018, 16:56
      » 11/05/2018, 16:57,  Фрэд 
Я понял. Попробую ещё раз подумать)
      » 12/05/2018, 01:24,  Pochemuk 
Фрэд (11 мая 2018, 16:57)
Я понял. Попробую ещё раз подумать)

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

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

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

Тогда и суть альфа-бета отсечений станет ясной и, самое главное, будет понятно, как этот диапазон границ кэшировать. А кэширование - это сокращение перебора, примерно, на два порядка даже для единичного расклада. Для группы похожих раскладов - эффект гораздо выше.
      » 12/05/2018, 02:00,  Фрэд 
Да это я уяснил) Не зря же я сказал о смене всей идеологии. Это надо переделывать рекурсию, чтобы вызывать её с доп.параметрами, а у меня сейчас в ней всего один параметр - номер хода. Я вот прямо сейчас попытался пока что прикрутить к тому, что есть, дополнительные 2 параметра (один для играющего, другой для вистующего), но глобальных. Чтобы они ползли только вверх и в любой момент указывали на тот уровень (который априори выше текущего), с которым надо сравнивать текущий результат. При этом неважно, в какой ветви ты находишься. Заработало оч.быстро, но неправильно) Где-то я перемудрил, буду разбираться. А может, как часто бывает, что-то скопировал и забыл, грубо говоря, поменять 2 на 3 или х на у.
      » 16/05/2018, 02:26,  Фрэд 
А, ну всё!))

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

Короче говоря, твой, Андрей, расклад у меня посчитался где-то секунды за 3-4. А полностью 15 раскладов (5 вариантов козырей*3 варианта первых хода) за 38 секунд. По моему старому алгоритму такой массив раскладов считался примерно за 2 с половиной минуты. Это всё, естессно, при отключённом хешировании. Теперь ещё с ним нужно разобраться и переделать.

Только в твоём псевдокоде, который ты мне присылал ещё давно, есть одна такая мелочь, которая даст всегда результат либо +10 либо -10. У тебя: "если (!root && (t > alpha)) {alpha= t}". Вот не надо здесь никакой проверки на корневищность) Т.е. надо просто: "если (t > alpha) {alpha= t}". Я это заметил только когда адаптировал твой код под себя и поглыбже в него вникнул. Вообще конечно альфа-бета штука интуитивно плохо понятная именно для конкретно этой задачи. Начинаешь что-то понимать только когда реально пытаешься её реализовать.

Ну и ещё конечно я в конце рекурсивной функции ввёл пару действий, чтобы она выдавала результат не -10...+10, а нормальное кол-во взяток, и всегда именно взяток разыгрывающего (а то ведь если первый ход вистующих, то она их кол-во взяток и выдаст).
      » 16/05/2018, 13:47,  Pochemuk 
Фрэд (16 мая 2018, 02:26)
Только в твоём псевдокоде, который ты мне присылал ещё давно, есть одна такая мелочь, которая даст всегда результат либо +10 либо -10. У тебя: "если (!root && (t > alpha)) {alpha= t}". Вот не надо здесь никакой проверки на корневищность) Т.е. надо просто: "если (t > alpha) {alpha= t}". Я это заметил только когда адаптировал твой код под себя и поглыбже в него вникнул. Вообще конечно альфа-бета штука интуитивно плохо понятная именно для конкретно этой задачи. Начинаешь что-то понимать только когда реально пытаешься её реализовать.

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

Надо на "корневищность" проверять.

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

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

А сделать это, не отключая альфа-бета отсечения, нельзя.

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

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

Кажется там в псевдокоде еще одна проверка на "корневищность" есть. На предмет отсечения по бете. Она тоже неспроста ... Тому как, даже если какой-то ход дает все 10 взяток, то отсекать из рассмотрения остальные варианты ходов не надо. Иначе мы не узнаем, какие из них такие же хорошие, а какие хуже и насколько.

Что касается представления результатов, то это на любителя. Можно и от 0 до 10, можно и по другому. Просто у меня (и у Словеснова, независимо от меня) результатом считается именно разность между числом уже взятых взяток тем, чей ход, и числом взяток, взятых его противником/ами.

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

Представление результата в виде разности полностью удовлетворяет этому требованию. Вот вернула рекурсивная функция перебора какой-то результат. Если при этом ход передавался сопернику, то берем его со знаком "минус", а если остался наш или партнера по висту, то со знаком "плюс". И ничего лишнего. Никаких дополнительных сложений и вычитаний.
      » 16/05/2018, 14:07,  Pochemuk 
Вдогонку ...

Можно не использовать подход NegaMax. Можно снизить уровень абстракции и использовать для корневых позиций отдельные процедуры. Это позволит избежать проверок и упростит каждую процедуру. Но потребует большего их количества.

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

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

Это сообщение отредактировал Pochemuk - 16/05/2018, 14:17
      » 16/05/2018, 23:33,  Фрэд 
Ну вот смотри. После цикла надо вернуть альфа. Другими словами, присвоить результату рекурсивной функции значение, которое на данный момент имеет переменная альфа. Если написать условие как у тебя, то при рекурсивном подъёме, когда будет достигнут самый первый ход, проверка даст, что это корневая позиция, и переменной альфа (которая задаётся в качестве параметра рекурсии) не будет присвоено значение t. Т.е. не будет присвоено значение, соответствующее оценке позиции. Т.е. переменная альфа останется равной той, которую мы укажем в основном теле программы в качестве параметра при вызове рекурсии. Т.е. -10.

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

Короче. Проверка на корневищность в конце цикла даёт мне при любом раскладе стабильно результат +10 или -10, в зависимости от того, чей первый ход, мизер или нет. Если её убрать, даёт правильный результат, это я с одной стороны прокрутил в голове, ну и протестировал на конкретных раскладах и определении в них оптимальных ходов на разной глубине розыгрыша. Повторю: определение оптимальных карт для хода у меня прописано отдельной процедурой, включающей в себя основную рекурсию, только вызванную с параметром номера хода, большем, чем 1.

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

Это сообщение отредактировал Фрэд - 16/05/2018, 23:34
      » 16/05/2018, 23:53,  Фрэд 
У меня, кстати, в самой первой версии определялась последовательность оптимальных ходов и записывалась в хеш, но ведь это увеличивает объём таблицы. Поэтому я от этого отказался. Теперь при просчёте расклада выдаётся только результат, т.е. кол-во взяток, которые берё разыгрывающий. Но если нажать кнопку "показать оптимальные ходы", то происходит вот что: делаются (без визуализации) все допустимые правилами ходы из конкретной позиции, и для каждого сделанного хода вызывается рекурсивная функция с параметром "номер_хода+1", и если результат не отличается от первоначального, данная карта помечается как оптимальная. Можно сделать свой ход любой другой картой, тогда высветится другое значение результата, и просчёт дальнейших ходов противоположной стороны уже будет определяться исходя из этого. Ну просто для единичного расклада это же всё считается очень быстро (если с хешированием), задержки практически не ощущаются, особенно на поздних этапах розыгрыша.
      » 17/05/2018, 00:24,  Pochemuk 
Фрэд (16 мая 2018, 23:33)
Ну вот смотри. После цикла надо вернуть альфа. Другими словами, присвоить результату рекурсивной функции значение, которое на данный момент имеет переменная альфа. Если написать условие как у тебя, то при рекурсивном подъёме, когда будет достигнут самый первый ход, проверка даст, что это корневая позиция, и переменной альфа (которая задаётся в качестве параметра рекурсии) не будет присвоено значение t. Т.е. не будет присвоено значение, соответствующее оценке позиции. Т.е. переменная альфа останется равной той, которую мы укажем в основном теле программы в качестве параметра при вызове рекурсии. Т.е. -10.

Это ты чего-то недопонял.

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

А результаты - это совсем другие переменные.

В том псевдокоде, который я тебе приводил, они такие:

t - оценка результата последнего рассмотренного варианта хода.
m - наилучший результат (или его оценка) для рассмотренных вариантов. Она-то и возвращается.
res - результат текущей взятки (1 - взяли, -1 - отдали, 0 - взятка еще не закрыта).

И возвращать рекурсивная функция должна m, а не альфу.

Другое дело, что в ряде случаев альфа и m равны. Это происходит в том случае, если 1) включен механизм отсечения без амортизации отказов; 2) m находится внутри первоначально диапазона альфа .. бета.

Но если механизм отсечения выключить (а в корневых позициях это необходимо делать, если мы хотим не просто найти какой-то один лучший ход, а точно узнать результаты каждого варианта без отсечений), то корректировать альфу не надо. Поэтому она будет отличаться от m.
Точно так же в корневых позициях не надо производить выход из цикла при превышении m беты.
      » 17/05/2018, 01:17,  Фрэд 
Это я всё понимаю. Может просто в силу малой начитанности не вполне ясно выражаю свои мысли на великом и могучем) Без разницы, что возвращать, m или альфу, насколько я на данный момент понял. От m я тупо избавился. Но я другое имел в виду. Вот когда рекурсия вызывается изначально, в самый первый раз, т.е. не сама себя внутри самой себя, а в основном теле программы, ведь там должны в качестве параметров (которые потом будут фигурировать как альфа и бета) прописаны конкретные цифры. Т.е. для нулевой позиции (у всех по 10 карт) это -10 для альфа и 10 для бета. И в самый-самый первый раз, т.е. из корневой позиции, рекурсия начинает работать именно с этими параметрами в качестве альфа и бета, которые в процессе сужаются. Но. Вот мы рекурсивно поднялись к корню, а там ведь как раз фигурируют эти альфа и бета, равные -10 и +10 соответственно. Ну то есть что я хочу сказать. Каждый вызов рекурсии внутри самой себя - это спуск на уровень вниз, куда и передаются новые альфа и бета. А подъём на уровень вверх происходит как бы неявно, т.е. тогда, когда завершается работа текущего нижнего уровня. И поднявшись вот так неявно вверх, мы сталкиваемся с теми же альфа и бета, которые там фигурировали до последнего спуска. Блин. Чё-то я уже запутался... Так... Стоп. Всё-таки альфа снизу вверх тоже передаётся. Т.к. если оценка хода оказалась больше неё, то она присваивается альфа. Это всё внутри цикла из допустимых ходов. И если вот эта новая альфа стала равна или превысила бета, мы моментально выходим из цикла ходов.
      » 17/05/2018, 01:54,  Фрэд 
Так, ещё раз. Вызвали рекурсию. Сначала формируется массив допустимых ходов. Потом идёт цикл по этим ходам, внутри которого сначала идёт проверка, если альфа больше или равна, чем бета, и если это не корневая позиция (вот здесь только проверка корневой позиции!wink.gif, то моментальный выход из цикла и возврат альфа, после чего происходит рекурсивный подъём к предыдущему уровню. А если это корневая позиция или альфа меньше бета, то мы вызываем рекурсию дальше (спускаемся вниз), меняя для следующего вызова местами параметры альфа и бета (а также их знаки, а также приплюсовывая или вычитая из них моментальный результат текущего хода), если следующий ход делает другая сторона или не меняя, если та же. И результат этой рекурсии (когда она вычислится и произойдёт возврат на этот же уровень) передаём в результат текущего хода. И уже после этого альфе текущего уровня присваиваем вот этот вот результат, но только при условии, если она до этого была меньше его. А у тебя стоит условие, что ещё должна быть некорневая позиция. Но тогда в корневой позиции никогда не получим альфа, отличающееся от забитого туда руками вначале, т.е -10.

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

Это сообщение отредактировал Фрэд - 17/05/2018, 01:55
      » 17/05/2018, 21:51,  Pochemuk 
Фрэд (17 мая 2018, 01:17)
Без разницы, что возвращать, m или альфу, насколько я на данный момент понял. От m я тупо избавился.

И зря smile.gif Лучше бы подумал, зачем она нужна была ...

До чего я был педантом лет 10-15-20 назад и стремился не использовать переменные сверх необходимого, но это не помешало мне ввести дополнительную переменную. Для чего, как думаешь? wink.gif

Фрэд (17 мая 2018, 01:54)
И вижу, что на всех этюдных раскладах (типа Галактионова и т.д.) у меня всё работает правильно, я их уже все выучил наизусть, как правильно ходить)

Это смотря какую задачу ты решаешь.

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

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

Вся суть альфа-бета отсечений заключается в следующем:

Пусть r - точное значение функции, а t - ее оценка (примерная из-за отсечений).
Тогда (для отсечений без амортизации отказов):

Если t = alpha, то r <= alpha
Если alpha < t < beta, то r = g
Если t = beta, то r >= beta

Для алгоритма с амортизацией чуть по другому (равенства заменяются на нестрогие неравенства и границы сильнее сдвигаются):

Если t <= alpha, то r <= t
Если alpha < t < beta, то r = t
Если t >= beta, то r >= t

Но особой разницы нет.

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

Если же для корневой позиции мы альфу трогать не будем, то t для всех вариантов ходов будет находиться внутри диапазона альфа .. бета. Таким образом, t всегда будет равно точному значению r (даже если t=alpha, то r=alpha, т.к. меньше начального значения альфы уже ничего быть не может).
      » 18/05/2018, 20:14,  Pochemuk 
Свершилось! Как говорил один профессор: "Пока объяснял студентам, сам все понял!" smile.gif

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

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

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

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

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

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

1. Если оценка результата хода t=alpha или t<alpha, то в обоих случаях это приведет к одинаковым последствиям, вернее к одинаковому отсутствию последствий: не будет изменена ни одна граница, ни лучший результат, последовательность перебора не изменится.

2. Если оценка результата хода t=beta или t>beta, то в любом случае будет мгновенно произведена отсечка - прекращение рассмотрения оставшихся вариантов ходов.
Единственно, на более высокий уровень будет возвращено тоже выходящее из диапазона границ значение оценки, но и оно, как следует из этих двух рассмотренных возможностей, тоже ни на что не повлияет.

Как влияет на логику перебора модификация с амортизацией отказов в случае использования кэширования границ, теоретически объяснить сложно. Интуитивно же понятно, что тоже, скорее всего, никак. И практические исследования это подтверждают.

Так в чем же разница? Зачем следовало придумывать вариант с амортизацией отказов, если он чуть сложнее и чуть медленнее классического алгоритма?

Разница сказывается в том случае, если лучший ход ищется не в лоб однократным перебором, а с помощью многопроходного перебора с использованием т.н. "нулевого окна" - алгоритмы NegaScout и MTD(f).

Собственно говоря, в NegaScout я разбираюсь не слишком хорошо. Мне он кажется несколько искусственным и громоздким. Поэтому объясню на примере алгоритма MTD(f).

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

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

Далее, если полученный диапазоне всё еще остается достаточно широким, мы можем произвести его деление пополам при помощи нового нулевого окна. Иначе производим поиск с отсечениями на всем диапазоне полученных границ.

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

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

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

Казалось бы, многопроходный MTD(f) имеет кучу преимуществ перед классическим перебором с альфа-бета отсечениями. Только вот для решения префраскладов он не слишком подходит. Спасибо Николаю extasy - объяснил мне, почему.

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

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

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

Это сообщение отредактировал Pochemuk - 18/05/2018, 21:16
      » 18/05/2018, 22:46,  Фрэд 
Тут я кстати попробовал прикрутить хеширование к последней (ну ладно, крайней) модификации своей проги, той, где перебор с границами альфа-бета. И столкнулся вот с чем.

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

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

Как нетрудно догадаться, это сильно увеличивает количество якобы "разных" раскладов, но только в этом случае результат работы программы получается корректным. Вообще даже в этом случае для единичных раскладов скорость расчёта выше (не намного, не больше, чем в 2 раза), чем в версии без альфа-бета перебора, а вот на массиве раскладов скорость, наоборот, ниже. Что объяснимо, конечно. Как минимизировать количество этих "разных" раскладов, и соответственно количество записей в кеш, я че-то пока не пойму. Каким-то образом надо "играть" с границами.
      » 18/05/2018, 23:52,  Pochemuk 
Да ... кэширование границ весьма трудно постигается умом. Я в свое время так и не смог разобраться, как это сделано у Словеснова. Там у него, как я понял, кэшируется только одно значение и устанавливается флаг, верхняя это граница, нижняя или точное значение. А если нужно закэшировать обе? Короче, не понял ...

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

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

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

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

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

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

Там, на самом деле, не все так страшно. Посидеть полчасика/час и можно разобраться.
      » 19/05/2018, 01:01,  Фрэд 
Насчёт комментариев я уже не помню, надо поднять литературку, т.е. переписку)

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

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

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

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

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

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

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

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


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

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

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

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

Остальные тоже как-то стремновато выглядят.
      » 19/05/2018, 02:04,  Фрэд 
Т.е. ты хочешь сказать, что если вистующий вышел с туза (или в масть, которую второй вистующий бьёт козырем), то у нас есть варианты, что подкладывать? Я берусь утверждать, что вариантов, кроме младшей карты, у нас нет. Нет, ну играя вживую, мы конечно можем скинуть даму вместо семёрки в надежде, что не угадают снос, но в программе рассматривается абсолютно полная информация о раскладе, и снос известен.

Естественно, обратное неверно. Т.е. вистующие на нашего туза совсем не обязаны скидывать младшие, а порой должны ровно наоборот. А иногда даже и второго короля надо скинуть на наши ТДх.
      » 19/05/2018, 11:27,  Pochemuk 
Фрэд (19 мая 2018, 02:04)
Т.е. ты хочешь сказать, что если вистующий вышел с туза (или в масть, которую второй вистующий бьёт козырем), то у нас есть варианты, что подкладывать?

Извини, не заметил, что ты имеешь в виду синглетного туза.
      » 25/05/2018, 10:47,  платан 
Фрэд (11 мая 2018, 16:29)
Любопытно, первый ход надо делать в 9 черв, я бы сходу и не сообразил наверное.

Да и не сходу - тоже. Первый ход втёмную делается вообще-то. Это из той же серии, когда профессор го считает, что мизер чистый, если зайти первым ходом воооон с того короля. Но ни одна программа вам этого не просчитает )
      » 25/05/2018, 12:36,  Pochemuk 
платан (25 мая 2018, 10:47)
Первый ход втёмную делается вообще-то. Это из той же серии, когда профессор го считает, что мизер чистый, если зайти первым ходом воооон с того короля. Но ни одна программа вам этого не просчитает )

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

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

Та-да-а-ам!!!
      » 25/05/2018, 13:00,  платан 
Ну, ладно. На открытых картах, когда очевидно, какой делать снос, играть и правда легче )

https://www.gambler.ru/php/protocol?gameno=...e=3&uin=1312691
      » 25/05/2018, 22:22,  Фрэд 
Ну насчёт скачек, это очевидно, чтобы вскрылись до первого хода. Не сходу-то сообразить можно. Чтобы отдачи скорректировать) Но секунд за 10 я бы вряд ли додумался до этого. Другой вопрос, зачем снос-то от длинной?)
« Предыдущая тема | Перечень тем | Следующая тема »
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей: