Минимаксная процедура с alpha и beta отсечениями

@VladSharikov · Регистрация: 02.12.2010

Студворк — интернет-сервис помощи студентам

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

Дан простой граф:

Минимаксная процедура с alpha и beta отсечениями

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

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

Когда применять минимаксную процедуру? Одногруппник пытается впарить, что нужно сначала пройти по всему дереву решений (обычный минимакс), а потом отсекать, да еще и как-то сверху вниз. Даже слушать не стал, ибо показалось бредом. Ведь мы же юзаем минимакс с отсечениями для ускорения поиска решения, отсекая заведомо неоптимальные варианты. Рассудите, пожалуйста.

P.S.: а AI тут нет?

@wingblack · 19.05.2014, 10:44

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

Сообщение от VladSharikov

P.S.: а AI тут нет?

Минимакс можно использовать для написания AI.
Вики: компьютерные шахматы

@VladSharikov · 19.05.2014, 18:30 **[ТС]**

Сообщение от wingblack

Минимакс можно использовать для написания AI.

Не так немного спросил — непонятно.

Я имел в виду то, что Artfical Intellegence тут нет подфорума? Это как раз туда скорее.

Сообщение от wingblack

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

Я правильно понимаю? "Голый" минимакс. Просто берем наш граф, выбираем полностью решаем 2 снизу ряд вершин (выбираем минимальное/максимальное, в данном случае МИНимальное) из их потомков. Затем 3 ряд решаем (3 снизу) — выбирается максимальное из их потомков. Правильно?

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

Мы же решаем эту задачу снизу вверх? И минимакс просто, и минимакс с отсечениями. Так ведь?

Мне кажется вот очень хороший пример:

(который нифига не работает тут, на киберфоруме — гифка. Просмотреть можно нажатием на него и просмотром в оригинальном размере).

Как раз здесь (нижние цифры не видно), сначала выбирается что-то из нижних цифр, которые мы не видим. При этом заполняется альфа — максимальное число из выбранных. Как только потомки у вершины кончились, то присваиваем вершине, потомков которой мы рассматривали, получившееся альфа, бета делаем равной альфа, бета сбрасываем. Проходим по второй ветви, пишем в альфа текущее из правой ветви. Если вдруг альфа стала больше бета, то отсекаем остальные вершины (считай просто перестаем рассматривать потомков вершины (правый кружочек)), делаем бета = альфа, альфа обнуляем и т.д. Если бы альфа не стало бы больше бета, то мы бы все таки просмотрели всех потомков правого кружочка, определились бы с финальным альфа. Далее видимо, выбирали мы минимальное, ибо в итоге 7 записали в верхний ромб. И т.д.

Что это в итоге есть? Это часом не обычный обход дерева? Как-то нет, кажется... Хотя... Вот бывают такие варианты обхода деревьев (с алголиста):
В прямом порядке
Симметричный
В обратном порядке
В ширину

У обхода в обратном порядке есть такое примечание:

Узлы посещаются 'снизу вверх'.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддерево
Обойти правое поддерево
Посетить узел

Кажется, это похоже на то, что показывается на картинке?

Или же есть примечание для Симметричного обхода:

Посещаем сначало левое поддерево, затем узел, затем - правое поддерево.

Для корня дерева рекурсивно вызывается следующая процедура:

Обойти левое поддерево
Посетить узел
Обойти правое поддерево

Единственное, здесь нету примечания "обход с нижних вершин" к верхним. Хотя это тоже похоже на то, что мне нужно.

@wingblack · 19.05.2014, 19:48

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

На вики дается вот такой алгоритм

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
01 function alphabeta(node, depth, α, β, maximizingPlayer)
      if depth = 0 or node is a terminal node
          return the heuristic value of node
      if maximizingPlayer
          for each child of node
              α := max(α, alphabeta(child, depth - 1, α, β, FALSE))
              if β ≤ α
                  break (* β cut-off *)
          return α
     else
         for each child of node
             β := min(β, alphabeta(child, depth - 1, α, β, TRUE))
             if β ≤ α
                 break (* α cut-off *)
         return β

http://en.wikipedia.org/wiki/A... ta_pruning
http://ru.wikipedia.org/wiki/%... 1%82%D1%8B

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

@VladSharikov · 20.05.2014, 02:17 **[ТС]**

