Alpha-Beta法

# 
#                  +--h--1
#            +--d--+--i--5 (goal)
#            |     +--j--3
#      +--b--|
#      |     +--e--+--k--6
#      |           +--l--2
# --a--|
#      |     +--f--+--m--2
#      |     |     +--n--4
#      +--c--|
#            +--g--+--o--9
#                  +--p--8

class Node
  attr_accessor :value
  attr_accessor :name

  def initialize( name = '', value = 0)
    @name = name 
    @value = value
    @children = []
  end

  def is_leaf
    return @children == []
  end

  def add_child( c)
    @children.push( c)
  end

  def each_child
    @children.each{ |c|
      yield( c)
    }
  end
end


def Node.create_sample
  a = Node.new( 'a')
  a.add_child( b = Node.new( 'b'))
  a.add_child( c = Node.new( 'c'))
  b.add_child( d = Node.new( 'd'))
  b.add_child( e = Node.new( 'e'))
  c.add_child( f = Node.new( 'f'))
  c.add_child( g = Node.new( 'g'))
  d.add_child( h = Node.new( 'h', 1))
  d.add_child( i = Node.new( 'i', 5))
  d.add_child( j = Node.new( 'j', 3))
  e.add_child( k = Node.new( 'k', 6))
  e.add_child( l = Node.new( 'l', 2))
  f.add_child( m = Node.new( 'm', 2))
  f.add_child( n = Node.new( 'n', 4))
  g.add_child( o = Node.new( 'o', 9))
  g.add_child( p = Node.new( 'p', 8))
  return a
end


def alpha_beta( node, min_or_max, alpha, beta)
  print "alpha_beta( #{node.name}, #{min_or_max}, #{alpha}, #{beta})\n"
  hand = ''
  if node.is_leaf
    return [node.value, hand]
  end
  if min_or_max == 1
    node.each_child{ | cn |
      v,h = alpha_beta( cn, -1, alpha, beta)
      if v > alpha
        alpha = v
        hand = cn.name
      end
      if alpha >= beta
        return[ beta, hand]
      end
    }
    return [alpha, hand]
  else
    node.each_child{ | cn |
      v,h = alpha_beta( cn, 1, alpha, beta)
      if v < beta
        beta = v
        hand = cn.name
      end
      if alpha >= beta
        return[ alpha, hand]
      end
    }
    return[ beta, hand]
  end
end

INFINITY=99999

(v,hand) = alpha_beta( Node.create_sample, 1, -INFINITY, INFINITY)
print "result=#{hand}\n"