MinMax法

ゲームの木の探査の[[アルゴリズム]]
[[MinMax法]]の改良として [[Alpha-Beta法]]があります。


=== サンプルとして以下のよう木を探索するプログラムを 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
}}}

#begin rubyscript

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 minmax( node, min_or_max)
  print "minimax( #{node.name}, #{min_or_max}) \n"
  hand = ''
  if node.is_leaf
    return [node.value, node.name]
  else
    if min_or_max == 1
      max   = -9999
      node.each_child{ | cn |
        v,l = minmax( cn, -1)
        if v > max
          max = v
  	  hand = cn.name
        end
      }
      return [max, hand]
    else
      min   = 9999
      node.each_child{ | cn |
        v,l = minmax( cn, 1)
        if v < min
          min = v
  	  hand = cn.name
        end
      }
      return [min, hand]
    end
  end
end

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

#end