mysimulator.uk
🔍 Пошук симуляцій…/
UK ▼
EnglishТиповаУкраїнськаPolski
Головна▸ Алгоритми та AI▸ Мінімакс і альфа-бета

♟️ Мінімакс і альфа-бета

DFS-обхід ігрового дерева за припущення оптимальної гри суперника; альфа-бета відсікання пропускає гілки, що не можуть вплинути. Дивіться, як вікно (α, β) звужується, відсічення сіріє піддерева, і порівнюйте відвідані листки.

Алгоритми та AI2DСкладний60 FPS
minimax-tree ↗ Відкрити окремо
DRAG · SCROLL · CLICK — керуйте прямо у вікні симуляції.

Схожі симуляції

3D Boids — Роїння500 агентів у 3D-просторі за правилами Рейнольдса: розділення, вирівнювання, зчеКолонія МурахСтигмергічна симуляція: мурашки знаходять їжу за феромонними шляхами.Пошук шляху — A*, Дейкстра, BFSМалюйте стіни, генеруйте лабіринти, спостерігайте за A*, Дейкстра, BFS у реально

Про мінімакс з альфа-бета відсіканням

Мінімакс — це рекурсивний алгоритм змагального пошуку, що використовується в двобічних іграх з нульовою сумою. Гравець MAX (наприклад, ШІ) намагається максимізувати евристичне значення стану гри, тоді як гравець MIN (суперник) намагається його мінімізувати; мінімакс виконує пошук углиб до листкових вузлів, а потім поширює значення вгору, чергуючи вибір максимуму та мінімуму на кожному рівні. Для ігрового дерева з коефіцієнтом розгалуження b і глибиною d наївний мінімакс обчислює O(b^d) вузлів — для шахів це астрономічно велике число.

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

Часті запитання

У чому різниця між чистим мінімаксом і альфа-бета відсіканням?

Чистий мінімакс відвідує кожен вузол, щоб обчислити правильне значення. Альфа-бета досягає того самого результату, пропускаючи гілки, які доведено не можуть змінити підсумок — лічильник «Cutoffs» показує, скільки їх було пропущено.

Чому порядок ходів впливає на обсяг відсікання?

Відсікання спрацьовує лише тоді, коли вже відоме хороше значення. Найкращий-перший порядок спершу досліджує перспективні дочірні вузли, швидше звужуючи вікно й викликаючи більше відсічень; випадковий порядок відсікає менше в середньому.

Що означають червоні та сині вузли?

Червоні вузли — це MAX, що намагається максимізувати результат; сині вузли — це MIN, що намагається його мінімізувати. Ці дві ролі чергуються на кожному рівні глибини.

Що відбувається з перекресленими гілками?

Щойно вікно α/β вузла закривається (β ≤ α), його ще не досліджені дочірні вузли пропускаються та малюються перекресленими пунктирною лінією, оскільки жодне їхнє значення не могло б змінити рішення батьківського вузла.

Чи впливають разом коефіцієнт розгалуження та глибина на час пошуку?

Так — загальна кількість листків приблизно дорівнює b у степені d, тож збільшення глибини на одиницю має подібний ефект до множення коефіцієнта розгалуження. Слідкуйте за «Nodes total» на панелі статистики.