Checkers

examples/checkers/main.cr

require "../../src/eagle"
require "./checkers"
include Eagle

# Checkers. Red (bottom) moves first. Captures are mandatory, multi-jumps supported.
# Menu: pick 1 player (vs AI) or 2 players. Keys: R restart, M menu, U undo, 1-8 AI depth.
class CheckersGame < App
  SIZE = 70
  ORIGIN = v2(50, 50)

  @board = Checkers::Board.new
  @ai = Checkers::AI.new(6)
  @selected : Int32? = nil
  @legal = [] of Checkers::Move
  @mode : Symbol = :menu
  @last : Checkers::Move? = nil
  @menu = CanvasLayer.new
  @status = ""
  @snd : Sound? = nil

  def load
    @snd = Sound.tone(330, 0.07, Sound::Wave::Triangle, 0.35)
    SceneTree.root.add(@menu)
    build_menu
    # `checkers ai` / `checkers two` skips the menu
    start(:ai) if ARGV.includes?("ai")
    start(:two) if ARGV.includes?("two")
  end

  def build_menu
    @menu.clear_children
    panel = Panel.new(size: v2(360, 0))
    panel.anchor = Anchor::Center
    panel.fit_content = true
    box = VBox.new(size: v2(340, 0))
    box.position = v2(10, 10)
    box.fit_content = true
    title = Label.new("Checkers", align: TextAlign::Center)
    title.font_scale = 1.5
    box.add(title)
    box.add(Button.new("1 player (vs AI)") { start(:ai) })
    box.add(Button.new("2 players") { start(:two) })
    depth_label = Label.new("AI depth #{@ai.depth}")
    depth = Slider.new(1, 8, @ai.depth, step: 1)
    depth.on_value_changed { |v| @ai.depth = v.to_i; depth_label.text = "AI depth #{v.to_i}" }
    box.add(depth_label, depth)
    panel.add(box)
    @menu.add(panel)
    @menu.visible = true
  end

  def start(mode : Symbol)
    @mode = mode
    @board = Checkers::Board.new
    @selected = nil; @legal.clear; @last = nil
    @menu.visible = false
    update_status
  end

  def square_at(p : Vec2) : Int32?
    l = p - ORIGIN
    return nil if l.x < 0 || l.y < 0 || l.x >= SIZE * 8 || l.y >= SIZE * 8
    (7 - (l.y / SIZE).to_i) * 8 + (l.x / SIZE).to_i
  end

  def square_pos(i : Int32) : Vec2
    ORIGIN + v2((i % 8) * SIZE, (7 - i // 8) * SIZE)
  end

  def human_turn? : Bool
    @mode == :two || @board.turn.red?
  end

  def input(e : Event)
    return if @mode == :menu
    if e.is_a?(MouseButtonEvent) && e.pressed? && e.button.left? && human_turn? && !@board.game_over?
      sq = square_at(e.position)
      return unless sq
      if @selected && (mv = @legal.find { |m| m.to == sq })
        @board.play(mv)
        @last = mv
        @snd.try(&.play)
        @selected = nil; @legal.clear
        update_status
      elsif (c = @board[sq]) && c.side == @board.turn
        @selected = sq
        @legal = @board.legal_moves_from(sq)
      else
        @selected = nil; @legal.clear
      end
    elsif e.is_a?(KeyEvent) && e.pressed?
      case e.key
      when Key::R then start(@mode)
      when Key::M then @mode = :menu; build_menu
      when Key::U then undo
      end
    end
  end

  def undo
    n = (@mode == :ai && @board.history.size >= 2) ? 2 : 1
    return if @board.history.size < n
    hist = @board.history[0...-n]
    @board = Checkers::Board.new
    hist.each { |m| @board.apply(m) }
    @last = hist.last?
    @selected = nil; @legal.clear
    update_status
  end

  def update(dt : Float32)
    if @mode == :ai && @board.turn.black? && !@board.game_over?
      if mv = @ai.best_move(@board)
        @board.apply(mv)
        @last = mv
        @snd.try(&.play(pitch: 0.8))
        update_status
      end
    end
    Eagle.quit if Input.pressed?(Key::Escape)
  end

  def update_status
    @status = case @board.status
              when .red_wins? then "Red wins!"
              when .black_wins? then "Black wins!"
              when .draw? then "Draw"
              else "#{@board.turn.red? ? "Red" : "Black"} to move#{@board.legal_moves.first?.try(&.capture?) ? ", must capture" : ""}"
              end
  end

  def draw(g : Graphics)
    return if @mode == :menu
    64.times do |i|
      p = square_pos(i)
      c = Checkers.dark?(i) ? Color.hex("#6b4f3a") : Color.hex("#e8d8c0")
      c = c.lerp(Color::YELLOW, 0.35) if (l = @last) && (l.path.includes?(i))
      c = c.lerp(Color::GREEN, 0.4) if @selected == i
      g.rect(p.x, p.y, SIZE, SIZE, color: c)
    end
    @legal.each { |m| p = square_pos(m.to) + v2(SIZE / 2, SIZE / 2); g.circle(p, 10, color: Color.new(0, 0, 0, 0.3)) }
    64.times do |i|
      c = @board[i]
      next unless c
      p = square_pos(i) + v2(SIZE / 2, SIZE / 2)
      base = c.side.red? ? Color.hex("#c0392b") : Color.hex("#2c2c2c")
      g.circle(p + v2(2, 3), SIZE * 0.38, color: Color.new(0, 0, 0, 0.35))
      g.circle(p, SIZE * 0.38, color: base)
      g.circle(p, SIZE * 0.3, DrawMode::Line, color: base.lighten(0.3))
      g.print("K", p.x, p.y - 8, Color::YELLOW, align: TextAlign::Center) if c.king?
    end
    g.print(@status, ORIGIN.x, ORIGIN.y + SIZE * 8 + 14, Color::WHITE)
    g.print("red #{@board.count(Checkers::Side::Red)}  black #{@board.count(Checkers::Side::Black)}   #{@mode == :ai ? "vs AI depth #{@ai.depth}, nodes #{@ai.nodes}" : "two players"}   U undo  R restart  M menu", ORIGIN.x, ORIGIN.y + SIZE * 8 + 38, Color::GRAY)
  end
end

Eagle.run(CheckersGame, title: "Eagle Checkers", width: 900, height: 700)

examples/checkers/checkers.cr

# Checkers (English draughts) rules + AI, independent of rendering.
# 8x8 board, dark squares only, forced captures, multi-jumps, kings.
module Checkers
  enum Side : Int8
    Red = 0   # moves up (increasing row)
    Black = 1 # moves down
    def other : Side; red? ? Black : Red; end
  end

  struct Cell
    getter side : Side
    getter? king : Bool
    def initialize(@side, @king = false); end
    def crowned : Cell; Cell.new(@side, true); end
  end

  struct Move
    getter path : Array(Int32)       # squares visited (from ... to)
    getter captures : Array(Int32)   # captured squares
    def initialize(@path, @captures = [] of Int32); end
    def from : Int32; @path.first; end
    def to : Int32; @path.last; end
    def capture? : Bool; !@captures.empty?; end
    def to_s : String; @path.map { |i| Checkers.name(i) }.join(capture? ? "x" : "-"); end
    def ==(o : Move) : Bool; @path == o.path; end
  end

  def self.name(i : Int32) : String; "#{('a'.ord + i % 8).chr}#{i // 8 + 1}"; end
  def self.index(name : String) : Int32; (name[0].ord - 'a'.ord) + (name[1].to_i - 1) * 8; end
  def self.dark?(i : Int32) : Bool; (i % 8 + i // 8).even?; end

  enum Status
    Playing
    RedWins
    BlackWins
    Draw
  end

  class Board
    getter cells : Array(Cell?)
    getter turn : Side
    getter history = [] of Move
    getter quiet_moves = 0 # moves without capture/crowning (draw at 40 each side)

    def initialize
      @cells = Array(Cell?).new(64, nil)
      @turn = Side::Red
      setup
    end

    protected def initialize(@cells, @turn, @history, @quiet_moves); end

    def clone : Board; Board.new(@cells.dup, @turn, @history.dup, @quiet_moves); end

    def setup : Nil
      @cells.fill(nil)
      64.times do |i|
        next unless Checkers.dark?(i)
        r = i // 8
        @cells[i] = Cell.new(Side::Red) if r < 3
        @cells[i] = Cell.new(Side::Black) if r > 4
      end
    end

    # Layout from 8 text rows, top row first: r/R red (R = king), b/B black, . empty
    def self.from_layout(rows : Array(String), turn : Side = Side::Red) : Board
      b = new
      b.cells.fill(nil)
      rows.each_with_index do |row, ri|
        r = 7 - ri
        row.each_char.with_index do |c, f|
          i = r * 8 + f
          case c
          when 'r' then b.cells[i] = Cell.new(Side::Red)
          when 'R' then b.cells[i] = Cell.new(Side::Red, true)
          when 'b' then b.cells[i] = Cell.new(Side::Black)
          when 'B' then b.cells[i] = Cell.new(Side::Black, true)
          end
        end
      end
      b.set_turn(turn)
      b
    end

    # :nodoc:
    def set_turn(@turn); end

    def [](i : Int32) : Cell?; @cells[i]; end
    def count(side : Side) : Int32; @cells.count { |c| c && c.side == side }; end

    private def dirs(c : Cell) : Array({Int32, Int32})
      return [{1, 1}, {-1, 1}, {1, -1}, {-1, -1}] if c.king?
      c.side.red? ? [{1, 1}, {-1, 1}] : [{1, -1}, {-1, -1}]
    end

    # All legal moves (captures are mandatory).
    def legal_moves : Array(Move)
      captures = [] of Move
      simple = [] of Move
      64.times do |i|
        c = @cells[i]
        next unless c && c.side == @turn
        jumps(i, c, [i], [] of Int32, captures)
        next unless captures.empty?
        dirs(c).each do |(df, dr)|
          f = i % 8 + df; r = i // 8 + dr
          next unless (0 <= f <= 7) && (0 <= r <= 7)
          t = r * 8 + f
          simple << Move.new([i, t]) if @cells[t].nil?
        end
      end
      captures.empty? ? simple : captures
    end

    private def jumps(i, c, path, caps, out_moves)
      found = false
      dirs(c).each do |(df, dr)|
        f = i % 8 + df; r = i // 8 + dr
        f2 = f + df; r2 = r + dr
        next unless (0 <= f2 <= 7) && (0 <= r2 <= 7)
        mid = r * 8 + f; t = r2 * 8 + f2
        m = @cells[mid]
        next unless m && m.side != c.side && !caps.includes?(mid)
        next unless @cells[t].nil? || t == path.first
        found = true
        # stop multi-jump when a man reaches the king row
        last_row = c.side.red? ? 7 : 0
        if !c.king? && r2 == last_row
          out_moves << Move.new(path + [t], caps + [mid])
        else
          jumps(t, c, path + [t], caps + [mid], out_moves)
        end
      end
      out_moves << Move.new(path, caps) if !found && caps.size > 0
    end

    def legal_moves_from(i : Int32) : Array(Move)
      legal_moves.select { |m| m.from == i }
    end

    def apply(m : Move) : Nil
      c = @cells[m.from].not_nil!
      @cells[m.from] = nil
      m.captures.each { |x| @cells[x] = nil }
      last_row = c.side.red? ? 7 : 0
      crowned = !c.king? && m.to // 8 == last_row
      @cells[m.to] = crowned ? c.crowned : c
      @quiet_moves = (m.capture? || crowned) ? 0 : @quiet_moves + 1
      @history << m
      @turn = @turn.other
    end

    def play(m : Move) : Bool
      real = legal_moves.find { |lm| lm == m }
      return false unless real
      apply(real)
      true
    end

    def play(path : String) : Bool
      squares = path.split(/[-x]/).map { |n| Checkers.index(n) }
      play(Move.new(squares))
    end

    def status : Status
      return Status::Draw if @quiet_moves >= 80
      if legal_moves.empty?
        return @turn.red? ? Status::BlackWins : Status::RedWins
      end
      Status::Playing
    end

    def game_over? : Bool; !status.playing?; end

    def to_s(io : IO) : Nil
      7.downto(0) do |r|
        8.times do |f|
          c = @cells[r * 8 + f]
          io << (c ? (c.side.red? ? (c.king? ? 'R' : 'r') : (c.king? ? 'B' : 'b')) : (Checkers.dark?(r * 8 + f) ? '.' : ' ')) << ' '
        end
        io << '\n'
      end
    end
  end

  class AI
    property depth : Int32
    getter nodes = 0

    def initialize(@depth = 6); end

    def evaluate(b : Board) : Int32
      score = 0
      64.times do |i|
        c = b[i]
        next unless c
        v = c.king? ? 300 : 100
        # advancement bonus for men
        r = i // 8
        v += (c.side.red? ? r : 7 - r) * 3 unless c.king?
        # edge safety
        v += 4 if i % 8 == 0 || i % 8 == 7
        score += c.side.red? ? v : -v
      end
      b.turn.red? ? score : -score
    end

    def best_move(b : Board) : Move?
      @nodes = 0
      moves = b.legal_moves
      return nil if moves.empty?
      return moves[0] if moves.size == 1
      best = moves[0]; best_score = Int32::MIN
      alpha = -1_000_000; beta = 1_000_000
      moves.each do |m|
        c = b.clone; c.apply(m)
        s = -search(c, @depth - 1, -beta, -alpha)
        if s > best_score
          best_score = s; best = m
        end
        alpha = Math.max(alpha, s)
      end
      best
    end

    private def search(b : Board, depth : Int32, alpha : Int32, beta : Int32) : Int32
      @nodes += 1
      moves = b.legal_moves
      return -100_000 - depth if moves.empty?
      # extend search while captures are available (quiescence)
      return evaluate(b) if depth <= 0 && !moves[0].capture?
      return evaluate(b) if depth <= -4
      moves.each do |m|
        c = b.clone; c.apply(m)
        s = -search(c, depth - 1, -beta, -alpha)
        return beta if s >= beta
        alpha = Math.max(alpha, s)
      end
      alpha
    end
  end
end