|
아마 누구나 어릴 적에 몇 번은 해본 게임일거다.
방법은 일단 상대는 모르는 4자리 숫자를 하나 정한다.(상대도 마찬가지)
게임참가자를 A,B라 할때
A는 B가 정한 숫자를 추측한다. B는 A가 추측한 숫자와 자신이 정한 숫자를 비교하여
결과를 A에게 알려준다. (A가 추측한 숫자가 B정한 숫자에 자리수가지 일치할 경우는
스트라익으로, 포함은 되지만 자리수가 맞지 않으면 볼로 표현한다. 예를 들어
1S 1B는 총 2개의 숫자가 B가 처음 정한 숫자열에 있는데 1개는 자리수까지 맞고, 1개는 자리수가 맞지 않은 상태임을 나타낸다.)
반대로 B가 A가 정한 숫자열를 추측하고 A는 결과를 알려준다.
위와 같은 질문을 번갈하 하면서 먼저 상대방의 숫자열을 추측하는 게임이다.
문제는 최선의 전략으로 4자리 숫자를 추측할 경우 평균 몇회만에 맞출 수 있느냐하는 것이다.
답: 5.22회
1. 위 결과는 프로그램으로 문제풀이를 1000회 실시한 평균 값이다.
(저는 이 알고리즘이 최선이라고 생각하지만 제생각이 100%맞다는 보장은 없습니다.)
프로그램화된 추측 알고리즘은 아래와 같다.
일단 해 집합을 정의하는데 답이 될 수 있는 문자열을 모두 포함하는 집합이다.
해집합 R(i) = { i번째 질문까지 만족하는 문자열} 으로 정의한다.
예를 들어 설명하자면
R(0) = {0123,0124,0125 ... 9876} (원소의 갯수는 총 5040개)
첫번째 시도에서 0123를 추측했고 결과가 0S 0B 라면
R(1) = { 4567,4568,....,9876} (원소의 갯수는 총 360가지, 아래 참조)
다음 과정은 해집합에 있는 한 수를 선택하여 그 결과를 질의 한다.
최종적으로 해집합의 원소의 수가 1개가 될 때까지 과정을 반복 한다.
실제 프로그램의 핵심 루프는 아래와 같다.
for i = 0 to 9
for j = 0 to 9
for k = 0 to 9
for l = 0 to 9
if i,j,k,l에 공통된 수자가 있으면 계속 루프를 돌도록
pstr = i & j & k & l ' i=0, j =1, k =2 , l = 3 일때 숫자열 0123 생성
if 이전 질의 결과를 모두 만족하는지 확인
만족한다면 숫자열을 상대방에게 알리고 결과를 요청
만족하지 않는다면 계속루프
next i
next k
next j
next i
예를 들어 첫 추측을 0123 으로 했는데 결과가 1b라면
끝자리부터 하나증가하면서 1b를 만족시키는 숫자열을 찾는다.
01234 는 0123 과 3s로 1b가 아니다.
01235는 0123 과 3s로 1b가 아니다.
.....
0987 은 0123 과 1s로 1b가 아니다.
1234 는 0123 과 3b로 1b가 아니다.
....
...
1567은 0123 과 1b이다.
그러므로 다음 추측은 1567로 한다. (1567은 해집합 R(1)의 한 원소이다)
결과가 만약 0s 2b로 나왔다면
1567에서 또 숫자를 증가시켜 가면 0123과 1b 이고 1567과는 2b인 숫자를 찾는다.
2658이 바로 그런 숫자열이다. (2658은 해집합 R(2) 한 원소이다)
2. 이 전략은 최선일까?
각 단계의 해집합은 이전 질의를 만족하는 원소로만 구성되어 있고 다음 추정은 그 해집합에 있는 한 원소로 하는 것은 직관적으로 타당해 보인다. 그러나 사실은 아니다. 반례가 있다.
A는 B의 수자를 마지막 자리를 제외하고 다 알고 있다.
추축한 숫자열은 123 * 이거 *에 대체될 수 이 수 있는 숫자는 4,5,6,7 4개라고 하자
해집합은 {1234,1235,1236,1237 } 이다. 다음 추측은 1234로 할 것이다.
1) 답이 1234 일 경우
1회에 성공
2) 답이 1235 일 경우
1234 오답이 되면 1235로 2회에 성공
3) 답이 1236일 경우 - 3회에 성공
4) 답이 1237일 경우 - 4회에 성공
성공까지의 시도회수 평균은 =1/4 *1 + 3/4*1/3*2 + 3/4*2/3*1/2*3 + 3/4*2/3*1/2*1*4 =
(1+2+3+4)/4 = 10/4 =2.5회
이번에는 다른 방법으로 풀어보자
9054 를 질의하면 1S 이면 답이 1234 이고 1B이면 1235 이고 아무것도 없으면 답은 1236이나
1237이 된다.
정리하면
1) 답이 1234 나 1235 이면 2회만에 정답
2) 답이 1236이면 첫번째 질의에서 0S0B 이므로 1234 ,1235가 아니라는 것을 알 수 있으므로
1236을 선택 - 2회 성공
3) 답이 1237이면 3회 성공
성공까지의 시도회수 평균은 =0*1/2 + (1/2 *2 + 1/2*1/2 * 2 )+ 1/2 * 1/2 * 3 = 2.25 회
문제는 다음 추측의 문자열을 해집합에서만 선택한다는 것이 문제인 것같다. (해집합외의 문자열로 질의하는 것이 더 좋을 수도 있다는 것이 위 예로 알 수 있다.
그래서 프로그램을 일부수정 했는데 , 매 질의때 마다 01234 ~ 9876 까지 모든 문자열에 대해
해집합의 문자열과 비교하여 가능한 모든 결과의 확률을 계산하다. 이로부터 전달되는 정보엔트로피를 계산할 수 있다. 이 경우 정보엔트로피는 질의로 전달되는 정보량을 의미하게 되므로 이 값이 큰 것이 좋은 질의이다.(정보엔트로피는 가능한 모든 경우에 대해 -P * log P , P는 각 경우의 확률이다. 정확한 수식은 http://ko.wikipedia.org/wiki/%EC%A0%95%EB%B3%B4_%EC%97%94%ED%8A%B8%EB%A1%9C%ED%94%BC 을 참조)
앞에 예에 대해 정보 엔트로피를 구해보면
해집합은 {1234,1235,1236,1237}
1234로 질의 할 경우
4S 일 경우 1가지 경우 1/4
3S 일 경우 3가지 경우 3/4
정보엔트로피 = - (1/4) * log2 (1/4) - (3/4) * log2 (3/4) = 0.811
9045로 질의 할 경우
1S 일 경우 1가지(1234) 1/4
1B 일 경우 1가지(1235) 1/4
0일 경우 2가지(1236,1237)
정보엔트로피 = - (1/4) * log2 (1/4) - (1/4) * log2 (1/4) - (1/2) * log2 (1/2) = 1.5
예상한대로 9045가 더 좋은 질의임을 엔트로피 계산으로 부터 알 수 있을 것 같다.
3. 추가
첫번째 프로그램은 답을 맞추는데 평균 5.55 회
두번째 프로그램은 답을 맞추는데 평균 5.52 회
그다지 큰 차이는 없다.
다음은 첫번째 프로그램으로 30000만회 문제풀이 결과의 통계값을 기록해본다.
(2번째 프로그램은 연산시간이 너무 많이 걸려 1000회 실시하는데 대략 하루가 걸렸다)
정답을 맞추기 위한 시행 회수
평균 : 5.55
표준편차 : 1.08
1회에 맞추는 확률 : 0.04 %
2회에 맞추는 확률 : 0.25 %
3회에 맞추는 확률 : 2.66 %
4회에 맞추는 확률 : 13 %
5회에 맞추는 확률 : 31 %
6회에 맞추는 확률 : 36 %
7회에 맞추는 확률 : 15 %
8회에 맞추는 확률 : 2.8 %
9회에 맞추는 확률 : 0.12 %
가능한 총 문자열의 갯수 : 5040
위 경우의 정보엔트로피 : 12.3
첫번째 시도에서 얻는 정보량
최대엔트로피(각 경우의 동일한 확률일 경우) : 3.91
실제엔트로피(아래 리스트의 확률을 이용) : 2.77
0 s 0 b 360 가지 7.14 %
0 s 1 b 1440 가지 28.57 %
0 s 2 b 1260 가지 25.00 %
0 s 3 b 264 가지 5.24 %
0 s 4 b 9 가지 0.18 %
1 s 0 b 480 가지 9.52 %
1 s 1 b 720 가지 14.29 %
1 s 2 b 216 가지 4.29 %
1 s 3 b 8 가지 0.16 %
2 s 0 b 180 가지 3.57 %
2 s 1 b 72 가지 1.43 %
2 s 2 b 6 가지 0.12 %
3 s 0 b 24 가지 0.48 %
3 s 1 b 불가능
4 s 0 b 1 가지 0.02%
문제가 가지는 엔트로피는 12.3
첫 시도에서 획득되는 정보량은 2.77
|
인기도 :
