IT Duel 2017: "Battle of the Bots - Hexagon" Creation of the Game - The Game Engine

In the previous articles of the series we decided on the required playground functionality and prepared a runtime infrastructure for game bots and sandboxes. It’s time to actually program the game engine. As the main tools we will use RoR and Sidekiq on the backend, ReactJS and WebSocket on the frontend.

Prepare dependencies for the task queue

Let’s add sidekiq to our Ruby on Rails application. During the tournament we will need to process a lot of game battles between bots, and it would be nice to perform the games calculation in multithreaded mode, with the horizontal scaling possibility in case of need. The delayed tasks queue, processed by the worker processes pool, is a simple and effective way to achieve this.

Use sidetiq as the manager for periodic tasks. In the game engine there will be implemented a single periodic task, performed every 15 seconds, responsibility of which is to summarize the current games round and prepare the next round.

It is worth noting that the periodic task in the sidetiq implementation is nothing more than the periodic addition of the same delayed task. We will prevent duplication of this task using sidekiq-unique-jobs gem.

Let’s learn how to order and remove DigitalOcean droplets for players based on the image we prepared

A droplet_kit with a small add-on will help us:

class DropletClient
 # The name of master SSH key in the DigitalOcean panel
 SSH_KEY_NAME = 'fourcolor'.freeze

 # API token and name of DigitalOcean image for bots
 def initialize(access_token, image_name)
  @access_token, @image_name = access_token, image_name
 end

 # Generate a unique name for the created droplet,
 # using the value of the auto-increment primary key from the database
 def name(local_id)
  "#{@image_name}-#{Tournament::CURRENT_SANDBOX}-#{local_id}"
 end

 # Creating a droplet based on the prepared image,
 # along with this put the master SSH key into the root user
 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

 # Removing a droplet
 def delete(id)
  client.droplets.delete(id: id)
  true
 rescue DropletKit::Error
  false
 end

 # Receiving an IP address of the created droplet
 # Remember that the IP becomes available 20-30 seconds
 # after the creation of the droplet
 def fetch_host(id)
  client.droplets.find(id: id).networks.v4.first&.ip_address
 rescue DropletKit::Error
 end

 private

 # client for DigitalOcean API
 def client
  @client ||= DropletKit::Client.new(access_token: @access_token)
 end

 # Identifier for DigitalOcean image
 def image
  @image ||= client.images.all.detect{|d| d.name == @image_name}.id
 end

 # Fingerprint for the master SSH key
 def ssh_keys
  @ssh_keys ||= client.ssh_keys.all
   .select{|k| k.name == SSH_KEY_NAME}
   .map(&:fingerprint)
 end

end

All operations with droplets are performed through delayed tasks, since the process, frankly speaking, is not instantaneous - fetch_host will start to return the droplet IP in 20 seconds after its creation:

class Droplet < ApplicationRecord

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

 # Mass order of droplets
 def self.mass_create!(count)
  transaction { count.times { create! } }
 end

 # Mass removing of droplets
 def self.mass_destroy!(ids)
  transaction { find(ids).count { |droplet| droplet.destroy } }
 end

 # Order a droplet on DigitalOcean, save its external identifier,
 # and schedule the delayed task for obtaining the IP address of the created droplet.
 # This method should be called solely from the delayed task.
 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

 # Try to receive and save the droplet IP address,
 # in case of failure, schedule the corresponding delayed task one more time.
 # When restarting the delayed task, do not rely on the regular `job retry` feature,
 # It is better to re-schedule the task manually, in accordance with the principle
 # "normal business logic should not be based on raising of exceptions".
 #
 # This method should be called solely from the delayed task.
 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

 # Schedule delayed task for ordering a droplet
 def create_client_async
  CreateDropletJob.perform_later(id)
 end

 # Schedule a delayed task for removing a droplet
 def delete_client_async
  DeleteDropletJob.perform_later(client_id) if client_id
 end

end

The code for pending tasks is fairly primitive, as it should be:

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

Teams registration in the admin panel

The list of teams management is an ordinary CRUD, with using dynamic-fields-for when building a list of players.

To generate login tokens (and in the future - also to generate the identifiers for games and replays) we will use the wonderful library hashids. Since this token generation algorithm is reversible, we do not need to store tokens in the database. In addition, if we use SECRET_KEY_BASE as the “salt” of the algorithm, we can, if desired, invalidate all tokens simultaneously with the sessions:

class Team < ApplicationRecord
 # Initiate a token generator
 HASHIDS = Hashids.new(
  Rails.application.secrets[:secret_key_base] + 'Team',
  16,
  ('A'..'Z').to_a.join
 )

 # Generating a token based on the primary key value
 def auth_token
  @auth_token ||= HASHIDS.encode(id)
 end

 # Readable token - break it into 4 symbols, combine through a hyphen
 def auth_token_humanized
  auth_token.scan(/.{4}/).join('-')
 end

 # Search for a record in the database by a token
 def self.find_by_auth_token(token)
  find_by_id(HASHIDS.decode(token.to_s))
 rescue Hashids::InputError
 end

end

Printing the team flyer

Let’s give the admin the ability to print the team flyer directly from the page with the list of teams or from the team edit page, without reloading the page. The task is solved using the iframe in the layout template:

!!!
%html
 %body
  -# any custom markup
  yield

  -# iframe with a special data attribute
  %iframe{ src: flash[:print], data: {'print-target' => true} }

Hide iframe with styles:

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

Revive the iframe using the coffee script:

$(document).on 'turbolinks:load', ->
 # Automatically open the system dialog box of a printer
 # when loading something into the iframe
 $('[data-print-target]').on 'load', (event) ->
  event.target.contentWindow.print() if $(event.target).attr('src')

$ ->
 $(document).on 'click', 'a[data-print]', (event) ->
  # Load link addresses from the "print" data attribute
  # not into the main browser window, but in the iframe
  $('[data-print-target]').get()[0].src = $(event.target).parent().attr('href')
  event.preventDefault()

Now you can print the response of any endpoint from an arbitrary location in the application:

# Printing from the view
link_to teams_manage_path(resource), data: {print: true} do
 %i.material-icons print

# Printing from the controller
# print_and_new - this is the name of one of the submit buttons on the edit form.
# To recognize the clicking on a particular button, use the well-known trick -
# instead of showing in the template several submit buttons
# with the same name attribute, and painful recognition in the controller
# of a specific button by the value attribute
# (multilingual, icon instead of text, etc.) - each button is given a unique name,
# and in the controller a corresponding CGI parameter is recognized
# by the fact that it is there, whatever its actual value is
if params[:print_and_new]
 flash[:print] = teams_manage_path(@resource)
 redirect_to action: :new
else
 redirect_to action: :index
end

Adding the player’s SSH key to the team droplet

The players enter their public SSH key into the form on the sandbox site, then this key will be used to deploy new bot releases into the gameplay droplet. Remember that in the sandbox container there is already a private master SSH key, and in the droplets with bots the public master SSH key is put in the root user - it should work!

When validating the SSH key format, sshkey will help us:

class Droplet < ApplicationRecord
 def add_ssh_key(key)
  # player's public SSH key comes from user input - validate carefully!!!
  return :blank if key.blank?
  return :wrong unless SSHKey.valid_ssh_public_key?(key)

  # escape the key (!!!), and add it to the dokku user in a player's droplet
  `echo #{key.shellescape} | ssh -oStrictHostKeyChecking=no -oUserKnownHostsFile=/dev/null root@#{host} "sudo sshcommand acl-add dokku [player]"`

  # Check the exit code of the last shell command
  $?.to_i == 0 ? :ok : :error
 end
end

Apparently, without SSHKey.valid_ssh_public_key? and key.shellescape, we would provide an opportunity for anyone who wants to execute an arbitrary shell script using the SSH key input form, with all the consequences () =) ;;;;>

Mechanics of rounds calculation

As the main loop of the game engine, we implement a periodic task that runs every 15 seconds.

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

 # Disable the regular retry, turn on the task uniqueness in the queue
 sidekiq_options(
  retry: false,
  unique: :until_and_while_executing
 )

 # Set the task periodicity
 recurrence { minutely.second_of_minute(0, 15, 30, 45) }

 def perform
  # Wait for the round calculation completion
  unless Game.pending.any?
   finish_previous_rounds
   delete_marked_teams
   prepare_tournament
   apply_events
   prepare_next_round
  end
 end

  # Finalize the calculated round
 def finish_previous_rounds
  Round.finish_pending
 end

 private

 # Delete the teams marked for deletion by the admin -
 # for application health it is safer to do it between rounds
 # but not in the middle, when the team is involved in the games calculation
 def delete_marked_teams
  Team.destroy_marked!
 end

 # Prepare the tournament as a whole -
 # open the game interface instead of promo page stub, reset team points,
 # initiate the game events queue.
 #
 # The method performs useful work at the end of the countdown
 # to the tournament start on the promo page, as well as when the administrator
 # restarts the tournament manually.
 def prepare_tournament
  Tournament.instance.prepare!
 end

 # Apply game events, if the term of their entry into the game has come
 def apply_events
  Event.apply!
 end

 # Prepare the next round for the calculation,
 # schedule the delayed tasks for calculating specific games.
 def prepare_next_round
  Round.prepare!
 end

