CEDEC AI CHALLENGE 2014 まとめ(Part2 戦略)

戦略

大まかな戦略

・公開されている情報から相手の動きを予測する(期待値計算に使用)。
・対戦サーバーに公開される対戦ログを参考にする。
・熱狂度の配分により、目標値を設定する。
・乱択アルゴリズム(モンテカルロ)に頼る。
ただし、予測や配分などによる重み付けを行い、
期待度が高い女の子が選ばれやすくなるようにしている。

モンテカルロ戦略根拠

不完全情報要素が強い

他プレイヤーの熱狂度配分ポイントが半分近く公開されないため、予測がたてづらい。
全ポイント45ptの内、休日の20ptが公開されない。
20ptの配分によりゲームの優劣は大きく変わるため、現時点で自分が勝っているか、負けているがわからない。
また公開情報として与えられる休日のデートの有無もプレイヤーの特定が難しく、
予測にばらつきがでてしまう。

４人同時ゲーム

本ゲームは4人が同時にデート相手を決定する。
4人の各プレイヤーの動きにより、自分の優劣が左右されるため、確実に勝てる方法を決められない。

他プレイヤーの戦略の影響

各プレイヤーの戦略が自分の配分に大きく影響する。
例えば、「相手プレイヤーの動きにあわせて女の子へ好感度を配分」、「決められた定数値を割り当てる」、
「好感度の高い相手にすべての好感度を費やす」...などの戦略が予選に見られた。
ある一人のプレイヤーが「好感度の高い相手にすべての好感度を費やす」戦略をとった場合、
全体のゲームバランスが大きく変化する。
故に、どのような相手であっても勝てるように戦略をたてるのが難しい。
(当日、全パターンを探索し、期待値の高い動作を選択する選手がいた。この対策を行えば、本項目は対象外になると思われる。)

▶︎よって乱数を用いてゆらぎを与えることが必須と考える。

熱狂度分布による割当根拠

ログの解析をした結果

例えば「６・５・５・５・５・４・３」という熱狂度の組み合わせがあった場合、
６点の女の子を狙うより、５点の女の子を２人狙う方が確実に期待値が高い。
なぜなら６点の女の子は狙われやすく、また５点の女の子は４人居るため、競争相手が分散される可能性が高いためである。
よってただ単に、熱狂度の高い女の子を狙うよりかは、熱狂度の分布に応じて戦略を変えるべきだと考えた。
▶︎実際のログでも５点の女の子を狙っている選手が一位の結果が多いように思う。

対戦サーバーのログ収集

