Альфа-бета отсечение

[Tookser]

Пытаюсь разобраться с этой темой по вот этой статье. Понимаю, почему функции $F_1$ и $F_2$ возвращают именно то значение, которое нужно, но не совсем понимаю, что именно отсекают альфа и бета, и при отходе от формулировок статьи всё становится совсем непонятно. Возможно, кто-нибудь знает более понятное объяснение альфа-бета отсечения.

[Geen]

http://www.k-labs.ru/dms/kalah.html
Возьмите размер поля 2 и 3 камня исходно. (Включить рисование дерева)
и сравните деревья без отсечения и с "базовым" отсечением.
Возможно станет понятнее.

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

[Tookser]

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

[Geen]

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

-- 29.10.2016, 12:00 --

Число справа от стрелки это количество не посчитанных ходов из данной позиции (если включить "анимацию", будет сразу заметно)

-- 29.10.2016, 12:04 --

"?" означает, что для данной позиции вообще нет оценки, "^" - что некоторая оценка уже имеется

[mustitz]

Рассмотрим пример из шахмат. Допустим мы ищем за чёрных ответ на 1. e2-e4.

I. Мы смотрим вариант 1. e4 c5, перебираем все варианты и получаем его оценку допустим +0.18.

II. Потом мы переходим к рассмотрению хода 1... f5. Смотрим ответы белых. Начинаем, допустим, с 2. Nc3 что даст нам оценку +0.55. И в этот момент происходит alpha-beta отсечение: алгоритм может смело окончить перебор для линии 1... f5 и не рассматривать остальные 28 альтернатив белых. Мы уже получили достаточно информации, что 1... c5 лучше 1... f5. Потому что оценка 1... c5 +0.1, а оценка 1... f5 не меньше чем +0.55. На самом деле точная оценка хода 1... f5 будет +1.19, потому что вместо 2. Nc3 в распоряжении белых есть более сильный ход 2. exf5. Но сама ветка 1. e4 f5 2. exf5 в данном порядке не рассматривается. Другие словами, alpha-beta не уточняет насколько плоха худшая альтернатива.

[Tookser]

