Comments 9
Было бы интересно сравнить как к такой задаче подошли разные алгоритмы на нейронных сетях и насколько они эффективны.
Всегда интуитивно предполагал что оптимальная (выигрышная) схема игры в случае поля 4х4 будет в «прижимании» к одной из сторон. Например прижимаем вправо — т.е. двигаем только вверх, вниз и вправо. Судя по gif-ке — я был прав:)
Когда играл в эту игрушку, то тактика была проста как три копейки — можно использовать только 3 направления сдвига (к примеру влево, вправо, вниз), направление выбирается на максимальное схлопывание.
Ну и как следствие этой тактики — 2048 был достигнут множество раз. Потом игра наскучила :)
Ну и как следствие этой тактики — 2048 был достигнут множество раз. Потом игра наскучила :)
Больше не смог, хотя, теоретически можно было еще выжать
Описание алгоритма можно назвать минимаксом с построением на максимульную глубину. Делал решение этой же игры на минимаксе с построением на один шаг в глубину с полным расчетом в ширину, и бот достаточно часто доходил до 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
Удивительно, но все картинки в статье — svg!
Почему удивительно? Это подходящий формат для схем и графов.
Просто непривычно, ранее не видел на Хабре такое.
К сожалению, https://habrastorage.org пока что не поддерживает прямую загрузку svg, но поддерживает косвенную (загружает из другого ресурса на свои серверы).
Sign up to leave a comment.
Оптимальная игра в 2048 с помощью марковского процесса принятия решений