wingblack, чем инициализируется функция alphabeta?

Добавлено через 5 часов 28 минут
wingblack, да, пасибо, что мордой тыкнули в вики, как-то я не додумался (я про английскую).

Искал искал. Часа три искал. Потом еще часа 2. Потом плюнул, переписал псевдокод на вики в JS — сейчас наслаждаюсь рабочей прогой.

Profit.

На бумаге прорешал минимаксом — сошлось, минимаксом с отсечениями — тоже самое, все сошлось. ПК, мои руки и мои руки с отсечениями считают одинаково

Спасибо за ссылочку.

Осталось прикрутить интерфейс.

Код даже выкладывать не буду — все есть в вики.

@wingblack · 20.05.2014, 20:54

Сообщение от VladSharikov

wingblack, чем инициализируется функция alphabeta?

На вики там же указано как рекурсивная функция запускается.
На ютубе видел что для инициализации альфа-бэта используется плюс и минус бесконечность.

@VladSharikov · 22.05.2014, 00:00 **[ТС]**

Сообщение от wingblack

На вики там же указано как рекурсивная функция запускается.

Указано. Неясно было, что такое depth: ну да, глубина, ну и что? Методом тыка понял, что это. Сразу не понял, что за origin, почему не root? Разобрался уже с этим моментом.

Сообщение от wingblack

На ютубе видел что для инициализации альфа-бэта используется плюс и минус бесконечность.

Это и на вики указано, с этим проблем нет.

У меня следующий вопрос. Все не как у людей

Мне нужно сделать визуализацию результата работы алгоритма. Мне надо нарисовать граф и показать, какие вершины отсекаются и т.д.

Вот есть код:

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
function alphabeta(node, depth, alpha, beta, isMax, g) {
    if((depth == 0) || (node.isTerminal == true)) {
        return node.value;
    }
    if(isMax) {
        console.log('maximizing');
        for (var i in node.children) {
            var child = node.children[i];
            console.log(child);
            alpha = Math.max(alpha, alphabeta(child, depth-1, alpha, beta, false, g));
            if(beta <= alpha) {
                console.log('beta '+beta+' alpha '+alpha);
                break;
            }
        }
 
        return alpha;
    } else {
        console.log('minimizing');
        for (var i in node.children) {
            console.log('1 child');
            var child = node.children[i];
            console.log(child);
            beta = Math.min(beta, alphabeta(child, depth-1, alpha, beta, true, g));
            if (beta <= alpha) {
                console.log('beta '+beta+' alpha '+alpha);
                break;
            }
        }
 
        return beta;
    }
}

Это JavaScript. На самом деле все тоже самое, что и в псевдокоде с вики. Давайте его прикреплю, скорее всего Вам так будет понятнее:

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 function alphabeta(node, depth, alpha, beta, maximizingPlayer)
      if depth = 0 or node is a terminal node
          return the heuristic value of node
      if maximizingPlayer
          for each child of node
              alpha := max(alpha, alphabeta(child, depth - 1, alpha, beta, FALSE))
              if beta <= alpha
                  break (* beta cut-off *)
          return alpha
      else
          for each child of node
              beta := min(beta, alphabeta(child, depth - 1, alpha, beta, TRUE))
              if beta <= alpha
                  break (* alpha cut-off *)
          return beta

Вот примерно так же выглядит нарисованное дерево в начале:

Мне нужно заполнить все вершины (или не заполнить, в случае, если ветвь отсеклась) и показать отсечения. Вопрос не в том, как это сделать на JS, вопрос в том, как перенести результат работы алгоритма на граф, то есть когда что выводить и куда. Я полагаю, в этом помогут alpha и beta. Можете это прояснить, пожалуйста?

@wingblack · 24.05.2014, 14:27

думаю, что в местах где break метить узел и все поддерево для отсечения

@VladSharikov · 25.05.2014, 18:45 **[ТС]**

wingblack, допустим, спасибо.

А в узлы что писать и где? Там же где break? alpha и beta выводить нужно? Или как? Я не очень этот момент понимаю что-то

@wingblack · 25.05.2014, 19:52

Сообщение от VladSharikov

break (* alpha cut-off *)

это обозначает что нужно провести отсечение

если тебе нужна по альфа-бэта - то выводи

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