mustitz, я понял пример, но не понял полностью связь между альфа и бета и наилучшими вариантами. Что такое альфа и бета в каждой вершине?
Пока мне удалось хорошо запомнить алгоритм. Вот тут вроде понятное объяснение, но про альфа и бета написано как-то не очень понятно (http://web.cs.ucla.edu/~rosen/161/notes/alphabeta.html). "Альфа - максимальная из нижних граней возможных решений, бета - минимальная из верхних граней возможных решений" (в этом примере цена игры максимизируется первым игроком и минимизируется вторым). Т.е. всё множество цен игры каким-то образом ограничивается сверху и снизу так, чтобы решение попало внутрь границ. Для каждого узла решение своё, а интересует нас решение самого верхнего узла. Тут я не совсем понимаю, почему в максимизирующих узлах мы меняем только альфа, а в минимизирующих только бета, и опять же, что такое альфа и бета для каждого узла?

-- Вт ноя 01, 2016 00:52:32 --

Geen в сообщении #1164045 писал(а):

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

-- 29.10.2016, 12:00 --

Число справа от стрелки это количество не посчитанных ходов из данной позиции (если включить "анимацию", будет сразу заметно)

-- 29.10.2016, 12:04 --

"?" означает, что для данной позиции вообще нет оценки, "^" - что некоторая оценка уже имеется

Без значений альфа и бета не очень понятно.
UPD. Хотя альфа это значения в ещё не полностью просчитанных узлах, они показываются, а бета тоже должны как-то отображаться, наверное.

[Geen]

Tookser в сообщении #1164822 писал(а):

Без значений альфа и бета не очень понятно.

В принципе, всё есть в вершинах выше по дереву...

Tookser в сообщении #1164822 писал(а):

бета тоже должны как-то отображаться, наверное.

А зачем?

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

Кстати, Вы код смотрели?

[mustitz]

Tookser в сообщении #1164822 писал(а):

Что такое альфа и бета в каждой вершине?

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

Например, ищём ответ на 1. e2-e4. Вначале $\alpha=-\infty$, $\beta=+\infty$.
> Смотрим 1... d7-d5, получаем оценку $\beta = +0.56$ (обновляем $\beta$).
> Смотрим 1... c7-c5:
> > Смотрим 2. Nb1-c3, получам оценку $\alpha=+0.25$ (обновляем $\alpha$).
> > Смотрим 2. b2-b4.
> > > Смотрим 2... Qd8-b5
> > > > Смотрим 3. b4xa5, получаем оценку $+10.95 > \beta$. Значит смотреть другие альтернативы на 2... Qa5 не имеет смысла
> > > Смотрим 2... c5 x b4, получаем оценку $-0.19 < \alpha$. Значит смотреть на другие альтернативны на 2. b4 не имеет смысла, это не изменит того факта, что этот ход хуже 2. Nc3
> > Смотрим 2. Ng1-f3, получам оценку $\alpha=+0.30$ (обновляем $\alpha$).

[Tookser]

mustitz, разобрал. Альфа и бета здесь это просто две переменные, одни на весь алгоритм, как я понял, да? А что делать, если, скажем, оценка хода 3.b4xa5 будет меньше $\alpha$? Мне кажется, тут нужно перебирать ходы из этой вершины дальше, ведь дальше у нас может оказаться ход, оценка которого будет между $\alpha$ и $\beta$.
В конце у нас $\alpha=+0.30$ и $\beta=+0.56$ . Если оценка хода 1... e7-e5 будет меньше $\alpha$, то что делать? По идее, надо будет выбирать его, но он же вне отрезка...

Geen, код ещё не смотрел, посмотрю через некоторое время.

[mustitz]

Tookser в сообщении #1165610 писал(а):

mustitz, разобрал. Альфа и бета здесь это просто две переменные, одни на весь алгоритм, как я понял, да?

Не совсем так, $\alpha$ и $\beta$ привязаны к текущей позиции.

Если ход белых, то мы можем обновлять оценку $\alpha$, когда находим ход лучше, чем предыдущие альтернативы. Но в этом случае мы продолжаем перебор альтернатив дальше. И мы можем выполнять отсечение по $\beta$, когда находим опровержение предыдущего хода чёрных.

Аналогично, если ход чёрных, то мы можем обновлять оценку $\beta$, и выполняем отсечение по $\alpha$.

Tookser в сообщении #1165610 писал(а):

А что делать, если, скажем, оценка хода 3.b4xa5 будет меньше $\alpha$?

Ничего не делать, в данной ситуации мы отсекаем по $\beta$, не по $\alpha$. Поэтому, если мы получили оценку ниже $\alpha$, то значит, что ход неудачный, надо искать дальше. Если все хода слабые, значит 2. b2-b4 просто плохой ход и надо искать другие.

Tookser в сообщении #1165610 писал(а):

Если оценка хода 1... e7-e5 будет меньше $\alpha$, то что делать?

У нас в этот момент $\alpha = -\infty$. Надо было наверное индексы стасить, на какой глубине какое значение используется.

-- 03.11.2016, 15:47 --

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

Например, ищём ответ на 1. e2-e4. Вначале $\alpha_0=-\infty$, $\beta_0=+\infty$.
> Смотрим 1... d7-d5, получаем оценку $\beta_0 = +0.56$ (обновляем $\beta_0$).
> Смотрим 1... c7-c5: $\beta_1 = \beta_0 = +0.56$, $\alpha_1 = \alpha_0 = -\infty$.
> > Смотрим 2. Nb1-c3, получам оценку $\alpha_1=+0.25$ (обновляем $\alpha_1$).
> > Смотрим 2. b2-b4: $\beta_2 = \beta_1 = +0.56$, $\alpha_2 = \alpha_1 = +0.25$.
> > > Смотрим 2... Qd8-a5: $\beta_3 = \beta_2 = +0.56$, $\alpha_3 = \alpha_2 = +0.25$.
> > > > Смотрим 3. b4xa5, получаем оценку $+10.95 > \beta_3$. Значит смотреть другие альтернативы на 2... Qa5 не имеет смысла
> > > Смотрим 2... c5 x b4, получаем оценку $-0.19 < \alpha_2$. Значит смотреть на другие альтернативны на 2. b4 не имеет смысла, это не изменит того факта, что этот ход хуже 2. Nc3
> > Смотрим 2. Ng1-f3, получам оценку $\alpha_1=+0.30$ (обновляем $\alpha_1$).

Допустим, что остальные ходы белых не улучшили $\alpha_1$, мы возвращаемся на уровень нуль, обновляем $\beta_0 = +0.30$

> Смотрим 1... e7-e5: $\beta_1 = \beta_0 = +0.30$, $\alpha_1 = \alpha_0 = -\infty$.