IT дуэль 2017: "Битва ботов - Гексагон" создание игры - Часть 3 - игровой движок

Engine

В предыдущих статьях цикла мы определились с требуемым функционалом игровой площадки и подготовили runtime инфраструктуру для игровых ботов и песочниц. Настало время запрограммировать собственно игровой движок. В качестве основных инструментов будем использовать Ruby on Rails и Sidekiq на бэкенде, ReactJS и WebSocket на фронтенде.

Подготовим зависимости для очереди задач

Добавим sidekiq в наше Ruby on Rails приложение. Во время турнира нам понадобится просчитывать множество игровых боёв между ботами, и было бы неплохо выполнять просчёты игр в многопоточном режиме, с возможностью горизонтального масштабирования в случае нужды. Очередь отложенных задач, обрабатываемая пулом worker-процессов, является простым и эффективным способом этого достичь.

В качестве диспетчера периодических задач используем sidetiq. В игровом движке будет реализована единственная периодичная задача, выполняемая каждые 15 секунд, сфера ответственности которой - подведение итогов текущего раунда игр и подготовка следующего раунда.

Стоит отметить, что периодичная задача в реализации sidetiq есть ничто иное как периодичное добавление отложенной задачи, одной и той же. Предотвратим дублирование этой задачи с помощью sidekiq-unique-jobs гема.

Научимся заказывать и удалять DigitalOcean дроплеты для игроков на основе подготовленного нами образа.

Нам поможет droplet_kit, с небольшой надстройкой:

class DropletClient
  # Название мастер SSH ключа в панели DigitalOcean
  SSH_KEY_NAME = 'fourcolor'.freeze

  # API токен и название DigitalOcean образа для ботов
  def initialize(access_token, image_name)
    @access_token, @image_name = access_token, image_name
  end

  # Генерируем уникальное название для создаваемого дроплета,
  # используя значение автоинкрементного первичного ключа из базы данных
  def name(local_id)
    "#{@image_name}-#{Tournament::CURRENT_SANDBOX}-#{local_id}"
  end

  # Создание дроплета на основе подготовленного образа,
  # при этом подкладываем мастер SSH ключ в root пользователя
  def create(name)
    droplet = client.droplets.create(DropletKit::Droplet.new(
      name: name,
      region: 'fra1',
      image: image,
      size: '1gb',
      ssh_keys: ssh_keys
    ))

    droplet.id
  rescue DropletKit::Error
  end

  # Удаление дроплета
  def delete(id)
    client.droplets.delete(id: id)
    true
  rescue DropletKit::Error
    false
  end

  # Получение IP адреса созданного дроплета
  # При вызове данного метода помним,
  # что IP становится доступен спустя 20-30 секунд после создания дроплета
  def fetch_host(id)
    client.droplets.find(id: id).networks.v4.first&.ip_address
  rescue DropletKit::Error
  end

  private

  # клиент для DigitalOcean API
  def client
    @client ||= DropletKit::Client.new(access_token: @access_token)
  end

  # Идентификатор DigitalOcean образа
  def image
    @image ||= client.images.all.detect{|d| d.name == @image_name}.id
  end

  # Отпечаток мастер SSH ключа
  def ssh_keys
    @ssh_keys ||= client.ssh_keys.all
      .select{|k| k.name == SSH_KEY_NAME}
      .map(&:fingerprint)
  end

end

Все операции с дроплетами проводим через отложенные задачи, так как процесс, прямо скажем, не мгновенный - fetch_host начнёт возвращать IP дроплета секунд через 20 после create:

class Droplet < ApplicationRecord

  with_options unless: :imported? do
    after_commit :create_client_async, on: :create
    after_destroy :delete_client_async
  end

  # Множественный заказ дроплетов
  def self.mass_create!(count)
    transaction { count.times { create! } }
  end

  # Множественное удаление дроплетов
  def self.mass_destroy!(ids)
    transaction { find(ids).count { |droplet| droplet.destroy } }
  end

  # Заказываем дроплет в DigitalOcean, сохраняем его внешний идентификатор,
  # и планируем отложенную задачу для получения IP адреса созданного дроплета.
  # Данный метод должен вызываться исключительно из отложенной задачи.
  def create_client
    with_lock do
      unless client_id
        if self.client_id = DROPLET_CLIENT.create(name)
          save!
          FetchDropletJob.perform_later(id)
        else
          CreateDropletJob.set(wait: 10.seconds).perform_later(id)
        end
      end
    end
  end

  # Пытаемся получить и сохранить IP адрес дроплета,
  # при неудаче вновь планируем соответствующую отложенную задачу.
  # При перезапуске отложенной задачи не полагаемся на штатный job retry,
  # лучше вновь запланировать задачу вручную, в соответствии с принципом
  # "нормальная бизнес логика не должна основываться на генерации и перехвате исключений".
  # 
  # Данный метод должен вызываться исключительно из отложенной задачи.
  def fetch_client
    with_lock do
      if client_id && !host
        if self.host = DROPLET_CLIENT.fetch_host(client_id)
          save!
        else
          FetchDropletJob.set(wait: 10.seconds).perform_later(id)
        end
      end
    end
  end

  private

  # Планируем отложенную задачу для заказа дроплета
  def create_client_async
    CreateDropletJob.perform_later(id)
  end

  # Планируем отложенную задачу для удаления дроплета
  def delete_client_async
    DeleteDropletJob.perform_later(client_id) if client_id
  end

end

Код отложенных задач предельно примитивен, каким и должен быть:

class SystemJob < ActiveJob::Base
  queue_as :default
end

class CreateDropletJob < SystemJob
  def perform(droplet_id)
    Droplet.find(droplet_id).create_client
  end
end

class FetchDropletJob < SystemJob
  def perform(droplet_id)
    Droplet.find(droplet_id).fetch_client
  end
end

class DeleteDropletJob < SystemJob
  def perform(droplet_client_id)
    Droplet.delete_client(droplet_client_id)
  end
end

Регистрация команд в админке

Администрирование списка команд является обычным CRUD, с применением dynamic-fields-for при формировании списка игроков.

Для генерации игровых токенов входа (а в будущем - ещё и для генерации идентификаторов игр и реплеев) будем использовать чудесную библиотеку hashids. Поскольку данный алгоритм генерации токена обратим, у нас нет нужды хранить токены в базе данных. К тому же, если в качестве "соли" алгоритма использовать SECRET_KEY_BASE, мы сможем при желании инвалидировать все токены одновременно с инвалидацией всех сессий:

class Team < ApplicationRecord
  # Инициируем генератор токенов
  HASHIDS = Hashids.new(
    Rails.application.secrets[:secret_key_base] + 'Team',
    16,
    ('A'..'Z').to_a.join
  )

  # генерация токена на основе значения первичного ключа
  def auth_token
    @auth_token ||= HASHIDS.encode(id)
  end

  # Читабельный токен - разбиваем по 4 символа, объединяем через дефис
  def auth_token_humanized
    auth_token.scan(/.{4}/).join('-')
  end

  # Ищем запись в базе данных по токену
  def self.find_by_auth_token(token)
    find_by_id(HASHIDS.decode(token.to_s))
  rescue Hashids::InputError
  end

end

Печать флаера команды

Дадим админу возможность распечатать флаер команды прямо со страницы со списком команд или со страницы редактирования команды, без перезагрузки страницы. Задачка решается с помощью iframe в layout шаблоне:

!!!
%html
  %body
    -# какая-нибудь кастомная разметка
    yield

    -# iframe со специальным data атрибутом
    %iframe{ src: flash[:print], data: {'print-target' => true} }

Спрячем iframe с помощью стилей:

[data-print-target] {
  display: none;
}

Оживим iframe с помощью coffee скрипта:

$(document).on 'turbolinks:load', ->
  # Автоматически открываем системное диалоговое окно принтера при загрузке чего-либо в iframe
  $('[data-print-target]').on 'load', (event) ->
    event.target.contentWindow.print() if $(event.target).attr('src')

$ ->
  $(document).on 'click', 'a[data-print]', (event) ->
    # Загружаем адреса ссылок с "print" data атрибутом не в основное окно браузера, но в iframe
    $('[data-print-target]').get()[0].src = $(event.target).parent().attr('href')
    event.preventDefault()

Теперь можно распечатывать response любого endpoint-а из произвольного места приложения:

# Распечатывание из шаблона
link_to teams_manage_path(resource), data: {print: true} do
  %i.material-icons print

# Распечатывание из контроллера
# print_and_new - это имя одной из submit кнопок на форме редактирования
# Для распознавания нажатия на конкретную кнопку используем известный трюк -
# вместо того, чтоб показывать а шаблоне несколько submit кнопок с одинаковым name атрибутом,
# и мучительным распознаванием в контроллере конкретной кнопки по value атрибуту
# (многоязычность, иконка вместо текста и т.п.) - каждой кнопке даём уникальный name,
# и в контроллере распознаём по факту наличия соответствующего CGI параметра,
# безотносительно его значения
if params[:print_and_new]
  flash[:print] = teams_manage_path(@resource)
  redirect_to action: :new
else
  redirect_to action: :index
end

Добавление ssh ключа игрока в командный дроплет

Свой публичный SSH ключ игроки вводят в форму на сайте песочницы, затем этот ключ будет использоваться для деплоя новых релизов бота в игровой дроплет. Помним, что в контейнере песочницы уже лежит приватный master ключ, а в дроплетах с ботами публичный master ключ подложен в рута - должно сработать!

При валидации формата SSH ключа нам поможет sshkey:

class Droplet < ApplicationRecord
  def add_ssh_key(key)
    # публичный SSH ключ игрока приходит из пользовательского ввода - тщательно валидируем!!!
    return :blank if key.blank?
    return :wrong unless SSHKey.valid_ssh_public_key?(key)

    # Экранируем ключ (!!!), и отправляем его в dokku пользователя дроплета игрока
    `echo #{key.shellescape} | ssh -oStrictHostKeyChecking=no -oUserKnownHostsFile=/dev/null root@#{host} "sudo sshcommand acl-add dokku [player]"`
    
    # Проверяем код выхода последней shell команды
    $?.to_i == 0 ? :ok : :error
  end
end

Как видно, без SSHKey.valid_ssh_public_key? и key.shellescape мы предоставили бы возможность всем желающим выполнить произвольный shell скрипт с помощью формы ввода SSH ключа, со всеми вытекающими ()=);;;;>

Механика просчёта раундов

В качестве основного цикла игрового движка реализуем периодическую задачу, выполняющуюся каждые 15 секунд.

class RoundWorker
  include Sidekiq::Worker
  include Sidetiq::Schedulable

  # Отключаем штатный retry, включаем режим уникальности задачи в очереди
  sidekiq_options(
    retry: false,
    unique: :until_and_while_executing
  )

  # Задаём периодичность задачи
  recurrence { minutely.second_of_minute(0, 15, 30, 45) }

  def perform
    # Ждём завершения просчёта раунда
    unless Game.pending.any?
      finish_previous_rounds
      delete_marked_teams
      prepare_tournament
      apply_events
      prepare_next_round
    end
  end

   # Финализируем просчитанный раунд, начисляем очки за игры
  def finish_previous_rounds
    Round.finish_pending
  end

  private

  # Удаляем команды, помеченные админом для удаления -
  # для здоровья приложения безопасней это делать между раундами,
  # а не посередине оного, когда команда участвует в просчёте игр
  def delete_marked_teams
    Team.destroy_marked!
  end

  # Подготавливаем турнир в целом - вместо промо заглушки
  # открываем игровой интерфейс песочницы, обнуляем очки команд,
  # инициируем очередь игровых событий.
  #
  # Метод выполняет полезную работу при окончании отсчёта времени до начала турнира
  # на промо странице, а также при ручном перезапуске турнира админом.
  def prepare_tournament
    Tournament.instance.prepare!
  end

  # Применяем игровые события, если срок их вступления в игру пришёл
  def apply_events
    Event.apply!
  end

  # Подготавливаем для просчёта следующий раунд,
  # планируем отложенные задачи для просчёта конкретных игр.
  def prepare_next_round
    Round.prepare!
  end

end

Данный воркер ждёт, пока не доиграются все игры раунда, затем выполняет ряд действий...

RoundWorker#finish_previous_rounds

Начисляем командам очки за игры в текущем раунде, помечаем раунд как "оконченный":

class Round < ApplicationRecord

  scope :pending, -> { where(pending: true) }

  def self.finish_pending
    pending.lock.each do |round|
      transaction do
        Score.calculate(round)

        round.update_attributes! pending: false
      end
    end
  end
end

RoundWorker#delete_marked_teams

Вместо того, чтобы думать, каким образом на движке скажется немедленное удаление команды (упавшие отложенные задачи просчёта игр, обновление WEB интерфейса и т.п.) - админ лишь помечает команду к удалению, фактическое удаление происходит после просчёта текущего раунда:

class Team < ApplicationRecord

  scope :for_delete, -> { where(for_delete: true) }

  def self.destroy_marked!
    for_delete.each do |team|
      team.destroy!
    end
  end

end

RoundWorker#prepare_tournament

Админ может перезапустить турнир - как и в случае с удалением команды, фактический перезапуск происходит после просчёта текущего раунда:

class Tournament < ApplicationRecord

  def prepare!
    start_from_beginning! if start_from_beginning?
  end

  private

  def start_from_beginning!
    transaction do
      # Чистим очередь отложенных задач
      Sidekiq::Queue.new('game').clear

      # Приводим атрибуты турнира в исходное состояние
      update_attributes!(
        started: false,
        finished: false,
        start_from_beginning: false
      )

      # Очищаем игровые таблицы в базе данных
      [Game, Round, Score, RoundType].each(&:truncate!)

      # Отменяем уже наступившие игровые события
      Event.update_all(applied: false)

      # Обнуляем очки команд
      Team.all.each(&:create_initial_score)
    end

    # Очищаем статистику выполненных отложенных задач
    Sidekiq::Stats.new.reset

    # Через WebSocket оповещаем клиента о необходимости обновить страницу.
    # В случае, если время начала турнира выставлено в будущем -
    # игровой интерфейс будет заблокирован промо заглушкой с обратным отсчетом
    # до начала турнира.
    LadderIndexChannel.broadcast(:reload)
  end

end

RoundWorker#prepare_next_round

Подготовим следующий раунд.

class Round < ApplicationRecord

  def self.prepare!
    # Типы раундов представляют из себя параметры игрового поля - размер, множитель очков. 
    # Типы раундов меняются циклически, один за другим и по кругу.

    # Находим тип раунда, разыгрывавшийся в предыдущем раунде
    last_round_type_id = order(:id).last&.round_type_id || 0

    # Получаем следующий тип раунда
    round_type_scope = RoundType.order(:id)
    next_round_type = round_type_scope.where('id > ?', last_round_type_id).first ||
      round_type_scope.first

    if next_round_type
      transaction do
        # Создаём новый раунд
        round = create!(
          round_type_id: next_round_type.id,
          size: next_round_type.size,
          timeout_secs: next_round_type.timeout_secs,
          score_multiplier: next_round_type.score_multiplier
        )

        # Берём все комбинаторные комбинации команд по две,
        # комбинации рандомизируем с целью равномерно распределить нагрузку на ботов
        Team.all.to_a.combination(2).to_a.shuffle!.each do |teams|
          # Первая команда в данной паре будет ходить первой, оттого -
          # рандомизируем массив, лишая геймплей предсказуемости
          teams.shuffle!

          # Создаём игру для пары команд, на выбранном типе доски
          association_class(:games).create!(
            round: round,
            team1: teams[0],
            team2: teams[1],
          )
        end
      end
    end
  end

end

Все созданные матчи помещаются в очередь отложенных задач для дальнейшего просчёта. По ходу дела с помощью WebSocket оповещаем клиента о новом матче:

class Game < ApplicationRecord

  after_commit :add_to_ladder_and_schedule, on: :create

  private

  def add_to_ladder_and_schedule
    [team1_id, team2_id].each do |team_id|
      LadderShowChannel.broadcast(team_id, :add_game, game: to_ladder(true))
    end

    GameJob.set(wait: 1.seconds).perform_later(id)
  end

end

Просчёт матча

Наконец, самое интересное! Запрограммируем игровую логику )

Для начала, научимся генерировать случайные игровые поля:

class Board
  cattr_reader(:scaffolds) { {} }
  attr_reader :size, :cells

  # Генерируем заготовку для игрового поля требуемого размера,
  # она будет включать в себя все игровые элементы (камни, пустые клетки,
  # начальное положение фишек игроков) - всё, кроме случайных дополнительных камней.
  def self.scaffold(size)
    # Заготовки всегда одинаковы относительно затребованного размера поля - мемоизируем
    scaffolds[size] ||= begin
      cells_size = size * 2 - 1

      # Подготовим пустое игровое поле
      cells = Array.new(cells_size) {
        Array.new(cells_size, 0)
      }

      # Вот как-то так "обрамим" поле камнями по периметру,
      # в итоге оставшиеся пустые клетки образуют правильный шестиугольник
      left_rocks = 0
      right_rocks = 0
      left_increment = size % 2 == 0

      (size-1).times do |i|
        left_increment ? left_rocks += 1 : right_rocks += 1
        left_increment = !left_increment

        [size-2-i, size+i].each do |ii|
          [
            *(0...left_rocks),
            *((cells_size - right_rocks)...cells_size)
          ].each do |jj|
            cells[ii][jj] = -1
          end
        end
      end

      # Выложим на поле начальные фишки игроков
      cells[size-1][0] = 2
      cells[size-1][cells_size-1] = 1

      [0, cells_size-1].each do |i|
        cells[i][left_rocks] = 1
        cells[i][cells_size - right_rocks - 1] = 2
      end

      # Соберём в массив координаты пустых ячеек -
      # это пригодится при "набрасывании" на поле случайных камней
      empty_cells = cells_size.times.inject([]) { |mem, i|
        cells_size.times.inject(mem) { |mem, j|
          mem << [i, j] if cells[i][j] == 0
          mem
        }
      }

      # Посчитаем оптимальное количество случайных камней
      additional_rocks_count = empty_cells.size / 10
      # Добавим ещё один случайный камень,
      # чтобы общее количество доступных для игры ячеек было нечётным -
      # минимизируем вероятность ничьи
      additional_rocks_count += 1 if (empty_cells.size - additional_rocks_count).even?

      # Заготовка готова!
      {
        cells: cells,
        empty_cells: empty_cells,
        additional_rocks_count: additional_rocks_count
      }.freeze
    end
  end

  # Собственно, генерация случайного поля
  def initialize(_size)
    @size = _size

    # Берём заготовку нужного размера
    scaffold = self.class.scaffold(size)

    # Клонируем заготовку, набрасываем на полученную доску рандомные камни
    @cells = scaffold[:empty_cells]
      .sample(scaffold[:additional_rocks_count])
      .inject(scaffold[:cells].deep_dup){ |mem, (i, j)|
        mem[i][j] = -1
        mem
      }
  end

end

Игровую логику вынесем в пару отдельных классов. Программируем с особым вниманием - данные классы имеют дело с пользовательским вводом, именно здесь обрабатываются ходы игроков.

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