@VladSharikov · 25.05.2014, 20:27 **[ТС]**

Попробовал сделать то, что Вы сказали. Вот результат:

Не получилось :'(

Вывод в условиях перед break:

JavaScript
1
2
3
4
5
if(beta <= alpha) {
    console.log('beta '+beta+' alpha '+alpha);
    g.nodes[node.name].shape.items["1"].attr("text", alpha);
    break;
}

и во второй части:

JavaScript
1
2
3
4
5
if (beta <= alpha) {
    console.log('beta '+beta+' alpha '+alpha);
    g.nodes[node.name].shape.items["1"].attr("text", beta);
    break;
}

@wingblack · 26.05.2014, 12:16

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

@VladSharikov · 29.05.2014, 11:25 **[ТС]**

Вот результат работы алгоритма:

Этого я достиг при этом коде. Ссылка на гитхаб, желтым выделена добавленная строчка.

Другой вопрос как сделать вывод нужных значений в нужные узлы дерева.

Я попытался вывести alpha и beta перед return alpha и return beta соответственно, но это привело к плохому результату

К неправильному. Что в общем-то не удивительно, потому что никаких сбросов alpha и beta нет, следовательно если в самой левой ветви дерева самое маленькое из возможных alpha, то оно будет тянуться по всем ветвям и запишется туда. В общем что говорить, лучше 1 раз показать. Вот результат такого вывода:

Вот проблемные места, по которым видно, что что-то тут не так:

Почему у первой стрелочки минимальное из 7 и 6 вдруг стало 5? У второй стрелки: как вдруг из 4, 3 и 2 выбралось 5 как максимальное. Что-то тут не так...

Да и вообще страшно предполагать теперь насколько каждая из вершин отображена правильно.

Это результат работы такого кода. Ссылка все туда же, желтым выделено новое по отношению к предыдущему сниппету.
P.S.: ссылка показывает только одну строку, забыл, что тут нельзя выделить сразу две строчки. Вторая строка в конце такого же блока во втором блоке.

Что касаемо логов, то их нет. Что именно выводить нужно, чтобы получить логи работы алгоритма и где? Я выведу.

Вообще по работе алгоритма моего... Зеленый цвет показывает, что идет-то он похоже правильно и обходит все так, как надо и отсекает правильно, так ведь? Но проблема с выводом значений в неконцевые узлы. Как уже писалось выше, скорее всего где-то нужно сбрасывать значения Alpha и Beta или же, скорее всего, добавить какое-то доп. значение и сбрасывать его, чтобы не ломать сам алгоритм.

@wingblack · 29.05.2014, 13:20

Сообщение от VladSharikov

Другой вопрос как сделать вывод нужных значений в нужные узлы дерева.

А разве у тебя в функцию не передается нода ? в эту ноду и выводить.
Да, на рисунке есть ноды без цифр, так же быть не должно?

Сообщение от VladSharikov

Что касаемо логов, то их нет. Что именно выводить нужно, чтобы получить логи работы алгоритма и где? Я выведу.

Сделай вывод логов в текстовом виде, что пришло, что получили, какое отсечение. В общем все что нужно чтобы понять откуда берутся цифры, также для дебага сделать вывод номеров нод и на график и в логах, чтобы было проще ориентироваться в ходе алгоритма.
console.log('beta '+beta+' alpha '+alpha);
А это куда пишет ?
На крайний случай - запись в переменную, которую потом вывести в код страницы.

@VladSharikov · 29.05.2014, 13:40 **[ТС]**

А разве у тебя в функцию не передается нода ? в эту ноду и выводить.

Забыл уточнить. А что выводить то)

Пишу с телефона, не очень удобно цитировать. По поводу узлов без цифр - дак они отсечены, поэтому и без цифр и без цвета.

А по поводу логов - вечером буду дома, попробую что-то сделать, но разобраться будет нереально, ибо ресурсия. Я уже пытался. Попробую, как дома буду.

@wingblack · 29.05.2014, 19:17

На графе выводить в числа в каждую ноду, а то в последнем рисунке цифры были не везде

Добавить в рекурсию инкрементацию глобальной переменной, которую и выводить вместе с остальной информацией для дебага ?

@VladSharikov · 29.05.2014, 21:10 **[ТС]**

Сообщение от wingblack

а то в последнем рисунке цифры были не везде

