보드게임 SET®의 확률 with AlgeoMath

보드게임 SET®

• SET(이하 세트) 게임의 목표는 12장의 카드 가운데 '세트'가 되는 3장의 카드를 찾는 것이다.
• 여기서는 실제 보드게임 세트에서 쓰이는 카드 그림 대신에 변형한 다른 그림을 사용했다.
  

  

  그림1. 변형한 세트 카드 그림의 예

• 모든 카드는 4가지 속성 분류마다 3가지 특성 중 하나씩을 골라 조합한 그림으로 결정된다.
  • 모양: 원, 세모, 네모.
  • 색깔: 파랑, 초록, 빨강.
  • 개수: 한 개, 두 개, 세 개.
  • 음영: 다 칠함, 줄무늬만 칠함, 둘레만 칠함.
• 예를 들어,
  • 그림1의 마지막 줄에 있는 첫 번째 카드에는 초록색으로 둘레만 칠한 원 모양이 한 개 그려져 있다.
  • 그림1의 마지막 줄에 있는 세 번째 카드에는 파란색으로 둘레만 칠한 네모 모양이 세 개 그려져 있다.
• '세트'는 네 속성별 분류의 특성이 모두 같거나 모두 다른 3장의 카드 묶음을 말한다.
  

  

  그림2. 세트가 되는 3장의 카드 묶음의 예

  • 예를 들어, 그림1의 카드 중에서 그림2와 같은 3장의 카드 묶음 2쌍은 세트가 된다.
    • 그림2의 첫 번째 묶음의 3장의 카드는 모양이 모두 같고, 색깔은 모두 다르고, 개수가 모두 같고, 음영은 모두 다르다.
    • 그림2의 두 번째 묶음의 3장의 카드는 모양, 색깔, 개수, 음영의 속성마다 특성이 모두 다르다.
  • 플레이어는 세트가 되는 3장의 카드를 찾아내 가져가고, 빈 곳에 3장의 카드를 추가한다.
    • 이를 거듭하여 더 이상 남는 카드가 없을 때까지 반복하여 게임을 끝낸다.
    • 게임이 끝났을 때, 가장 많은 카드를 가져간 플레이어가 승리한다.
  • 그런데 이 게임의 백미 또는 난감한 지점은 플레이어가 세트를 찾지 못할 때 발생한다.
    • 모든 플레이어가 세트를 찾지 못하면, 게임의 진행을 위해 플레이어들의 합의를 통해 12장의 카드에 3장의 카드를 추가하여 15장의 카드 중에서 세트를 찾을 수 있다.
    • 15장에서도 찾지 못하면 3장의 카드를 거듭하여 추가할 수도 있다.
    • 재밌는 점은 플레이어의 실력 부족이 아니라, 실제로 펼쳐진 카드들 중에 세트가 없을 수도 있다는 것이다.

설명서에 나온 '세트가 없을 확률'

보드게임 SET®의 한국어 설명서 3페이지

• 위 그림에서 녹색으로 밑줄 친 부분과 같이 보드게임 SET®의 한국어 설명서에 따르면, 12장의 카드 중에서 세트가 없을 확률은 1/33이고, 15장의 카드 중에서 세트가 없을 확률은 1/2500이다. 언뜻 생각해도 세트가 없을 경우의 수를 세기는 만만치 않을 듯한데, 정확한 값을 제시하는 한국어 설명서는 꽤나 미심쩍다.
  • 12장의 카드 중에서 세트가 없을 경우의 수만 고려해도 너무 복잡하다.
  • 우선 모든 경우의 수는 '12장으로 구성되는 서로 다른 카드판'의 수이다. 이는 전체 81장의 카드 중에서 12장의 카드를 선택하는 조합의 수 즉, \(_{81}C_{12}\)이다. 수로 표현하면 70,724,320,184,700인데 약 70조가지 경우가 있다는 뜻이다.
  • 그리고 세트가 없을 경우의 수는 약 70조가지의 모든 카드판 마다 세트가 있는지 없는지 확인해야 하는데, 12장의 카드 중에서 3장의 카드를 골라서 확인해야 하므로 \(_{12}C_{3}\) 즉, 220번 확인해야 한다.
  • 다시 말해 \(_{81}C_{12}\)가지의 모든 카드판마다 \(_{12}C_{3}\)번 확인을 해야 경우의 수를 셀 수 있는데, 확인만 \(_{81}C_{12}\times_{12}C_{3}\)번이다. 수로 표현하면 15,559,350,440,634,000번인데 약 1경 5,559조번 확인해야 한다.
• 그래서 원문 영어 설명서를 찾아봤다.

보드게임 SET®의 영어 설명서 2페이지