class BoardSolver
  class WrongMove < StandardError; end

  # Дешево и сердито - хардкодим разницы индексов между целевой ячейкой и её соседями
  NEIGHBOR_DELTAS = [
    # для ячеек из чётных строк
    [
      # Нулевое расстояние до соседей - соседей нет.
      # Впишем пустой массив просто для того, чтобы использовать Array, а не Hash,
      # и не суетиться с индексацией
      [],
      # Расстояние до соседей равно одной ячейке, тип хода - размножение
      [[-1,-1],[-1,0],[1,-1],[1,0],[0,-1],[0,1]],
      # расстояние до соседей равно двум ячейкам, тип хода - прыжок
      [
        [-1,-2],[-1,1],[1,-2],[1,1],[0,-2],[0,2],
        [-2,-1],[-2,0],[-2,1],[2,-1],[2,0],[2,1]
      ]
    # Аналогично для ячеек из нечётных строк
    ],[
      [],
      [[-1,0],[-1,1],[1,0],[1,1],[0,-1],[0,1]],
      [
        [-1,-1],[-1,2],[1,-1],[1,2],[0,-2],[0,2],
        [-2,-1],[-2,0],[-2,1],[2,-1],[2,0],[2,1]
      ]
    ]
  ].freeze

  attr_reader :cells_size, :possible_moves, :jumps, :populates, :score

  def initialize(cells)
    @cells_size = cells.size

    # Будем поддерживать данные о возможных ходах в формате
    # possible_moves[color][move_from][move_to] = distance
    # При наполнении possible_moves будем игнорировать количество доступных прыжков.
    # Также, наличие ключа move_from в хэше @possible_moves[color] косвенно говорит о том,
    # что ячейка move_from закрашена в цвет color
    @possible_moves = Array.new(3){ {} }

    # Для каждого игрового цвета поддерживаем информацию о доступных прыжках,
    # произведенных ходах типа "размножение", и игровых очках
    @jumps, @populates, @score = 3.times.map{ {1 => 0, 2 => 0} }

    # заполним possible_moves[0] пустыми клетками - ходить из них нельзя,
    # но нам понадобится тот самый косвенный признак пустой клетки
    each_cell(cells) do |cell, color|
      possible_moves[color][cell] = {} if color == 0
    end

    # По сути, стартовые фишки выставлены на пустую доску с помощью хода "размножение" -
    # пропускаем их через общий метод apply_changes.
    each_cell(cells) do |cell, color|
      apply_changes([[*cell, 0, color]]) if (1..2).include?(color)
    end
  end

  # Применение изменений доски
  def apply_changes(changes)
    # Поддерживаем jumps и populates в актуальном состоянии
    _, _, old_color, new_color = changes.first

    # Ситуация, когда первым изменением ячейка освобождается - признак хода типа "прыжок"
    if new_color == 0
      # прыжок потрачен
      jumps[old_color] -= 1
    else
      # Произведён ход типа "размножение" 
      populates[new_color] += 1
      # За каждое второе размножение игрок получает один доступный прыжок
      jumps[new_color] += 1 if populates[new_color] % 2 == 0
    end

    changes.each do |i, j, old_color, new_color|
      cell = [i, j]

     # Поддерживаем score в актуальном состоянии
      score[old_color] -= 1 if old_color != 0
      score[new_color] += 1 if new_color != 0

      # Ячейка меняет цвет, значит предыдущий её владелец больше не может из неё походить
      possible_moves[old_color].delete(cell)

      # Ячейка перестала быть свободной, значит в неё уже никто не может походить
      if old_color == 0
        possible_moves[1..2].each do |moves|
          moves.each do |_, to|
            to.delete(cell)
          end
        end
      end

      # Ячейка обрела новый цвет!
      possible_moves[new_color][cell] = {}
      neighbor_colors = new_color == 0 ? (1..2) : (0..0)

      neighbor_colors.each do |neighbor_color|
        (1..2).each do |distance|
          neighbors(cell, distance, neighbor_color).each do |neighbor_cell|
            color, from, to = new_color == 0 ?
              # ячейка освободилась, теперь в неё могут походить соседние фишки игроков
              [neighbor_color, neighbor_cell, cell] :
              # ячейка перекрашена в цвет игрока, теперь игрок может походить из неё
              # в соседние пустые ячейки
              [new_color, cell, neighbor_cell]

            possible_moves[color][from] ||= {}
            possible_moves[color][from][to] = distance
          end
        end
      end
    end
  end

  # Попытка применить ход игрока
  def apply_move!(color, move_from, move_to)
    # Нет нужды проверять формат входящих данных и вхождение индексов в размеры доски -
    # possible_moves заведомо хранит только допустимые ходы в правильном формате.
    # Достаточно лишь проверить наличие запрашиваемого ключа в possible_moves.
    distance = possible_moves.dig(color, move_from, move_to)

    # Ход недопустим из-за неверного формата, выпадания индексов за пределы доски,
    # или несоответствия хода правилам игры
    raise WrongMove unless distance && possible_distance?(color, distance)

    opposite_color = self.class.opposite_color(color)

    # Сформируем массив changes для последующей отправки игрокам
    neighbors(move_to, 1, opposite_color).map{ |i, j|
      # Ячейки противника, соседние по отношению к целевой ячейке хода,
      # перекрашиваются в цвет игрока
      [i, j, opposite_color, color]
    }.tap{ |changes|
      # Целевая ячейка перекрашивается в цвет игрока
      changes.unshift([*move_to, 0, color])

      # Ячейка, из которой произведён ход, освобождается, если произведён ход типа "прыжок"
      changes.unshift([*move_from, color, 0]) if distance == 2

      # Обновляем данные по игре в соответствии с вычисленным массивом changes
      apply_changes(changes)
    }
  end

  # Существует хоть один допустимый ход для игрока,
  # если есть хоть одна запись в possible_moves для этого игрока
  # с допустимой с точки зрения jumps дистанцией
  def any_possible_move?(color)
    possible_moves[color].any? { |_, to|
      to.any?{ |_, distance|
        possible_distance?(color, distance)
      }
    }
  end

  # Дистанция хода всегда допустима для "размножения", для "прыжка" же регулируется
  # значением в хэше jumps 
  def possible_distance?(color, distance)
    distance == 1 || jumps[color] > 0
  end

  # Просто реверсия цвета
  def self.opposite_color(color)
    color == 1 ? 2 : 1
  end

  # Поиск ячеек, отстоящих на заданное расстояние от целевой, и закрашенных в заданный цвет
  def neighbors(cell, distance, color)
    # Отличный ruby трюк для создания Enumerable объектов, со всеми вытекающими
    return enum_for(:neighbors, cell, distance, color) unless block_given?

    NEIGHBOR_DELTAS[cell.first%2][distance].each do |deltas|
      # Получаем индексы соседней ячейки
      neighbor_cell = deltas.each_with_index.map{ |delta, index|
        cell[index] + delta
      }

      # Итерируем соседнюю ячейку, если её индексы в пределах доски,
      # и закрашена в заданный цвет
      yield(neighbor_cell) if indexes_inside_board?(neighbor_cell) &&
        possible_moves[color].key?(neighbor_cell)
    end
  end

  private

  # Просто утилитарный метод для итерирования исходной двумерной доски
  def each_cell(cells)
    cells_size.times.each do |i|
      cells_size.times.each do |j|
        yield([i, j], cells[i][j])
      end
    end
  end

  # Проверка индексов ячейки на вхождение в размеры доски
  def indexes_inside_board?(cell)
    cell.all?{ |index| (0...cells_size).include?(index) }
  end
