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

진화론 이야기 - 시뮬레이션(simulation)

다윈 이후 백여년간 진화론은 (진정한 유사과학인) 창조론계로부터 '유사과학'이라는 비난을 받아 왔습니다. 물론 이것은 종교적 도그마를 과학에 도입하려는(또는 과학을 종교의 도구로 삼으려는) 창조론자들의 딴지이긴 했습니다만, 한편으로는 진화론 자체가 실험이 불가능한 과학이라는 한계를 가지고 있었기 때문이기도 합니다. 진화라는 현상이 최소한 수천년단위로 일어나기에 진화의 정확한 메커니즘을 실험을 통해 밝히기가 쉽지 않았기 때문입니다.

하지만 20세기 중후반에 들어 진화론자들은 강력한 실험도구를 얻을 수 있었습니다. 바로 컴퓨터죠. 유전자의 움직임을 (때로는 화학반응 수준에서, 때로는 재생산과 돌연변이 수준에서) 묘사하는 시뮬레이션을 통해 생물의 진화과정에서 어떤 일이 벌어지는지 분석할 수 있게 되었습니다.

컴퓨터에서 유전자를 시뮬레이션하면 대부분 다음과 같은 과정이 벌어집니다.(물론 이름은 학술적인 이름이 아닙니다.)

1. 낙원기(Era of Paradise)
시 뮬레이션의 초기단계입니다. 주변에 자원은 많고 유전자는 적으니 유전자들은 마음껏 자원을 얻어 번식을 할 수 있죠. 이 시기에는 보다 효율적인 번식을 해나가는 유전자들이 대세를 차지합니다. 보다 적은 자원으로 보다 빠른 시간에 번식을 하는 유전자들로 가득 차게 됩니다.

2. 경쟁기(Era of Competition)
유전자들은 점점 많아지고 슬슬 자원의 부족이 찾아옵니다. 여기서부터 유전자들의 이전투구가 극심해집니다. 무슨 수를 써서든 자원을 모아 자신의 복제를 만드는 유전자가 대세를 차지하기에, 옆에 있는 유전자를 분해해서 자신의 복제를 만들 재료로 삼는 만행(?)도 사양치 않습니다.

3. 협동기(Era of Cooperation)
밑의 죄수의 딜레마에 서도 언급했지만 일부의 유전자들이 협동의 방법을 알아냅니다. 물론 그들의 성급한 협동시도는 주위의 다른 유전자들에게 먼저 이득을 주겠지만, 그들끼리 만난다면 이기적인 주위의 다른 유전자에 비해 훨씬 효율적으로 번식해 나갈 수 있습니다. 결국 협동하는 유전자들은 시뮬레이션공간을 가득 채우게 됩니다.

4. 기생기(Era of Parasite)
서로 협력하는 유전자들 사이에서 기생충이 나타납니다. 이들은 다른 유전자를 착취한다는 점에서는 협동기때의 수많은 유전자들과 비슷하지만, 그 착취의 방법이 전문화되었다는 점이 다릅니다. 즉, 눈에는 눈 전략을 가진 숙주로부터 착취하기 위해 숙주를 속이는 쪽으로 발달한 것입니다. 하지만 그런만큼 기생충들은 자력생존은 불가능하죠. 지나치게 번식해서 숙주의 수가 줄어든다면 기생충들 역시 위기에 빠질 수밖에 없습니다.

5. 극복기(Era of Overcome)
숙주가 마침내 기생충을 찾는 방법을 알아내고 기생충에게 눈에는 눈 전략을 시전할 수 있게 됩니다. 즉 기생충을 상대로 승리할 수 있는 것이죠. 하지만 기생충은 사라지지 않습니다.

6. 기생충들은 숙주를 피하는 새로운 방법을 찾아내어 되돌아와 4번부터 되풀이됩니다.

이를테면, 숙주가 완벽하게 기생충을 찾는 방법을 찾아내어 기생충을 몰아냈다고 하더라도 기생충은 시간이 지나면 (거의 반드시) 되돌아옵니다. 왜냐하면 기생충을 찾는 방법 자체가 시간과 자원을 소모하는 과정이기 때문이죠.
기생충이 있는 상황에서는 시간과 자원을 소모하여 기생충을 검색해 없애는 숙주가 번식에 유리합니다. 그러나 기생충들이 추방된 상황에서는 더이상 기생충을 검색하는 행위는 시간과 자원을 소모할 뿐인 일이 되죠. 그때는 기생충 검색을 생략하는 숙주가 유리해져 번성하고 그에따라 기생충이 다시 돌아올 터전이 만들어지는 것입니다.

