遺伝的アルゴリズム - じゅんじゅんのきまぐれ

こっちをあげるのを忘れてた。
前日の安直なバトルゲームの強い遺伝子を探す、遺伝的アルゴリズム。

スクリプト

ゲームのスクリプトに依存しています。

OPTION EXPLICIT

Call Battle


Battle.LogLevel = 3

TEXTBLOCK GENS_BLOCK
2c2oXqLR1hCFyDODBLHD7GVquqPUmXHP4nXi6A0ymG2jUzi5yvoTB5dRKkKrzkJU7N55OiOVJEd4 116勝31敗 : atk(292) def(154) eva(10) hp(544) ran0(985) ran1(694) ran2(841)
2cMvqnLufGTu0CJZjfl3b86A7GqsSj0DgUIz1sOwvI3qRzi5yvoTB5dRKkKrzkJU7N55OiOVJEd4 152勝44敗 : atk(239) def(142) eva(21) hp(598) ran0(992) ran1(272) ran2(505)
CBLxg2IBdrMkstSHF3ygMGHdpvqsSj0DgUIz1sOw6KlFQkeoi9BhFkxzvIvOdXU2fttJi1E5bwVx 178勝67敗 : atk(310) def(101) eva(371) hp(218) ran0(88) ran1(774) ran2(859)
FtM8u5u2HXgqSeSoxikLn7Diim7F1YHlXYGYVJXZ1cOGlJtKIid8suQMMxwrE9yJMTsfoIpYWp3S 135勝61敗 : atk(217) def(432) eva(1) hp(350) ran0(550) ran1(13) ran2(524)
CBLxgwIBdrMkstODBLHDBYpDQHD0i6WKYnXi6A0ymG2jUzi5yvoTB5dRKkKrzkJU7N55OiOVJwVx 64勝34敗 : atk(340) def(101) eva(371) hp(188) ran0(88) ran1(774) ran2(859)
UPGH5eHssVR14ageEawSb86A7GqsSj0DgUIz1muGDbvA7mYntOaiPuOVHFCQNa8d8qjNMMyj2j1g 107勝40敗 : atk(120) def(207) eva(67) hp(606) ran0(763) ran1(344) ran2(814)
ccE72wZqQEnse30bVEM3An72i2DYCS8malAgoScAOIEjH2dLu6d51V1ZjPIcPXYwbnMKNC9QVxUX 69勝29敗 : atk(200) def(470) eva(180) hp(150) ran0(758) ran1(835) ran2(280)
KrBzjRf85CMkstSHF3ygMGHdpvH0htxuaBsWhW6q6KlFQkeoi9BhWw5ugqUiMHXBlHPngjqaPatW 69勝29敗 : atk(251) def(25) eva(550) hp(174) ran0(876) ran1(543) ran2(861)
fK9XDVjMoEEFyDODBLHD7GVquqPUmXHP4nXi6A0ymG2jUSj2g5lktSelLePCarU2w65zZPhaBldU 102勝45敗 : atk(159) def(78) eva(424) hp(339) ran0(89) ran1(664) ran2(121)
qfAp7u3WGAE7GuYvScqSGkjoNDWkBBrAehahtV7fFgFctxAR7nUutjtf2w3IJZ9kajmuyKyJC9bc 98勝49敗 : atk(44) def(775) eva(49) hp(132) ran0(631) ran1(576) ran2(615)
Fz4bW2oYRRslRTJ7uNZNUuTyFW4ZaSJi88RHrNVowpVkdAgJuhtRHehI7h2DWUEKdOR4YHXuPkK1 62勝36敗 : atk(66) def(617) eva(79) hp(238) ran0(1) ran1(605) ran2(886)
poKCSf9WAoYF4nOxKdaii1xvgyvlJBK5IU1FY5z09yxlJF6TPpM19iNgxDzKGSSFt4Z5tqU8LxGp 91勝56敗 : atk(387) def(65) eva(269) hp(279) ran0(801) ran1(898) ran2(110)
IavuVJprbfEPIIx4O5f93Awsbral3sYfZeE0uVDKoS6otwoIzhJrpC00EeUJiZFxRunInQo84pmT 102勝45敗 : atk(35) def(115) eva(465) hp(385) ran0(671) ran1(963) ran2(304)
7GJ6Al8mqBJLHfXZ35B4blsSZO03nOAJGnFaQP59gJALJ5OUO6RFEPJl8DsPMlPHLnKXebPCj3Pj 64勝34敗 : atk(13) def(286) eva(44) hp(657) ran0(641) ran1(483) ran2(660)
6DKHh3AuMuWoC1fN3ZUU03uzDsrYgW63ZyTJhd4pAX071dducqBmWPqyIw6syGT4bTSQqU3Ba4h0 62勝36敗 : atk(533) def(203) eva(84) hp(180) ran0(716) ran1(630) ran2(435)
ENDTEXTBLOCK
DIM gbs = SPLIT(GENS_BLOCK, "<#CR>")