end

Отлично, работает! ) Теперь опишем класс, реализующий общий геймплей:

class Gameplay
  attr_reader :solver, :players, :current_player, :current_color, :game_over

  def initialize(board, *_players)
    # Нам понадобится взаимодействовать с доской
    @solver = BoardSolver.new(board.cells)

    # Массив игроков, первый из них ходит первым
    @players = _players
    @current_player = players.first

    # Игра начинается с цвета 1
    @current_color = 1

    # Признак того, что игра окончена
    @game_over = false

    # Паранойя - она такая.. )
    @mutex = Mutex.new
  end

  # Хэш-отображение первичного ключа игрока в его игровой счёт
  def score_by_team_id
    players.map.with_index{ |p, i| [p.id, solver.score[i+1]] }.to_h
  end

  # Утилитарный метод для получения проигравшего игрока
  def looser
    points = solver.score.values.uniq

    points.size == 1 ?
      # Очки одинаковые, ничья
      nil :
      players[solver.score.key(points.min)-1]
  end

  # Попытка применить ход игрока
  def apply_turn(player, move_from, move_to)
    @mutex.synchronize do
      # Проверяем допустимость хода с точки зрения общего геймплея
      check_move_possibility!(player)

      # Применяем ход, получаем массив changes
      changes = solver.apply_move!(current_color, move_from, move_to)

      # Меняем текущего игрока и текущий цвет на противоположные,
      # проверяем, не достигнут ли конец игры
      @game_over = true

      # Игра окончена, если оба игрока не имеют допустимых ходов
      2.times do
        @current_color = opposite_color
        @current_player = opposite_player

        if solver.any_possible_move?(current_color)
          @game_over = false
          break
        end
      end

      [:ok, changes]
    end
  rescue BoardSolver::WrongMove
    :wrong
  end

  private

  # Противоположный цвет
  def opposite_color
    solver.class.opposite_color(current_color)
  end

  # Противоположный игрок
  def opposite_player
    players.first == current_player ? players.second : players.first
  end

  # Ходить можно только текущему игроку, и только если игра не окончена
  def check_move_possibility!(player)
    raise BoardSolver::WrongMove if game_over || player != current_player
  end

end

Код просчёта матча не таит в себе ничего сверхъестественного - много строк, суть есть механическая работа - просто сесть и аккуратно закодить.

Некоторый сумбур в коде является следствием того, что один и тот же класс используется как для синхронно-бескомпромиссной игры между двумя ботами, так и для игры между тренировочным ботом и web-пользователем, который играет асинхронно, не имеет таймаутов и наказания за неверные ходы. Была предпринята попытка "выпрямить" код с помощью Fiber, но обнаружилось, что Fiber теряет контекст при resume (следствие серриализации-десерриализации где-то в недрах ActionCable). Пришлось использовать throw & catch. Облагораживать код сверх приведённого ниже не было ни времени, ни сил.

Особое внимание уделяем исключительным ситуациям - данный код имеет дело с пользовательским вводом, при этом имеет ключевое влияние на результат турнира.

Для запросов к API ботов используем крайне комфортную библиотеку httparty.

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