И правильно, что не везде цифры — ветви без цифр - отсечены.

Сообщение от wingblack

Добавить в рекурсию инкрементацию глобальной переменной, которую и выводить вместе с остальной информацией для дебага ?

Сделал немного по другому... И в общем-то все сходится

До места, где начинают выводится неверные значения.

Вот результат:

P.S.: Красным и синим отмечены узлы, которые считают минимальное из своих детей и максимальное из своих детей: maximizing - синий, minimizing - красный.

Вот лог достижения этого результата:

P.S.: В логе фигурируют названия узлов — min1, max23, min223 и т.д. На самом деле все просто... Но вот еще картинка, чтобы понять это было легче:

P.P.S: В логе встретится ****** — с этого момента начинают неправильно выводится значения, значение конечного узла 7, а бета остается 5, значение 6, а бета остается 5. Что в общем-то неудивительно и я, кажется, уже предполагал в чем проблема — alpha и beta тянутся с самой левой ветви и до конца. Надо что-то придумывать для того, чтобы выводились правильные значения в узлы. В этом и вопрос — что?

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
maximizing (root)
minimizing (min1)
maximizing (max11)
minimizing (min111)
getting value from terminal node node1 (value is 5)
beta value is set to 5
getting value from terminal node node2 (value is 4)
beta value is set to 4
returning beta, node min111 value is set as 4
going back to node max11
alpha value is set to 4
minimizing (min112)
getting value from terminal node node3 (value is 7)
beta value is set to 7
getting value from terminal node node4 (value is 5)
beta value is set to 5
returning beta, node min112 value is set as 5
going back to node max11
alpha value is set to 5
minimizing (min113)
getting value from terminal node node5 (value is 3)
beta value is set to 3
alpha cut-off (3<=5), others children wouldn't be visited
returning beta, node min113 value is set as 3
going back to node max11
alpha value is set to 5
returning alpha, node max11 value is set as 5
going back to node min1
beta value is set to 5
maximizing (max12)
minimizing (min121)
**************************
getting value from terminal node node8 (value is 7)
beta value is set to 5
getting value from terminal node node9 (value is 6)
beta value is set to 5
returning beta, node min121 value is set as 5
going back to node max12
alpha value is set to 5
beta cut-off (5<=5), others children wouldn't be visited
returning alpha, node max12 value is set as 5
going back to node min1
beta value is set to 5
returning beta, node min1 value is set as 5
going back to node
alpha value is set to 5
minimizing (min2)
maximizing (max21)
minimizing (min211)
getting value from terminal node node15 (value is 8)
beta value is set to 8
getting value from terminal node node16 (value is 7)
beta value is set to 7
getting value from terminal node node17 (value is 9)
beta value is set to 7
returning beta, node min211 value is set as 7
going back to node max21
alpha value is set to 7
returning alpha, node max21 value is set as 7
going back to node min2
beta value is set to 7
maximizing (max22)
minimizing (min221)
getting value from terminal node node18 (value is 4)
beta value is set to 4
alpha cut-off (4<=5), others children wouldn't be visited
returning beta, node min221 value is set as 4
going back to node max22
alpha value is set to 5
minimizing (min222)
getting value from terminal node node20 (value is 3)
beta value is set to 3
alpha cut-off (3<=5), others children wouldn't be visited
returning beta, node min222 value is set as 3
going back to node max22
alpha value is set to 5
minimizing (min223)
getting value from terminal node node22 (value is 2)
beta value is set to 2
alpha cut-off (2<=5), others children wouldn't be visited
returning beta, node min223 value is set as 2
going back to node max22
alpha value is set to 5
returning alpha, node max22 value is set as 5
going back to node min2
beta value is set to 5
alpha cut-off (5<=5), others children wouldn't be visited
returning beta, node min2 value is set as 5
going back to node
alpha value is set to 5
minimizing (min3)
maximizing (max31)
minimizing (min311)
getting value from terminal node node29 (value is 2)
beta value is set to 2
alpha cut-off (2<=5), others children wouldn't be visited
returning beta, node min311 value is set as 2
going back to node max31
alpha value is set to 5
minimizing (min312)
getting value from terminal node node31 (value is 5)
beta value is set to 5
alpha cut-off (5<=5), others children wouldn't be visited
returning beta, node min312 value is set as 5
going back to node max31
alpha value is set to 5
returning alpha, node max31 value is set as 5
going back to node min3
beta value is set to 5
alpha cut-off (5<=5), others children wouldn't be visited
returning beta, node min3 value is set as 5
going back to node
alpha value is set to 5
returning alpha, node root value is set as 5
going back to node null

