-- ai_level4.lua
-- ※ 現時点においては、ai_level3.lua と同内容です。
--
-- author IZUMI STUDIO
-- date 2010-01-19 Create New

MAX_VALUE = 10000
MIN_VALUE = -10000

BOARD_WIDTH  = 8
BOARD_HEIGHT = 8
CHIP_EMPTY = 0
CHIP_WHITE = 1
CHIP_BLACK = 2
CHIP_WALL  = 3
MAX_TURN   = 60

local evaluateFunc      -- 評価関数
local limitMax          -- 先読み手数
local myChip            --

LIMIT_START = 0

PHASE_1_START     = 0   -- フェーズ開始ターン
PHASE_1_LIMIT_MAX = 2   -- 先読み手数（0：次の手のみ読む）
PHASE_2_START     = 55
PHASE_2_LIMIT_MAX = 5

function flipChip( _chip )
	if( _chip == CHIP_BLACK ) then
		return CHIP_WHITE
	else
		return CHIP_BLACK
	end
end

function outLog( _limit, _log )
	local s = _log
	
	if( limitMax <= _limit ) then
	else
		local i
		for i=0, (limitMax-_limit) do
			s = string.format( "    %s", s )
		end
	end
	
	AI.PrintLog(s)
end


function evaluate_1()
	local i
	
	local lastTurn = AI.GetTurnCount()-1
	local lastChip = AI.GetHistoryChip( lastTurn )
	local putX
	local putY
	putX, putY = AI.GetHistoryPos( lastTurn, 0 )
	
	-- 確定石
	local fixedB = AI.CheckFixed( CHIP_BLACK )
	local fixedW = AI.CheckFixed( CHIP_WHITE )
	
