ぷよクエの最適解探索を行うプログラム。ぷよクエのスクショから譜面を自動読み込みする機能も付けた。並列処理対応。まだ分岐を含む斜めの消し方(一度通ったぷよを再び通るなぞり方)には対応していない。

puyo_solver.rb

require 'highline'
require 'rmagick'
require 'parallel'
require 'pp'

class ImageAnalize
  attr_reader :img

  COLOR_MAP = [
    nil,
    0,
    219,
    112,
    36,
    275,
    333
  ]

  ERROR = 6

  SYMBOL_COLOR_MAP = [
    [0.0, 0.0, 60.0, 1.0],
    [356.0, 246.0, 162.0, 1.0],
    [213.0, 255.0, 162.0, 1.0],
    [116.0, 146.0, 149.0, 1.0],
    [53.0, 221.0, 147.0, 1.0],
    [270.0, 255.0, 182.0, 1.0],
    [298.0, 255.0, 187.0, 1.0]
  ]

  def initialize(img_magick)
    @img = []
    img_magick.each_pixel do |p, x, y|
      @img[y] ||= []
      @img[y][x] = p
    end
  end

  def size
    return @img[0].size, @img.size
  end

  def to_board
    img_size = size()
    margins = []
    test_max = 100
    [0, 1].each { |rl|
      margins[rl] = []
      test_max.times { |i|
        before_luminousity = nil
        check_y = (img_size[1] * Rational(i + 1, test_max + 1)).round
        (img_size[0] / 10).times { |j|
          if rl == 0
            check_x = j
          elsif rl == 1
            check_x = img_size[0] - j
          end
          current_luminousity = @img[check_y][j].to_hsla[2]
          if before_luminousity && (before_luminousity - current_luminousity).abs >= 50
            # p [j, before_luminousity, current_luminousity, (before_luminousity - current_luminousity).abs]
            margins[rl] << j
            break
          end
          before_luminousity = current_luminousity
        }
      }
    }
    margin = []
    [0, 1].each { |rl|
      margin_freq = {}
      margins[rl].each { |v|
        margin_freq[v] ||= 0
        margin_freq[v] += 1
      }
      # p margin_freq
      max = margin_freq.to_a.sort_by { |v| v[1] }.reverse[0]
      if max[1] >= 30
        margin[rl] = max[0]
      else
        margin[rl] = 0
      end
    }
    board_size = [(img_size[0] - margin.inject(:+)), (img_size[0] - margin.inject(:+)) * Rational(719, 1024)]
    board_base = [margin[0], img_size[1] - board_size[1]]
    include_np_board_size = [(img_size[0] - margin.inject(:+)), (img_size[0] - margin.inject(:+)) * Rational(784, 1024)]
    include_np_board_base = [margin[0], img_size[1] - include_np_board_size[1]]
    cell_size = [board_size[0] * Rational(1, 8), board_size[1] * Rational(1, 6)]
    cell_size_np = [board_size[0] * Rational(1, 8), include_np_board_size[1] - board_size[1]]
    p ['img_size', img_size.map(&:to_f)]
    p ['margin', margin.map(&:to_f)]
    p ['board_size', board_size.map(&:to_f)]
    p ['board_base', board_base.map(&:to_f)]
    p ['include_np_board_size', include_np_board_size.map(&:to_f)]
    p ['include_np_board_base', include_np_board_base.map(&:to_f)]
    p ['cell_size', cell_size.map(&:to_f)]
    check_relative = []
    30.times { |x|
      30.times { |y|
        check_x = cell_size[0] * Rational(1, 4) + (cell_size[0] * Rational(1, 2)) * Rational((x + 1), 30)
        check_y = cell_size[1] * Rational(1, 4) + (cell_size[1] * Rational(1, 2)) * Rational((y + 1), 30)
        check_relative << [check_x, check_y]
      }
    }
    check_relative_np = []
    30.times { |x|
      30.times { |y|
        check_x = cell_size_np[0] * Rational(2, 5) + (cell_size_np[0] * Rational(1, 5)) * Rational((x + 1), 30)
        check_y = cell_size_np[1] * Rational(3, 7) + (cell_size_np[1] * Rational(1, 2)) * Rational((y + 1), 30)
        check_relative_np << [check_x, check_y]
      }
    }
    board = []
    8.times { |x|
      7.times { |y|
        rgb = []
        if y == 0
          check_relative_np.each_with_index { |r_coord, i__|
            check_x = (include_np_board_base[0] + x * cell_size[0] + r_coord[0]).round
            check_y = (include_np_board_base[1] + r_coord[1]).round
            rgb << [@img[check_y][check_x].red, @img[check_y][check_x].green, @img[check_y][check_x].blue]
          }
        else
          check_relative.each_with_index { |r_coord, i__|
            check_x = (board_base[0] + x * cell_size[0] + r_coord[0]).round
            check_y = (board_base[1] + (y - 1) * cell_size[1] + r_coord[1]).round
            rgb << [@img[check_y][check_x].red, @img[check_y][check_x].green, @img[check_y][check_x].blue]
          }
        end
        rgb_ave = rgb.transpose.map { |v|
          v.inject(:+) / rgb.size
        }
        hsla = Magick::Pixel.new(*rgb_ave).to_hsla
        # p [x, y]
        # p hsla
        index = nil
        COLOR_MAP.each_with_index { |hue, i|
          next if hue.nil?
          ok = false
          if hsla[2] > 100
            if hue - ERROR < 0
              ok = hsla[0] > (360 + hue - ERROR) || hsla[0] < hue + ERROR
            else
              ok = hsla[0] > hue - ERROR && hsla[0] < hue + ERROR
            end
          end
          if ok
            index = i
            break
          end
        }
        board[y] ||= []
        board[y][x] = index || 0
        # p rgb_ave
      }
    }
    return board
  end

  def self.to_magick(img_da)
    new_img = Magick::Image.new(img_da[0].length, img_da.length)
    img_da.each_with_index do |y_p, y|
      y_p.each_with_index do |pi, x|
        pixel = Magick::Pixel.from_hsla(*pi)
        # pixel = Magick::Pixel.new(*pi)
        new_img.pixel_color(x, y, pixel)
      end
    end
    return new_img
  end

  def self.board_to_img(path, board)
    new_img = []
    board.each_with_index { |row, y|
      row.each_with_index { |cell, x|
        40.times { |rx|
          (y == 0 ? 20 : 40).times { |ry|
            color = (ry == 0 || rx == 0) ? [0.0, 255.0, 255.0, 1.0] : SYMBOL_COLOR_MAP[cell]
            new_img[(y >= 1 ? -20 : 0) + y * 40 + ry] ||= []
            new_img[(y >= 1 ? -20 : 0) + y * 40 + ry][x * 40 + rx] = color
          }
        }
      }
    }
    self.to_magick(new_img).write(path)
  end

  def self.hr_board_to_img(path, board_arr)
    new_img = []
    board_arr.each_with_index { |board, i|
      board.each_with_index { |row, y|
        row.each_with_index { |cell, x|
          40.times { |rx|
            (y == 0 ? 20 : 40).times { |ry|
              color = (ry == 0 || rx == 0) ? [0.0, 255.0, 255.0, 1.0] : SYMBOL_COLOR_MAP[cell]
              new_img[(y >= 1 ? -20 : 0) + y * 40 + ry] ||= []
              new_img[(y >= 1 ? -20 : 0) + y * 40 + ry][i * 40 * 8 + i * 60 + x * 40 + rx] = color
            }
          }
        }
      }
      if board_arr.size - 1 != i
        60.times { |rx|
          (20 + 40 * 6).times { |ry|
            new_img[ry] ||= []
            new_img[ry][(i + 1) * 40 * 8 + i * 60 + rx] = [0.0, 255.0, 255.0, 1.0]
          }
        }
      end
    }
    self.to_magick(new_img).write(path)
  end
