GA - 오델로 - 경쟁 및 재생산

3. 경쟁
이제 유전자도 설계했으니 이들을 경쟁시켜서 적응도를 측정해야 합니다. 그런데 무엇과 경쟁시킬까요? 특정한 AI를 하나 만들어서 이 AI와 경쟁시켜야 할까요?
아, 전에도 종종 사용했던 공진화를 이용하면 구태여 AI를 따로 만들 필요가 없겠네요. 일이 줄었습니다.
여기서는 이 오델로플레이어들을 6개의 무리로 나누었습니다. 각 무리에는 512개씩의 오델로플레이어를 포함시켰습니다. 그리고는 이들 사이에서 경쟁을 시켰습니다.
각 오델로플레이어들은 같은 무리에 있는 것들과는 싸우지 않습니다. 다른 무리에 있는 것들과 싸우게 됩니다.

procedure Compatition()
.. for h := 0, 6 do
..... for p := 0, 512 do
........ Horde[h][p].Fitness := 0; // 모든 객체의 적응도 초기화
..... end
.. end

.. // 경쟁 시작
.. for white := 0, 6 do
..... for black := 0, 6 do
........ if white != black then
........... // Horde[white]와 Horde[black]간의 대결
........... // 랜덤한 상대를 만나기 위해
........... for k := 0, 512 do
.............. CardDeck[k] = k;
........... end
........... for k := 0, 512 do
.............. rnd := Random(0, 512);
.............. tmp = CardDeck[k];
.............. CardDeck[k] = CardDeck[rnd];
.............. CardDeck[rnd] = tmp;
........... end
........... for k := 0, 512 do
.............. Compatition(Horde[white][k], Horde[black][CardDeck[k]];
........... end
........ end
..... end
.. end
end

Compatition프로시저는 생략하겠습니다. 두 오델로플레이어끼리 대결을 시킨 후, 남아있는 자신의 돌 수를 Fitness에 더하는 프로시저입니다.

4. 재생산
이렇게 적응도를 구했으면 보다 많은 돌을 가진 오델로플레이어를 찾아 재생산을 시킵니다. 일단 재생산 대상은 T=0.99인 4차 토너먼트법 - 2⁴ = 16개의 후보를 선택 후 토너먼트를 반복해서 하나 설정, 토너먼트의 승부는 1% 확률로 적응도 낮은 것이 승 - 으로 결정했습니다.

4.1 교차
다음과 같은 유전자를 가진 두 오델로플레이어가 선택되었다고 합시다.

가
'...+...', 0.327
'.MM.+EE.', 0.932
'EE+.M..', 0.142
'.MEEE+EE', 0.527
'EMMEE+EM', 0.106
'..EE+EEE', 0.172
'MME+MM..', 0.018
'..E+...', 0.437


나
'.MM.+EE.', 0.762
'..M+...', 0.007
'..EE+EEE', 0.120
'..M.+EE', 0.607
'E+EMME', 0.742
'EMMEE+EM', 0.224


검은색으로 표시된 유전자는 '가'와 '나'에 다 있지만, 붉은색으로 표시된 유전자는 '가'에만, 녹색 유전자는 '나'에만 존재하는 유전자입니다. 이를테면 '나'는 '..E+...'라는 패턴을 만난 적이 없습니다. 만약 '나'가 그 패턴을 만난다면 어떨까요? 규칙에 의해 이 패턴을 랜덤한 가중치와 함께 추가할 것입니다. 그러므로 지금 추가하더라도 상관 없겠죠.
교차를 하기 전에 '가'와 '나'는 서로가 가지고 있는 패턴을 공유합니다.


가
'...+...', 0.327
'.MM.+EE.', 0.932
'EE+.M..', 0.142
'.MEEE+EE', 0.527
'EMMEE+EM', 0.106
'..EE+EEE', 0.172
'MME+MM..', 0.018
'..E+...', 0.437
'..M+...', 0.725
'E+EMME', 0.176


나
'.MM.+EE.', 0.762
'..M+...', 0.007
'..EE+EEE', 0.120
'..M.+EE', 0.607
'E+EMME', 0.742
'EMMEE+EM', 0.224
'...+...', 0.301
'.MEEE+EE', 0.815
'MME+MM..', 0.328
'..E+...', 0.663


즉 '가'와 '나' 둘 다 10개의 동일한 패턴(가중치는 다르지만)을 가진 유전자가 되었습니다.
이후에는 '가'와 '나'에서 동일한 패턴을 꺼내서 50%확률로 가중치를 바꾸면 교차 완료입니다.

function FindPattern(gene, pattern) // gene에서 pattern과 동일한 것 찾음
.. for k := 0, gene.Size do
..... if IsSamePattern(gene.Pair[k].Pattern, pattern) then
........ return k; // 찾았으면 위치 리턴
..... end
.. end
.. return -1;
end

procedure CrossOver(childA, childB)
.. geneA = childA.Gene
.. geneB = childB.Gene
.. for locA := 0, geneA.Size do
..... locB := FindPattern(geneB, geneA.Pair[locA].Pattern
..... if locB == -1 then // 맞는 패턴이 없음, B에 추가
........ geneB.Pair[childB.Gene.Size].Pattern = geneA.Pair[locA].Pattern
........ geneB.Pair[childB.Gene.Size].Weight = Random(0, 1)
........ childB.Gene.Size + childB.Gene.Size + 1
..... end
.. end
.. // 생략 - 동일한 방법으로 B에만 있는 유전자 A에 추가

.. // 교차 시작
.. for locA := 0, geneA.Size do
..... locB := FindPattern(geneB, geneA.Pair[locA].Pattern
......... // 동일한 패턴을 B에서 찾음

..... if Random(0, 1)＜ 0.5 then // 50%확률로 가중치 교환
........ tmp = geneA.Pair[locA].Weight
........ geneA.Pair[locA].Weight = geneB.Pair[locB].Weight
........ geneB.Pair[locB].Weight = tmp
..... end
.. end
end

4.2 돌연변이
돌연변이는 비교적 간단합니다. 오델로플레이어의 모든 유전자를 돌면서 일정확률로 가중치값을 변화시키면 됩니다.

procedure Mutantation(child)
.. for k := 0, child.Gene.Size do
..... if Random(0, 1)＜ 0.001 then
........ child.Gene.Pair[k].Weight = Random(0, 1)
..... end
.. end
end

5. 이주
앞에서 설명한 것처럼, 오델로플레이어들을 공진화시키기 위해 고립된 6개의 무리를 만들어 그 안에서만 번식이 일어나도록 하였습니다. 특히 512개밖에 안되는 무리 안에서만 번식시킨다면 아무리 돌연변이를 적용시키더라도 유전자가 획일화되기 쉽습니다. 그러므로 이렇게 유전적으로 고립시킨 경우에는 가끔씩 일부 개체들을 이주시켜 새로운 유전자를 섞어주는 것이 좋습니다.

procedure Migration()
.. if Generation % 10 == 9 then // 10세대에 한번씩
..... do
........ a := Random(0, 6)
........ b := Random(0, 6)
..... while a == b

..... aa := Random(0, 512)
..... bb := Random(0, 512)
..... tmp = horde[a][aa];
..... horde[a][aa] = horde[b][bb];
..... horde[b][bb] = tmp;
end