@VladSharikov · 29.05.2014, 21:56 **[ТС]**

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

Код тут.

А вот результат:

Вот, что стало отображаться правильно:

Но уровнем выше те же проблемы:

Что-то делаю не так.

@wingblack · 29.05.2014, 23:43

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

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

@VladSharikov · 30.05.2014, 00:51 **[ТС]**

Сообщение от wingblack

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

wingblack, Вы прям как моя девушка — она мне тоже самое пытается доказать, но я непоколебим.

Давайте рассуждать вместе:

Зачем нужен minimax? Минимаксная процедура? Я не про какое-то сложное определение и проекцию на шахматы или крестики-нолики или крестики-нолики-пять-в-ряд, а про пример выше. Вот есть данный граф (понятно, что это пример, но все же). Минимакс мы применяем для того, чтобы найти корень — значение узла на самом верхнем уровне.

А зачем нужен AlphaBeta (оптимизация минимакса)? Затем, чтобы найти корень.

Минимакс займет, к примеру, 10 минут — просто, например. А альфабета — 3 минуты. Это хорошо. Вместо 3 тратим 10.

Вы предлагаете выполнить минимаксную процедуру, а затем выполнить ее оптимизацию и потратить 10+3 минуты = 13 минут. Какая тут оптимизация? Я вот это себе твержу и стою на своем. Разве неправильно думаю?

Вот Вы же сами приводили пример с шахматами. Полного дерева решений мы не получим никогда — не хватит памяти, ибо комбинаций нереально много, поэтому там мы применяем не минимакс, а альфабета. Согласитесь, там же не надо каждый узел раскрывать (да и не сможем)? А чем мой пример отличается? Тоже самое, но кол-во узло и глубина не миллионы и десятки тысяч, а ~50 и 4.

Или я неправильно думаю?

Вот логи с текущей вершиной (к сожалению через строку, очень знаете ли неудобно убирать каждый пробел. Или регулярку на возврат на предыдущую строку подскажете?

):

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
root — maximizing (root)
 
min1 — minimizing (min1)
 
max11 — maximizing (max11)
 
min111 — minimizing (min111)
 
node1 — getting value from terminal node node1 (value is 5)
 
min111 — beta value is set to 5
 
node2 — getting value from terminal node node2 (value is 4)
 
min111 — beta value is set to 4
 
min111 — returning beta, node min111 value is set as -999
 
min111 — going back to node max11
 
max11 — alpha value is set to 4
 
min112 — minimizing (min112)
 
node3 — getting value from terminal node node3 (value is 7)
 
min112 — beta value is set to 7
 
node4 — getting value from terminal node node4 (value is 5)
 
min112 — beta value is set to 5
 
min112 — returning beta, node min112 value is set as 4
 
min112 — going back to node max11
 
max11 — alpha value is set to 5
 
min113 — minimizing (min113)
 
node5 — getting value from terminal node node5 (value is 3)
 
min113 — beta value is set to 3
 
min113 — alpha cut-off (3<=5), others children of max11 wouldn't be visited
 
min113 — returning beta, node min113 value is set as 5
 
min113 — going back to node max11
 
max11 — alpha value is set to 5
 
max11 — returning alpha, node max11 value is set as 5
 
max11 — going back to node min1
 
min1 — beta value is set to 5
 
max12 — maximizing (max12)
 
min121 — minimizing (min121)
 
node8 — getting value from terminal node node8 (value is 7)
 
min121 — beta value is set to 5
 
node9 — getting value from terminal node node9 (value is 6)
 
min121 — beta value is set to 5
 
min121 — returning beta, node min121 value is set as -999
 
min121 — going back to node max12
 
max12 — alpha value is set to 5
 
max12 — beta cut-off (5<=5), others children of min1 wouldn't be visited
 
max12 — returning alpha, node max12 value is set as 5
 
max12 — going back to node min1
 
min1 — beta value is set to 5
 
min1 — returning beta, node min1 value is set as -999
 
min1 — going back to node
 