class GamePerformer

  include HTTParty
  format :json
  headers(
    'Content-Type' => 'application/json',
    'Accept' => 'application/json'
  )

  attr_reader :session_id, :gameplay, :board, :team1, :team2,
    :moves, :timeout_secs, :score_multiplier

  def initialize(game_id, _board, _team1, _team2, _timeout_secs = 1)
    @board, @team1, @team2, @timeout_secs = _board, _team1, _team2, _timeout_secs
    @session_id = Game.encode_hashid(game_id, team1.id)
    @gameplay = Gameplay.new(board, team1, team2)

    # В этом массиве будем накапливать ходы игроков для реплея
    @moves = []
  end

  # Особый случай инициации игры с человеком  
  def init_async
    [:create, game: {
      team1_id: team1.id,
      team1_name: team1.name,
      team2_id: team2.id,
      team2_name: team2.name,
      board: board,
      jumps: gameplay.solver.jumps
    }]
  end

  # Особый случай начала игры с человеком  
  def play_async(*args)
    catch(:async) do
      play(*args)
    end
  end

  # Основная точка входа в просчёт игры
  def play(*args)
    # Ловим событие окончания игры
    looser, reason = catch(:game_over) do
      # Инициализируем игру для ботов
      init if moves.empty?

      # Запускаем основной цикл просчёта ходов
      turns(*args)
    end

    # Финализируем игру для ботов
    finish

    winner = case looser
      when team1.id then team2.id
      when team2.id then team1.id
      else nil
    end

    moves << {
      type: :game_over,
      reason: reason,
      winner: winner,
      score: gameplay.score_by_team_id.deep_dup,
      jumps: gameplay.solver.jumps.deep_dup
    }

    # Опять пляски вокруг ассинхронного web игрока
    throw(:async, [:game_over, move: moves.last]) if team1.async || team2.async

    moves
  end

  # Рассылаем игрокам уведомление об окончании игры
  def finish
    unless moves.last[:type] == :game_over
      [team1, team2].each_with_index do |team, index|
        moves << {
          type: :delete,
          team: team.id,
          status: delete(team)
        } if moves[index][:type] == :create
      end
    end
  end

  private

  # Рассылаем игрокам уведомление о начале игры
  def init
    teams = [team1, team2]

    teams.each do |team|
      moves << {
        type: :create,
        team: team.id,
        status: create(
          team,
          gameplay.current_player == team,
          teams.any?(&:async)
        )
      }
      check_move_status!(moves)
    end
  end

  # Основной цикл опроса игроков
  def turns(action = nil, move_from = nil, move_to = nil)
    while(true) do
      unless action == :updated
        team = gameplay.current_player
        color = gameplay.current_color

        # Запрашиваем ход у игрока
        status, move_from, move_to = team.async && action == :got ?
          [:ok, move_from, move_to] :
          get(team, color)

        moves << {
          type: :get,
          team: team.id,
          status: status,
          color: color,
          move_from: move_from.deep_dup,
          move_to: move_to.deep_dup
        }
        check_move_status!(moves)

        # Пробуем применить ход игрока
        turn_status, changes = gameplay.apply_turn(team, move_from, move_to)
        if (turn_status == :wrong)
          if team.async
            # Прощаем web игроку неверный ход
            moves.pop
            get(team, color)
          else
            # Наказываем бота немедленным поражением за неправильный ход
            moves.last[:status] = :wrong_move
            throw(:game_over, [team.id, :wrong_move])
          end
        else
          moves.last[:changes] = changes.deep_dup
          moves.last[:score] = gameplay.score_by_team_id.deep_dup
          moves.last[:jumps] = gameplay.solver.jumps.deep_dup
        end
      end

      # Рассылаем игрокам уведомление об изменении состояния доски
      move = moves.reverse.detect{ |m| m[:type] == :get }
      teams = team1.id == move[:team] ?
        [team1, team2] :
        [team2, team1]
      teams.shift if moves.last[:type] == :update

      teams.each do |team|
        status = team.async && action == :updated ?
          :ok :
          update(team, move)
        moves << {
          type: :update,
          team: team.id,
          status: status
        }
        check_move_status!(moves)
      end

      # Отправляем вверх по стеку вызовов сообщение об окончании игры
      throw(:game_over, [gameplay.looser&.id, :by_score]) if gameplay.game_over
      action = nil
    end
  end

  # Обёртка вокруг всех HTTP запросов, для отлова ошибок соединения и таймаутов
  def catch_errors
    yield
  rescue Net::OpenTimeout, Errno::ECONNREFUSED
    :no_connection
  rescue Net::ReadTimeout
    :timeout
  rescue
    :wrong_response
  end

  # POST запрос в сторону бота, содержащий информацию о начальной доске
  def create(team, first_turn, training)
    return :ok if team.async

    catch_errors do
      raise 'Wrong!' unless self.class.post(droplet_url(team, false),
        timeout: timeout_secs,
        body: {
          id: session_id,
          board: board,
          jumps: gameplay.solver.jumps,
          first_turn: first_turn,
          training: training
        }.to_json
      ).parsed_response['status'] == 'ok'

      :ok
    end
  end

  # PUT запрос в сторону бота, содержащий информацию о изменении состояния доски
  def update(team, move)
    # Пляски вокруг ассинхронного web игрока..
    if team.async
      # В данном случае sleep не признак беспомощности программиста,
      # но сознательная задержка после хода web игрока -
      # иначе ход web игрока визуально сливался с немедленным ответным ходом
      # тренировочного бота, и следить за геймплеем было крайне затруднительно 
      sleep 0.5 unless move[:team] == team.id

      throw(:async, [:update, move: {
        type: :get,
        team: move[:team],
        color: move[:color],
        move_from: move[:move_from],
        move_to: move[:move_to],
        changes: move[:changes],
        score: move[:score],
        jumps: move[:jumps]
      }])
    end

    catch_errors do
      raise 'Wrong!' unless self.class.put(droplet_url(team),
        timeout: timeout_secs,
        body: {
          changes: move[:changes],
          jumps: move[:jumps]
        }.to_json
      ).parsed_response['status'] == 'ok'

      :ok
    end
  end

  # GET запрос в сторону бота, запрашивающий очередной ход
  def get(team, color)
    throw(:async, [:get, color: color]) if team.async

    catch_errors do
      response = self.class.get(droplet_url(team),
        timeout: timeout_secs,
        query: {color: color}
      ).parsed_response
      raise 'Wrong!' unless response['status'] == 'ok'

      [:ok, response['move_from'].map(&:to_i), response['move_to'].map(&:to_i)]
    end
  end

  # DELETE запрос в сторону бота, уведомляющий об окончании игры
  def delete(team)
    return :ok if team.async

    catch_errors do
      raise 'Wrong!' unless self.class.delete(droplet_url(team),
        timeout: timeout_secs
      ).parsed_response['status'] == 'ok'

      :ok
    end
  end

  # URL для endpoint-а бота 
  def droplet_url(team, with_session = true)
    "http://#{team.droplet.host}/games".tap{ |url|
       url.concat("/#{session_id}") if with_session
     }
  end

  # Немедленно засчитываем поражение игроку при любой неудаче )
  def check_move_status!(moves)
    throw(:game_over, [
      moves.last[:team],
      moves.last[:status]
    ]) unless moves.last[:status] == :ok
  end

end

Что ж, на бэкенде практически всё готово, время заняться фронтендом!

Real time обновления web интерфейса

Для оповещения клиента об изменениях в игровом мире используем WebSocket-ы.

В качестве примера разберём страницу ладдера, то есть турнирного списка команд. Страница должна реагировать на:

  • CRUD-действия админа относительно команд;
  • Изменения очков команд, как следствие - изменение порядка команд в ладдере;
  • Реакция на новые релизы.

Напишем простой контроллер WebSocket канала:

class LadderIndexChannel < ApplicationCable::Channel

  # Подписываем клиента на канал
  def subscribed
    stream_from self.class.stream_name
  end

  # Генерируем имя канала
  def self.stream_name
    'ladder_index'
  end

  # Отправка сообщения в канал
  # Данный метод можно вызывать откуда угодно - модели, контроллеры, отложенные задачи и т.п.
  def self.broadcast(action, options = {})
    ActionCable.server.broadcast(
      stream_name,
      options.merge(action: action)
    )
  end

end

Отступая в сторону и лишь в качестве примера параметризованного канала - приведём код контроллера для страницы наблюдения за конкретной командой:

class LadderShowChannel < ApplicationCable::Channel

  def subscribed
    # Подписываем клиента на общий канал ладдера
   # На клиенте реагируем на команду обновления страницы при перезапуске турнира
    stream_from LadderIndexChannel.stream_name

    # Подписываем на общий для всех команд канал просмотра игр.
    # Используется для обновления графика набора очков командами.
    stream_from self.class.stream_name

    # Подписываем на канал конкретной команды.
    # Именно по нему распространяется информация о текущих играх команды.
    stream_from self.class.stream_name(params[:team_id])
  end

  # Параметризованное имя канала
  def self.stream_name(team_id = nil)
    "ladder_show".tap { |name|
        name << "_#{team_id}" if team_id
      }
  end

  # Отправка сообщения в командный канал
  def self.broadcast(team_id, action, options = {})
    ActionCable.server.broadcast(
      stream_name(team_id),
      options.merge(action: action)
    )
  end

