GA - 죄수의 딜레마(Prisoner's Dilemma)

몇달 전에 '죄수의 딜레마'란 포스트를 올린 적이 있습니다. 그때는 미처 시뮬레이션을 직접 해 보진 못했습니다(너무 간단한 것이라 별로 하고 싶지 않더군요).
그런데 이번에 회사일로 Lua란 언어를 공부해야 할 기회가 생겼습니다. 아시다시피 어떤 언어를 공부하기 위해서는 그 언어로 프로그램을 만들어 보는 것이 가장 좋은 방법이죠.
그래서 한번 죄수의 딜레마 시뮬레이션을 루아로 만들어 봤습니다.

1. 유전자 설계 및 초기화
간단하게 1턴 앞을 보는 유전자를 설계했습니다. 유전자는 오른쪽 그림과 같은 3자리 영문자로 각각 협력(Cooperation), 배신(Betray)을 의미합니다.
최초에는 BBB형(상대가 어떻게 나오든 항상 배신)의 유전자 768개를 만든 후 모든 유전자들이 리그전을 펼칩니다. 즉 모든 유전자는 자신 이외의 767개 유전자들 모두와 한번씩 협력/배신 게임을 하는 것이죠.

2. 리그전
만약 둘 다 협력했으면 쌍방이 20점씩, 둘다 배신했다면 10점씩, 한쪽만 배신당했다면 배신한 쪽은 35점, 배신당한 쪽은 5점*을 얻게 됩니다. 767개의 다른 유전자들과 협력/배신 게임을 한 후 총 점수가 그 유전자의 적응도가 됩니다. 결국 한 세대는 ₇₆₇C₇₆₈회의 경기를 거친 후 재생산에 들어갑니다.

* 뒤에서도 나오지만, 여기서는 룰렛선택법을 사용했습니다. 이것은 적응도를 그대로 선택비율로 사용하기에, 만약 -적응도가 나온다면 오작동할 가능성이 큽니다. 그러므로 적응도를 항상 0 이상으로 하기 위해 전체적으로 적응도를 향상시켰습니다.

3. 재생산
한 세대 유전자들의 적응도가 모두 계산되면 다음 세대를 만들기 위해 재생산 루틴에 들어갑니다.
우선 각 유전자들의 적응도를 비율로 하여 룰렛선택법으로 하나의 유전자를 골라냅니다(여기서는 유전자가 크지 않으므로 구태여 교차까지 할 필요성을 느끼지 못해 돌연변이만을 사용했습니다).이 유전자를 복사한 후 적당한 돌연변이('C'를 'B'로, 또는 'B'를 'C'로)를 적용시켜 다음 세대를 만들었습니다.

4. 결과
위와 같은 방식으로 2000세대를 진화시킨 결과입니다.
바로 앞의 상황만을 기억하는 경우 가능한 유전자 타입은 다음과 같은 8가지입니다.

CCC CCB CBC CBB BCC BCB BBC BBB

각 유전자들의 갯수 변화를 그래프로 나타낸 것이 다음 그림입니다.


처음에 모든 유전자가 BBB(항상 배신)로 시작했지만, BBB는 급격히 줄어들면서 전반적으로 우세를 보이는 것은 붉은색 CCB형입니다. 이 CCB형은 전형적인 눈에는눈 전략을 보이는 유전자입니다. 가끔씩 우위를 뺏기긴 합니다만 곧바로 다시 우위를 뺏는 모습을 보여줍니다.
CCB가 우세를 점한 환경에서는 CCC도 불이익을 받지 않습니다. CCB는 먼저 배신을 하지 않기 때문입니다.
하지만 CCC가 너무 많아지면 그때부터는 CBB 또는 BBB가 살판납니다. 배신을 당해도 앙갚음을 할 줄 모르는 CCC는 CBB/BBB의 밥이기 때문이죠. 그때문에 CBB/BBB의 수가 늘어나고 때때로 CCB를 넘어설 때도 있습니다.
그러나 그렇게 되면 CCC는 도태되고 그에따라 CBB/BBB도 도태되기에 CCB가 다시 우세를 점할 수 있는 것이죠.

즉, http://chamsol4.blogspot.com/2009/06/prisoners-dilemma_08.html에서 예측했던 것처럼 눈에는눈이 가장 유효한 전략임을 확인할 수 있습니다.

뱀발 : 여기서는 바로 전의 상황만을 기억하는 경우의 시뮬레이션이었습니다. 그렇다면 더 오래 기억을 한다면 어떻게 될까요?
2턴의 기억만을 가진다고 해도 유전자의 길이는 7이 됩니다. 3개짜리 유전자에, 앞의 두 판이 (CC), (CB), (BC), (BB)인 경우가 붙어야 하기 때문이죠.
그런데 그렇게 하면 유전자의 갯수는 CCCCCCC부터 BBBBBBB까지 128개가 됩니다. 128개를 모두 분석하기가 쉽지 않아 다음 기회로 미루어야겠습니다.