end

class Board
  attr_reader :board

  PROXIMITY_VANISH = [6]

  COLOR_NAME_MAP = [
    :blank,
    :red,
    :blue,
    :green,
    :yellow,
    :purple,
    :pink
  ]

  # blank  : 0
  # red    : 1
  # blue   : 2
  # green  : 3
  # yellow : 4
  # purple : 5
  # pink   : 6

  def initialize(board)
    @board = Array.new(board.size) { |i| Array.new(board[i].size) { |j| board[i][j] } }
    @h = HighLine.new
  end

  def filled?(color_index = nil)
    @board.all? { |row|
      row.all? { |cell|
        if color_index.nil?
          cell != 0
        else
          cell == color_index
        end
      }
    }
  end

  def count(color_index)
    count = 0
    @board.each { |row|
      row.each { |cell|
        if cell == color_index
          count += 1
        end
      }
    }
    return count
  end

  def print
    board_colored = []
    @board.each_with_index { |row, y|
      row_colored = []
      row.each_with_index { |cell, x|
        row_colored << get_color(cell)
      }
      board_colored << row_colored
    }
    puts board_colored.map { |v| v.join(' ') }.join("\n")
    puts
  end

  def delete(x, y)
    @board[y][x] = 0
  end

  def exec(output = false)
    all_vanished = []
    vanished = {}
    np_drop = false
    loop {
      drop_check(output, np_drop)
      vanished = vanish_check(output)
      if vanished.empty?
        if np_drop
          break
        else
          np_drop = true
        end
      else
        all_vanished << vanished
      end
    }
    return all_vanished
  end

  private
  def drop_check(output = false, np_drop = false)
    result_board = []
    @board.transpose.each_with_index { |col, x|
      result_col = []
      move = 0
      r_col = (np_drop ? col : col[1..-1]).reverse
      # p r_col
      r_col.size.times { |y|
        result_cell = r_col[y + move]
        if y + move >= r_col.size
          result_cell = 0
        elsif r_col[y + move] == 0
          move += 1
          redo
        end
        result_col << result_cell
      }
      result_col << col[0] unless np_drop
      result_board << result_col.reverse
    }
    result_board = result_board.transpose
    @board = result_board
    print() if output
  end

  def vanish_check(output = false)
    checked_board = Array.new(@board.size) { Array.new(@board[0].size) { 0 } }
    all_vanished = {}
    @board.each_with_index { |row, y|
      # p row
      next if y == 0
      row.each_with_index { |cell, x|
        if checked_board[y][x] == 1
          next
        end
        vanish = false
        normal_vanish_coords, proximity_vanish_coords = check_around(x, y)
        if normal_vanish_coords.size >= 4
          vanish = true
          all_vanished[@board[normal_vanish_coords[0][1]][normal_vanish_coords[0][0]]] ||= []
          all_vanished[@board[normal_vanish_coords[0][1]][normal_vanish_coords[0][0]]] << normal_vanish_coords.size
          if proximity_vanish_coords.size != 0
            all_vanished[@board[proximity_vanish_coords[0][1]][proximity_vanish_coords[0][0]]] ||= []
            all_vanished[@board[proximity_vanish_coords[0][1]][proximity_vanish_coords[0][0]]] << normal_vanish_coords.size
          end
        end
        # p ['normal_vanish_coords', normal_vanish_coords]
        normal_vanish_coords.each { |coord|
          # p ['coord', coord]
          checked_board[coord[1]][coord[0]] = 1
          if vanish
            delete(*coord)
          end
        }
        proximity_vanish_coords.each { |coord|
          if vanish
            delete(*coord)
          end
        }
      }
    }
    print() if output
    return all_vanished
  end

  def check_around(x, y, normal_vanish_coords = [], proximity_vanish_coords = [])
    # puts "traced"
    # p normal_vanish_coords
    current_cell = @board[y][x]
    if current_cell == 0
      return normal_vanish_coords, proximity_vanish_coords
    end
    if PROXIMITY_VANISH.include?(current_cell)
      proximity_vanish_coords << [x, y]
    else
      normal_vanish_coords << [x, y]
      # p normal_vanish_coords
    end
    around = []
    around << (y - 1 <= 7 - 1 && y - 1 >= 1 ? [x, y - 1] : nil)
    around << (y + 1 <= 7 - 1 && y + 1 >= 1 ? [x, y + 1] : nil)
    around << (x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y] : nil)
    around << (x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y] : nil)
    around.each { |coord|
      if coord.nil? || normal_vanish_coords.include?(coord) || proximity_vanish_coords.include?(coord)
        next
      end
      if @board[coord[1]][coord[0]] == current_cell
        # puts "recursive"
        normal_vanish_coords, proximity_vanish_coords = check_around(*coord, normal_vanish_coords, proximity_vanish_coords)
        # p ['current', x, y]
        # p normal_vanish_coords
      elsif PROXIMITY_VANISH.include?(@board[coord[1]][coord[0]])
        normal_vanish_coords, proximity_vanish_coords = check_around(*coord, normal_vanish_coords, proximity_vanish_coords)
      end
    }
    # puts 'return'
    # p normal_vanish_coords
    return normal_vanish_coords, proximity_vanish_coords
  end

  def get_color(num)
    color = [:black, :red, :blue, :green, :yellow, :cyan, :white]
    return @h.color(num.to_s, color[num])
  end
