이를테면 지금 같은 상황에서 어디를 찍어야 잘 찍엇다고 얀봇 츤봇에게 인식될 수 있는지에 대하여
난 항상 승률지향이거든. (속도에는 경쟁력이 없다고 생각해서.)
단도직입적으로 확률 계산 들어갈거임
보다시피 타일들에 영역을 지정해서 이름을 이쁘게 붙였어.
그리고 모든 경우의 수를 구할거야.
고등학교 수학시간때 배운 조합 알지? 그거 정도만 쓰일 듯.
일단 체크해야 할건
지뢰의 숫자 : 14개
숫자와 인접하지 않은 칸의 개수 : 25개
지뢰가(지뢰녀아님) 숫자와 인접한 칸에 들어가는 개수를 알아보자.
일단 경계가 둘로 나뉘어 있는데 왼쪽 부터 살펴볼까?
왼쪽부터 살펴보자.
우선, t2, t4에 지뢰가 있는 경우 인접한 영역에 지뢰가 동시에 채워지는 효과가 나서 지뢰 숫자가 하나 줄어드는 효과가 난다.
물론 비슷한 형태라도 그렇지 않은 경우도 있어서 뇌내 시뮬레이션 좀 돌려서 확신해야돼.
왼쪽의 경우의 수는 다음과 같아.
i). t2, t4에 지뢰가 동시에 있을 때
지뢰의 수는 3, t5에 지뢰가 들어가는데 왼쪽에 들어갈 수도 있고, 오른쪽에 들어갈 수도 있지? t5입장에선 경우의 수가 하나이지만 t2, t4 입장에선 두 경우 모두 지뢰가 있기 때문에 경우의 수는 2가 곱해져.
(t1, t2, t3, t4, t5, 총 경우의 수) = (0, 2, 0, 2, 1, 2)
앞으로 주구장창 하게 될 일이니 설명을 하자면
지뢰찾기 보드의 어떤 부분 A만을 떼서 해당 부분에 지뢰를 배치해봐.
그 과정에서 가능한 배치의 수가 총 경우의 수이고,
그 모든 배치의 수에서 특정 타일에 지뢰가 있는 배치들의 개수가 그 타일의 경우의 수라고 할 수 있어.
그러면 또 다른 부분인 B를 A랑 합쳐서 생각하고 싶다고 해보자. 그런데 A와 B는 서로 독립되어 있어.(상호작용하지 않아.)
이때 A에 속한 타일들의 경우의 수는 어떻게 될까? B에게도 총 경우의 수가 있겠지?
이 경우 A에 속한 타일들의 경우의 수는 B의 총 경우의 수 만큼 곱해지게 돼.
그룹이 3개가 되어도 마찬가지로 자신의 그룹을 제외한 나머지 두 그룹 각자의 총 경우의 수를 곱한 것이 새 경우의 수가 된다.
앞으로 수십번 하게 될 작업이라 설명해봤는데 천천히 이해하길바라
ii) t2에는 지뢰가 없고 t4에는 지뢰가 있음
지뢰의 수는 4
(t1, t2, t3, t4, t5, 총 경우의 수) = (8, 0, 2, 8, 4, 8)
iii) t2에 지뢰가 있고 t4에는 지뢰가 없음
지뢰의 수는 4
(t1, t2, t3, t4, t5, 총 경우의 수) = (0, 4, 1, 0, 4, 4)
vi) t2, t4모두 지뢰가 없음
t3에 지뢰가 2개 들어간다. 이때 다른 타일들에 곱해지는 숫자는 4C2로 6. t3자신은 3이야.
이렇게 표로 만들어봤어.
사용한 지뢰의 숫자별로 정리했다.
계산량을 줄이기 위해 조금 걸러보자. 우리는 가장 지뢰가 있을 확률이 낮은 칸을 조사해야 하니까.
t4는 t2보다 모든 행에서 더 같거나 크지? 얘는 빼버리자.
t5도 t1보다 더 크기만 하니까 얘도 뺄 수 있겠지.
편안하네.
이제 오른쪽으로 넘어가자. 여긴 보기보다 경우의 수가 적으니 그냥 찍어왔어.
지뢰가 4개 사용되는 경우와 5개 사용되는 경우가 있어.
2위의 3칸은 단지 3칸 중에 하나가 있을 뿐이니까 여기를 계산에 넣는 건 그저 전체 경우의 수를 3씩 곱해주는 결과밖에 안돼. 그러니 고려하지 않을거야.
역시 필요없는 칸을 빼자.(아래첨자 쓰기 너무 귀찮으니 앞으로는 ○번 이라고 부를거임)
10번, 9번은 각각 6번, 7번과 같으니 통합하고, 8번은 6번보다 크기만 하니 역시 빼버리자.
(나중에 보니 7, 9를 왜 포함시켰는지 모르겠네.. 그냥 넘어가줘)
이제 두 부분을 합칠거야.
물론 이렇게 늘여놓는다고 합쳐지진 않겠지.
지뢰의 숫자에 따라 차례대로 정렬할거야.
왼쪽 부분은 지뢰가 3~5이고, 오른쪽은 4~5이니 다뤄야 할 지뢰의 수는 7~10이 되겠네.
대충 이런 형태가 될거야.
각 행을 채우기 위해서 어떻게 표를 조합해야 할지 알겠지.
7 : 3+4
8 : 3+5, 4+4
9 : 4+5, 5+4
10 : 5+5
둘을 각각 A파트, B파트라고 하면
앞서 말했듯 A파트에 속하는 경우의 수는 B파트의 총 경우의 수로 곱하면 돼. 반대의 경우도 마찬가지고.
지금까지 구한 건 숫자와 인접한, 경계에서의 경우의 수일 뿐이야. 숫자와 인접하지 않은 내부의 경우의 수는 계산하지 않았지.
'경계', '내부'는 이런 개념으로 쓸거니까 기억해둬.
경계에 지뢰가 7개 있다고 했지? 지뢰는 총 14개가 있으니 내부에는 지뢰가 7개 들어가겠지. 8개인 경우는 6개, 9개인 경우는 5개. 이런 느낌으로.
내부의 타일 숫자는 위에서 이미 셌듯이 25개야. 이때 내부에 배치되는 지뢰의 경우의 수는 25C7이 될거야.
지뢰찾기 보드의 총 경우의 수는 (경계의 경우의 수) * (내부의 경우의 수)가 될거야. 이걸 표에 반영할거야.
'내부에서 찍기'는 항상 고려해야할 선택지야. 이걸 계산하는 방법은 어렵지 않아. 내부에서 특정 타일에 지뢰가 있었다면 나머지 n-1타일에 m-1개의 지뢰가 있겠지. 거기에 외부의 경우의 수를 곱하면 돼.
지뢰 숫자별로 따로 경우의 수를 구했으니 다 더해야 총합이 나오겠지.
확률까지 구했더니 결과가 나왔다.
6번이나 10번을 찍는게 가장 가능성이 높다는 걸 알 수 있어. 이때 19.27%의 확률로 죽을 가능성이 있네.
아무튼 살음
어떻게 이런 결과가 나왔을까? 우리는 마지막으로 도출한 표를 분석해볼 필요가 있다.
우선 경계의 경우의 수 이야기야. 경계에 있는 지뢰의 숫자에 따라서, 비록 4개가 전부이기는 하나 최솟값과 최댓값에서 가장 경우의 수가 적고, 중간값에서 가장 경우의 수가 많은 아치 느낌의 경향성을 보여주고 있어. 이해되지?
반면 내부의 경우의 수는 조합 특성상 숫자가 하나씩 늘어날 때마다 꾸준히 작아지거든. (이 작아지는 비율은 내부의 칸의 갯수, 지뢰의 숫자에 따라 달라짐)
이 둘을 곱한게 우리가 알고싶은 값이니 이것이 최대가 되는 값은 최솟값에 가까운 어딘가가 될거야.
이 표에서는 8에서 값이 가장 커지는 모습을 보여주고 있음. 7에 비해서 내부의 경우의 수는 4배 줄었으나 경계에서 8배가 늘어났기 때문이지.
다른 사례에서는 최솟값이 가장 큰 경우도 있고 그래.
간단히 살펴보면 25C5를 25C7로 나누면 0.11 정도가 되거든? 어떤 느낌인지 알 것 같지?
대충 이 표에서 맨 위의 2행 아래로는 신경 안써도 된다는 이야기임. (내부가 큰 경우의 이야기임..)
그런 느낌으로 접근하면 좋다.
그렇다면 경계에서 지뢰가 최소일 때 지뢰가 없는 경우 꽤 매력적인 선택지가 될거야.
최소보다 하나 많은 경우는 어떻게 될까.
위 경우에는 크게 두 부분으로 나뉘어져서 서로 곱했잖아? 실제 상황에서도 두 부분, 세 부분으로 나뉘는 경우가 많을거야.
이때 속해있지 않은 반대 파트의 총 경우의 수가 많은 경우를 조심해야해.
6번을 예로 들자면
지뢰수 7 : 0*2=0
지뢰수 8 : 0*12+1*2=2
이 된다.
2행까지 분석이 되려면 각 파트의 총 경우의 수, 내부의 경우의 수가 감소하는 비율 등은 고려를 할 정도가 되어야 함
사실 쉽지 않지. 하지만 직접 계산을 따라가는 과정에서 참고가 된다면 좋겠어.
마지막은 단순화된 케이스에 대한 이야기야.
A위치에 지뢰가 있다고 하면 B위치에 있을 때에 비해 지뢰의 숫자가 하나 작아져.
지뢰는 A혹은 B에 반드시 하나 있어야하지만 둘 다에 있을 수는 없어.
마지막으로, 해당 상황에서 A위치와 B위치의 경우의 수는 동일해.
이 상황을 표로 나타내면 어떨까?
이 경우 B를 찍는 것과 내부에서 찍는 것은 차이가 없어.
이때 A의 경우의 수가 B보다 크다고 하자.
이럴 땐 B의 경우의 수는 그대로인데 내부에서의 찍기 경우의 수는 증가했으니 확실히 B를 찍는 게 유리하다고 할 수 있겠네.
지뢰찾기 탐구는 이정도로 마치겠음