그러한 '기생충'들은 유전자의 세계에만 있는 것이 아닙니다. 현실사회에서도 사회를 좀먹는 기생충들이 존재하죠.
그때문에 원시사회에서조차 그런 기생충을 막기 위한 '사회 규범'이 존재합니다(진화론적으로 말하자면 그런 사회규범이 없는 사회는 이미 붕괴해 버렸다고 할 수 있습니다).
다만 그런 사회규범은 '약속을 어기면 도깨비가 나타나 약속할때 걸었던 손가락을 잘라먹어버린다', '거짓말을 하면 이가 모두 빠진다' 등등 미신적이고 주술적인 모습으로 전해내렸기에 현대인에게 폄하당하고 있을 뿐입니다.
하지만 아주 옛날 사람들에게 '약속을 어기면 상대방도 약속을 어기게 되고 결국에는 서로가 믿지 못하는 사회가 된다'는 설명보다 '약속을 어기면 도깨비가 나타나 약속할때 걸었던 손가락을 잘라먹어버린다'는 설명이 훨씬 이해되기 쉬웠겠죠. '서로가 거짓말을 하면 결국 다른 사람의 말을 믿지 못하게 되고 그것은 사회공동체의 불이익이 된다'는 설명보다 '거짓말을 하면 이가 모두 빠진다'는 설명이 훨씬 간단하면서도 쉽게 와닿는 설명일 것입니다.

불행하게도 일제시대 이후 급격한 근대화를 이루면서 과거의 많은 사회규범은 '미신'이라는 이유로 대부분 사라졌습니다. 한편 그것들을 대신할 새로운 사회규범이 만들어지지는 않은 상태입니다. 그 때문에 지금 우리사회가 어지러운 것이겠죠.

진화론 이야기 - 진화적 군비 경쟁

나무와 벌레들이 같이 살고 있는 조그만 숲이 있습니다. 여기서 벌레는 나무를 갉아먹습니다.
이 숲의 나무들은 벌레의 공격에 의해 두꺼운 껍질을 가진 나무가 진화적 우위를 갖습니다*.
마찬가지로 벌레들 역시 나무껍질에 의해 크고 단단한 턱을 가진 벌레가 진화적 우위를 갖습니다*.
그러므로 시간이 지날수록 그 숲의 나무들은 점점 두꺼운 껍질을, 그 숲의 벌레들은 점점 더 크고 단단한 턱을 갖게 됩니다.
그럼에도 불구하고 벌레가 나무를 먹는 상황은 변하지 않습니다. 예전에는 작은 턱으로 얇은 나무껍질을 뚫고 나무를 파먹었다면 지금은 큰 턱으로 두꺼운 나무껍질을 뚫고 나무를 파먹는다는 차이일 뿐입니다.
*위에서 '진화적 우위를 갖는다'는 말은, 두꺼운 껍질을 가진 나무/크고 단단한 턱을 가진 벌레들이 생존경쟁에 유리하게 되어 더 많은 번식기회를 갖고, 그로인해 두꺼운 껍질을 가진 나무/크고 단단한 턱을 가진 벌레들이 많아진다는 뜻입니다.

밑에 공진화 이야기가 있습니다만. 공진화에 의해 천적관계의 진화가 계속되는 현상을 진화적 군비 경쟁이라고 합니다. 사실 두꺼운 나무껍질이나 크고 단단한 턱은 그들이 번식하는데는 오히려 방해가 됩니다. 나무껍질이나 턱을 만들기 위해 자원을 쓰느라 번식에 들어가는 자원이 줄어들죠.
하지만 그렇다고 해서 어느 한쪽이 진화를 멈춘다면 그들은 전멸하게 될 것입니다. 마치 냉전시대 미소의 군비경쟁처럼 말입니다.

혹시 나무와 벌레들이 협정을 맺을 수도 있겠죠.
"우리가 아무리 두꺼운 껍질과 큰 턱을 만들어봐야 벌레가 나무를 파먹는 관계는 변하지 않는다. 그럴 바에는 우리가 최소한의 껍질과 턱을 만들고 나머지는 번식에 힘쏟자"
그렇게 되면 그들은 두꺼운 나무껍질과 큰 턱을 만들 자원을 번식에 쏟을 테니 더 많은 나무들과 벌레들이 사는 지상낙원이 될 것입니다.