// 初期世代作成
DIM a = 1, gens[49], ws[49], i
FOR i = 0 TO LENGTH(gens) - 1
	IFB i < LENGTH(gbs) THEN
		gens[i] = COPY(TRIM(gbs[i]), 1, 76)
	ELSE
		gens[i] = Battle.CreateGen()
	ENDIF
	ws[i] = 0
NEXT

// 開始
DIM gen[1], w, j, atk, def, eva, hp, ran[2], pat, loop = TRUE
HASHTBL wins, loses
WHILE loop
	Battle.Log("第" + a + "世代", 2)
	// 各組み合わせで9本勝負。5本先取で勝負あり
	FOR i = LENGTH(gens) - 2 TO 0 STEP -1
		gen[0] = gens[i]
		FOR j = i + 1 TO LENGTH(gens) - 1
			FUKIDASI("第" + a + "世代 " + i + " vs " + j)
			gen[1] = gens[j]
			w = 0
			IFB Battle.Do(gen, 5) = 0 THEN
				ws[i] = ws[i] + 1
				wins[gens[i]] = wins[gens[i]] + 1
				loses[gens[j]] = loses[gens[j]] + 1
			ELSE
				ws[j] = ws[j] + 1
				wins[gens[j]] = wins[gens[j]] + 1
				loses[gens[i]] = loses[gens[i]] + 1
			ENDIF
			IFB GETKEYSTATE(VK_ESC) THEN
				IFB MSGBOX("終了？", BTN_YES OR BTN_NO) = BTN_YES THEN
					loop = FALSE
					IF MSGBOX("即時終了？", BTN_YES OR BTN_NO) = BTN_YES THEN BREAK 2
				ENDIF
			ENDIF
		NEXT
	NEXT
	QSORT(ws, 1, gens)
	FOR i = 0 TO LENGTH(ws) - 1
		// 世代結果表示
		Battle.AnalyzeGen(gens[i], atk, def, eva, hp, ran[0], ran[1], ran[2], pat)
		Battle.Log(COPY(gens[i], 1, 76) + " " + ws[i] + "勝 : atk(" + atk + ") def(" + def + ") eva(" + eva + ") hp(" + hp + ") ran0(" + ran[0] + ") ran1(" + ran[1] + ") ran2(" + ran[2] + ")", 2)
		ws[i] = 0
	NEXT
	// 20〜39は、0〜19の交差+突然変異
	FOR i = 0 TO 19 STEP 2
		Gen(gens[i], gens[i+1], gens[i+20], gens[i+21])
	NEXT
	// 40〜48は、0〜8と49の交差+突然変異
	FOR i = 0 TO 8
		Gen(gens[i], gens[49], gens[i+40], i)
	NEXT
	// 49は更新
	gens[49] = Battle.CreateGen()
	a = a + 1
WEND

// ソート結果表示
DIM rgs, rws, rls, rrs
a = LENGTH(wins)
rgs = SAFEARRAY(0, a - 1)
rws = SAFEARRAY(0, a - 1)
rls = SAFEARRAY(0, a - 1)
rrs = SAFEARRAY(0, a - 1)
FOR i = 0 TO a - 1
	rgs[i] = wins[i, HASH_KEY]
	rws[i] = wins[i, HASH_VAL]
	rls[i] = loses[rgs[i]]
	rrs[i] = rws[i] / (rws[i] + rls[i])