• 위 그림에서 녹색으로 밑줄 친 부분과 같이 보드게임 SET®의 영어 설명서에 따르면, 12장의 카드 중에서 세트가 등장하는 오즈(Odds)는 대략(~) 33:1이고, 15장의 카드 중에서 세트가 오즈는 대략(~) 2500:1이다.
  • 한국어 설명서에서는 오즈(Odds)를 확률로 번역했지만, 오즈와 확률은 다르다.
  • 예를 들어, 주사위를 던져서 6이 나올 오즈는 1:5이다. 6이 안나올 오즈는 5:1이다.
    • 확률로 말하면지만, 주사위를 던져서 6이 나올 확률은 1/6이고, 안나올 확률을 5/6이다.
• 영어 설명서의 오즈를 확률로 말하면, 12장의 카드 중에서 세트가 등장할 확률이 대략 33/34이라는 뜻이다.
• 다시 말해, 12장의 카드 중에서 세트가 없을 확률은 대략 1/34 약 0.0294이라는 것이다.
• 그러나 여전히 수학적 확률을 구하는 방법은 알 수 없으므로, 통계적 확률을 알지오매스 블록코딩으로 알아본다.

12장의 카드 중에서 세트가 없을 확률 모의실험

원본 열기

설명

• 세트 게임의 첫 번째 차례 다시 말해, 모든 카드 중에서 12장의 카드를 골라 놓은 상태에서 세트가 없는 경우를 센다.

알고리즘

1. '실험 횟수' 변수를 사용자가 원하는 만큼 정한다.
2. '회차' 변수를 0으로 정한다.
3. '세트가 없는 경우의 수' 변수를 0으로 정한다.
4. 4가지 속성에 대한 리스트 4개 만든다.
   • 개수 속성 리스트에는 '1'을 27개, '2'를 27개, '3'을 27개 넣는다.
   • 색깔 속성 리스트에는 '청'을 9개, '녹'을 9개, '적'을 9개 넣기를 3회 반복한다.
   • 음영 속성 리스트에는 '백'을 3개, '회'를 3개, '흑'을 3개 넣기를 9회 반복한다.^[각주:1]
   • 모양 속성 리스트에는 '원'을 1개, '세모'를 1개, '네모'를 1개 넣기를 27회 반복한다.
5. 1번 부터 81번의 리스트 항목 번호 중에서 12개의 번호를 선택한다.
6. 무작위로 선택한 12개의 번호 중에서 3개의 번호를 빠짐없이 골라서 세트가 되는지 확인한다. 총\(_{12}C_{3}\) 즉, 220번 확인해야 한다.
7. 확인한 220번 모두 세트가 아니면, '세트가 없는 경우의 수' 변수에 1을 더한다.
8. '회차' 변수에 1을 더한다. '회차'가 '실험 회수' 보다 작으면 3번부터 다시 반복하고, 아니면 종료한다.

결과

• 1,000회의 실험에서 세트가 없는 경우는 39회였다.
• 추가로 9,000회를 더 실험하여 총 10,000회의 실험에서 세트가 없는 경우는 328회였다.
• 다시 말해, 12장의 카드 중에 세트가 없을 확률은 대략 0.0328이다.
• 영문 설명서의 확률 근사치인 0.0294와는 멀다고 할 수는 없지만, 가깝다고 할 수도 없다.
• 특히, 각각의 실험은 모든 카드 중에서 12장의 카드를 임의로 선택하여 진행되므로 세트 게임이 진행됨에 따라 확률이 어떻게 달라지는지는 알 수 없다.

구글링 결과

세트 설명서에 제시된 확률이 잘못된 것임을 더 알아보기 위해 구글링을 했다. 찾아보니 세트 설명서를 의심했던 여러 사람들의 훌륭한 실험과 결과가 담긴 좋은 글들을 찾았다.

Peter Norvig의 블로그

• 구글의 연구책임자 Peter Norvig은 100,000번의 게임의 첫 차례에서 3,299번 세트가 없었다고 밝힌다.
• 그의 실험에 따르면 확률은 대략 0.03299이다.
• 더 나아가 그는 게임이 진행됨에 따라 12장의 카드 중에 세트가 없을 평균적인 확률은 첫 차례에서 세트가 없을 확률에 대략 2배가 됨을 확인했다고 밝혔다.

Henrik Warne의 블로그

• 소프트웨어 개발자 Henrik Warne은 Peter Norvig의 블로그 포스트 내용을 기반으로 자신이 직접 설계한 프로그램을 통해 세트 게임이 진행됨에 따른 확률의 변화를 그래프로 정리함은 물론이고 상세하게 설명했다.

Mathematics StackExchange의 질의응답

• StackExchange는 네이버 지식인과 비슷한 서비스인데 전세계의 다양한 분야에서 활동하는 전문가들이 모여서 질의응답을 나눈다.
• 구글링 중에 우연히 다음과 같은 질문을 찾았다.
  "카드 게임 세트에서 세트가 n장의 카드로 존재할 확률은 얼마인가요?"