end

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

class Team < ApplicationRecord

  after_create :add_to_ladder
  after_update :update_in_ladder, if: -> { name_changed? || no_contest_changed? }
  after_destroy :remove_from_ladder

  private

  def add_to_ladder
    LadderIndexChannel.broadcast(:add_score,
      score: scores.last.to_ladder
    )
  end

  def update_in_ladder
    LadderIndexChannel.broadcast(:rename_score,
      team_id: id,
      name: name,
      no_contest: no_contest
    )
  end

  def remove_from_ladder
    LadderIndexChannel.broadcast(:remove_score,
      team_id: id
    )
  end

end

Отреагируем на изменение очков команды и на новый релиз (метку нового релиза оказалось очень удобно держать именно в модели Score, чтобы показывать моменты релизов на графике набора очков командой):

class Score < ApplicationRecord

  after_create :update_in_ladder
  after_update :release_to_ladder, if: :release_changed?

  private

  def update_in_ladder
    LadderIndexChannel.broadcast(:update_score,
      score: to_ladder
    )
  end

  def release_to_ladder
    LadderIndexChannel.broadcast(:new_release, score: {
      round_id: round_id,
      team_id: team_id,
      score: score,
      release: release
    })
  end

end

На стороне сервера всё готово, займёмся клиентом. Используем react-rails библиотеку, пишем пару злобных React компонент:

var LadderIndex = React.createClass({

  componentDidMount() {
    // Устанавливаем WebSocket соединение
    this.channel = App.cable.subscriptions.create('LadderIndexChannel', {
      received: (data) => {
        // Вызываем метод, соответствующий названию полученной из канала команды,
        // если данный метод объявлен
        this[data.action] && this[data.action](data)
      }
    });
  },

  componentWillUnmount() {
    // Закрываем соединение
    this.channel.unsubscribe();
  },

  reload(data) {
    // Реагируем на команду обновления страницы
    location.reload()
  },

  update_scores(data) {
    // Реагируем на команду обновления очков команд,
   // отправляем данные во вложенный компонент
    this.refs.scores.update_scores(data.scores)
  },

  add_score(data) {
    // Реагируем на команду обновления очков конкретной команды,
   // отправляем данные во вложенный компонент
    this.refs.scores.add_score(data.score)
  },

  rename_score(data) {
    // Реагируем на команду обновления атрибутов команды,
   // отправляем данные во вложенный компонент
    this.refs.scores.rename_score(data.team_id, data.name, data.no_contest)
  },

  remove_score(data) {
    // Реагируем на команду удаления команды,
   // отправляем данные во вложенный компонент
    this.refs.scores.remove_score(data.team_id)
  },

  new_release(data) {
    // Реагируем на новый релиз команды,
   // отправляем данные во вложенный компонент
    this.refs.scores.new_release(data.score)
  },

  render() {
   // Отображаем вложенный компонент
    return (
      <div className="teams">
        <LadderIndexScores ref="scores" scores={this.props.scores} />
      </div>
    );
  }

});
var LadderIndexScores = React.createClass({

  getInitialState() {
    // Начальное состояние турнирной таблицы передаётся прямо через props
    return this.scores_to_state(this.props.scores)
  },

  update_scores(scores) {
    // Обновляем очки команд
    this.setState(this.scores_to_state(scores))
  },

  scores_to_state(scores) {
    // Генерируем объект для обновления state
    return {
      scores: _(scores).reduce((memo, score) => {
        memo[score.team_id] = score
        return memo
      }, {})
    }
  },

  add_score(score) {
    // Обновляем очки одной команды
    let new_scores = React.addons.update(this.state.scores, {
      [score.team_id]: {$set: score}
    })

    this.setState({scores: new_scores})
  },

  rename_score(team_id, name, no_contest) {
    // Обновляем атрибуты одной команды
    let new_scores = React.addons.update(this.state.scores, {
      [team_id]: { team_name: {$set: name}, team_no_contest: {$set: no_contest} }
    })

    this.setState({scores: new_scores})
  },

  remove_score(team_id) {
    // Удаляем команду
    let new_scores = _(this.state.scores).omit(team_id)

    this.setState({scores: new_scores})
  },

  new_release(score) {
    // Помечаем команду как имеющую свежий релиз
    let new_scores = React.addons.update(this.state.scores, {
      [score.team_id]: { release: {$set: score.release} }
    })

    this.setState({scores: new_scores})
  },

  scoreClass(score) {
    var classSet = 'mdl-list__item teams__list-item ';

    if (score.team_no_contest) {
      classSet = classSet + 'teams__list-item--no-contest';
    }

    return classSet;
  },

  render() {
    // Сортируем команды по убыванию очков
    let scores = _(this.state.scores).sortBy('position')

   // Отображаем турнирный список
    return (
      <ul className="mdl-list teams__list">
        { _(scores).map((score, index) => {
          return (
            <li key={score.team_id} className={this.scoreClass(score)}>
              <i className="teams__place">{index+1}</i>
              <a className="teams__link" href={'/teams/ladder/' + score.team_id}>
                {score.team_name}
              </a>
              <span className="teams__score">{score.score}</span>
              {score.release && <span className="teams__release">Новый релиз!</span>}
            </li>
          )
        })}
      </ul>
    )
  }

});

Осталось лишь отрисовать LadderIndex компонент, и он заживёт своей жизнью. Рендерить будем прямо из Rails контроллера, с прекомпиляцией на стороне сервера:

module Teams
  class LadderController < ApplicationController
    def index
      render component: 'LadderIndex', props: {
        scores: Score.to_ladder
      }
    end
  end
end

Тренировочный бот

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

Писать будем на Ruby on Rails, в режиме API-only. За основу берём соответствующую заготовку, обновляем лишь код контроллера и добавляем один утилитарный класс. Алгоритм самый примитивный, лишь бы сколь угодно осознанно доиграть до конца партии, не нарушив правила - полный перебор всех доступных ходов, подсчёт разницы в фишках после каждого хода, выбор случайного хода из тех, что дают наибольшую разницу в фишках. Заодно оценим, посильна ли задачка для игроков, то есть сколько времени занимает минимально осмысленная реализация бота.

Приведём код бота как есть, без купюр. Контроллер выглядит именно так, как должен:

class GamesController < ApplicationController
  # Небольшой трюк - хранение состояний досок в переменной класса, а не в файле или DB,
  # то есть избегаем серриализации - благо дефолтный веб-сервер *puma* многопоточный,
  # а не многопроцессный
  @@games = {}

  def create
    # Вскрылась проблема со *StrongParameters* в рельсах, дебажил и правил её
    # буквально за несколько часов до мероприятия. Симптом - непомерное время обработки
    # *POST* запроса на больших досках (сильно за пределами timeout-а), при предельно
    # примитивной реализации контроллера. Вскрытие показало, что *params* с некоторых пор
    # уже совсем не *Hash* о_О, доступ к значению по ключу реализован полным перебором,
    # оттого каждое обращение по ключу в моем случае занимает около 1мс.
    # В обычном приложении сей прискорбный факт не играет особой роли -
    # *CGI* параметров приходит немного (а значит, дистанция полного перебора невелика),
    # количество обращений незначительно. В нашем же случае, если итерировать наш игровой
    # параметр cells прямо из *params* на доске размера 7 - теряем 170мс только на чтение
    # из *params*. Лечится с помощью *params.to_unsafe_h*.
    @@games[params[:id]] = Robot.new(
      params[:board].to_unsafe_h,
      params[:jumps].to_unsafe_h
    )

    render json: {status: :ok}
  end

  def show
    render json: {
      status: :ok,
    }.merge(
      @@games[params[:id]].turn(params[:color].to_i)
    )
  end

  def update
    @@games[params[:id]].update(params[:changes], params[:jumps].to_unsafe_h)
    render json: {status: :ok}
  end

  def destroy
    @@games.delete(params[:id])
    render json: {status: :ok}
  end

end

Беглый, без особых заморочек, код бота:

class Robot

  attr_reader :board, :jumps

  # Запоминаем начальное состояние доски
  # Хранить доску будем в исходном формате, то есть в двумерном массиве
  def initialize(_board, _jumps)
    @board = _board['cells'].deep_dup
    @jumps = _jumps
  end

  # Применяем изменения доски
  def update(changes, _jumps)
    changes.each do |i, j, _, new_color|
      board[i][j] = new_color
    end
    @jumps = _jumps
  end

  def turn(color)
    opposite_color = color == 1 ? 2 : 1

    # Переводим runtime сложность алгоритма из квадратичной в линейную -
    # за один проход по доске группируем ячейки по цветам.
    color_groups = (0...board.size).inject({}) { |mem, i|
      (0...board[i].size).inject(mem) { |mem, j|
        c = board[i][j]
        mem[c] ||= []
        mem[c] << [i, j]
        mem
      }
    }

    # Собираем все возможные ходы
    moves = []

    # Для всех пустых ячеек..
    color_groups[0].each do |to|
      # ищем такую фишку нашего цвета, что..
      color_groups[color].each do |from|
        distance = cell_distance(from, to)
        # дистанция полученного хода соотносится с правилами игры
        next if distance == :wrong || (distance == :jump && jumps[color.to_s] <= 0)

        # Считаем ценность хода, размножение даёт +1 очко само по себе
        value = distance == :populate ? 1 : 0
        # Каждая вражеская фишка вокруг целевой ячейки хода даёт +2 очка,
        # так как она перекрашивается в наш цвет -
        # противник теряет одно очко, мы получаем
        value += neighbor_indexes(*to).count{ |i, j| board[i][j] == opposite_color} * 2

        moves << {move_from: from, move_to: to, value: value}
      end
    end

    # Выбираем "Лучший" ход
    choose_best(moves)
  end

  private

  def choose_best(moves)
    # Находим максимальную ценность среди всех доступных ходов
    best_value = moves.map{ |m| m[:value] }.max

    # Выбираем случайных ход из самых "ценных"
    moves.select{ |move| move[:value] == best_value }.sample
  end

  # Расчёт дистанции между двумя ячейками.
  # Не спрашивайте, почему и как это работает - 
  # писалось второпях, в "турнирном" режиме, суть есть результат
  # возни с листиком и ручкой )
  def cell_distance(from, to)
    y_delta = if from[0] % 2 == to[0] % 2
      0
    elsif from[0] % 2 == 0
      -0.5
    else
      0.5
    end

    x_distance = (from[0] - to[0]).abs
    y_distance = (from[1] - to[1] + y_delta).abs

    distance = x_distance + y_distance

    if distance <= 1.5
      :populate
    elsif distance <= 2.5 || ( distance == 3 && x_distance == 2)
      :jump
    else
      :wrong
    end
  end

  # Поиск соседних ячеек.
  # По хорошему надо просто хардкодить разницы индексов
  # как мы делали в классе BoardSolver, но захотелось заморочиться -
  # дабы компенсировать то, что я начал  писать бота уже неделю зная о сути игры.
  def neighbor_indexes(i, j)
    6.times.map { |edge_id|
      neighbor_i = i
      if edge_id == 0 || edge_id == 1
        neighbor_i -= 1
      elsif edge_id == 3 || edge_id == 4
        neighbor_i += 1
      end

      neighbor_j = j;
      if edge_id == 2 || (i % 2 == 1 && [1, 3].include?(edge_id) )
        neighbor_j += 1
      elsif edge_id == 5 || (i % 2 == 0 && [0, 4].include?(edge_id) )
        neighbor_j -= 1
      end

      (
        (0...board.size).include?(neighbor_i) &&
        (0...board[0].size).include?(neighbor_j)
      ) ? [neighbor_i, neighbor_j] : nil
    }.compact
  end

end

Тренировочный бот готов - деплоим в $10 дроплет, такой же, как и у всех игроков. Время ответа на любой запрос - ~3мс. При этом бот принимает полноценное участие в турнире сразу в четырех песочницах, то есть в худшем случае опрашивался в 40 потоков вместо обычных для игроков 10ти - никаких таймаутов не замечено на всём протяжении турнира.

Конкретное время написания этого бота озвучивать не стану: назову циферку слишком малой - будет выглядеть как бахвальство; если циферка слишком велика - распишусь в проф непригодности; в любом случае получается плохо ) Скажем так - было признано, что нечто подобное возможно написать в рамках турнирного времени, и должно остаться время на попытку реализации чего-нибудь более интеллектуального - того же MiniMax-а.

Да, пора закругляться программированием движка )

За кадром остаётся огромное количество работы - онлайн игра, реплеи, игровые события, real-time график набора очков с метками релизов (пожалуй, самая изматывающая в реализации фича, но насколько эффектная!), множество мелочей.

В заключительной статье поговорим о том, как это всё тестировалось - продолжение следует )

Связаться