予選以前より、対戦サーバー( http://arena.ai-comp.net )において対戦が行われていた。
自身ははじめに、対戦サーバーのログを見て、1位と2位の割当を平均化し、それを割り付けることを考えていた。

以下、その時に使用したスクリプトを記載しておく。

ログ収集(Ruby)

require 'open-uri'

url = "http://arena.ai-comp.net/contests/1/battle_results/"
file = "Match_"

#START_CNT = 1651
START_CNT = 5225
#END_CNT = 5224
END_CNT = 5546

for cnt in START_CNT..END_CNT do
	filename = file + cnt.to_s + ".txt"
	urlname = url + cnt.to_s

	open(filename,"w"){|f|
		open(urlname){|g|
			f.write g.read
		}
	}

	sleep(1) 
end

ログ解析(Ruby)(公開するレベルでない)

#変数宣言
f_enth=""		#熱狂度
f_real = []     #好感度
f_score = []    #最終スコア
f_romeo=""
filecnt = 0
CNT_START = 11852 
#CNT_END = 5224
CNT_END = 12603 
total_cnt = 0
OUT_FILE = "sum.csv"
myEgentFlg = 0

HEADER = "ID,Match,\
Es_Girl0,P0_Point0,P1_Point0,P2_Point0,P3_Point0,\
Es_Girl1,P0_Point1,P1_Point1,P2_Point1,P3_Point1,\
Es_Girl2,P0_Point2,P1_Point2,P2_Point2,P3_Point2,\
Es_Girl3,P0_Point3,P1_Point3,P2_Point3,P3_Point3,\
Es_Girl4,P0_Point4,P1_Point4,P2_Point4,P3_Point4,\
Es_Girl5,P0_Point5,P1_Point5,P2_Point5,P3_Point5,\
Es_Girl6,P0_Point6,P1_Point6,P2_Point6,P3_Point6,\
Es_Girl7,P0_Point7,P1_Point7,P2_Point7,P3_Point7,\
P0_Score,P1_Score,P2_Score,P3_Score,\
EthNum6,EthNum54,EthNum3,ROMEO_AI_NO"

#ヘッダー書き込み
File.open(OUT_FILE,"a") do |file|
	file.write(HEADER + "\n")
end


for filecnt in CNT_START .. CNT_END do
	#一行ずつ読み出し
	filename = "Match_" + filecnt.to_s + ".txt"
	open(filename){|file|
		myEgentFlg = 0
		while line = file.gets
			if line =~ /Enthusiasm/
			#再度一行読み出し(熱狂度)
				f_enth = file.gets
			end
	
			if line =~ /Real Love/
			#８行分読み出し(女の子の好感度)
				for cnt in 0..7 do
					f_real[cnt] = file.gets
				end
			end

			if line =~ /Ranking:/
			#スコア読み出し(4人プレイヤー分)
				for cnt in 0..3 do
						f_score[cnt] = file.gets
				end
			end

		end
	}

	#不要データ削除 全配分が0のプレイヤーがいる場合
	girlsPoint = []
	for cnt in 0..7 do
		girlsPoint[cnt] = Array.new(4)
		s_tmp = f_real[cnt].split(" ")
		s_tmp[3] = s_tmp[3].gsub("\n","")
		for cnt2 in 0..3 do
			girlsPoint[cnt][cnt2] = s_tmp[cnt2].to_i
		end
	end
	flg = 0
	for cnt in 0..3 do
		sum = 0
		for cnt2 in 0..7 do
			sum += girlsPoint[cnt2][cnt]
			if girlsPoint[cnt2][cnt] > 40 #一人に40以上与えているのは不要サンプル 
				flg = 1
				break
			end
		end
		if sum < 40 || flg == 1#トータル配分が40以下の場合不要サンプル
			flg = 1
			break
		end

	end

	if flg == 1
		next
	end


	#フォーマット整形
	#Format
	#ID,X
	#Match_xxx
	#Player,0,1,2,3
	#girl0,a,b,c,d,A
	#girl1,....
	#...
	#girl7,e,f,g,h,G
	#score,y,y,y,y
	#enthNum,x,y,z
	#end


	enthArray = f_enth.split(" ")
	enthArray[7] = enthArray[7].gsub("\n", "")

	girls = []
	for cnt in 0..7 do
		girls[cnt] = ""
		s_tmp = f_real[cnt]
		s_tmp = s_tmp.gsub(" ", ",")
		s_tmp = s_tmp.gsub("\n", ",")
		girls[cnt] += s_tmp
	end

	score = []
	for cnt in 0..3 do
		#Example "Player 2: 25 popularity\n"
		scoreArray = f_score[cnt].split(" ")
		scoreArray[1] = scoreArray[1].gsub(":","");
		score[scoreArray[1].to_i] = scoreArray[2];
	end

	scores =  score[0] + "," + score[1] + "," + score[2] + "," + score[3]

	#EnthAnalyze
	enthNumArray = [0,0,0]
	for cnt in 0..7 do
		if enthArray[cnt].to_i == 6
			enthNumArray[0]+=1
		elsif enthArray[cnt].to_i == 5 || enthArray[cnt].to_i == 4
			enthNumArray[1]+=1
		else 
			enthNumArray[2]+=1
		end
	end
	enthNum = enthNumArray[0].to_s + "," + enthNumArray[1].to_s + "," + enthNumArray[2].to_s
	

	#FileWrite
	
	body = total_cnt.to_s + "," #ID
	body += filecnt.to_s + ","  #Match
	for cnt in 0..7 do
		body += enthArray[cnt] + ","
		body += girls[cnt] 
	end
	body += scores + ","
	body += enthNum 

	File.open(OUT_FILE,"a") do |file|
		file.write(body + "\n")
	end
	total_cnt += 1
end

実際に提出したコードと結果はpart3で