TwiddleLab / Искусственный интеллект / Поиск, игры и планы
Монте-Карло: играем случайные партии
Что ты узнаешь
- Случайный доигрыш (rollout) заканчивает партию случайными ходами за обе стороны.
- Сыграй много таких для каждого хода и посчитай долю побед: это доля побед. Самый высокий столбик обычно хороший ход.
- Несколько партий скачут; много партий усредняются (закон больших чисел). Больше доигрышей, сильнее бот.
- Такой способ оценки по случайным пробам называется Монте-Карло. Ему не нужны ни стратегия, ни правило оценки.
Как идёт урок
В го слишком много ходов для минимакса, а хорошие правила оценки писать трудно. А если просто доигрывать случайные партии до конца?
Ходит X. Ставка: какой ход выиграет больше всего партий, если потом обе стороны играют совсем наугад?
Возьми один ход и играй из него случайные партии.
Сыграй 1, чтобы посмотреть партию. Потом 10, потом 100. Следи за столбиком.
Теперь дай каждому ходу по 100 случайных партий и выбери лучший.
Фиолетовая часть это доля партий, которые выиграл X.
Левый нижний угол перекрывает диагональ O, поэтому O не может выиграть сразу, а у X остаются шансы на победу. После других ходов случайный O часто находит диагональ. Бот ничего этого не знает: он только считает результаты.
Это называется поиском Монте-Карло.
Случайный доигрыш (rollout) заканчивает партию наугад. Доля доигрышей, которые выигрывает ход, это его доля побед. Оценка чего-то по многим случайным пробам называется Монте-Карло, в честь казино.
Ход выиграл 62 из своих 100 случайных партий. Какая у него доля побед?
62 победы из 100 партий это 62 / 100 = 0,62, или 62%. При 50 партиях было бы победы / 50.
Сколько случайных партий нужно боту?
Задай число партий на ход, потом перезапусти 5 раз. Найди число, при котором каждый перезапуск выбирает лучший ход.
Каждая доля побед это среднее случайных результатов. Мало партий дают шумное среднее, которое скачет между перезапусками. Много партий дают устойчивое: это закон больших чисел. Тогда лучший ход побеждает каждый раз.
Игра: сыграй против ботов Монте-Карло.
Сначала бот с 10 случайными партиями на ход: обыграй его. Потом бот с 300: не проиграй.
Небрежный бот пробовал одни ходы чаще других. Какой ход ему сыграть?
Смотри на долю побед и на то, по скольким партиям она посчитана.
Доля побед по одной партии это чистая удача: с тем же успехом могло быть 0%. 68 побед из 100 партий это надёжная оценка. Хороший бот Монте-Карло даёт каждому ходу достаточно партий, прежде чем доверять числам.
Тот же трюк, новая задача: оцени число пи случайными дротиками.
Бросай дротики наугад. Считай, сколько попадает внутрь четверти круга.
Предыдущий урок: Альфа-бета: пропусти лишнее · Следующий урок: Планирование: от цели к шагам · Часть курса: Поиск, игры и планы
Уроки интерактивные и работают на JavaScript. Включи его, чтобы играть.