root — alpha value is set to 5
 
min2 — minimizing (min2)
 
max21 — maximizing (max21)
 
min211 — minimizing (min211)
 
node15 — getting value from terminal node node15 (value is 8)
 
min211 — beta value is set to 8
 
node16 — getting value from terminal node node16 (value is 7)
 
min211 — beta value is set to 7
 
node17 — getting value from terminal node node17 (value is 9)
 
min211 — beta value is set to 7
 
min211 — returning beta, node min211 value is set as 5
 
min211 — going back to node max21
 
max21 — alpha value is set to 7
 
max21 — returning alpha, node max21 value is set as 7
 
max21 — going back to node min2
 
min2 — beta value is set to 7
 
max22 — maximizing (max22)
 
min221 — minimizing (min221)
 
node18 — getting value from terminal node node18 (value is 4)
 
min221 — beta value is set to 4
 
min221 — alpha cut-off (4<=5), others children of max22 wouldn't be visited
 
min221 — returning beta, node min221 value is set as 5
 
min221 — going back to node max22
 
max22 — alpha value is set to 5
 
min222 — minimizing (min222)
 
node20 — getting value from terminal node node20 (value is 3)
 
min222 — beta value is set to 3
 
min222 — alpha cut-off (3<=5), others children of max22 wouldn't be visited
 
min222 — returning beta, node min222 value is set as 5
 
min222 — going back to node max22
 
max22 — alpha value is set to 5
 
min223 — minimizing (min223)
 
node22 — getting value from terminal node node22 (value is 2)
 
min223 — beta value is set to 2
 
min223 — alpha cut-off (2<=5), others children of max22 wouldn't be visited
 
min223 — returning beta, node min223 value is set as 5
 
min223 — going back to node max22
 
max22 — alpha value is set to 5
 
max22 — returning alpha, node max22 value is set as 5
 
max22 — going back to node min2
 
min2 — beta value is set to 5
 
 
min2 — alpha cut-off (5<=5), others children of  wouldn't be visited
 
 
min2 — returning beta, node min2 value is set as 5
 
min2 — going back to node
 
root — alpha value is set to 5
 
min3 — minimizing (min3)
 
max31 — maximizing (max31)
 
min311 — minimizing (min311)
 
node29 — getting value from terminal node node29 (value is 2)
 
min311 — beta value is set to 2
 
min311 — alpha cut-off (2<=5), others children of max31 wouldn't be visited
 
min311 — returning beta, node min311 value is set as 5
 
min311 — going back to node max31
 
max31 — alpha value is set to 5
 
min312 — minimizing (min312)
 
node31 — getting value from terminal node node31 (value is 5)
 
min312 — beta value is set to 5
 
min312 — alpha cut-off (5<=5), others children of max31 wouldn't be visited
 
min312 — returning beta, node min312 value is set as 5
 
min312 — going back to node max31
 
max31 — alpha value is set to 5
 
max31 — returning alpha, node max31 value is set as 5
 
max31 — going back to node min3
 
min3 — beta value is set to 5
 
 
min3 — alpha cut-off (5<=5), others children of  wouldn't be visited
 
 
min3 — returning beta, node min3 value is set as 5
 
min3 — going back to node
 
root — alpha value is set to 5
 
root — returning alpha, node root value is set as 5
 
