Мінімакс і Прибирання Альфа-Бета: Дослідження Дерева, Якого Ніхто Не Може Завершити

Припустимо, що ваш опонент ідеальний

Мінімікс – це основний алгоритм пошуку для двоігральних нульових ігор з повною інформацією - крестики-нолики, шашки, шахи. Він будує дерево можливих майбутніх позицій, чергуючи між гравцем, який прагне отримати найвищий бал (максимізуючий гравець), та гравцем, який прагне отриграти найнижчий бал (мінімізуючий гравець), і оцінює кожну позицію, припускаючи, що обидва гравці завжди роблять найкраховий можливий хід з цієї точки зору.

Назва алгоритму точно описує його функціональність: кожен гравець мінімізує максимальний збиток, який може завдати інший гравець, або максимізує свій гарантований мінімальний результат, залежно від того, чи на черзі у нього грати.

minimax(node, depth, maximizingPlayer):
  if depth == 0 or node is terminal:
    return evaluate(node)
  if maximizingPlayer:
    value = −infinity
    for each child of node:
      value = max(value, minimax(child, depth−1, false))
    return value
  else:
    value = +infinity
    for each child of node:
      value = min(value, minimax(child, depth−1, true))
    return value

Експоненційний бар'єр

Звичайний мінімакс досліджує кожен вузол дерева, і розмір дерева вибухає як O(b^d), де b - це фактор розгалуження (приблизно 35 законних ходів у шаху) а d - це кількість ходів вперед, які ви оглядаєте. Навіть невелику глибину в 10 півхвилин у шаху вже означає дослідження порядку 35^10 позицій – набагато більше, ніж будь-який комп'ютер може відвідати, тому шахові двигуни ніколи не шукають до буквального кінця гри. Замість цього вони шукають до фіксованої глибини та замінюють справний результат на функцію евристичної оцінки, яка оцінює позицію за матеріали, безпеку короля, активність фігур тощо.

Альфа-бета: обрізання того, що не може мати значення

Обрізання альфа-бета пришвидшує мінімах без зміни їхньої відповіді, відстежуючи два обмеження під час пошуку: альфа, найкращий бал, який гарантовано отримав максимізатор будь-де в дереві, і бета, найкращий бал, який гарантовано отримав мінімізатор будь-де. Як тільки значення вузла виявиться за межами поточного (альфа, бета) вікна - тобто раціональний опонент ніколи не дозволить грі досягти його - всі наступні брати-близнюки цього вузла повністю пропускаються, оскільки незалежно від того, що вони оцінять, це не вплине на рішення на одному рівні вище.

alphabeta(node, depth, α, β, maximizingPlayer):
  if depth == 0 or node is terminal:
    return evaluate(node)
  if maximizingPlayer:
    value = −infinity
    for each child of node:
      value = max(value, alphabeta(child, depth−1, α, β, false))
      α = max(α, value)
      if α >= β: break        // β cutoff — rest of the siblings pruned
    return value
  else:
    value = +infinity
    for each child of node:
      value = min(value, alphabeta(child, depth−1, α, β, true))
      β = min(β, value)
      if β <= α: break        // α cutoff — rest of the siblings pruned
    return value

Однакова відповідь, значно менше роботи

Це властивість, яка робить альфа-бета обрізання безпечним у використанні скрізь, де використовується мінімакс: це не евристичний ярлик, а точна оптимізація. За однакової глибини пошуку та функції оцінки альфа-бета завжди повертає саме хід, який би знайшов звичайний мінімакс, оскільки кожен пропущений гілку доведено непотрібним, а не просто припускалося, що він неприбутковий. У найкращому випадку, коли рухи досліджуються в ідеальному порядку, альфа-бета зменшує ефективну розгалуження від b приблизно до √b, обрізаючи дерево з O(b^d) до приблизно O(b^(d/2)) - що на практиці означає пошук у два рази глибше для того ж обчислювального часу.

Порядок пошуку – це все

Розмір прискорення залежить повністю від порядку, в якому перевіряються ходи. Обрізання спрацьовує лише тоді, коли знайдено достатньо хорошу ходу, тому якщо найсильнішу ходу шукати першим, то (альфа, бета) вікно миттєво закривається і більшість із решти братів-близнюків обрізаються без оцінки. Шукайте слабку ходу першою, і вікно залишається відкритим, обрізання майже не спрацьовує, а продуктивність погіршується до звичайного неподільного мінімакс пошуку. Саме тому реальні двигуни значно інвестують у евристики порядку ходів – перевіряйте захоплення першими, першочерговість вже виявлених найкращих ходів, ‘вбивчих’ ходів, які викликали обрізання в братів-близнюків, оскільки хороший порядок часто вартий більше за будь-яку іншу оптимізацію загальної швидкості пошуку.

Frequently asked questions

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Minimax and Alpha-Beta Pruning і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.