An implementation of minimax and alpha-beta punning written in Ruby, with visualization using Graphviz dot language.

abvis.rb

class Node
  attr_accessor :symbol, :score, :my_turn, :children, :visited

  def initialize(symbol, score, my_turn, children)
    @symbol = symbol
    @score = score
    @my_turn = my_turn
    @children = children
    @visited = false
  end

  def leaf?
    @children.nil?
  end

  def to_dot
    str = @symbol.to_s
    str += ' [label = "{' + @symbol.to_s + '|'
    if not @score.nil?
      str += score.to_s
    end
    str += '}"'
    if not @my_turn
      str += ', shape = Mrecord'
    end
    if not @visited
      str += ', style = filled, fillcolor = "#cccccc"'
    end
    str += '];'

    if not @children.nil?
      @children.each do |child|
        str += child.to_dot
        str += @symbol.to_s + ' -> ' + child.symbol.to_s + ';'
      end
    end

    str
  end
end

def build_tree
  Node.new(:A, nil, true, [
    Node.new(:B, nil, false, [
      Node.new(:E, nil, true, [
        Node.new(:N, 8, false, nil),
        Node.new(:O, 3, false, nil)]),
      Node.new(:F, nil, true, [
        Node.new(:P, 9, false, nil),
        Node.new(:Q, 6, false, nil)]),
      Node.new(:G, nil, true, [
        Node.new(:R, 4, false, nil)])]),
    Node.new(:C, nil, false, [
      Node.new(:H, nil, true, [
        Node.new(:S, 5, false, nil)]),
      Node.new(:I, nil, true, [
        Node.new(:T, 9, false, nil),
        Node.new(:U, 2, false, nil)]),
      Node.new(:J, nil, true, [
        Node.new(:V, 6, false, nil),
        Node.new(:W, 5, false, nil)])]),
    Node.new(:D, nil, false, [
      Node.new(:K, nil, true, [
        Node.new(:X, 3, false, nil)]),
      Node.new(:L, nil, true, [
        Node.new(:Y, 7, false, nil)]),
      Node.new(:M, nil, true, [
        Node.new(:Z, 16, false, nil)])])])
end

def convert_to_dot(node)
  puts 'digraph Game {'
  puts 'node [shape = record];'
  puts node.to_dot
  puts '}'
end

def minimax(node, depth)
  node.visited = true

  if node.leaf? or depth == 0
    return node.score
  elsif node.my_turn
    score = -Float::INFINITY
    node.children.each do |child|
      score = [score, minimax(child, depth - 1)].max
    end
    node.score = score
    return score
  else
    score = Float::INFINITY
    node.children.each do |child|
      score = [score, minimax(child, depth - 1)].min
    end
    node.score = score
    return score
  end
end

def alphabeta(node, depth, alpha, beta)
  node.visited = true

  if node.leaf? or depth == 0
    return node.score
  elsif node.my_turn
    node.children.each do |child|
      alpha = [alpha, alphabeta(child, depth - 1, alpha, beta)].max
      if alpha >= beta
        node.score = beta
        return beta
      end
    end
    node.score = alpha
    return alpha
  else
    node.children.each do |child|
      beta = [beta, alphabeta(child, depth - 1, alpha, beta)].min
      if alpha >= beta
        node.score = alpha
        return alpha
      end
    end
    node.score = beta
    return beta
  end
end

tree = build_tree()
#minimax(tree, Float::INFINITY)
#alphabeta(tree, Float::INFINITY, -Float::INFINITY, Float::INFINITY)
convert_to_dot(tree)