end

This worker waits until all the games of the round have finished, then performs a series of actions …

RoundWorker#finish_previous_rounds

Give the teams points for the games in the current round, mark the round as “finished”:

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

Instead of thinking about how the engine will be affected by the immediate team removal (crashed the delayed tasks of games calculation, WEB interface update, etc.) - the admin only marks the team for deletion, the actual deletion occurs when the current round ends:

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

The administrator can restart the tournament - the actual restart occurs when the current round ends, just like the team removal:

class Tournament < ApplicationRecord

 def prepare!
  start_from_beginning! if start_from_beginning?
 end

 private

 def start_from_beginning!
  transaction do
   # Clean the delayed tasks queue
   Sidekiq::Queue.new('game').clear

   # Bring the tournament attributes to the initial state
   update_attributes!(
    started: false,
    finished: false,
    start_from_beginning: false
   )

   # Clear game tables in the database
   [Game, Round, Score, RoundType].each(&:truncate!)

   # Cancel the game events which have already begun
   Event.update_all(applied: false)

   # Reset team points
   Team.all.each(&:create_initial_score)
  end

  # Clear statistics of the executed delayed tasks
  Sidekiq::Stats.new.reset

  # Notify the client via WebSocket about the need to reload the page.
  # In case the tournament start time is set in the future -
  # the game interface will be blocked by a promo stub page with a countdown
  # to the tournament start.
  LadderIndexChannel.broadcast(:reload)
 end

end

RoundWorker#prepare_next_round

Let’s prepare the next round.

class Round < ApplicationRecord

 def self.prepare!
  # Round types are just a containers for game session parameters -
  # board size, points multiplier, etc.
  # The round type changes cyclically, one after another and in a circle.

  # Find the round type that was played in the previous round
  last_round_type_id = order(:id).last&.round_type_id || 0

  # Get the next round type
  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
    # Create a new round
    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
    )

    # Take all teams combinatorial combinations in two,
    # the combinations list is randomized to evenly distribute the load on bots
    Team.all.to_a.combination(2).to_a.shuffle!.each do |teams|
     # The first team in this pair will take the first move, thus -
     # randomize the array, depriving the gameplay of predictability
     teams.shuffle!

     # Create a game for a teams pair on the selected board type
     association_class(:games).create!(
      round: round,
      team1: teams[0],
      team2: teams[1],
     )
    end
   end
  end
 end

end

All created game sessions are placed in the delayed tasks queue for further calculation. In the process, notify the client about a new match using 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

Calculation of the match

Finally, the most interesting! Program the game logic :)

To begin with, let’s learn how to generate random game fields:

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

 # Generate the template for the game board with the required size,
 # it will include all the game elements (stones, empty cells,
 # the initial position of the players' chips) -
 # everything, except random additional stones.
 def self.scaffold(size)
  # The board templates are always the same
  # relative to the requested size of the field - memoize
  scaffolds[size] ||= begin
   cells_size = size * 2 - 1

   # Prepare an empty playing field
   cells = Array.new(cells_size) {
    Array.new(cells_size, 0)
   }

   # Here's how to "frame" the field by stones around the perimeter,
   # as a result, the remaining empty cells form a regular hexagon
   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

   # Put the initial players chips on the field
   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

   # Gather the empty cells coordinates into the array -
   # this will come in handy when "placing" random stones on the field
   empty_cells = cells_size.times.inject([]) { |mem, i|
    cells_size.times.inject(mem) { |mem, j|
     mem << [i, j] if cells[i][j] == 0
     mem
    }
   }

   # Calculate the optimal number for random stones
   additional_rocks_count = empty_cells.size / 10
   # Add one more random stone,
   # so that the total number of cells available for the game was odd -
   # minimize the draw chance
   additional_rocks_count += 1 if (empty_cells.size - additional_rocks_count).even?

   # The board template is ready!
   {
    cells: cells,
    empty_cells: empty_cells,
    additional_rocks_count: additional_rocks_count
   }.freeze
  end
 end

 # Actually, the random board generation
 def initialize(_size)
  @size = _size

  # Take the board template with the size asked for
  scaffold = self.class.scaffold(size)

  # Clone the template, place random stones on it
  @cells = scaffold[:empty_cells]
   .sample(scaffold[:additional_rocks_count])
   .inject(scaffold[:cells].deep_dup){ |mem, (i, j)|
    mem[i][j] = -1
    mem
   }
 end