NEXT
QSORT(rrs, 1, rws, rls, rgs)
FOR i = 0 TO a - 1
	Battle.AnalyzeGen(rgs[i], atk, def, eva, hp, ran[0], ran[1], ran[2], pat)
	Battle.Log(COPY(rgs[i], 1, 76) + " " + rws[i] + "勝" + rls[i] + "敗 : atk(" + atk + ") def(" + def + ") eva(" + eva + ") hp(" + hp + ") ran0(" + ran[0] + ") ran1(" + ran[1] + ") ran2(" + ran[2] + ")", 2)
NEXT



// 交差および突然変異
PROCEDURE Gen(g0, g1, var r0, var r1, r=50)
	DIM l = LENGTH(g0), p0 = RANDOM(l), p1 = RANDOM(l), p2 = p0
	IFB p0 > p1 THEN
		p0 = p1
		p1 = p2
	ENDIF
	r0 = COPY(g0, 1, p0 - 1) + COPY(g1, p0, p1 - p0) + COPY(g0, p1)
	r1 = COPY(g1, 1, p0 - 1) + COPY(g0, p0, p1 - p0) + COPY(g1, p1)
	FOR p0 = 0 TO 1
		IFB RANDOM(10000) < r OR EVAL("r" + p0 + "=g" + p0) THEN
			REPEAT
				p1 = RANDOM(l)
				EVAL("r" + p0 + " := COPY(r" + p0 + ", 1, p1 - 1) + Battle._adicn[RANDOM(62), HASH_KEY] + COPY(r" + p0 + ", p1 + 1)")
			UNTIL EVAL("r" + p0 + "<>g" + p0)
		ENDIF
	NEXT
FEND

解説

交差および突然変異用にGen関数を作成しています。
親の遺伝子を与えると、子の遺伝子を作るイメージ。
初期状態で、0.5%の確率で突然変異を入れていますが、結果が親と同じになったケースも突然変異させています。

パラメーターは適当に、
50の遺伝子を用意。
相互に戦って、順位をつける。
上位20はそのまま次世代へ。
上位20を二つづつ交差して、子の20を作成。
最下位と上位9を交差して、上位優勢な子を作成。（やさしい人にダメンズが多い）
最後一つは、新規生成して、次世代が完成。

ESCを押されるまで、延々と繰り返します。
回避が乱数なので、その影響を抑えるために、1取組5本勝負にしています。

遺伝的アルゴリズムの場合、交差や突然変異のパラメーターの他に、次世代をどう作るかも難しいですね。
やはり、実際にやってみることは重要。

元のゲームの遺伝子について

スクリプトを読めばわかる話ですが、遺伝子はアルファベット大文字・小文字と数字の62進数の数値です。
76桁。

先頭6桁が、攻撃力・防御力・回避力（それぞれ0〜999）と最初二手を保持。
体力は、CalcHpで合計値が1000になるように計算しています。（他の値も適宜変更）

次の6桁が、ランダム行動率1/2/3と初手・第二手、行動パターン3桁分。
ランダム行動率は、行動パターン通りの手を打つか、ランダムにするかの率。
1/2/3と三つあるのは、残りHPが2/3以上で1を、1/3以上で2を、1/3以下で3を使います。
（以上・以下は、どっちか知らない。そんなに厳密に作ってないので）

残り64桁は、行動パターンテーブル。
行動パターンテーブルもランダム行動率と同様、3セットある。
1セットは、自分と相手の前二回の手の組み合わせで決定するので、
(自分3手 * 相手3手) ^ 前二回分 = 81 通り。
3手の81通りが3セットなので、3進数で243桁。
3桁分は取得済みなので、残り240桁。

UWSCの数値精度は15桁なので、3進数で30桁、62進数で8桁程度。
30桁8個分なので、62進数で64桁。
合計76桁。

ま、行動パターンテーブルが期待通り機能しているか検証してないけど、、、。
厳密なものじゃないし、いいよね。