게임이론 - NoSmok

GameTheory.

Decision Making(의사결정방법)의 한 분야.
의사결정론의 기본은 주체과 세계가 있고, 주체는 세계에 대하여 최대의 이익을 얻을 수 있는 행동을 선택하게 되는 상황이다. 여기서 세계는 주어진 입력에 대해 특정한 반응을 하는, 말하자면 정적인 함수상자와 같다. 그러나 게임이론에서의 세계에는 주체와 같이 이익을 추구하고 전략을 짜는 다른 주체들이 존재한다. 그러므로 게임이론에서의 의사결정은 한층 복잡해지며, '상대도 나와 같은 전략'을 구사한다는 것을 염두에 두어야 한다. 증권시장, 전쟁, 무역행위 등은 같은 목적을 갖는 다수의 주체가 참여하므로 게임이론의 대상이 된다. 헝가리의 수학자 폰 노이만이 개척하였으며, 최근에 '뷰티플 마인드'로 유명한 존 내쉬가 non-zerosum 상태에서의 균형점 정리,로 노벨경제학상을 수상하였다.

게임이론은 합리적으로 행동한다고 가정된 -이상적 상황이지만- 게임 당사자들간의 상호관계에 대한 연구이다. 폰 노이만은 그것이 미래의 엄밀 경제학의 핵심이 되기를 희망했다. 게임이론하의 분석이 가능하기 위해서는 게임당사자들의 모든 동기가 미리 규정되어 있어야 한다. 그러한 의미에서 게임이론은 인간의 갈등양식에 대한 고도의 인공적인 모델이다. 그러나 폰 노이만은 대분분의 경우 동기는 중요하지 않다는 것을 깨달았다. 삼목(三目) 게임(tic-tac-toe), 바둑, 장기 그리고 포커에서 유일한 목표는 승리하는 것이다. 게임 당사자가 이기고자 하는 것으로 충분하며 그외의 동기를 규정할 필요가 없다.

3목 게임(tic-tac-toe)을 몇번 실행해 보면 더 이상 게임을 계속해야 할 의미가 없다는 것을 깨닫게 될것이다. 만일 두 게임당사자가 현명하다면 그 게임은 항상 무승부로 종결될 것이기 때문이다. 승패는 두 당사지중 한쪽 또는 둘다가 전략적 오류를 범할 때만 생긴다. 폰 노이만은 서양장기와 같은 그러한 게임도 똑같은 방식으로 무의미하다는 것을 증명할수 있었다.

그렇다고 폰 노이만이 장기의 "올바른" 전략을 규정해 주었다는 것은 아니다. 그러기위해서는 게임의 모든 단계에서 가능한 모든 수에 대한 대응수를 규정해 주어야 한다. 수와 대응수의 선택지는 기하급수적으로 증대해 곧 처리 불가능하게 된다. 그러나 그와 그의 동료 모겐슈테른(O.Morgenstern)은 한 쪽이 이기면 다른 쪽은 반드시 패하게 되어있고(어떠한 상호협조도 배제된 "제로-섬"게임), 연관된 모든 정보가 두 당사자들에게 모두 알려져 있는(한 쪽이 다른 쪽의 패를 볼수 없는 카드게임과는 반대되는 "완전 정보"의 게임) 형식의 모든 1 대 1 게임에서는 한쪽 또는 두 당사자를 위한 불패의 전략이 꼭 존재한다는 것을 보여 주었다.

불패의 전략은 승리를 보증해주는 것은 아니다. 두 당사자 모두 불패의 전략을 가질 경우 즉 두 당사자 모두 합리적 전략을 선택할 경우 -3목 경기 처럼- 반드시 무승부로 끝난다. 물론 한 당사자만이 불패의 전략을 가진다면 그는 항상 이길것이다. 바둑에 있어서 두 당사자간의 유일한 비대칭성은 누가 첫수를 두느냐 하는 것이다.흑돌을 쥔 사람이 첫수를 먼저 둔다고 하자. 폰 노이만의 게임이론은 다음것 중의 하나를 예측한다. 완전히 합리적인 게임에서는 먼저 둔 흑돌을 쥔자가 승리하거나 또는 무승부로 끝난다. 반면 뒤에 둔 백돌을 쥔자는 패하거나 무승부로 끝난다. 결과적으로 첫수를 둔 흑돌이 유리하다. 어떤 사람도 그 사례가 어떠한 것인지 확실히 알수는 없다.