end

Let’s put the game logic into a couple of separate classes. Program with particular attention - these classes deal with the user input, it is here that players’ moves are processed.

First, write a class that is responsible for the game field operations logic. There is a temptation to store the board state in the form of a two-dimensional array, in the same manner in which it is generated and sent to the bots. I admit, this option was implemented at the stage of prototyping, with all the consequences - for example, a complete search of the entire board when searching for available moves. In the release version, only the players’ available moves were stored and maintained in the actual state - the code turned out to be nicer, the productivity increased two times (although I expected a more convincing increase…). So,

class BoardSolver
 class WrongMove < StandardError; end

 # Cheap and cheerful - hardcode the differences in indexes
 # between the target cell and its neighbors
 NEIGHBOR_DELTAS = [
  # for cells from even-numbered rows
  [
   # Zero distance to neighbors - no neighbors.
   # Just write an empty array to use Array but not Hash,
   # and do not fuss with indexing
   [],
   # Distance to neighbors is equal to one cell, move type is reproduction
   [[-1,-1],[-1,0],[1,-1],[1,0],[0,-1],[0,1]],
   # distance to neighbors is equal to two cells, type of move - jump
   [
    [-1,-2],[-1,1],[1,-2],[1,1],[0,-2],[0,2],
    [-2,-1],[-2,0],[-2,1],[2,-1],[2,0],[2,1]
   ]
  # Similarly for cells from odd rows
  ],[
   [],
   [[-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

  # We will keep the possible moves data in the format
  # possible_moves[color][move_from][move_to] = distance
  # When filling possible_moves, we will ignore the number of available jumps.
  # Also, the presence of the move_from key in the @possible_moves[color] hash
  # indirectly indicates that the cell move_from is colored in color
  @possible_moves = Array.new(3){ {} }

  # For each game color, support information about available jumps,
  # taken moves of "reproduction" type, and game points
  @jumps, @populates, @score = 3.times.map{ {1 => 0, 2 => 0} }

  # Fill possible_moves[0] with empty cells -
  # it's impossible to make a move from them, but we will need
  # that indirect indication of an empty cell
  each_cell(cells) do |cell, color|
   possible_moves[color][cell] = {} if color == 0
  end

  # In fact, the starting chips are exposed to an empty board
  # with the help of the "reproduction" -
  # pass them through the generalized apply_changes method.
  each_cell(cells) do |cell, color|
   apply_changes([[*cell, 0, color]]) if (1..2).include?(color)
  end
 end

 # Applying board changes
 def apply_changes(changes)
  # Keep jumps and populates up to date
  _, _, old_color, new_color = changes.first

  # The situation when the cell is released by the first change -
  # a sign of a move like "jump"
  if new_color == 0
   # the jump is spent
   jumps[old_color] -= 1
  else
   # A move of the type "reproduction" is made
   populates[new_color] += 1
   # For every second reproduction the player receives one available jump
   jumps[new_color] += 1 if populates[new_color] % 2 == 0
  end

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

   # Keep score up to date
   score[old_color] -= 1 if old_color != 0
   score[new_color] += 1 if new_color != 0

   # The cell changes color,
   # so its previous owner can no longer make a move from it
   possible_moves[old_color].delete(cell)

   # The cell has ceased to be blank, so no one can make a move into it anymore.
   if old_color == 0
    possible_moves[1..2].each do |moves|
     moves.each do |_, to|
      to.delete(cell)
     end
    end
   end

   # The cell has a new color!
   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 ?
       # the cell was released,
       # now neighboring players' chips can take a move into it
       [neighbor_color, neighbor_cell, cell] :
       # the cell is repainted in the player's color,
       # now the player can take a move from it
       # to neighboring empty cells
       [new_color, cell, neighbor_cell]

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

 # An attempt to apply the player's move
 def apply_move!(color, move_from, move_to)
  # There is no need to check the format of incoming data
  # and the indexes entry in the board size -
  # possible_moves knowingly stores only valid moves in the correct format.
  # It is enough just to check the requested key presence in possible_moves.
  distance = possible_moves.dig(color, move_from, move_to)

  # The move is invalid because of an incorrect format,
  # the indexes falling outside the board,
  # or inadequacy of the move to the rules of the game
  raise WrongMove unless distance && possible_distance?(color, distance)

  opposite_color = self.class.opposite_color(color)

  # Create the changes array for the subsequent sending to the players
  neighbors(move_to, 1, opposite_color).map{ |i, j|
   # The enemy cells adjacent to the target cell of the move,
   # are recoloured in the color of the player
   [i, j, opposite_color, color]
  }.tap{ |changes|
   # The target cell is recoloured in the player's color
   changes.unshift([*move_to, 0, color])

   # The cell from which the move is made is released
   # if a move such as "jump" is made
   changes.unshift([*move_from, color, 0]) if distance == 2

   # Update the game data according to the calculated changes array
   apply_changes(changes)
  }
 end

 # There is at least one valid move for the player,
 # if there is at least one possible_moves entry for this player
 # with an allowable distance in terms of jumps
 def any_possible_move?(color)
  possible_moves[color].any? { |_, to|
   to.any?{ |_, distance|
    possible_distance?(color, distance)
   }
  }
 end

 # The distance of the move is always permissible for "reproduction",
 # for "jump" it is regulated by the value in the jumps hash
 def possible_distance?(color, distance)
  distance == 1 || jumps[color] > 0
 end

 # Just reversing the color
 def self.opposite_color(color)
  color == 1 ? 2 : 1
 end

 # Search for cells spaced a specified distance from the target,
 # and painted in the specified color
 def neighbors(cell, distance, color)
  # An excellent ruby trick for creating Enumerable objects,
  # with all the consequences
  return enum_for(:neighbors, cell, distance, color) unless block_given?

  NEIGHBOR_DELTAS[cell.first%2][distance].each do |deltas|
   # Get the neighboring cell indexes
   neighbor_cell = deltas.each_with_index.map{ |delta, index|
    cell[index] + delta
   }

   # Iterate an adjacent cell if its indexes are within the board,
   # and painted in the specified color
   yield(neighbor_cell) if indexes_inside_board?(neighbor_cell) &&
    possible_moves[color].key?(neighbor_cell)
  end
 end

 private

 # Just a utility method for iterating the original two-dimensional board
 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

 # Checking the cell indexes for entering the dimensions of the board
 def indexes_inside_board?(cell)
  cell.all?{ |index| (0...cells_size).include?(index) }
 end
end

Great, it works! :) Now let’s describe a class that implements the general gameplay:

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

 def initialize(board, *_players)
  # We will need to interact with the board
  @solver = BoardSolver.new(board.cells)

  # The array of players, the first of them makes the first move
  @players = _players
  @current_player = players.first

  # The game starts with color 1
  @current_color = 1

  # A flag that the game is over
  @game_over = false

  # Paranoia like it is.. )
  @mutex = Mutex.new
 end

 # Hash-mapping of the player's primary key to his game score
 def score_by_team_id
  players.map.with_index{ |p, i| [p.id, solver.score[i+1]] }.to_h
 end

 # The utility method for getting the loser player
 def looser
  points = solver.score.values.uniq

  points.size == 1 ?
   # Points are equal, a draw
   nil :
   players[solver.score.key(points.min)-1]
 end

 # An attempt to apply the player's move
 def apply_turn(player, move_from, move_to)
  @mutex.synchronize do
   # Check the possibility of the move from the general gameplay point of view
   check_move_possibility!(player)

   # Apply the move, get the changes array
   changes = solver.apply_move!(current_color, move_from, move_to)

   # Change the current player and the current color to opposite,
   # check if the end of the game is reached
   @game_over = true

   # The game is over if both players do not have valid moves
   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

 # The opposite color
 def opposite_color
  solver.class.opposite_color(current_color)
 end

 # The opposite player
 def opposite_player
  players.first == current_player ? players.second : players.first
 end

 # Only the current player can make a move, and only if the game is not over
 def check_move_possibility!(player)
  raise BoardSolver::WrongMove if game_over || player != current_player
 end

end

The match calculation code does not conceal in itself anything supernatural - many lines, the essence is mechanical work - just sit down and carefully code.

Some confusion in the code is a consequence of the fact that the same class is used for both synchronous and uncompromising game between two bots, and for the game between the training bot and the web user who plays asynchronously, has no timeouts and penalties for incorrect moves. An attempt was made to “straighten” the code with Fiber, but it turned out that Fiber was losing its resume context (the consequence of the serialization-deserialization somewhere in the depths of ActionCable). I had to use throw & catch. There was neither time nor energy to refine the code in excess of the following.

Particular attention is paid to exceptional situations - this code deals with a user input, while it has a key impact on the tournament outcome.

For requests to the bots API, we use the extremely comfortable httparty library.

During the game session, remember the moves and key parameters of the playing board - it will come in handy for displaying replays.

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)

  # In this array we will accumulate player moves for the replay
  @moves = []
 end

 # A special case of initiating an online game with a man
 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

 # A special case of starting an online game with a man
 def play_async(*args)
  catch(:async) do
   play(*args)
  end
 end

 # The main entry point into the game calculation
 def play(*args)
  # Catch the game over event
  looser, reason = catch(:game_over) do
   # Initialize the game for bots
   init if moves.empty?

   # Start the basic moves calculation loop
   turns(*args)
  end

  # Finalize the game for bots
  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
  }

  # Again dances around an asynchronous web player
  throw(:async, [:game_over, move: moves.last]) if team1.async || team2.async

  moves
 end

 # Send players a notification of the game over
 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

 # Send players a notification of the game beginning
 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

 # The main loop for players polling
 def turns(action = nil, move_from = nil, move_to = nil)
  while(true) do
   unless action == :updated
    team = gameplay.current_player
    color = gameplay.current_color

    # Request a move from the player
    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)

    # Try to apply the player's move
    turn_status, changes = gameplay.apply_turn(team, move_from, move_to)
    if (turn_status == :wrong)
     if team.async
      # Forgive the wrong move to the web player
      moves.pop
      get(team, color)
     else
      # Punish the bot immediately for a wrong move
      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

   # Send players a notification about the change in the board state
   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

   # Stack surface when the game is over
   throw(:game_over, [gameplay.looser&.id, :by_score]) if gameplay.game_over
   action = nil
  end
 end

 # A wrapper around all HTTP requests, for catching connection errors and timeouts
 def catch_errors
  yield
 rescue Net::OpenTimeout, Errno::ECONNREFUSED
  :no_connection
 rescue Net::ReadTimeout
  :timeout
 rescue
  :wrong_response
 end

 # POST request to a bot side containing information about the initial board
 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 request to a bot side containing information about board state changes
 def update(team, move)
  # Dancing around an asynchronous web player...
  if team.async
   # In this case, sleep is not a sign of a programmer's helplessness,
   # but a conscious delay after the web player's move -
   # otherwise the web player's move was visually merged
   # with the immediate response from training bot,
   # and monitoring the gameplay was extremely difficult
   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 request to the side of bot, requesting another move
 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 request to the side of the bot, giving notification of the game over
 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 for bot endpoint
 def droplet_url(team, with_session = true)
  "http://#{team.droplet.host}/games".tap{ |url|
    url.concat("/#{session_id}") if with_session
   }
 end

 # Immediately count the defeat to the player at any failure :)
 def check_move_status!(moves)
  throw(:game_over, [
   moves.last[:team],
   moves.last[:status]
  ]) unless moves.last[:status] == :ok
 end

