Связано root для алгоритма альфа-бета-отсечения - PullRequest
Новая
       112

Связано root для алгоритма альфа-бета-отсечения

1 голос
/ 14 февраля 2020

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

Вот мой вывод терминала: 

eval A
min 2 min1 -9223372036854775807 10.0
eval B
min 2 min2 10.0 10.0
*** FAIL: test_cases/q3/6-tied-root.test
***     Incorrect generated nodes for depth=3
***         Student generated nodes: A B max min1 min2
***         Correct generated nodes: A B C max min1 min2
***     Tree:
***         max
***        /   \
***     min1    min2
***      |      /  \
***      A      B   C
***     10     10   0

Насколько я понял, однажды B оценивается, min2 увидит, что max не выберет ничего меньше 10, поэтому, даже если будет найдено меньшее значение (x <= 10), это не будет иметь значения. В этом случае min2 будет иметь стимул смотреть на C только если B больше 10. </p>

Заранее спасибо

1 Ответ

0 голосов
/ 18 февраля 2020

Насколько я понимаю, после оценки B min2 увидит, что max не выберет ничего меньше 10, поэтому даже если будет найдено меньшее значение (x <= 10), это не будет иметь значения. </p>

Это правильно и может быть проверено с помощью онлайн-симулятора (например, http://homepage.ufp.pt/jtorres/ensino/ia/alfabeta.html или https://raphsilva.github.io/utilities/minimax_simulator/):

image0,0,2,1,-1000,393.75,30,-1000,1000,-1,-1,undefined,1,1,1,3,1000,225,295,undefined,undefined,0,-1,undefined,2,1,2,4,1000,562.5,295,undefined,undefined,0,-1,undefined,3,2,0,-1,10,225,560,undefined,undefined,1,undefined,undefined,4,2,0,-1,10,450,560,undefined,undefined,2,undefined,undefined,5,2,0,-1,0,675,560,undefined,undefined,2,undefined,undefined,<">

min2 будет стимулировать смотреть на C, только если B больше 10.

Одинаково правильно:

image0,0,2,1,-1000,393.75,30,-1000,1000,-1,-1,undefined,1,1,1,3,1000,225,295,undefined,undefined,0,-1,undefined,2,1,2,4,1000,562.5,295,undefined,undefined,0,-1,undefined,3,2,0,-1,10,225,560,undefined,undefined,1,undefined,undefined,4,2,0,-1,12,450,560,undefined,undefined,2,undefined,undefined,5,2,0,-1,0,675,560,undefined,undefined,2,undefined,undefined,<">

min2 должны проверить C также, если A меньше 10.

Может ли будет неправильный контрольный пример?

...