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개를 모두 분석하기가 쉽지 않아 다음 기회로 미루어야겠습니다.

진화론 이야기 - 죄수의 딜레마(Prisoner's Dilemma)

1. 상황
G는 보석을 가지고 있습니다. 하지만 돈이 쪼들립니다.
M은 돈을 가지고 있습니다. 하지만 그는 보석을 가지고 싶어합니다.
그들은 모종의 이유로 서로 만날 수도, 연락을 할 수도 없습니다. 단지 지정된 시간(동시)에 G는 보석을, M은 돈을 서로 상대방에게 택배로 보낼 뿐입니다.
이 경우에 이들이 선택할 최선의 전략은 어떤 것일까요?
(물론 실제의 죄수의 딜레마와는 조금 다르지만 진화론과 관련해서 설명하기에는 이쪽이 낫습니다)
서로가 약속을 지키면(협력하면) G는 돈을, M은 보석을 얻는 최선의 결과를 얻습니다.(양쪽에 10점씩)
서로가 서로를 배신하면 둘 다 아무 변화가 없습니다(양쪽에 0점)
어느 한쪽만이 배신하면 배신한 쪽은 돈과 보석을 다 얻지만(15점) 배신당한 쪽은 다 잃습니다(-5점)
원래의 죄수의 딜레마와 같이 배신하는 쪽이 항상 이득입니다.

하지만 G는 많은 보석을 가지고 있으며 계속 돈을 필요로 합니다. M은 돈은 매우 많으며 보석욕심도 점점 커집니다. 이후에도 두 사람은 계속 거래를 해야 합니다. 이럴 경우에는 어떤 전략을 사용하는 것이 가장 좋을까요?

2. Tit-for-Tat
1970년대 엑셀로드(Axelrod)는 이런 상황을 가정하여 최적의 전략 - 과거 상대방의 반응으로부터 협력할지 배신할지를 선택하는 프로그램을 공모했습니다. 그리고 토너먼트식으로 공모된 전략들을 맞붙여 어떤 전략이 가장 높은 득점을 하는지 확인했습니다.

그 토너먼트에서 우승한 전략이 Tit-for-Tat(받은만큼돌려주기 또는 눈에는눈)이었습니다. 즉 가장 처음에는 협력하고, 그 다음부터는 상대가 한 대로 돌려주는 것입니다.

눈에는눈은 협력을 우선하여 상호간의 이익을 추구합니다. 즉 먼저 배신하지 않습니다.
눈에는눈은 배신을 당했을 경우 자신도 배신함으로써 응징합니다.
눈에는눈은 응징에 성공(자신이 배신할때 상대가 협력)한다면 용서하고 다시 상호간의 이익을 추구합니다.

정확히 말해서 눈에는눈을 능가하는 단 하나의 전략이 있었습니다. 이것은 처음부터 배신해서 상대의 반응을 살핍니다. 상대가 내 배신에 반응하지 않으면 계속 배신으로 상대를 착취하는 것입니다. 내 배신에 상대도 배신으로 반응한다면 그때는 눈에는눈으로 변신하는 것이죠. 하지만 그것은 특수한 상황 - 상대중에 Random이라는, 50%확률로 협력과 배신을 결정하는 전략이 있었기에 가능했던 것입니다. 만약 Random이 없다면 상대를 떠보기 위한 배신의 부담으로 순수한 눈에는눈에 비해 낮은 점수를 얻게 됩니다.

3. 생존경쟁
윗실험에 참가했던 전략들을 일정 수만큼 컴퓨터에 넣고, 임의로 짝을 지워 게임을 시킵니다. 그리고 그때 얻은 점수 비율에 따라 다음 세대의 수를 결정하는 프로그램을 만듧니다.
초기에는 '어떻게든 상대를 착취하는 사기꾼' 전략들이 강세를 보입니다. '순진한 촌뜨기' 전략들을 착취하면서 세력을 떨치는 것이죠.
하지만 촌뜨기들이 줄어들고 더이상 착취할 상대가 남아있지 않게 되면 사기꾼들 역시 나락으로 떨어지고 맙니다. 눈에는눈을 착취하려고 하면 응징을 당하고, 다른 사기꾼 상대를 만나도 착취할 건덕지가 없습니다.
반면 눈에는눈은 사기꾼을 만나면 한번 배신당하지만 응징에 의해 더이상의 착취를 당하지는 않습니다. 다른 눈에는눈이나 촌뜨기를 만나면 상호협력에 의해 양측 다 점수를 얻습니다.
결국 시간이 지나면 눈에는눈이 대세를 이루고, 눈에는눈에 기대는 소수의 촌뜨기, 그리고 가끔씩 만나는 촌뜨기를 삥뜯으며 살아가는 소수의 사기꾼이 평형을 이루는 상태가 됩니다.

4. 유전자 알고리즘
윗 실험은 이미 개발된 전략들의 우열을 판가름하는 내용이었습니다. 그런데 완전한 무질서 상태에서도, 도덕이니 양심이니 하는 것이 전혀 없는 상태에서도 저런 협력이 나올 수 있을까요?

4-1. 초기에 무조건 배신하는 전략들만을 모아놓고 3번의 생존경쟁과 같은 프로그램을 돌립니다. 역시 가장 높은 점수를 얻은 전략은 많은 자손을 남길 수 있습니다. 그러나 이때는 약간의 돌연변이를 일으킨 자손을 만듧니다.
돌연변이에 의해 조심스럽게 협력을 시도하는(하지만 배신당했다면 바로 협력관계를 취소하는) 전략이 생깁니다. 이들은 많은경우 주위에게 조금씩 착취당하지만, 이런 변이체들끼리 만난다면 더 높은 점수를 얻고 더 많은 번식기회를 가질수 있습니다. 그 다음 세대에는 협력하는 전략들끼리 만날 기회가 더 많아지고 더 높은 점수를 얻을 것입니다.
결국 이 생태계는 눈에는눈은 아니지만 눈에는눈과 비슷한 형태의 전략으로 가득 차게 됩니다.

4-2. 반대로 초기에 무조건 협력하는 전략들만을 모아놓는다면 어떨까요? 배신하는 돌연변이가 나온다면 그는 주위 모든 것들을 착취해서 급격히 세를 불려나갑니다. 결국 4-1의 초기상태와 비슷하게 되고 마찬가지 결과가 나옵니다.

5. 결론
진화론에 의해서도 착한 놈이 이긴다.(진화론이 정설이 되면 사회가 약육강식의 정글이 된다고 걱정하는 창조론자들이 있어서...)

출처 : 카오스에서 인공생명으로(미셸 월드롭 Mitchell Wakdrop)

시뮬레이션은 여기