А, ну всё!))

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вдогонку ...

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

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

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

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

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

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

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

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

Это сообщение отредактировал Фрэд - 16/05/2018, 23:34

У меня, кстати, в самой первой версии определялась последовательность оптимальных ходов и записывалась в хеш, но ведь это увеличивает объём таблицы. Поэтому я от этого отказался. Теперь при просчёте расклада выдаётся только результат, т.е. кол-во взяток, которые берё разыгрывающий. Но если нажать кнопку "показать оптимальные ходы", то происходит вот что: делаются (без визуализации) все допустимые правилами ходы из конкретной позиции, и для каждого сделанного хода вызывается рекурсивная функция с параметром "номер_хода+1", и если результат не отличается от первоначального, данная карта помечается как оптимальная. Можно сделать свой ход любой другой картой, тогда высветится другое значение результата, и просчёт дальнейших ходов противоположной стороны уже будет определяться исходя из этого. Ну просто для единичного расклада это же всё считается очень быстро (если с хешированием), задержки практически не ощущаются, особенно на поздних этапах розыгрыша.

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

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

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

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

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

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

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

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

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

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

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

Это сообщение отредактировал Фрэд - 17/05/2018, 01:55

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

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

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

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

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

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

Пусть 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, т.к. меньше начального значения альфы уже ничего быть не может).

Свершилось! Как говорил один профессор: "Пока объяснял студентам, сам все понял!"

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

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

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

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

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

На самом деле, для самого перебора с альфа-бета отсечениями принципиальной разницы в использовании амортизации отказов нет. Реакция внутри дерева перебора на возвращаемое значение оценки результата хода будет совершенно одинаковой, независимо от того, строго она ограничена диапазоном [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