현대적 게임이론의 역사는 대략 반 세기 전으로 거슬러 올라간다. 헝가리 출신의 유태인 천재 이론물리학자 폰 노이만(John Von Neumann)과 오스트리아 출신의 경제학자 모르겐슈테른(Oskar Morgenstern)이 1944년 출간한 '게임의 이론과 경제적 형태'(Theory of Games and Economic Behavior)에서 찾아 볼 수있다. 사실 이 저작이 출판되기 훨씬 전에 폰 노이만은 게임의 정의와 해의 개념을 수학적으로 정립했다는 신빙성있는 근거가 있다. 이 책에는 경제학의 많은 분야를 게임이론으로 접근하였으며, 전략적 게임과 확장형 게임으로 분류하여 표현하였고, MINIMAX라는 개념을 정의하였으며, 모든 2인형 제로섬 게임에서 MINIMAX의 해가 존재함을 증명하는 증의 내용이 수록되어 있다.또한 2인 게임에서 출발하여 여러 명이 하는 게임을 체계적으로 확장시켜 분석하였다. 그리고 이 책은 기대효용이론(expected utility theory)을 분석한 책으로도 잘 알려져 있다.

게임이론이 응용된 대표적인 예가 3인 결투이다. A, B, C 세사람이 결투를 하게되었다. 세사람이 모두 총을 한자루씩 들고 세사람 중 한사람만 살아남을 때까지 돌아가며 총을 쏘기로 하였다. 그런데 C는 총을 매우 잘쏘아 명중률이 100%였다. B는 C보다는 못쏘지만 그래도 2/3의 명중률을 갖고 있었다. A는 세사람 중에 총을 제일 못쏜다. 그의 명중률은 1/3이었다.

공정한 결투를 위해 명중률이 낮은 사람부터 먼저 한발씩 쏘기로 하였다. 먼저 A가 쏘고, 다음으로 B가 쏘고 마지막으로 C가쏘기로 하였다. 단 한사람 만이 살아남을 때까지 이런 순서로 계속 돌아가며 쏘기로 한 것이다.

그렇다면 제일 먼저 쏘기로 한 A는 과연 어떤 전술로써 이 결투에 임해야 한는가? 명중률이 제일 낮은 그는 누구를 먼저 쏘아야 하는가?

1)A가 B를 쏘아 명중시킨다면 그는 최악의 선택을 한 것이다. 다음 쏘게될 C는 명중률 100%를 자랑하며 A를 겨누게 될 것이기 때문이다.

2)A가 C를 쏘아 명중시킨다면 어떻게 될까? 그는 2/3의 명중률을 가진 B의 총구를 맞이하게 될 것이다.

3)명중률이 제일 낮은 A로서 최선의 선택은 누구도 명중시키지 않는 것이다. 확실하게 명중시키지 않으려면 허공에 대고 쏘면된다. 이렇게 했을 때 결과를 따져보자. 다음 차례인 B는 C를 쏘아야 한다. 그렇지 않고 A를 쏘아 명중시킨다면 그 역시 100% 명중률을 가진 C의 총구를 맞이하게 되기 때문이다. B가 C를 쏘아 명중시켰다면 다음은 A차례이다. 그는 이제 명중률은 낮지만 그가 쏘는 위치에 있게 된다. B가 C를 쏘았지만 맞추지 못할 경우에 C의 차례이다. 그에게는 A보다 B가 더 위험한 존재이기 때문에 B를 쏘게 된다. C는 100% 명중률이기 때문에 B는 죽은 목숨이다. 이제 다시 A에게 C를 쏠 기회가 주어진다.

A가 허공에 쏜다면 그는 어떤 경우라도 그에게는 총구를 맞이하는 것이 아닌 총구를 겨눌 위치에 서기 때문에 최선의 선택을 한 것이다.

위의 예에서 B와 C 모두 자신의 상황에 최선의 선택을 할 것을 가정하고 A의 전술을 세웠다. B 또는 C가 어리석은 선택을 한다면 이 전술은 통하지 않게된다.

게임이론은 또 하나의 대표적인 예 - 죄수의 딜레마

A와 B의 죄수가 있다.

1. 둘 다 자백했을 때에는 각각 5년형을 받게 된다.
2. 한 쪽만 자백을 했을 때에는 자백한 쪽은 바로 석방되고 자백을 하지 않은 쪽은 8년형을 받게 된다.
3. 둘다 자백하지 않았을 때는 각각 1년형을 받게 된다.