end

Well, almost everything is ready on the backend, it’s time to get busy with the frontend!

Real time web interface update

Let’s use WebSockets to notify the client about changes in the game world.

As an example, we will analyze the ladder page, that is, the tournament list of teams. The page should respond to:

  • CRUD-actions of the administrator regarding the teams;
  • Changes in teams scores, as a consequence - changing the order of teams in the ladder;
  • Reaction to new releases.

Let’s write a simple WebSocket channel controller:

class LadderIndexChannel < ApplicationCable::Channel

 # Subscribe the client to the stream
 def subscribed
  stream_from self.class.stream_name
 end

 # Generate the stream name
 def self.stream_name
  'ladder_index'
 end

 # Sending a message to a stream
 # his method can be called from anywhere - models, controllers, delayed tasks, etc.
 def self.broadcast(action, options = {})
  ActionCable.server.broadcast(
   stream_name,
   options.merge(action: action)
  )
 end

end

Stepping aside and only as an example of a parametrized channel, we give the controller code for the page for monitoring the specific team:

class LadderShowChannel < ApplicationCable::Channel

 def subscribed
  # Subscribe the client to the ladder general stream
  # On the client, respond to the page refresh command
  # when the tournament is restarted
  stream_from LadderIndexChannel.stream_name

  # Subscribe to the general channel for all teams.
  # It is used to update the chart with teams score dynamics.
  stream_from self.class.stream_name

  # Sign up to a specific team stream.
  # This is the stream that distributes information on the current team games.
  stream_from self.class.stream_name(params[:team_id])
 end

 # The parameterized stream name
 def self.stream_name(team_id = nil)
  "ladder_show".tap { |name|
    name << "_#{team_id}" if team_id
   }
 end

 # Sending a message to the team channel
 def self.broadcast(team_id, action, options = {})
  ActionCable.server.broadcast(
   stream_name(team_id),
   options.merge(action: action)
  )
 end

