ИИ и 2048. Часть 2: Минимакс + альфа-бета отсечение

[roryorangepants]

К чему здесь хаб «машинное обучение»? Это же классические алгоритмы.

[valemak]

Кстати, да. Наверное, когда я этот хаб выбирал, думал про другой способ обучения компьютера стратегии игры в 2048, где как раз используется машинное обучение. Заменил на «VBA».

[valemak]

UPD. Добавил в статью ява-скриптовый код пользователя ovolve, описавшего на stackoverflow метод минимакса и заменил на хаб «JavaScript».

[Akon32]

Тогда уж лучше добавить хаб "Искусственный интеллект", и для первой части тоже. "Тестирование игр" и "Совершенный код" менее характеризуют тему.

[valemak]

Кажется, модераторы убрали хаб «JavaScript» (хотя именно java-script версия легла в основу этой хабрастатьи и ключевые участки этого кода в статье приводятся), так что, попробую на вакантное место поставить по Вашему совету хаб «Искусственный интеллект».

[neurocore]

Не хватает вывода о целесообразности использования альфа-беты здесь. Мне кажется монте-карло будет тут намного сильнее (из-за случайного характера выпадения 2-ек и 4-к).

[valemak]

На практике метод минимакса лучше.

Монте-Карло, в приципе, без труда доходит до 2048, очень редко до 4096, и почти никогда до 8192. При этом, неважно, насколько много случайных прогонов за раз ставить, это не сильно влияет на качество ходов.

Минимакс, в принципе, без особых затруднений достигает и 8192 если задать достаточно большую глубину поиска.

[neurocore]

Интересно. Я думал минимакс будет слабо играть из-за того, что формально выпадение 2-ки и 4-ки будут считаться как ходы соперника, а значит всегда будет выбираться наихудший вариант. Но похоже возымел обратный эффект — система «старается» выстраивать блоки так, чтобы затруднить плохой вброс очередного блока.

[Deosis]

Минимакс как раз старается минимизировать ущерб от ходов противника.

[neurocore]

Ну да, а значит пессимистичен. Вот если бы был соперник, который подкидывал эти блоки самым лучшим для себя способом, но вопросов нет — минимакс тут лучший. Но подкидывания случайны. Поэтому я подумал, что монте-карло может быть лучше, что не реализовалось на практике (вероятно из-за большой глубины просчёта минимакса)

[yasha_akimov]

Целесообразно располагать плитки змейкой, самая ценная в углу, так мы можем легко стакать плитки и доходить до 65536, а это уже максимально возможная плитка