Анализ 2048 3 на 3

[wataru]

Единственный вопрос, как понять, в каком порядке обходить вершины?

Ведь каждый раз после хода игрока в случайной (или худшей) клетке появляется 2 или 4. А значит общая сумма очков на поле увеличится. Поэтому все поля топологически упорядочены по сумме очков. Тут нет циклов. Поэтому тут вообще работает динамика. Если бы были циклы, то пришлось бы решать систему линейных уравнений для поиска матожидания.

Простой способ не думать о порядке, это реализовать динамику сверху вниз, через рекурсию от начального состояния. Это просто пустое поле.

Не совсем понял, как вы тут применяете 1-2-bfs. Можно по-подробнее? Предполагаю, что это у вас топологическая сортировка снизу-вверх. Так тоже можно. Но проще же отсортировать все тупо по сумме очков. Можно даже подсчетом за линию.

Еще, если рассматривать "злобную" клетку, то у вас получается игра двух игроков - один сдвигает поле, другой кидает в пустую клетку 2 или 4. Первый максимизирует сумму, второй минимизирует. Тут уже можно рассматривать не матожидание, а минимакс: какое максимальное количество очков может себе гарантировать первый игрок.

Еще вопрос, когда вы считаете, что игра остановилась?

Проводили ли вы какую-то дедупликацию состояний, вроде поворотов/отражений? Казалось, бы если гравитационный ход заменить на поворот и всегда падение вниз, то все состояния будут сильно более похожи: всего 4^3 вариантов какие клетки вообще могут быть заполнены, в каждом столбе количество очков должно различатся у соседних клеток.

[ilia-ili-ilya]

Да, про bfs не совсем точно написал, он нам нужен скорее не для порядка обхода, а чтобы понять какие вершины вообще достижимы, запускать динамику вообще на всех слишком долго. Дедуплицировать состояния действительно можно, выигрыш где-то в 5 раз должен быть (потому что 4 поворота + 2 отражения, но какие-то позиции сами в себя переходят), но потом не очень удобно пользоваться таким предподсчетом

[wataru]

а чтобы понять какие вершины вообще достижимы

И зачем там 1-2-bfs а не просто bfs?

Если запускать динамику рекурсивно, она сама только достижимые и обойдет.

[ilia-ili-ilya]

1-2-bfs нужен, потому что у нас есть ребра с весами 1 и 2 (когда добавляется плитка 2 и когда добавляется плитка 4). Рекурсивно запускать динамику тоже решение, вполне можно и так

[wataru]

Если вы его используете для поиска достижимых вершин, веса ребер вам вообще безразличны.

Видимо, вы его используете для подсчета суммарных очков в поле и получения их в порядке возрастания, т.е. это не стандартная топологическая сортировка через bfs снизу-вверх, а сортировка вершин по расстоянию от начала через обход сверзу-вниз, которая гарантирует топологический порядок. Так?

[ilia-ili-ilya]

Всё так и есть, после bfs-а мы получаем отсортированный по расстоянию список достижимых вершин, а потом запускаем на нем динамику

[wataru]

Только сейчас заметил, у вас rand-angry иногда даже лучше best-angry. Какое же оно тогда best? Что-то у вас явно не так, раз есть стратегия набирающая больше очков оптимальной.

Потому что, как я выше писал, в случае злодея надо оценивать не матожидание а тупо финальный счет. Игрок выбирает ход с максимальной оценкой, злыдень - с минимальной.

Если по дереву ходов где-то внизу расходятся рядом есть очень плохой путь и очень хороший, то игрок-то этот очень плохой никогда не выберет. Но при счите матожидания, этот плохой путь портит оценку хода в начале и ваша best стратегия выбирает средний вариант, потому что рядом с ним не было варианта сильно ошибиться.

А в случае случайных клеток, надо считать матожидание только по выбору новой клетки и никак не по движению. Игрок выбирает одно из 4 направлений минимизируя оценку. Матожидание только по случайной величине делается, ход игрока - не случаен, вы его вычисляете.

[ilia-ili-ilya]

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

А в случае случайных клеток, надо считать матожидание только по выбору новой клетки и никак не по движению. Игрок выбирает одно из 4 направлений минимизируя оценку. Матожидание только по случайной величине делается, ход игрока - не случаен, вы его вычисляете.

Да, я так и делаю

[wataru]

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

В смысле. Оптимальный на злом поле должен брать в расчет злое поле. Но в принципе, я понял. На этом стоит заострить внимание в статье, что алгоритм считает лучшую стратегию в среднем, но играет против худшего случая.