end

Let’s return to the ladder page, start sending messages to the channel about the admin’s actions in relation to the teams. The following code hardly needs the further comments:

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

React to change in the team’s score and to a new release (it was very convenient to keep the new release flag in the Score model to show the release moments on the dynamic scores chart):

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

Everything is ready on the server side, let’s deal with the client. Using the react-rails library, write a couple of spiteful React components:

var LadderIndex = React.createClass({

 componentDidMount() {
  // Establish WebSocket connection
  this.channel = App.cable.subscriptions.create('LadderIndexChannel', {
   received: (data) => {
    // Call a method corresponding to the action received from the channel,
    // if this method is declared
    this[data.action] && this[data.action](data)
   }
  });
 },

 componentWillUnmount() {
  // Close connection
  this.channel.unsubscribe();
 },

 reload(data) {
  // Respond to the page reload command
  location.reload()
 },

 update_scores(data) {
  // Respond to the command of teams scores upgrade,
  // send the data to the nested component
  this.refs.scores.update_scores(data.scores)
 },

 add_score(data) {
  // Respond to the scores upgrade command for a specific team,
  // send the data to the nested component
  this.refs.scores.add_score(data.score)
 },

 rename_score(data) {
  // Respond to the command for upgrading team attributes,
  // send the data to the nested component
  this.refs.scores.rename_score(data.team_id, data.name, data.no_contest)
 },

 remove_score(data) {
  // React to the command to remove the team,
  // send the data to the nested component
  this.refs.scores.remove_score(data.team_id)
 },

 new_release(data) {
  // React to the new release of the team,
  // send the data to the nested component
  this.refs.scores.new_release(data.score)
 },

 render() {
  // Display the nested component
  return (
   <div className="teams">
    <LadderIndexScores ref="scores" scores={this.props.scores} />
   </div>
  );
 }

});
var LadderIndexScores = React.createClass({

 getInitialState() {
  // The initial ladder state is provided directly through the props
  return this.scores_to_state(this.props.scores)
 },

 update_scores(scores) {
  // Update teams scores
  this.setState(this.scores_to_state(scores))
 },

 scores_to_state(scores) {
  // Generate an object to update the state
  return {
   scores: _(scores).reduce((memo, score) => {
    memo[score.team_id] = score
    return memo
   }, {})
  }
 },

 add_score(score) {
  // Update scores for a single team
  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) {
  // Update the team attributes
  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) {
  // Delete a team
  let new_scores = _(this.state.scores).omit(team_id)

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

 new_release(score) {
  // Mark the team as having a fresh release
  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() {
  // Sort teams by descending scores
  let scores = _(this.state.scores).sortBy('position')

  // Show the tournament list
  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">New release!</span>}
      </li>
     )
    })}
   </ul>
  )
 }

});