--	-- 配置可能数
--	local pc = AI.GetPutablesCount()
	
	-- 開放度
	local openLevelB = AI.EvaluateByOpenLevel( CHIP_BLACK )
	local openLevelW = AI.EvaluateByOpenLevel( CHIP_WHITE )
	
	-- 隅
	local cornerB = 0
	local cornerW = 0
	if( AI.GetChip(1,1) == CHIP_BLACK ) then
		cornerB = cornerB+1
	end
	if( AI.GetChip(8,1) == CHIP_BLACK ) then
		cornerB = cornerB+1
	end
	if( AI.GetChip(1,8) == CHIP_BLACK ) then
		cornerB = cornerB+1
	end
	if( AI.GetChip(8,8) == CHIP_BLACK ) then
		cornerB = cornerB+1
	end
	if( AI.GetChip(1,1) == CHIP_WHITE ) then
		cornerW = cornerW+1
	end
	if( AI.GetChip(8,1) == CHIP_WHITE ) then
		cornerW = cornerW+1
	end
	if( AI.GetChip(1,8) == CHIP_WHITE ) then
		cornerW = cornerW+1
	end
	if( AI.GetChip(8,8) == CHIP_WHITE ) then
		cornerW = cornerW+1
	end
	
	-- C打ち
	local putCPlaceB = 0
	if( (AI.GetChip(2,1) == CHIP_BLACK) and (AI.GetChip(1,1) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	if( (AI.GetChip(1,2) == CHIP_BLACK) and (AI.GetChip(1,1) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	if( (AI.GetChip(7,1) == CHIP_BLACK) and (AI.GetChip(8,1) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	if( (AI.GetChip(8,2) == CHIP_BLACK) and (AI.GetChip(8,1) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	if( (AI.GetChip(1,7) == CHIP_BLACK) and (AI.GetChip(1,8) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	if( (AI.GetChip(2,8) == CHIP_BLACK) and (AI.GetChip(1,8) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	if( (AI.GetChip(8,7) == CHIP_BLACK) and (AI.GetChip(8,8) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	if( (AI.GetChip(7,8) == CHIP_BLACK) and (AI.GetChip(8,8) == CHIP_EMPTY) ) then
		putCPlaceB = putCPlaceB + 1
	end
	
	local putCPlaceW = 0
	if( (AI.GetChip(2,1) == CHIP_WHITE) and (AI.GetChip(1,1) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	if( (AI.GetChip(1,2) == CHIP_WHITE) and (AI.GetChip(1,1) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	if( (AI.GetChip(7,1) == CHIP_WHITE) and (AI.GetChip(8,1) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	if( (AI.GetChip(8,2) == CHIP_WHITE) and (AI.GetChip(8,1) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	if( (AI.GetChip(1,7) == CHIP_WHITE) and (AI.GetChip(1,8) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	if( (AI.GetChip(2,8) == CHIP_WHITE) and (AI.GetChip(1,8) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	if( (AI.GetChip(8,7) == CHIP_WHITE) and (AI.GetChip(8,8) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	if( (AI.GetChip(7,8) == CHIP_WHITE) and (AI.GetChip(8,8) == CHIP_EMPTY) ) then
		putCPlaceW = putCPlaceW + 1
	end
	
	-- X打ち
	local putXPlaceB = 0
	if( (AI.GetChip(2,2) == CHIP_BLACK) and (AI.GetChip(1,1) == CHIP_EMPTY) ) then
		putXPlaceB = putXPlaceB + 1
	end
	if( (AI.GetChip(7,2) == CHIP_BLACK) and (AI.GetChip(8,1) == CHIP_EMPTY) ) then
		putXPlaceB = putXPlaceB + 1
	end
	if( (AI.GetChip(2,7) == CHIP_BLACK) and (AI.GetChip(1,8) == CHIP_EMPTY) ) then
		putXPlaceB = putXPlaceB + 1
	end
	if( (AI.GetChip(7,7) == CHIP_BLACK) and (AI.GetChip(8,8) == CHIP_EMPTY) ) then
		putXPlaceB = putXPlaceB + 1
	end
	
	local putXPlaceW = 0
	if( (AI.GetChip(2,2) == CHIP_WHITE) and (AI.GetChip(1,1) == CHIP_EMPTY) ) then
		putXPlaceW = putXPlaceW + 1
	end
	if( (AI.GetChip(7,2) == CHIP_WHITE) and (AI.GetChip(8,1) == CHIP_EMPTY) ) then
		putXPlaceW = putXPlaceW + 1
	end
	if( (AI.GetChip(2,7) == CHIP_WHITE) and (AI.GetChip(1,8) == CHIP_EMPTY) ) then
		putXPlaceW = putXPlaceW + 1
	end
	if( (AI.GetChip(7,7) == CHIP_WHITE) and (AI.GetChip(8,8) == CHIP_EMPTY) ) then
		putXPlaceW = putXPlaceW + 1
	end
	
	-- 最終的な評価値
	e = ( fixedB - fixedW ) *10
		+ ( openLevelW - openLevelB ) *5
		+ ( cornerB - cornerW ) * 300 
		+ ( putCPlaceW - putCPlaceB ) * 120
		+ ( putXPlaceW - putXPlaceB ) * 100
	if( myChip == CHIP_WHITE ) then
		e = -e
	end
	
	return e
end


function evaluate_2()
	
	local lastTurn = AI.GetTurnCount()-1
	local lastChip = AI.GetHistoryChip( lastTurn )
	
	-- 各チップの数を求める
	local x
	local y
	local chip
	local blackCount = 0
	local whiteCount = 0
	for y=1,BOARD_HEIGHT do
		for x=1,BOARD_WIDTH do
			chip = AI.GetChip(x,y)
			if( chip == CHIP_BLACK ) then
				blackCount = blackCount + 1
			elseif( chip == CHIP_WHITE ) then
				whiteCount = whiteCount + 1
			end
		end
	end
	
	-- それぞれのチップ数の差を求める
	local dif = blackCount - whiteCount
	if( lastChip == CHIP_WHITE ) then
		dif = -dif
	end
	
	local e = dif
	return e
end

function minLevel( _limit, _alpha, _beta )
	local limit = _limit
	local s
	
	outLog( limit, string.format( "minLevel -----------------------------\n", limit ) )
	
	-- 中断指示を確認
	if( AI.IsBroken() ) then
		return 0
	end
	
	-- 最深なら、評価する
	if( _limit <= 0 ) then
		AI.MarkPath(LIMIT_START-_limit+1)
		local eval = evaluateFunc()
		return eval
	end
	
	-- パス、あるいはゲーム終了になるかどうか
	local putablesCount = AI.GetPutablesCount()
	if( putablesCount == 0 ) then
		outLog( limit, "pass from minLevel\n" )
		AI.Pass()
		
		-- ゲーム終了になるなら、評価する
		if( AI.GetPutablesCount() == 0 ) then
			AI.MarkPath(LIMIT_START-_limit)
			return evaluateFunc()
		end
		
		-- パスなら、次の階層へ
		local sc = maxLevel( limit, _alpha, _beta )
		return sc
	else
--	end
	
	-- 各手を検索する
	local scoreMin = MAX_VALUE
	local score    = 0
	
	outLog( limit, string.format( "loop count : %d\n", putablesCount-1 ) )
	
	local i
	for i=0,putablesCount-1 do
		outLog( limit, string.format( "loop %d \n", i ) )
		
		local x
		local y
		x, y = AI.GetPutable(i)
		
		outLog( limit, string.format( "GetPutablesCount(before) %d\n", AI.GetPutablesCount() ) )
		
		-- 手を打つ
		AI.PutAndFlip( x, y )
		
		-- 次の自分の手
		score = maxLevel( _limit-1, _alpha, _beta )
		
		-- 手を戻す
		AI.Undo()
		
		outLog( limit, string.format( "GetPutablesCount(after) %d\n", AI.GetPutablesCount() ) )
		
		-- アルファ値を下回ったら、検索中止
		if( score <= _alpha ) then
			return score
		end
		
		-- 相手にとってより良い手が見付かった
		if( score < scoreMin ) then
			scoreMin = score
			_beta = math.min( _beta, scoreMin )
		end
	end
	
	return scoreMin
	end
end

function maxLevel( _limit, _alpha, _beta )
	local limit = _limit
	local s
	
	outLog( limit, string.format( "maxLevel -----------------------------\n", limit ) )
	
	-- 中断指示を確認
	if( AI.IsBroken() ) then
		return 0
	end
	
	-- 最深なら、評価する
	if( _limit <= 0 ) then
		AI.MarkPath(LIMIT_START-_limit+1)
		local eval = evaluateFunc()
		return eval
	end
	
	
	-- パス、あるいはゲーム終了になるかどうか
	local putablesCount = AI.GetPutablesCount()
	if( putablesCount == 0 ) then
		outLog( limit, "pass from maxLevel\n" )
		AI.Pass()
		
		-- ゲーム終了になるなら、評価する
		if( AI.GetPutablesCount() == 0 ) then
			AI.MarkPath(LIMIT_START-_limit)
			return evaluateFunc()
		end
		
		-- パスなら、次の階層へ
		local sc = minLevel( limit, _alpha, _beta )
		return sc
	else
--	end
	
	-- 各手を検索する
	local scoreMax = MIN_VALUE
	local score    = 0
	
	outLog( limit, string.format( "loop count : %d\n", putablesCount-1 ) )
	
	local i
	for i=0,putablesCount-1 do
		outLog( limit, string.format( "loop %d \n", i ) )
		
		local x
		local y
		x, y = AI.GetPutable(i)
		
		outLog( limit, string.format( "GetPutablesCount(before) %d\n", AI.GetPutablesCount() ) )
		
		-- 手を打つ
		AI.PutAndFlip( x, y )
		
		-- 次の自分の手
		score = minLevel( _limit-1, _alpha, _beta )
		
		-- 手を戻す
		AI.Undo()
		
		outLog( limit, string.format( "GetPutablesCount(after) %d\n", AI.GetPutablesCount() ) )
		
		-- ベータ値を上回ったら、検索中止
		if( score >= _beta ) then
			return score
		end
		
		-- 自分にとってより良い手が見付かった
		if( scoreMax < score ) then
			scoreMax = score
			_alpha = math.max( _alpha, scoreMax )
		end
	end
	
	return scoreMax
	end
end



function move( _board, _putablesCount, _putablesData )
	
	AI.PrintLog( "###########################################################\n" )
	
	-----------------------------------------------------------------
	-- 準備
	-----------------------------------------------------------------
	
	AI.ClearEvaluates()
	math.randomseed(os.time())
	
	-- フェーズによる処理
	if( PHASE_2_START <= AI.GetTurnCount() ) then
		evaluateFunc = evaluate_2
		limitMax     = PHASE_2_LIMIT_MAX
	else
		evaluateFunc = evaluate_1
		limitMax     = PHASE_1_LIMIT_MAX
	end
	
	local evalAlpha = MIN_VALUE
	local evalBeta  = MAX_VALUE
	
	myChip = AI.GetTurnChip()
	
	-- 定石設定
	
	-- 縦取りからの定石
	AI.AddTheory( 5, 6,5, 4,6, 3,3, 4,3, 3,4 )
	AI.AddTheory( 5, 6,5, 4,6, 3,5, 6,4, 5,3 )
	AI.AddTheory( 5, 6,5, 4,6, 3,5, 6,4, 4,3 )
	
	-- ななめ取りからの定石
	AI.AddTheory( 5, 6,5, 6,6, 5,6, 6,4, 5,3 )
	AI.AddTheory( 5, 6,5, 6,6, 5,6, 6,4, 7,5 )
	AI.AddTheory( 5, 6,5, 6,6, 5,6, 6,4, 3,3 )
	AI.AddTheory( 5, 6,5, 6,6, 5,6, 6,4, 7,6 )
	
	
	-----------------------------------------------------------------
	-- メイン
	-----------------------------------------------------------------
	local i
	local retX =0
	local retY =0
	
	-- 引数チェック
	if( _putablesCount <= 0 ) then
		return retX, retY
	end
	
	-- メイン処理
	local results = {}
	local eval    = 0
	local evalMax = MIN_VALUE
	
	for i=0, _putablesCount-1 do
		
		-- 中断指示を確認
		if( AI.IsBroken() ) then
			return 0,0
		end
		
		-- メイン処理
		while true do
			-- 定石かどうか
			if( AI.IsTheory( _putablesData[i*2+1], _putablesData[i*2+2] ) ) then
				eval = 1000
				
				-- 手を打つ
				AI.PutAndFlip( _putablesData[i*2+1], _putablesData[i*2+2] )
				do break end
			end
			
			-- 手を打つ
			AI.PutAndFlip( _putablesData[i*2+1], _putablesData[i*2+2] )
			
			-- 先読み手数を求める
			local limit = MAX_TURN - AI.GetTurnCount()
			if( limitMax < limit ) then
				limit = limitMax
			end
			LIMIT_START = limit
			AI.PrintLog( string.format( "LIMIT_START %d\n", LIMIT_START ) )
			
			-- パス、あるいはゲーム終了になるかどうか
			if( AI.GetPutablesCount() == 0 ) then
--				outLog( limit, "pass from maxLevel\n" )
				AI.Pass()
				
				-- ゲーム終了になるなら、評価する
				if( AI.GetPutablesCount() == 0 ) then
					AI.MarkPath(1)
					eval = evaluateFunc()
					do break end
				end
				
				-- 次の階層へ
				eval = minLevel( limit, evalAlpha, evalBeta )
				do break end
			else
			
				-- 次の階層へ
				AI.PrintLog( string.format( "turn %d, limit %d\n", AI.GetTurnCount(), limit ) )
				eval = minLevel( limit, evalAlpha, evalBeta )
				AI.PrintLog( string.format( "eval : %d\n", eval ) )
			
			end
			
			do break end
		end
		
		--
		AI.MarkEvaluate( eval )
		results[i+1] = eval
		
		-- 手を戻す
		AI.Undo()
		
		-- より評価の高い手が見つかったかどうか
		if( evalMax < eval ) then
			evalMax = eval
			retX = _putablesData[i*2+1]
			retY = _putablesData[i*2+2]
		end
	end
	
	-- 評価の一番高い手からランダムに選ぶ
	local nextCount = 0 -- 最高点になったセルの数
	local nexts = {}    -- 最高点になったセル
	for i=0, _putablesCount-1 do
		if( results[i+1] == evalMax ) then
			nexts[nextCount*2+1] = _putablesData[i*2+1]
			nexts[nextCount*2+2] = _putablesData[i*2+2]
			nextCount            = nextCount+1
		end
	end
	local nextIndex = math.floor( math.random() * nextCount )
	retX = nexts[ nextIndex*2 +1]
	retY = nexts[ nextIndex*2 +2]
	
	-- デバッグ表示
	s = string.format( "result(%d) : %d, %d\n", AI.GetTurnCount(), retX, retY )
	AI.PrintLog( s, 2 )
	return retX, retY
end