가끔씩 나오는 양심적 병역거부자가 그리는 세상이 저런 세상일 것입니다. 너도 나도 총을 놓는다면 전쟁으로 죽을 사람이 없으니 인구도 늘어나겠죠. 탱크대신 자동차를, 화약대신 비료를 만들테니 생산성도 늘어나는 낙원이 될 것입니다.
그런데 저런 세상이 얼마나 오래갈 수 있을까요?

하지만 극히 일부의 벌레들이 다른 벌레들보다 약간 큰 턱을 가진다면 어떻게 될까요? 그들은 더 많은 나무를 갉아먹으며 진화적 우위를 차지할 것입니다. 결국 모든 벌레들이 조금 더 큰 턱을 가지게 되며 나무들은 생존을 위해 더 두꺼운 껍질을 가져야 할 것입니다.
반대로 극히 일부의 나무들이 조금 더 두꺼운 껍질을 가져도 마찬가지가 될 겁니다.
그렇게 해서 저 지상낙원은 다시 진화적 군비경쟁이 판치는 예전의 숲으로 되돌아갈 수밖에 없습니다.

역시 아래에 있는 죄수의 딜레마상황처럼 배신자가 더 큰 이익을 가지게 됩니다. 병역거부자들의 낙원 역시 마찬가지죠. 아무도 무력을 가지고 있지 않다면 약간의 무장만으로도 커다란 이익을 얻을 수 있습니다. 그런 유혹에 빠지지 않을 사람을 찾기가 더 힘들 걸요. 그리고 그렇게 되면 결국 모든 사람들이 다시 무장을 하는 군비경쟁의 상황으로 되돌아갈 것입니다.

그렇다면 군비경쟁의 상황으로 돌아가지 않고 전쟁없는 낙원을 만들 가능성은 없을까요?

첫째로 죄수의 딜레마에서 가장 우수한 전략, 받은대로 돌려주는 Tit-for-Tat 전략을 사용하는 것입니다. 그런데 받은만큼 돌려주기 위해서는 나도 무장을 하고 있어야겠군요. 실제로 냉전중에 긴장이 높아도 전면전이 일어나지 않은 이유가 이것입니다. 하지만 모두가 무장을 한다면 '병역거부자의 낙원'이 아니게 되겠죠.

둘째로 더 두꺼운 나무껍질, 더 큰 턱을 만들었을 때 얻을 수 있는 진화적 우위를 박탈하는 방법이 있습니다. 만약 두꺼운 나무껍질이나 큰 턱을 만드는 비용이 너무 커서 그것으로 얻을 수 있는 이익이 더 작다면(즉 죄수의 딜레마에서 배신했을때의 보상을 낮추면) 다른 노력 없이도 자연스럽게 낙원이 만들어질 수 있습니다.
그런데 아무도 무장을 안한 상태에서 약간의 무장을 한 사람들에게 손해를 줄 방법이 마땅치 않다는 점이 문제겠네요.

이래저래 병역거부자들이 원하는 낙원은 불가능한가 봅니다.

그런데, 병역거부자들의 낙원은 불가능하다 치고 위에서 예로 든 나무와 벌레들의 낙원은 정말로 불가능할까요?
만약 모든 벌레들이 지나치게 큰 턱을 가진 벌레와는 짝짓기를 하지 않는다면 어떨까요(내 자손이 큰 턱을 가지고 쉽게 번식할 수 있겠다는 이익을 포기하고 말입니다)?
마찬가지로 모든 나무들이 지나치게 두꺼운 껍질을 가진 나무와는 꽃가루를 교환하지 않는다면 어떨까요(마찬가지로 내 자손들이 두꺼운 껍질을 가지고 오래 살 수 있겠다는 이익을 포기하구요)?
만약 그렇게 한다면 큰 턱과 두꺼운 껍질을 가진 '배신자'들은, 자신은 이익일 수 있으나 자손을 만들지 못하기에 도태되어버리고 지상낙원이 유지될 수 있겠군요.
물론 이 경우에는 '내 이익을 포기하고서라도 이 지상낙원을 유지하자'는 공감대가 모든 벌레들, 그리고 모든 나무들에게 퍼져있어야겠지만 말입니다.

현실에서도 '민주주의를 유지하자'는 공감대가 전 국민들에게 퍼져 있고 전 국민들이 민주주의를 유지하기 위해 자신의 이익을 약간 포기할 수 있어야 민주주의를 유지할 수 있습니다. 투표를 하기 위해 몇시간 늦게 애인과 만난다거나 몇시간동안만 온라인게임에서의 레벨업을 멈춘다든가 하는 식으로 말입니다.

진화론 이야기 - 죄수의 딜레마(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)

시뮬레이션은 여기