• 이 질문 글에서 채택된 한 답변을 보고 정말 놀랐다.
• 81장의 카드 중에서 n장의 카드를 무작위로 뽑았을 때 세트가 없을 경우의 수를 밝혔기 때문이다.
  • n=1부터 n=21까지의 경우의 수만 밝혔는데, n=21일 때 세트가 없을 경우의 수는 0이 되기 때문이다.
  • 다시 말해 카드가 21장 이상인 경우에는 항상 세트가 존재한다는 뜻이다.
  • 특히 응답자는 "2001년에 도널드 커누스(Donald Knuth)에 의해 이러한 경우의 수를 계산하는 프로그램이 작성되었다"고 전했다.
• n=12 즉, 12장의 카드 중에 세트가 없는 경우는 2,284,535,476,080가지 다시 말해 약 2조 가지 경우이다.
• 전체 \( _{81}C_{12} \) 약 1경 5,559조 가지 중에 약 2조 가지 경우에 세트가 없다는 뜻이다. 확률로는 약 0.0323이다.
• 불가능에 가깝게 느껴진 경우의 수를 세는 방법을 조금이라도 이해하고 싶었는데, 다행히 또 다른 답변에서 다음 링크를 찾았다.

미국 수학회 특집 칼럼 - Game. SET. Line.

• David Austin은 칼럼에서 그 방법을 설명한다.
• 우선 세트 카드를 각 좌표가 0, 1, 2인 4자리의 순서쌍으로 바꿔 카드를 4차원 유한체 \(\mathbb{F}_3^4\)의 점으로 본다.
  • (모양 번호, 색깔 번호, 개수 번호, 음영 번호)과 같이 바꿔 (0,0,0,0)부터 (2,2,2,2)까지 전체 3⁴ 즉, 81장의 카드가 순서쌍과 다름없다.
• 3장의 카드가 세트이기 위한 필요충분조건은 세 카드의 순서쌍의 합이 (0,0,0,0)이 되는 것이다.
  • 순서쌍의 합의 예 : (0,1,2,1) + (1,2,0,2) = (1,0,2,0)
    • 두 번째 좌표끼리의 합은 1+2=3 이지만, 3은 좌표가 될 수 없으므로 같은 좌표의 수끼리 더한 다음 3으로 나눈 나머지를 좌표로 삼는 것이다.
  • 세트가 되기 위한 필요충분조건은 각 좌표의 수가 모두 같거나 모두 다른 것이다.
    • 세 카드는 세 좌표에 해당하고,
    • 세 좌표의 수가 모두 같은 경우의 합은 항상 3의 배수이므로 3으로 나누면 0이 남고,
    • 세 좌표의 수가 모두 다른 경우이 합은 0, 1, 2의 합 즉, 3이 되어 3으로 나누면 0 남는다.
• 한편, 4차원 공간 \(\mathbb{F}_3^4\)의 서로 다른 3개의 점이 한 직선 위에 있기 위한 필요충분조건은 3개의 점의 순서쌍의 합이 (0,0,0,0) 즉 원점이 되는 것이다.
  • '4차원 공간의 서로 다른 3개의 점 \(c_1\), \(c_2\), \(c_3\)이 한 직선 위에 있다'는 것은
  • '벡터 \(c_1-c_2\)와 벡터 \(c_2-c_3\)이 한 직선 위에 있다'와 같은 뜻이고,
  • 이는 '\(c_1-c_2=\lambda\left(c_2-c_3\right)\)을 만족하는 어떤 \(\mathbb{F}_3^4\)의 원소 \(\lambda\)가 있다'는 뜻이다.
  • \(\lambda=0\)이면 \(c_1=c_2\)가 되어 서로 다른 세 점이라는 점에 모순되고,
  • \(\lambda=2\)이면 \(c_1-c_2=2c_2-2c_3\)이므로 \(c_1=3c_2-2c_3\)이고, 3은 0이므로 \(c_1=-2c_3\)이 되고 \(c_1+3c_3=c_3\) 즉 \(c_1=c_3\)이 되어 또 같은 이유로 모순된다.
  • 그러므로 \(\lambda=1\) 즉 \(c_1-c_2=c_2-c_3\)이므로 \(c_1-2c_2+c_3=0\)이 되어 \(c_1+c_2+c_3=3c_2\) 즉 \(c_1+c_2+c_3=0\)이다.
• 설명은 더 나아가 도널드 커누스의 프로그램까지 이어진다.

1. 백은 둘레만 칠한 것, 회는 줄무늬만 칠한 것, 흑은 다 칠한 것을 나타낸다. [본문으로]