선택 사항은 둘뿐이다 1. 자백한다 2. 자백하지 않는다. 어느 쪽이 정답인가? 정답은 자백한다이다. 상대가 자백을 했을 시, 자신도 자백을 했다면 5년형이지만 자백을 하지 않으면 8년형을 받게 된다. 상대가 자백을 하지 않았을 시에도 자신이 자백을 했다면 바로 풀려나게 되고 자백을 하지 않았다면 1년형을 받게 된다. --RedPain see also 이타적유전자

첫 돌은 흑이 놓습니다. 그리고 덤도 있고요.
먼저 두는 쪽이 승리하거나 무승부로 끝날 것을 어떻게 알 수 있나요? 후수필승인 게임들이 존재하는데...

먼저 두는게 중요한게 아니라, 완전 정보 게임에서는 한쪽 또는 두 당사자를 위한 불패의 전략이 꼭 존재한다는 것이 게임이론의 내용입니다.그러니 후수 필승인 게임이라면 게임 당사자가 후수를 선택하면 이기거나 비기거나 할수 있겠지요. 그리고 후수를 선택하는 것이 불패의 전략이 되겠지요. --안지성

그것은 알고 있습니다.

"바둑은 먼저 둔 쪽이 유리하다"고 단정적으로 쓰셔서 드린 질문이었습니다.

먼저두는 쪽이 유리하기 때문에 덤을 주는 것이죠

--안지성

물론 그것도 알고 있습니다.

그러나 그것은 경험상 그런 것뿐이잖습니까? 안지성 님께서 쓰신 글에는 마치 먼저 두는 쪽의 유리함이 증명이라도 된 것처럼 적혀 있어서 질문을 드렸던 것입니다. 혹시 압니까? 바둑의 신은 후수를 택할지.

먼저 두는 쪽이 유리한 것은 증명할 수 있습니다. 대부분의 바둑 규칙에서는 통과가 가능하니까요. 증명) 나중 두는 쪽이 유리하다고 가정하자. 그러면 먼저 두는 사람은 차례를 넘긴다. 그렇다면 가정에 의해 먼저 두는 쪽이 유리해진다. 이것은 불가능하다. 귀류법에 의해 증명 끝. -- 서상현

물론 덤이 없을 때의 이야기입니다.
이 증명의 맹점은 나중에 두는 쪽 또한 차례를 넘길 수 있다는 점입니다.

결국 바둑의 경우 (통과가 없을 때) 어느 쪽이 유리한지 알 수 없으므로 "먼저 두는 쪽이 당연히 유리하다"는 식의 서술에는 동의할 수 없습니다.

불패의 전략은 승리를 보증해주는 것은 아니다. 두 당사자 모두 불패의 전략을 가질 경우 즉 두 당사자 모두 합리적 전략을 선택할 경우 -3목 경기 처럼- 반드시 무승부로 끝난다.라는 말이 있는데요. --아무개

게임이론에 흥미가 많아요. 비협력게임인 제로섬게임보다는 협력게임에 대해 잘 알고 싶어요:) 수학은 못하지만.. --네코지현

바둑에 있어서는 패라고 하는 재미난 룰이 있습니다. 그런데 이 패를 이용하면 두사람중 누구도 그 패를 포기할 수 없는 상황이 존재하고, 그 패의 완벽한 수순은 양 당사자가 항상 똑같이 두어야만 하고 한쪽이 그 패에서 죽고나면 다시 처음부터 그 패를 만들어 끝없이 반복되는 상황이 존재합니다. 결국 바둑의 불패의 전략은 바둑판 전체가 하나의 패를 만드는 과정을 순환할 거라고 생각됩니다. 아마 바둑의 신이 바둑을 둔다면 영원히 그 바둑을 끝내지 못할겁니다. --munikang

바둑에는 "동형 반복 금지 규칙"이 있어서 '끝없이 반복되는 상황'은 있을 수 없습니다. 가능한 경우는 패가 3개 이상, 장생, 순환패인데 이때 어느 쪽도 양보하지 않으면 무승부가 됩니다. --쓴귤

[edit]

빵먹기 게임 ¶