end

class PuyoSolver
  def initialize(board)
    @board = board.board
    @want_vanish_color = nil
  end

  def solve(want_vanish_color = nil, delete_count = 5, inverse = false)
    start_time = Time.now
    @want_vanish_color = want_vanish_color ? [:blank, :red, :blue, :green, :yellow, :purple, :pink].index(want_vanish_color) : nil
    scores = []
    coords = []
    @board.size.times { |y| # 6
      next if y == 0
      @board[y].size.times { |x| # 8
        coords << [x, y]
      }
    }
    Parallel.map(coords) { |coords_|
      ret = []
      delete_start(*coords_, [], delete_count) { |delete_arr|
        verbose = false
        # if delete_arr == [[3, 6], [4, 6]]
        #   verbose = true
        # end
        score, all_vanished = evaluate(delete_arr, verbose)
        ret << {
          :score => score,
          :all_vanished => all_vanished,
          :delete_arr => delete_arr
        }
        # p ret if verbose
        # p ret if ret[:score] != 0
      }
      ret
    }.each { |ret|
      scores += ret
    }
    # pp scores
    # p scores.size()
    if inverse
      sorted_score = scores.sort_by { |v| (v[:score][:opt].to_r / (v[:score][:attack] * 100 + 1)).to_f }.reverse
    else
      sorted_score = scores.sort_by { |v| (v[:score][:attack] * 1000 + v[:score][:opt]).to_f }.reverse
    end
    # Board.new(@board, @chance).print
    # sorted_score[0..2].each_with_index { |v, i|
    #   puts i
    #   p v[:delete_arr]
    #   p v[:all_vanished]
    #   puts "score: #{v[:score]} sum: #{v[:all_vanished].values.inject(:+)}"
    #   test_board = Board.new(@board, @chance)
    #   v[:delete_arr].each { |coord|
    #     test_board.delete(*coord)
    #   }
    #   test_board.print
    #   test_board.exec()
    #   puts
    # }
    finish_time = Time.now
    puts "elapsed time: #{finish_time - start_time}s"
    return sorted_score[0]
  end

  private
  def delete_start(x, y, circled = [], delete_count = 5, delete_arr = [], started_coord = nil)
    return circled if @board[y][x] == 0
    delete_arr = Array.new(delete_arr.size) { |i| Array.new(delete_arr[i]) { |j| delete_arr[i][j] }  }
    delete_arr << [x, y]
    verbose = false
    # if delete_arr == [[6, 2], [5, 3], [4, 4], [3, 5], [2, 6]]
    #   verbose = true
    #   p ['delete_arr', delete_arr]
    # end
    p ['current', x, y] if verbose
    unless started_coord
      started_coord = [x, y]
    end
    p ['delete_count', delete_count] if verbose
    if delete_count == 1
      if x <= started_coord[0] - 1 && y <= started_coord[1] - 1
        return circled
      end
    end
    around = []
    around << (y - 1 <= 7 - 1 && y - 1 >= 1 ? [x, y - 1] : nil)
    around << (y + 1 <= 7 - 1 && y + 1 >= 1 ? [x, y + 1] : nil)
    around << (x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y] : nil)
    around << (x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y] : nil)
    around << (y - 1 <= 7 - 1 && y - 1 >= 1 && x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y - 1] : nil)
    around << (y + 1 <= 7 - 1 && y + 1 >= 1 && x - 1 <= 8 - 1 && x - 1 >= 0 ? [x - 1, y + 1] : nil)
    around << (y - 1 <= 7 - 1 && y - 1 >= 1 && x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y - 1] : nil)
    around << (y + 1 <= 7 - 1 && y + 1 >= 1 && x + 1 <= 8 - 1 && x + 1 >= 0 ? [x + 1, y + 1] : nil)
    before_circled = false
    passed_circle = nil
    available_around = []
    around.each { |coord|
      p coord if verbose
      if coord.nil?
        next
      end
      if @board[coord[1]][coord[0]] == 0
        next
      end
      if delete_arr.include?(coord)
        if delete_arr[-2] != coord
          before_circled = true
          if passed_circle.nil?
            p ['circled size', circled.size] if verbose
            circled.each { |arr|
              next if arr.size != delete_arr.size
              next if arr.last != delete_arr.last
              if arr.all? { |v| delete_arr.include?(v) }
                p ['existed', arr] if verbose
                passed_circle = true
                break
              end
            }
          end
          if passed_circle
            break
          end
        end
        next
      end
      available_around << coord
    }
    p [before_circled, passed_circle] if verbose
    if passed_circle
      return circled
    end
    if before_circled
      circled << delete_arr
    end
    yield(delete_arr)
    p delete_count if verbose
    if delete_count >= 2
      p ['available_around', available_around] if verbose
      available_around.each { |coord|
        circled = delete_start(*coord, circled, delete_count - 1, delete_arr, started_coord) { |delete_arr_|
          yield(delete_arr_)
        }
      }
    end
    return circled
  end

  def evaluate(delete_arr, verbose = false)
    test_board = Board.new(@board)
    delete_arr.each { |coord|
      test_board.delete(*coord)
    }
    all_vanished = test_board.exec(verbose)
    attack_score = 0.to_r
    opt_score = 0
    all_vanished.each_with_index { |vanished , i|
      chain_bonus = i + 1 <= 4 ? [1.0, 1.4, 1.7, 2.0][i].to_r : 2.0.to_r + 0.2.to_r * (i - 3)
      sum_vanished_include_proximity = vanished.values.flatten.inject(:+)
      sum_vanished = vanished.to_a.map { |v| Board::PROXIMITY_VANISH.include?(v[0]) ? [] : v[1] }.flatten.inject(:+)
      if @want_vanish_color
        if vanished.keys.include?(@want_vanish_color)
          division = vanished[@want_vanish_color].size
          attack_score += (1.to_r + 0.15.to_r * (sum_vanished - 4).to_r) * division.to_r * chain_bonus
        end
      end
      opt_score += sum_vanished_include_proximity
    }
    if test_board.filled?(0)
      opt_score += 100
    end
    if @want_vanish_color
      opt_score += test_board.count(@want_vanish_color)
    end
    score = {
      :attack => attack_score,
      :opt => opt_score
    }
    return score, all_vanished
  end
