Оптимальная игра в 2048 с помощью марковского процесса принятия решений

[nodonutsforyou]

Было бы интересно сравнить как к такой задаче подошли разные алгоритмы на нейронных сетях и насколько они эффективны.

[Andre_Sk]

Всегда интуитивно предполагал что оптимальная (выигрышная) схема игры в случае поля 4х4 будет в «прижимании» к одной из сторон. Например прижимаем вправо — т.е. двигаем только вверх, вниз и вправо. Судя по gif-ке — я был прав:)

[hottdog]

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

[Akhmad]

Больше не смог, хотя, теоретически можно было еще выжать

[Ogoun]

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

Код

public enum IterationSolve
    {
        Top, Left, Right, Bottom
    }


private static IterationSolve SolveCurrentIteration(List<Tile> tiles)
        {
            var matrix = new int[4, 4] { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
            var matrixLeft = new int[4, 4] { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
            var matrixRight = new int[4, 4] { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
            var matrixTop = new int[4, 4] { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
            var matrixBottom = new int[4, 4] { { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 }, { 0, 0, 0, 0 } };
            foreach (var t in tiles)
            {
                matrix[t.X - 1, t.Y - 1] = t.Number;
                matrixLeft[t.X - 1, t.Y - 1] = t.Number;
                matrixRight[t.X - 1, t.Y - 1] = t.Number;
                matrixTop[t.X - 1, t.Y - 1] = t.Number;
                matrixBottom[t.X - 1, t.Y - 1] = t.Number;
            }
            // 1. Left
            for (int i = 0; i < 3; i++)
            {
                Left(i, matrixLeft);
            }
            // 2. Right
            for (int i = 3; i > 0; i--)
            {
                Right(i, matrixRight);
            }
            // 3. Top
            for (int i = 0; i < 3; i++)
            {
                Top(i, matrixTop);
            }
            // 4. Bottom
            for (int i = 3; i > 0; i--)
            {
                Bottom(i, matrixBottom);
            }
            // Compare result
            var maxTileLeft = CalculateMaxTile(matrixLeft);
            var maxTileRight = CalculateMaxTile(matrixRight);
            var maxTileTop = CalculateMaxTile(matrixTop);
            var maxTileBottom = CalculateMaxTile(matrixBottom);

            bool canMoveToLeft = !MatrixEquals(matrix, matrixLeft);
            bool canMoveToRight = !MatrixEquals(matrix, matrixRight);
            bool canMoveToTop = !MatrixEquals(matrix, matrixTop);
            bool canMoveToBottom = !MatrixEquals(matrix, matrixBottom);

            var solvedTiles = new List<Tuple<Tile, IterationSolve>>();
            if (canMoveToBottom)
            {
                solvedTiles.Add(new Tuple<Tile, IterationSolve>(maxTileBottom, IterationSolve.Bottom));
            }
            if (canMoveToRight)
            {
                solvedTiles.Add(new Tuple<Tile, IterationSolve>(maxTileRight, IterationSolve.Right));
            }
            if (canMoveToTop)
            {
                solvedTiles.Add(new Tuple<Tile, IterationSolve>(maxTileTop, IterationSolve.Top));
            }
            if (canMoveToLeft)
            {
                solvedTiles.Add(new Tuple<Tile, IterationSolve>(maxTileLeft, IterationSolve.Left));
            }
            // Стратегия максимальной прибыли
            for (int i = 0; i < solvedTiles.Count; i++)
            {
                for (int t = 0; t < solvedTiles.Count; t++)
                {
                    if (i != t)
                    {
                        if (solvedTiles[i].Item1.Number < solvedTiles[t].Item1.Number)
                            continue;
                    }
                }
                return solvedTiles[i].Item2;
            }
            return solvedTiles[0].Item2;
        }

        private static bool MatrixEquals(int[,] matrixA, int[,] matrixB)
        {
            for (int x = 0; x < 3; x++)
            {
                for (int y = 0; y < 3; y++)
                {
                    if (matrixA[y, x] != matrixB[y, x])
                    {
                        return false;
                    }
                }
            }
            return true;
        }

        #region CalculateMax
        private static Tile CalculateMaxTile(int[,] matrix)
        {
            var max = new Tile { X = 0, Y = 0, Number = 0 };
            for (int x = 0; x < 3; x++)
            {
                for (int y = 0; y < 3; y++)
                {
                    if (matrix[y, x] > max.Number)
                    {
                        max.X = x;
                        max.Y = y;
                        max.Number = matrix[y, x];
                    }
                }
            }
            return max;
        }
        #endregion

[Belarus]

Удивительно, но все картинки в статье — svg!

[KvanTTT]

Почему удивительно? Это подходящий формат для схем и графов.

[Belarus]

Просто непривычно, ранее не видел на Хабре такое.

[KvanTTT]

К сожалению, https://habrastorage.org пока что не поддерживает прямую загрузку svg, но поддерживает косвенную (загружает из другого ресурса на свои серверы).