세개의 접시에 각각 세 개, 네 개, 다섯 개의 빵이 있다. 게임의 규칙은 이렇다. 두 사람이 게임을 한다. 첫번째 사람이 마음대로 접시를 하나 선택하고, 그 접시에 있는 빵을 원하는 갯수만큼 먹는다. 두번째 사람 역시 같은 규칙으로 빵을 먹는다. 이렇게 반복하여 마지막 빵을 먹는 사람이 진다. 이 경우 누가 이길까? 좀 더 일반화하여 M개의 접시가 입고 빵이 각 접시에 m1, m2, ..., mM 개 있을 때 누가 이기는지 일반적인 공식이 있는가?

네. 있습니다. 이 게임의 이름은 Nim이고, 게임의 전략은 이진법과 관련이 있습니다. --Puzzlist

아시는군요. 맞습니다. 게임의 전략은 이진법과 관련이 있습니다. --세벌

[edit]

바둑의 결과 예측 ¶

"만약 바둑의 모든 수를 DB화 시킨다면 상대가 어떤 수를 두던지 간에 내가 이기는 수를 둘수 있다. 만약 서로 그 DB를 가지고 있다면 첫수를 두는 순간 바둑의 결과는 결정될 것이다"라는 주장이 있습니다. 제가 궁굼한 것은 과연 그런 DB가 존재한다고 할때, 절대 승리의 해가 존재하는지 입니다. 저는 게임이론에 의거해 불패의 수(승리는 아닐지라도)는 존재한다고 생각합니다만. -- 안지성

이런 질문이 아마 인간대 컴퓨터 체스 경기 결과 다음에 나왔었던거 같은데, 현실적으로 그런 DB 구축이 불가능할 수준이고, 만일 가능하다고 하면, 바둑판을 몇줄 더 늘리면 해결된다는 얘기가 나왔던것 같습니다. 그리고, 바둑의 패를 이창호 수준으로 판단할 수 있어야 정규화 할 수 있을 것 같다는 생각이 들었습니다. -- dyaus

DB구축이 가능하다고 치고 바둑판을 몇줄 더 늘리면, 다시 그 DB를 구축할 수 있다고 봐야하지 않을까요. --kidfriend

코딩할 수 있고 없고의 문제가 아니겠죠.. 바둑판에서 볼 수 있는 모양의 총 가지수는 대략 361개의 격자에 3개의 다른 모양을 늘어놓는 것이거든요. 2개는 숫자가 같아야 하고, 나머지 한종류는 상관없구요. 그럼 그게 sum of (K comination K/2) for 1= k개로의 전이라고 생각하면, 그 경로에서 가능한 path의 수는 PI (K comination K/2) for 1=naya

경우가 너무 많다는 얘기신가요? 근데 제가 생각하기엔 지금의 바둑판도 '경우가 많아서 불가능하다'라는 문제가 있는건데 그걸 가능하다고 가정했다면 그 이상의 크기에도 가능하다고 봐야하는게 아닐까요...? 그러니까 저는 시간을 빼고 생각한다고 보면 되겠네요. 50년대에 지금의 컴퓨터의 연산속도를 상상하진 못했을거라 생각하거든요. --kidfriend

우선 TravelingSalesmanProblem 문제가 왜 난제라고들 하는지 생각해봅시다. --naya

간단히 답하면 일단 그런 DB는 구축할 수 없습니다. 현재 기술적 수준의 문제가 아니라 경우가 너무 많지요. 체스만해도 10^120가지 게임이 존재합니다. 우주 안에 있는 양성자의 갯수가 10^80개 정도 됩니다. 양성자 하나에 게임 하나를 저장한다고 해도 우주가 10^40개 필요합니다. --쓴귤

근데 바둑판의 격자는 천원을 중심으로 상하, 좌우, 대각선이 완벽하게 대칭됩니다. 상당한 경우의 수를 제할 수 있겠지요. 또한 단순히 경우의 수를 모두 입력해 DB를 구축하는 것이 아니라 특정한 수학적 공식을 찾아 패턴화 시킴으로써 DB의 용량을 줄이는 것도 가능하다는 생각도 듭니다. -- 코지모