end

# 8 * 6

# temp_board = [
# [1, 1, 1, 2, 2, 1, 1, 1],
# [1, 1, 2, 5, 4, 2, 1, 1],
# [5, 5, 5, 4, 5, 4, 4, 4],
# [4, 4, 4, 5, 4, 5, 5, 5],
# [5, 5, 5, 4, 5, 4, 4, 4],
# [4, 4, 4, 1, 4, 5, 5, 5],
# [1, 1, 1, 3, 3, 4, 4, 4]
# ]

# temp_board = [
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 1, 0, 1, 1, 0, 1, 0],
# [0, 1, 1, 2, 2, 1, 1, 0]
# ]

# temp_board = [
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 0, 3, 0, 3],
# [1, 1, 2, 2, 2, 2, 3, 3]
# ]

# temp_board = [
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [0, 0, 0, 0, 0, 0, 0, 0],
# [1, 0, 1, 0, 0, 1, 0, 1],
# [1, 1, 2, 2, 2, 2, 1, 1]
# ]

puts "puyo solver started"
img_src = Magick::ImageList.new('./img.jpg')
puts "image imported"
img_analize = ImageAnalize.new(img_src)
puts "image initialized"
imported_board = img_analize.to_board
puts "image analized"
test = Board.new(imported_board)
# test = Board.new(temp_board)
puts "board initialized"
test.print
p test.filled?
solver = PuyoSolver.new(test)
puts "solver initialized"
puts "vanish priority: #{ARGV[0]}"
puts "vanish priority index: #{ARGV[0] ? Board::COLOR_NAME_MAP.index(ARGV[0].to_sym) : nil}"
result = solver.solve(ARGV[0] ? ARGV[0].to_sym : nil, 5, false)
puts "solver finished"
p result[:delete_arr]
p result[:all_vanished]
sum_all_vanished = {}
result[:all_vanished].each { |v|
  v.each { |k, v_|
    sum_all_vanished[k] ||= 0
    sum_all_vanished[k] += v_.inject(:+)
  }
}
puts "attack score: #{result[:score][:attack].to_f} opt score: #{result[:score][:opt]} sum: #{sum_all_vanished.values.inject(:+)}"
before_board = Board.new(test.board)
result[:delete_arr].each { |coord|
  before_board.delete(*coord)
}
before_board.print()
after_board = Board.new(test.board)
result[:delete_arr].each { |coord|
  after_board.delete(*coord)
}
after_board.exec()
after_board.print()
ImageAnalize.hr_board_to_img('./out.png', [test.board, before_board.board, after_board.board])

# test.delete(0, 3)
# test.delete(0, 4)
# test.delete(1, 4)
# test.delete(2, 4)
# test.delete(1, 5)
# test.print
# test.exec(true)