마피아(게임)/전략
1. 개요
마피아 게임 역시 포커나 고스톱과 같이 적절한 전략을 통해 승리 확률을 높일 수 있다. 다만 틱택토나 특정 규칙을 가진 고누와 달리 2인 완전정보게임이 아니라서 무조건 승리할 수 있는 필승전략이 존재하는지는 알 수 없다.
아래의 최선 전략은 모든 플레이어가 이성적인 행동만 할 때를 고려한 것으로 실제 현실에선 재미를 위해 어그로를 끌 때가 많이 있으므로 바로 적용하긴 힘들 수 있다.
2. 모든 플레이어가 이성적일 때 최선의 전략
가장 기본적인 직업[1]만 존재하는 마피아 게임에 대해서는 모든 플레이어가 이성적이라는 가정 하에 최선의 전략을 찾을 수 있다.
프린스턴 대학의 Mark Braverman et al (Ann. Appl. Probab., 2008)이 수학적으로 이를 분석하였는데, 이 논문에서 말하는 최선의 전략은 다음과 같다.
2.1. 시민과 마피아만 있는 게임
'''시민의 전략'''
* 낮: 랜덤하게 아무나 죽인다.
이렇게 하면 시민의 입장에선 마피아나 시민이나 똑같이 행동하므로 시민과 마피아를 구별할 수가 없다. 결국 시민들이 할 수 있는 건 그냥 아무나 죽이는 것. 마피아의 입장에선 시민과 조금이라도 다른 행동을 했다간 바로 마피아인 것이 들통이 나므로 (이성적인 시민이라면 튀는 행동을 해서 마피아로 의심살 리가 없으므로) 시민과 똑같은 전략을 취할 수 밖에 없다. 따라서 위 전략은 최선의 전략이다.[2]'''마피아의 전략'''
* 낮:
* (시민 수 > 마피아 수인 경우): 시민의 전략을 따라한다.
* (시민 수 <= 마피아 수인 경우): 시민 중 랜덤하게 한 명을 골라 죽인다.
* 밤: 랜덤하게 시민 중 아무나 죽인다.
적절한 마피아 수
만약 모든 플레이어가 위 전략을 따른다고 하면 전체 플레이어 수가 $$N$$일 때 시민 승률과 마피아 승률이 비등하게 되는 마피아 수를 대략적[3] 으로 찾을 수 있다. 결론적으로 말하자면 마피아 수를 대략 $$\sqrt{N}$$으로 두면 게임이 비등해진다. 예를 들어, 8명이 마피아 게임을 한다면 적절한 마피아의 수는 $$\sqrt{8}$$, 내림하면 2명이 된다. 실제로 시뮬레이션을 돌려 마피아 대 시민의 승률을 계산해보면 51.04% : 48.96%로 거의 비슷한 것을 확인할 수 있다 (Migdał, P, 2010). 같은 논리로 10명, 12명, 20명, 100명이서 마피아 게임을 할 때 적절한 마피아의 수는 각각 3, 4, 5, 10명이다.2.2. 시민, 마피아, 그리고 경찰만 있는 게임
경찰이 존재할 경우 상황은 매우 달라진다. 다만 낮 시간동안 플레이어간의 암호통신 가능 여부에 따라 최선의 전략이 달라지는데, 현실에서 암호통신이 가능할리가 없기 때문에 암호통신이 불가능할 때의 최선의 전략을 설명하면 다음과 같다.
'''시민의 전략'''
* 낮:
* (경찰이 안 나왔을 때): 랜덤하게 아무나 죽인다.
* (경찰이 나왔을 때):
1. 먼저 나온 경찰(이하 첫경)의 수사 결과를 바로 요청하여 누가 시민인지 확인한다.[4]
1. 만약 첫경이 시민이라고 한 사람 중에서 자기가 경찰(이하 맞경)이라 주장하는 사람이 나오면 첫경을 죽이고, 그게 아니면 맞경을 죽인다.
1. 확인된 경찰의 수사 결과에 따라 마피아로 의심되는 사람들[5]
을 골라 랜덤하게 죽인다.
'''마피아의 전략'''
* 낮:
* (시민 수 > 마피아 수인 경우): 시민의 전략을 따라한다.[6]
* (시민 수 <= 마피아 수인 경우): 시민 중 랜덤하게 한 명을 골라 죽인다.
* 밤: 랜덤하게 시민 중 아무나 죽이되 경찰이 나왔으면 경찰을 먼저 죽인다.
위 전략 하에 경찰이 성공적으로 수사를 완료하면 증명된 시민 수가 아닌 사람보다 많기 때문에 확정적으로 시민이 승리하게 된다. 다만, 수사를 완료하기 전에 경찰이 죽을 확률도 꽤 높은 편[8]이므로, 시민팀이 무적이라는 의미는 아니다.'''경찰의 전략'''
* 낮: 현재 살아있는 사람 중 수사 결과 시민으로 밝혀진 사람 수가 과반이면 경찰임을 공개하고[7]
아니면 계속 수사를 한다.* 밤: 계속 수사를 한다.
적절한 마피아 수
경찰이 존재할 경우 적절한 마피아 수는 점근적인 관점에서 $$N$$에 비례한다. 점근 이론이 정확히 몇 명이 적절한 마피아 수인지는 알려주지 않기 때문에[9] 경험적으로 볼 때 전체 플레이어 수 중에서 20~30%를 마피아로 정하는 경우가 많다. [1] 마피아, 시민, 경찰[2] 결국 내쉬균형이다[3] 점근적인 관점에서[4] 만약 수사 결과에 모순이 있다면 경찰을 죽인다. 예를 들어 수사를 터무니 많이 했다던가 등[5] 수사 결과 마피아임이 확실한 사람 먼저, 그 다음 마피아인지 애매한 사람들 순으로 죽인다.[6] 이 때 마피아는 절대 맞경을 하지 않는다. 시민과 경찰의 전략을 보면 알겠지만 맞경하는 순간 마피아는 무조건 죽는다. 하지만 선경을 할 경우 잘하면 선동을 할 수 있는데 선경을 하는 것이 확률적으로 우월한 전략인지는 생각해볼 것.[7] 수사 결과를 공개했다면 그 뒤엔 죽던 말던 상관없다.[8] 대표적으로, 경찰이 퍼블인 경우를 생각할 수 있다. 의외로 자주 발생하는 상황.[9] finite sample아 아니라 large sample의 관점.