게임 이론의 최대 문제는 확률로 모든 것을 해석하려고 한다는 것입니다. 일반적인 게임 디자인에서 가장 중요한 것은 의외성이구요. 바둑의 확률을 100% DB로 구축했다고 하더라도 (그것이 가장 합리적인 선택이라고 할 지라도) 실제로 바둑에서는 두기를 포기하지는 않지만 그 지역에는 손을 안대는 '손빼기'같은 기술도 있지요. 또 다른 예로 48장의 카드를 가지고 하는 포커가 확률을 예측하는 게임이기는 하지만 언제나 발생하는 의외성 때문에 도박의 여지가 있는 겁니다. 내가 K포카드를 가지고 있다고 하더라도 A포카드를 가질 확률이 있고 그 자체가 위협이 되게하는 블러핑도 있지요. 룰로써는 확률이 모든 것을 해결해줄 수 있겠지만, 실제로는 저 의외성과 게임 룰 이외의 것에 의해서 게임이 완성되는 것입니다. (쉽게 말해서, 게임에는 심지어 '주먹질을 할' 확률도 있지요, 혹은 이창호가 똥이 마려워서 돌을 던지고 화장실로 뛰어갈 지 누가 압니까!) -- Nairrti

[edit]

선거 전략 ¶

2002대통령선거에서, 노무현, 이회창, 정몽준의 지지 성향이 다음과 같이 나타났다고 하자.

	노무현	이회창	정몽준
적극적지지자 수	31	42	27
적극적반대자 수	21	60	19

이회창 - 좋아하는 사람도 많고 싫어하는 사람도 많다.
노무현 - 좋아하는 사람은 적지않고, 싫어하는 사람은 적지 않다.
정몽준 - 좋아하는 사람도 적고, 싫어하는 사람도 적다.

[edit]

이회창 당선 시나리오 ¶

모두가 대선에 출마하도록 공정하고 정정당당한 페어플레이가 이루어지도록 유도한다. 괜히 헛 음모만 안꾸미면 된다. 그렇게만 하면, 대한민국의 보통선거, 평등선거 원칙에 따라, 유권자 1명은 가장 지지하는 후보 1명에게만 투표할 수 있고, 이 경우에, 거의 절반의 적극적 지지를 얻고 있는 이회창이 가볍게 당선이 된다.

[edit]

정몽준 당선 시나리오 ¶

이회창과 공동전선을 형성하여, 노무현을 온갖 좌익, 무식, 무능의 원흉으로 중상모략, 후보사퇴하게 만든다. 두 사람의 적극적 지지율을 합치면, 전체 국민의 70%에 가까우므로, 충분한 여론 몰이를 기대할 수 있는 가능한 전략이다.

이렇게 되면, 노무현을 지지하는 31%는 꼴보기 싫은 후보의 반대편을 찍을 것이다. 이렇게 되면, 노무현의 지지율인 31%가 이회창과 정몽준에 대해 각각 21:60의 비율로 분배된다. 그렇게 되면 이회창은 7%, 정몽준은 무려 24%에 가까운 지지율을 더 얻게 되고, 이회창은 49%, 정몽준은 51%에 달하는 지지를 얻으므로 정몽준이 대통령에 당선된다.

[edit]

노무현 당선 시나리오 ¶

상당히 골치아픈 상황이 노무현이다. 어려운 방법을 사용해야 한다.

대한민국 선거법의 틀 안에서, 노무현이 당선을 원한다면, 정몽준과 후보 단일화를 시도해야 한다.

이렇게 할 경우, 노무현/정몽준만을 대상으로 한 단일화 설문조사 과정에서, 이회창을 지지하던 사람들은 "적극적반대"하는 후보의 상대편을 선택할 것이다. 이 비율은 노무현과 정몽준이 각각 21:19이다. 따라서, 이회창 지지자들의 효과를 감안하면, 노무현의 지지율은 50.95%, 정몽준의 지지율은 49.05%가 된다. 이렇게 되면 일단 노무현이 정몽준을 꺾고 최종 후보가 된다.

그렇게 하여 최종 후보가, 노무현/이회창 으로 압축되면, 정몽준을 찍지 못하는 적극적지지자들은 노무현과 이회창에게로 각각분배된다. 이들은 "적극적반대"하는 후보의 상대편을 선택하게 된다. 즉 정몽준을 지지하는 27%의 지지율은 노무현과 이회창에게 약 3:1로 분배된다. 따라서 노무현은 약 20%의 지지율을 더 얻게 되고, 이회창은 약 7%의 지지율을 더 얻게 된다. 이렇게 되면, 노무현은 총 51%의 지지율을 얻고, 이회창은 49%의 지지율을 얻어 박빙으로 노무현은 대통령에 당선된다.

마지막 노무현 당선 시나리오가 실제로 일어난 일로, 당시 노무현의 당에는 최소한의 산수를 약간 할 줄 아는 사람이 다른 곳과는 달리 있었다는 뜻일 지도 모르겠다.

카지노도 두손 든 MIT 수재들