require 'othello'
require 'evaluate'

class Strategy
	class BootStrap < Strategy
		def select(othello)
			if othello.black_stones + othello.white_stones == 4 then
				init_upper = (othello.state.board_size / 2).ceil
				init_lower = init_upper - 1
				return [init_lower, init_lower - 1]
			elsif othello.black_stones + othello.white_stones == 5 then
				init_upper = (othello.state.board_size / 2).ceil
				init_lower = init_upper - 1
				if othello.state.is_black?(init_lower, init_lower - 1) then
					return [init_lower - 1, init_upper]
				elsif othello.state.is_black?(init_lower - 1, init_lower) then
					return [init_upper, init_lower - 1]
				elsif othello.state.is_black?(init_upper, init_upper + 1) then
					return [init_upper + 1, init_lower]
				else #othello.state.is_black?(init_upper + 1, init_upper) then
					return [init_lower, init_upper + 1]
				end
			end
			
			return nil
		end
		
		def lazy?; return true; end
	end

	class Boltzmann < Strategy
		def select(othello)
			othello.tree.children.keys[rand(othello.tree.children.size)]
		end
		
		def lazy?; return true; end
	end
	
	class Greedy < BootStrap
		@evaluator
		attr_reader :evaluator
		def initialize(evl = Evaluator::Bayes::new)
			@evaluator = evl
		end
		
		class SearchedResult
			@op
			@score
			attr_accessor :op
			attr_accessor :score
			def initialize(op = nil, score = nil)
				@op = op
				@score = score
			end
		end
		
		def brute_search(tree, target)
			if tree.is_leaf? then
				return SearchedResult::new(nil, @evaluator.evaluate(tree.root, target)) # 手と評価関数の組み合わせ
			else
				result = SearchedResult::new
				if target == tree.root.order then # 自分の手番なので最大化する手を探す
					tree.children.each{|child|
						searched = brute_search(child[1], target)
						if !result.score or (result.score < searched.score) then
							result.op = child[0]
							result.score = searched.score #max更新
						end
					}
				else # 相手の手番なので最小化する手を探す
					tree.children.each{|child|
						searched = brute_search(child[1], target)
						if !result.score or (result.score > searched.score) then
							result.op = child[0]
							result.score = searched.score #mix更新
						end
					}
				end
				return result
			end
		end
		
		def alpha_beta_search(tree, target, threshold = nil)
			if tree.is_leaf? then
				# [手, 評価関数]の組み合わせ
				return SearchedResult::new(nil, @evaluator.evaluate(tree.root, target))
			else
				result = SearchedResult::new
				if target == tree.root.order then
					# 自分の手番なので最大化する手を探す
					# betaよりも大きかったらやめる
					alpha = nil
					tree.children.each{|child|
						searched = alpha_beta_search(child[1], target, alpha)
						if threshold and threshold < searched.score then
							result.op = child[0]
							result.score = searched.score
							break
						elsif !result.score or (result.score < searched.score) then
							result.op = child[0]
							result.score = searched.score	#max更新
							alpha = searched.score
						end
					}
				else
					# 相手の手番なので最小化する手を探す
					# alphaよりも小さかったらやめる
					beta = nil
					tree.children.each{|child|
						searched = alpha_beta_search(child[1], target, beta)
						if threshold and threshold > searched.score then
							result.op = child[0]
							result.score = searched.score
							break
						elsif !result.score or (result.score > searched.score) then
							result.op = child[0]
							result.score = searched.score	#min更新
							beta = searched.score
						end
					}
				end
				return result
			end
		end
		
		def select(othello)
			boot = super(othello)
			if boot then
				puts "Replied by boot strap mode."
				return boot
			end
			
			#if othello.tree.children.size == 1 then
			#	puts "選択肢なし: #{othello.tree.children.keys[0].inspect}"
			#	return othello.tree.children.keys[0]
			#end
			
			#selected = brute_search(othello.tree, othello.state.order)
			selected = alpha_beta_search(othello.tree, othello.state.order)
			puts "最適手: #{selected.op.inspect}; 評価関数値: #{selected.score}"
			return selected.op
		end
		
		def lazy?; return false; end
	end
	
	class BiStrategy < Strategy
		def initialize(strategy1, strategy2, threshold = 0.5)
			@strategy1 = strategy1
			@strategy2 = strategy2
			@threshold = threshold
			@current_strategy = decide_strategy
		end
		
		def decide_strategy
			return rand < @threshold ? @strategy1 : @strategy2
		end
		
		def select(othello)
			op = @current_strategy.select(othello)
			@current_strategy = decide_strategy
			return op
		end
		
		def lazy?
			@current_strategy.lazy?
		end
	end
end

if $0 == __FILE__ then
	greedy = Strategy::Greedy::new
	othello = Othello::new(6)
	p othello.mount!(greedy.select(othello))
end