마피아(게임)/전략

1. 개요2. 모든 플레이어가 이성적일 때 최선의 전략

2.1. 시민과 마피아만 있는 게임2.2. 의사가 없는 게임의 경우2.3. 시민, 마피아, 경찰, 의사가 있는 게임

[clearfix]

1. 개요

마피아 게임 역시 포커나 고스톱과 같이 적절한 전략을 통해 승리 확률을 높일 수 있다. 다만 틱택토나 특정 규칙을 가진 고누와 달리 2인 완전정보게임이 아니라서 무조건 승리할 수 있는 필승전략이 존재하는지는 알 수 없다.

아래의 최선 전략은 모든 플레이어가 이성적인 행동만 할 때를 고려한 것으로 실제 현실에선 재미를 위해 어그로를 끌 때가 많이 있으므로 바로 적용하긴 힘들 수 있다.

2. 모든 플레이어가 이성적일 때 최선의 전략

모든 전략은 "모두가 이 규칙을 지킨다"가 성립될때의 기준입니다.

마피아, 의사, 경찰, 시민만 존재하는 게임의 규칙입니다.

프린스턴 대학교의 Mark Braverman et al (Ann. Appl. Probab., 2008)이 수학적으로 이를 분석하였는데, 이 논문에서 말하는 최선의 전략은 다음과 같다.

2.1. 시민과 마피아만 있는 게임

시민의 전략
* 낮: 랜덤하게 아무나 방출한다.

그러나 후반부에 증거 없이 아무나 방출하면 오히려 불리해질수 있다

마피아의 전략
* 낮:
* (시민 수 > 마피아 수인 경우): 시민의 전략을 따라한다.
* (시민 수 <= 마피아 수인 경우): 시민 중 랜덤하게 한 명을 골라 죽인다.
* 밤: 랜덤하게 시민 중 아무나 죽인다.

이렇게 하면 시민의 입장에선 마피아나 시민이나 똑같이 행동하므로 시민과 마피아를 구별할 수가 없다. 결국 시민들이 할 수 있는 건 그냥 아무나 방출하는 것. 마피아의 입장에선 시민과 조금이라도 다른 행동을 했다간 바로 마피아인 것이 들통이 나므로 (이성적인 시민이라면 튀는 행동을 해서 마피아로 의심살 리가 없으므로) 시민과 똑같은 전략을 취할 수밖에 없다. 따라서 위 전략은 최선의 전략이다.[1]

적절한 마피아 수

모든 플레이어가 위 룰을 지킨다는 가정 하에
시민 승률과 마피아 승률이 비등하게 되는 마피아 수를 대략적[2] 으로 찾을 수 있다. 결론적으로 말하자면 마피아 수를 대략 \sqrt{플레이어 수}(소수점은 내림)으로 두면 게임이 비등해진다. 예를 들어, 8명이 마피아 게임을 한다면 적절한 마피아의 수는

\sqrt{8}

≒ 2.828427, 내림하면 2명이 된다. 실제로 시뮬레이션을 돌려 마피아 대 시민의 승률을 계산해보면 51.04% : 48.96%로 거의 비슷한 것을 확인할 수 있다 (Migdał, P, 2010). 같은 논리로 10명, 12명, 20명, 100명이서 마피아 게임을 할 때 적절한 마피아의 수는 각각 3, 4, 5, 10명이다.

2.2. 의사가 없는 게임의 경우

경찰이 존재할 경우 상황은 매우 달라진다. 다만 낮 시간동안 플레이어간의 암호통신 가능 여부에 따라 최선의 전략이 달라지는데, 현실에서 암호통신이 가능할리가 없기 때문에 암호통신이 불가능할 때의 최선의 전략을 설명하면 다음과 같다.

시민의 전략
* 낮:
* (경찰이 안 나왔을 때): 랜덤하게 아무나 죽인다.
* (경찰이 나왔을 때):
1. 먼저 나온 경찰(이하 첫경)의 수사 결과를 바로 요청하여 누가 시민인지 확인한다.[3]
1. 만약 첫경이 시민이라고 한 사람 중에서 자기가 경찰(이하 맞경)이라 주장하는 사람이 나오면 첫경을 죽이고, 그게 아니면 맞경을 죽인다.
1. 확인된 경찰의 수사 결과에 따라 마피아로 의심되는 사람들[4]을 골라 랜덤하게 죽인다.

