Clickomania внутренняя ИТ-дуэль 2017: решение

Clickomania: Game board

Выдержка из правил:

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

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

case class Component(color: Int, boardSize: Int) {
  var cells: Set[Cell] = Set()
  ...
}

class Board(val size: Int, array: Array[Array[Byte]]) {
  val components : Seq[Component] = ...
}

Задача считалась решённой, если на поле оставался один компонент нейтрального цвета.

def isSolved: Boolean =
  components.size == 1 && components.head.color == -1

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

def loop(current: Board, acc: List[Move], visited: Set[Board]): Option[List[Move]] =
  if (current.isSolved) Some(acc)
  else if (!current.hasSolution) None
  else {
    val newBoards = (for {
      move <- current.possibleMoves
      newBoard = current.makeMove(move)
    } yield (newBoard, move :: acc)).toStream

    val newVisited = visited ++ newBoards.map(_._1)
    newBoards.map { case (newBoard, moves) =>
      loop(newBoard, moves, newVisited)
    }.find(_.isDefined)
      .flatten
  }

Основным недостатком BFS решения был обход всех (в т.ч. потенциально плохих) состояний игрового поля. Поэтому следующим эволюционным шагом стал обход поля, используя некую стратегию поиска "хороших" ходов. Для этой цели применили DFS (поиск в глубину). Сперва делается наилучший ход из доступных. После этого уже из нового состояния делается опять таки наилучший ход из доступных, пока не найдём решение.

В этом случае значительно сокращается количество проверяемых состояний и на первое место выходит стратегия выбора лучшего хода. Из-за этого компоненты игрового поля обросли множеством дополнительный характеристик, таких как ширина, длина, минимальная и максимальная координаты по X и Y, расстояние до точки респауна (точки, к которой двигались строки и столбцы, когда в них не оставалось цветных ячеек).

def loop(current: Board, acc: List[Move]): Option[List[Move]] =
  if (current.isSolved)
    Some(acc)
  else if (!current.hasSolution)
    None
  else {
    val components = strategy(current, scala.util.Random.shuffle(current.componentsToClick))
    current.possibleMovesFor(components)
      .foldLeft(Option.empty[List[Move]]) { case (acc1, move) =>
        if (acc1.isDefined) acc1
        else {
          val newBoard = current.makeMove(move)
          loop(newBoard, move :: acc)
        }
      }
  }

Измерения эффективности используемых алгоритмов на разных размерах игрового поля показали, что для набора победных очков наиболее продуктивным являлось решение полей минимального размера (т.е. 5х5):

| Алгоритм           | average, ms | min, ms | max, ms |
|-------------------|-------------|---------|---------|
| DFS maxX+Distance |        1714 |     895 |    2746 |
| DFS maxX+minY     |        1800 |     925 |    3123 |
| DFS maxX+MaxY     |        1841 |     920 |    3133 |
| BFS               |        4866 |    2336 |   12194 |

Что же касается полей большего размера, то спортивный интерес, конечно же, подбивал найти решение и для них. С помощью DFS удалось решить 12х12, а дальше процесс остановился. Как ни странно, решение пришло, откуда не ждали - из всеми любимого курса "Algorithms, Part1" от Р. Седжвика.

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

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

  override def findSolution(board: Board): Option[List[Move]] = {
    val visited = collection.mutable.HashSet.empty[Solution]

    val ordering: Ordering[Solution] = (x: Solution, y: Solution) =>
      if (x.points != y.points)
        x.points - y.points
      else x.componentCount - y.componentCount
    val pq = new collection.mutable.PriorityQueue[Solution]()(ordering).reverse

    pq.+=(Solution(board, Nil))

    @tailrec
    def loop(): Option[List[Move]] = {
      val current = pq.dequeue()
      val path = current.path
      val currentBoard = current.board
      if (currentBoard.isSolved) Some(path)
      else {
        val possibleSolutions = currentBoard.possibleMoves
          .map(move => Solution(currentBoard.makeMove(move), move :: path))
          .filter(_.board.hasSolution)
        val newSolutions = possibleSolutions
          .filterNot(visited)

        visited ++= newSolutions
        pq ++= newSolutions
        loop()
      }
    }

    loop()
  }

Интересные факты:

  • естественной проблемой, с которой столкнулся при работе с полями больших размеров, была нехватка памяти. Временно ликвидировал её с помощью изменения базового типа массива с Int (4 байта) на Byte;
  • на момент написания статьи максимальный размер решённой доски - 37x37
  • на малых размерах доски PQ проигрывал на тестовом наборе данных даже BFS.

Исходный код доступен на Gitlab.

Связаться