Alpha-Beta法のサンプルプログラム(Ruby)
以下のような木を探索するプログラムを Ruby で記します。
#
# +--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"