root — going back to node null

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824

	Минимаксная процедура с alpha и beta отсечениями 18.05.2014, 14:38. Показов 7703. Ответов 20 Метки нет (Все метки) Необходимо построить программу, которая бы реализовывала минимаксную процедуру. Дан простой граф: На нем нужно реализовать минимаксную процедуру. Для начала хочу сделать это на бумаге, ибо быдлокодить, без понимания алгоритма смысла нет совсем. Для чего нужна минимаксная процедура? Я полагаю, она нужна для того, чтобы ускорить поиск по дереву решений (в данном случае мой граф не огромный, но это просто пример, на самом деле это может быть игра в шахматы, где количество комбинаций не умещается в памяти компьютера). Это так? Когда применять минимаксную процедуру? Одногруппник пытается впарить, что нужно сначала пройти по всему дереву решений (обычный минимакс), а потом отсекать, да еще и как-то сверху вниз. Даже слушать не стал, ибо показалось бредом. Ведь мы же юзаем минимакс с отсечениями для ускорения поиска решения, отсекая заведомо неоптимальные варианты. Рассудите, пожалуйста. P.S.: а AI тут нет? 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	20.05.2014, 02:17 [ТС]
	wingblack, чем инициализируется функция alphabeta? Добавлено через 5 часов 28 минут wingblack, да, пасибо, что мордой тыкнули в вики, как-то я не додумался (я про английскую). Искал искал. Часа три искал. Потом еще часа 2. Потом плюнул, переписал псевдокод на вики в JS — сейчас наслаждаюсь рабочей прогой. Profit. На бумаге прорешал минимаксом — сошлось, минимаксом с отсечениями — тоже самое, все сошлось. ПК, мои руки и мои руки с отсечениями считают одинаково Спасибо за ссылочку. Осталось прикрутить интерфейс. Код даже выкладывать не буду — все есть в вики. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	24.05.2014, 14:27
	думаю, что в местах где break метить узел и все поддерево для отсечения 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	25.05.2014, 18:45 [ТС]
	wingblack, допустим, спасибо. А в узлы что писать и где? Там же где break? alpha и beta выводить нужно? Или как? Я не очень этот момент понимаю что-то 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	26.05.2014, 12:16
	Выведи значения альфа-бэта на всех узлах Пометь узлы где происходит отсечение более явно - смена цвета или формы. Также дай логи работы алгоритма. 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	29.05.2014, 11:25 [ТС]
	Вот результат работы алгоритма: Этого я достиг при этом коде. Ссылка на гитхаб, желтым выделена добавленная строчка. Другой вопрос как сделать вывод нужных значений в нужные узлы дерева. Я попытался вывести alpha и beta перед return alpha и return beta соответственно, но это привело к плохому результату К неправильному. Что в общем-то не удивительно, потому что никаких сбросов alpha и beta нет, следовательно если в самой левой ветви дерева самое маленькое из возможных alpha, то оно будет тянуться по всем ветвям и запишется туда. В общем что говорить, лучше 1 раз показать. Вот результат такого вывода: Вот проблемные места, по которым видно, что что-то тут не так: Почему у первой стрелочки минимальное из 7 и 6 вдруг стало 5? У второй стрелки: как вдруг из 4, 3 и 2 выбралось 5 как максимальное. Что-то тут не так... Да и вообще страшно предполагать теперь насколько каждая из вершин отображена правильно. Это результат работы такого кода. Ссылка все туда же, желтым выделено новое по отношению к предыдущему сниппету. P.S.: ссылка показывает только одну строку, забыл, что тут нельзя выделить сразу две строчки. Вторая строка в конце такого же блока во втором блоке. Что касаемо логов, то их нет. Что именно выводить нужно, чтобы получить логи работы алгоритма и где? Я выведу. Вообще по работе алгоритма моего... Зеленый цвет показывает, что идет-то он похоже правильно и обходит все так, как надо и отсекает правильно, так ведь? Но проблема с выводом значений в неконцевые узлы. Как уже писалось выше, скорее всего где-то нужно сбрасывать значения Alpha и Beta или же, скорее всего, добавить какое-то доп. значение и сбрасывать его, чтобы не ломать сам алгоритм. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	29.05.2014, 19:17
	На графе выводить в числа в каждую ноду, а то в последнем рисунке цифры были не везде Добавить в рекурсию инкрементацию глобальной переменной, которую и выводить вместе с остальной информацией для дебага ? 0

@VladSharikov 25 / 25 / 7 Регистрация: 02.12.2010 Сообщений: 824
	29.05.2014, 21:56 [ТС]
	Немного обновил код, попытался добавить переменную, которая, как я думал, помогла бы мне. Код тут. А вот результат: Вот, что стало отображаться правильно: Но уровнем выше те же проблемы: Что-то делаю не так. 0

@wingblack 294 / 265 / 48 Регистрация: 09.04.2013 Сообщений: 1,038
	29.05.2014, 23:43
	Eсли в логах в начале строки каждого вывода писать название текущей ноды, то будет более удобно понимать где сейчас алгоритм находится Снова в графе ноды без цифр - отсеченные ? У меня в голове пунктик что в альфа-бэта мы все равно должны пройти по всем нодам, разве нет ? 0

Минимаксная процедура с alpha и beta отсечениями

Решение