It remains only to draw the LadderIndex component, and it will live its own life. Render directly from the Rails controller, with server-side precompilation:

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

Training bot

Let’s write a training bot. This guy will be deployed from the very beginning of the tournament, but will not qualify for the prize. Its mission is to be an opponent in the online game, and also be a sparring partner for teams in the early stages of the tournament.

We will write in Ruby on Rails, in API-only mode. For a basis, take the corresponding template, update only the controller code and add one utility class. The algorithm is the most primitive, just to consciously finish the game, without violating the rules - a complete search of all available moves, counting the difference in chips after each move, choosing a random move from those that give the greatest difference in chips. At the same time, we will assess whether the programming problem is feasible for the players, that is, how long it takes for the bot implementation to be minimally meaningful.

Let’s show the bot code as it is, raw. The controller looks exactly as it should:

class GamesController < ApplicationController
 # A small trick is storing board states in a class variable, not in a file or DB,
 # that is, avoid serialization - the benefit is that the default web server *puma*
 # is multithreaded, rather than multi-process
 @@games = {}

 def create
  # There was a problem with *StrongParameters* in Rails,
  # I debugged and fixed it just a few hours before the event.
  # The symptom is an unreasonable processing time
  # of *POST* request on large boards (much beyond the timeout), with extremely
  # primitive implementation of the controller. The autopsy showed that *params*
  # for is not a *Hash* anymore o_O, the access to the value by the key
  # is implemented by a full search,
  # therefore each request by key in my case takes about 1ms.
  # In a normal application, this regrettable fact does not play a significant role -
  # there comes a bit of *CGI* parameters
  # (which means that the distance of the full search is not large),
  # the number of requests by key is insignificant. In our case,
  # if we iterate our cells gaming parameter directly from *params*
  # on a board of size 7 - we lose 170ms only for reading from
  # *params*. It is treated with *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

