TwiddleLab / Искусственный интеллект / Поиск, игры и планы
Минимакс
Что ты узнаешь
- Дай каждой концовке счёт: +1 за победу, -1 за поражение, 0 за ничью.
- Минимакс передаёт счета вверх по дереву: на твоих уровнях бери max, на уровнях соперника min.
- Значение наверху это то, что ты можешь гарантировать, как бы хорошо ни играл соперник.
- Правило вызывает само себя для каждого потомка: value(position) это рекурсивная функция.
Как идёт урок
Под ходом справа внизу есть выигрышная концовка для X. X ходит туда. Что сделает умный O?
Нажми на ответ O.
Смотри, как счета поднимаются по дереву.
Каждый уровень передаёт вверх один счёт: X берёт самый большой, O самый маленький.
Теперь с настоящими счетами. Чем больше, тем лучше для тебя.
Под каждым оранжевым узлом нажми на лист, который выберет соперник. Потом нажми на свой лучший ход.
В правой ветке есть 14, но соперник никогда тебе его не отдаст: он ответит 2. Левая ветка гарантирует 3, что бы ни делал соперник, и 3 это лучшая гарантия.
Такой способ выбора называется минимакс.
На своих уровнях бери max, на уровнях соперника min, от листьев до самого верха. Значение наверху это то, что ты можешь гарантировать против идеального соперника. Счёт позиции это её значение.
Теперь три уровня. Заполни дерево снизу.
Перетащи значение вверх к родителю. Фиолетовый оставляет самого большого потомка, оранжевый самого маленького.
Снизу вверх: max(4, 8) = 8, max(9, 3) = 9, max(2, 7) = 7, max(5, 6) = 6. Потом соперник берёт min(8, 9) = 8 и min(7, 6) = 6. Наверху ты берёшь max(8, 6) = 8.
Игра: обыграй бота-минимакса в палочки.
Бери 1 или 2 палочки за ход. Кто возьмёт последнюю палочку, тот выиграл. Первый ход твой. Бот обыскивает всё дерево.
Этот бот всё время попадает в ловушки. Исправь его правила.
Он играет ветку с самым большим листом. Нажми на фишку правила, чтобы переключить её.
С max на обоих уровнях бот надеется на 15 и играет среднюю ветку, где ты отвечаешь 1. С min на твоём уровне он видит, что середина стоит всего 1, и играет левую ветку, которая гарантирует 7.
Запиши минимакс как правило, которое может выполнить компьютер.
Перетащи слово в каждый пропуск. Правило применяет само себя к каждому потомку: в коде это рекурсивная функция.
value(position) спрашивает value(child) для каждого потомка, а тот спрашивает своих, вниз до концовок. Потом берётся max на твоём ходе и min на ходе соперника. Здесь наверху выходит 7. Функция, которая вызывает саму себя, рекурсивная; в треке cs её пишут на Python.
Какой счёт ты можешь гарантировать наверху этого дерева?
Фиолетовые уровни твои (max), оранжевые соперника (min).
Внизу: 5, 7, 9, 6. Соперник: min(5, 7) = 5 и min(9, 6) = 6. Наверху: max(5, 6) = 6.
Два идеальных бота играют в крестики-нолики. Кто выиграет?
Оба запускают минимакс по всему дереву с пустой доски.
Предыдущий урок: Деревья игр · Следующий урок: Оценка позиций: оценочные функции · Часть курса: Поиск, игры и планы
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
