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

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

Компания Anadea регулярно проводит IT-соревнования, поскольку подобные мероприятия являются идеальной средой для того, чтобы понять принципы работы, написать код и тут же получить обратную связь, а также показать себя.

16 декабря 2017 состоялась ИТ-дуэль среди сотрудников компании. Мероприятие проходило в 4 городах одновременно - Днепр, Минск, Гродно и Аликанте в стенах офисов нашей компании.

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

Clickomania

Для решения задачи требовалось написать JSON API веб-сервис, который будет общаться с игровым сервером. Сервер генерирует игровую доску, следит за соблюдением игровых правил, и начисляет призовые очки. Количество очков, которое в результате игры получает команда, зависит от того, остались ли ячейки на поле:

  • ячейки остались - решение верно, но очки не начисляются;
  • не осталось ячеек - команде начисляется количество очков, равное количеству ячеек на доске.

За 5 часов игры было сгенерировано 58377 досок. Решено 7909 досок размером 5Х5, 79 досок размером 6Х6 и 100 досок размером 7Х7.

По результатам соревнования финальная тройка выглядит так:

  • 1 место - Сб.Аликанте. Счёт 112701, сыграно игр 4391. Дали фору остальным и заняли первое место. Славно вышло!
  • 2 место - undefined отлично держались на протяжении всего соревнования. Вырвались на второе место. Поздравляем!
  • 3 место - Pink Lumberjacks. Весёлым составом шагнули в призёры. Молодцы, в общем.

По окончанию дуэли команды делились и впечатлениями.

Поздравляем победителей и благодарим всех за эмоции и настроение!

Решение задачи

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

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

Clickomania: Game board

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

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.