A brief, with no special frills, bot code:

class Robot

 attr_reader :board, :jumps

 # Remember the initial state of the board
 # We will store the board in the original format, that is,
 # in a two-dimensional array
 def initialize(_board, _jumps)
  @board = _board['cells'].deep_dup
  @jumps = _jumps
 end

 # Apply changes to the board
 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

  # Transform the runtime complexity of the algorithm from quadratic to linear -
  # in one play on the board we group cells by colors.
  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
   }
  }

  # Collect all possible moves
  moves = []

  # For all empty cells...
  color_groups[0].each do |to|
   # we are looking for such a chip of our color that...
   color_groups[color].each do |from|
    distance = cell_distance(from, to)
    # the distance of the given move is correlated with the rules of the game
    next if distance == :wrong || (distance == :jump && jumps[color.to_s] <= 0)

    # Calculate the value of the move, reproduction gives a +1 point by itself
    value = distance == :populate ? 1 : 0
    # Each enemy chip around the target cell gives +2 points,
    # since it is recoloured in our color -
    # the opponent loses one point, we get it
    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 "The Best" move
  choose_best(moves)
 end

 private

 def choose_best(moves)
  # Find the maximum value among all available moves
  best_value = moves.map{ |m| m[:value] }.max

  # Choose a random move from the most "valuable"
  moves.select{ |move| move[:value] == best_value }.sample
 end

 # Calculating the distance between two cells.
 # Do not ask why and how it works -
 # it was written in a hurry, in the "tournament" mode, the essence is the result of
 # fuss with paper and a pen :)
 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

 # Search for nearby cells.
 # An easy way is just to hardcode the differences in the indexes
 # as we did in the BoardSolver class,
 # but I wanted to go to the trouble of doing it -
 # in order to compensate for the fact that I started writing a bot
 # already knowing the essence of the game for a week before.
 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

The training bot is ready - let’s deploy it to a $10 droplet, the same as for all players. The response time for any request is ~3ms. In this case, the bot takes full participation in the tournament in four sandboxes at once, so in the worst case it was requested from 40 threads instead of the 10 usual for regular players, and no timeouts were observed throughout the whole tournament.

I will not disclose the exact time spent on writing this bot: a too small figure will look like bragging while too big one will mean my ineptitude - in any case, it won’t be good. Let’s just say that it was recognized that something like this can be written within the tournament time, and there should be time to try to implement something more intelligent, like MiniMax, for example.

It’s time to wrap it up

Behind the scenes, there is a huge amount of work - online game, replays, game events, real-time chart for the scores with release tags (perhaps the most exhausting, but a very spectacular feature!) and many small stuff.

In the final article, let’s talk about how all this was tested - to be continued :)

Keep reading

Do You Know How Hash Table Works? (Ruby Examples)

Do You Know How Hash Table Works? (Ruby Examples)

Hash table is a data structure that stores data in key-value pairs. It is also named as a dictionary or associative array. It stores data in a way that enables lookup and insertion in constant O(1) time. These properties of a hash make it one of the most useful data structures in a programmer's toolbox. The main question is where does this speed come from and how does it work?

Contact us

Let's explore how our expertise can help you achieve your goals! Drop us a line, and we'll get back to you shortly.