마피아의 전략
* 낮: 시민의 전략을 따라한다.
1. 경찰을 시민이라고 주장할 확률을 피할 자신이 있는 마피아는 경찰보다 먼저 자신이 경찰이라고 주장하여야 한다. (시민과 경찰의 전략을 보면 알겠지만 맞경하는 순간 마피아는 무조건 죽는다.) 성공한다면 굉장히 유리해질 수 있으나 운이 좋아야 한다.
* 밤: 랜덤하게 시민 중 아무나 죽이되 경찰이 나왔으면 경찰을 먼저 죽인다.

경찰의 전략
* 낮: 현재 살아있는 사람 중 수사 결과 시민으로 밝혀진 사람 수가 과반이면 경찰임을 공개하고[5] 아니면 계속 수사를 한다.
* 밤: 계속 수사를 한다.

위 전략 하에 경찰이 성공적으로 수사를 완료하면 증명된 시민 수가 아닌 사람보다 많기 때문에 확정적으로 시민이 승리하게 된다. 다만, 수사를 완료하기 전에 경찰이 죽을 확률도 꽤 높은 편[6]이므로, 시민팀이 무적이라는 의미는 아니다.

적절한 마피아 수

경찰이 존재할 경우 적절한 마피아 수는 점근적인 관점에서

N

에 비례한다. 점근 이론이 정확히 몇 명이 적절한 마피아 수인지는 알려주지 않기 때문에[7] 경험적으로 볼 때 전체 플레이어 수 중에서 20~30%를 마피아로 정하는 경우가 많다.

2.3. 시민, 마피아, 경찰, 의사가 있는 게임

경찰과 의사가 존재할 경우 소수인원이면 소수인원 일수록 시민팀이 유리해진다. 암호통신 불가. 경찰 조사결과 공표되지 않음.

시민의 전략
* 낮:
* (경찰이 안 나왔을 때): 랜덤하게 아무나 죽인다.
* (경찰이 나왔을 때):
1. 경찰이 한 명이라면 경찰이 밤마다 한명을 조사하고 의사는 경찰만 살리면 의사가 죽을 때까지 마피아는 이길 수 없다. 사망자의 직업을 알리는 방식이 아닌 경우 의사를 죽였는지 알 수 없어 쉽게 경찰을 죽일 수 없기 때문이다.
1. 만약에 경찰이 두명이라면 의사는 경찰 제외 시민들 아무나(기왕이면 자기 자신을) 살리라고 하고 둘다 죽인다. 직업 공개가 늦은 경찰을 우선으로 죽이나, 하루나 이틀 직업 공개가 늦은 경찰이 '늦은' 경찰이다.(똑같은 날에 직업 공개는 치지 않는다.)

마피아의 전략
* 낮: 시민의 전략을 따라한다. 경찰로 위장하는 방법도 있다.
* 밤: 랜덤하게 시민 중 아무나 죽이되 경찰이 나왔으면 경찰을 먼저 죽인다. 단, 경찰만 나왔을 경우 의사가 경찰을 살릴 것이기 때문에 경찰을 빼고 죽일 것. 의사가 나왔고 경찰도 나왔으면 둘 중 찍어야 한다.

경찰의 전략
* 낮: 의사가 있기 때문에 자신의 직업을 빨리 밝히고 조사 결과가 무엇이 되었던 시민들에게 줘야 한다. 그리고 의사에게 자신을 살리라고 한다.
* 밤: 계속 수사를 한다.

의사의 전략
* 낮: 자신의 정체를 밝히지 않는다. 시민의 전략을 쓴다.
* 밤: 자신을 살린다.
* (경찰이 나왔을 때):
1. 경찰을 살린다. 경찰이 두명일 경우 자신을 살린다,
* (경찰이 나오지 않을 때):
1. 자신을 살린다.

[1] 결국 내시균형이다.[2] 점근적인 관점에서[3] 만약 수사 결과에 모순이 있다면 경찰을 죽인다. 예를 들어 수사를 터무니 없이 많이 했다든가 등[4] 수사 결과 마피아임이 확실한 사람 먼저, 그 다음 마피아인지 애매한 사람들 순으로 죽인다.[5] 수사 결과를 공개했다면 그 뒤엔 죽든 말든 상관없다.[6] 대표적으로, 경찰이 퍼블인 경우를 생각할 수 있다. 의외로 자주 발생하는 상황.[7] finite sample아 아니라 large sample의 관점.