2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 Альфа-бета отсечение
Сообщение28.10.2016, 03:04 


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

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение28.10.2016, 12:42 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение29.10.2016, 02:27 


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

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение29.10.2016, 11:57 
Заслуженный участник
Аватара пользователя


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

-- 29.10.2016, 12:00 --

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

-- 29.10.2016, 12:04 --

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

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение29.10.2016, 16:24 


10/04/12
704
Рассмотрим пример из шахмат. Допустим мы ищем за чёрных ответ на 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 не уточняет насколько плоха худшая альтернатива.

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение31.10.2016, 23:47 


30/08/10
158
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. Хотя альфа это значения в ещё не полностью просчитанных узлах, они показываются, а бета тоже должны как-то отображаться, наверное.

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение01.11.2016, 12:07 
Заслуженный участник
Аватара пользователя


01/09/13
4318
Tookser в сообщении #1164822 писал(а):
Без значений альфа и бета не очень понятно.

В принципе, всё есть в вершинах выше по дереву... :-)
Tookser в сообщении #1164822 писал(а):
бета тоже должны как-то отображаться, наверное.

А зачем? ;-)

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

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

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение01.11.2016, 15:24 


10/04/12
704
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$).

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение03.11.2016, 04:33 


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

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

 Профиль  
                  
 
 Re: Альфа-бета отсечение
Сообщение03.11.2016, 16:38 


10/04/12
704
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$.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group