PGR21.com
- tvN '더 지니어스' 관련 게시글을 위한 임시 게시판입니다.
- 방송 기간 한정 임시로 운영됩니다. (선거, 올림픽, 월드컵 게시판과 같음)
Date 2014/02/23 04:00:59
Name 곧내려갈게요
Subject [분석] 좀 더 빠른 바이너리 서치법
그냥 모든 경우를 정직하게 반으로 쪼개는 바이너리 서치만 사용해도 14번 안에 게임은 끝납니다.
이를테면 1928 이라는 숫자를 맞추는 과정을 정직한 바이너리 서치법을 이용하면
"5000 이하"
"2500 이하"
"1250 이상"
이런식으로 접근하게 되겠죠.
그런데 바이너리 서치법을 쓰는 중에도 약간의 요행수를 노려볼 건덕지가 있습니다.

예를 들면 처음 질문할때, "3000보다 큽니까?" 라고 묻는거죠.
3000과 7000으로 쪼개었을때, 만약 3000보다 작다고 대답한다면 질문의 수가 하나가 줄어듭니다.
왜냐하면 3000은 2^12=4096보다 작기 때문이죠. 즉 앞으로 12번만 질문하면 정답에 도달하게 됩니다.
그렇다고 해서 상대가 3000보다 크다고 했을때 나빠지는게 있느냐? 정직한 바이너리보다 나쁠게 없습니다.
7000은 2^13=8192 보다 여전히 작기 때문에 앞으로 13번만 질문하면 답에 도달 할 수 있습니다.
이런식으로 두 선택지를 쪼갤때 비대칭으로 잘 선택한다면
운이 좋으면 질문해야 하는 횟수를 줄일 수도 있습니다.

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
14/02/23 04:11
수정 아이콘
만약 3000보다 크다고 하면 손해가 되겠죠.
그 후의 바이너리 서치의 구간이 7000 으로 정석인 5000보다 커져버리니까요.
곧내려갈게요
14/02/23 04:12
수정 아이콘
5000 이나 7000 이나

여전히 2^12(4096) <x <=2^13(8192) 구간 안에 있습니다.

검색 구간이 조금 넓어지긴 하지만 치명적인 손해는 아닙니다.

만약 7000의 구간으로 간다면 3000, 4000으로 다시 나눠 볼 수 있습니다.

3천이나 4천은 모두 2^11(2048) <x <=2^12(4096) 구간안에 들어갑니다.

3천을 선택하든 4천을 선택하든 그 당장엔 다를게 없죠.

하지만 상대가 3천을 선택한다면 그 후에 2000,1000으로 쪼개서 이득을 볼 여지가 생깁니다.

2천은 2^10 <x <=2^11 구간이지만, 천은 2^9 <x <=2^10 구간안에 들어옵니다.
14/02/23 04:24
수정 아이콘
필요검색횟수는 log_2(검색구간) 입니다.

초기 필요검색횟수 = log_2(10000) = 13.28 회

도박 성공시 2차시도 (검색구간 3000) : 필요 검색횟수 : log_2(3000) = 11.55 회
도박 실패시 2차시도 (검색구간 7000) : 필요 검색횟수 : log_2(7000) = 12.77 회

도박 안했을 시 1차시도 검색구간 5000 : 필요 검색횟수 : log_2(5000) = 12.28 회

도박성공확률 = 0.3
실패확률 = 0.7

성공(11.55회) 와 실패(12.77회) 와 3:7 내분점은 12.40 회 > 12.28 회

즉, 반으로 자르지 않는 이런 류의 도박은 바이너리 서치에서 오히려 손해입니다.
곧내려갈게요
14/02/23 04:31
수정 아이콘
기대값으로 접근하면 그러네요. 다만 이런 통계는 똑같은 검색을 무수히 반복했을때 그 진가가 발휘되는법 아닙니까?

똑같은 검색을 천번 정도 반복해서 하면 그냥 반으로 나누는게 확연하게 이득이겠지만,

단 한번 하는 검색이라면 충분히 해볼법한 도박 아닌가 싶습니다.

0.12의 기대값 차이고, 기대값의 소수점이 의미가 없는 단 한번의 검색이니까...
14/02/23 04:38
수정 아이콘
네 단 한번 하는 게임이니 그날의 운을 믿고 도박을 해 보는 것도 나쁘지 않습니다. 특히 제가 임요환이었다면 템빨리 딸리는 상황 (이상민보다 질문 기회가 한번 적음)에서 당연히 3000~4000 정도로 찔러봤을 것 같아요.
곧내려갈게요
14/02/23 04:39
수정 아이콘
사실 저도 제가 임요환이였다면 어떻게 했을까 고민하다가 생각한 방법이라서요.
14/02/23 04:44
수정 아이콘
실제로 3000을 했으면 1928 이었으니 성공했을거고... 기대값상으로 0.7회 정도를 줄이니 이상민 템빨 1.0회 만은 아니겠지만 그래도 불리하지만 충분히 싸워볼만하죠. 논외로 1928 비하인드 스토리는 정말 짠했습니다...
14/02/23 04:57
수정 아이콘
근데 생각못했던게 하나 있었네요. 임요환의 선공권... 결국 둘은 동등한 입장이었군요.
곧내려갈게요
14/02/23 05:04
수정 아이콘
둘다 바이너리서치를 하면 임요환이 불리한게 맞습니다. 이상민이 아이템을 쓰면 임요환의 선공권을 가져가는것과 같은 효과를 내니까요.
14/02/23 07:25
수정 아이콘
곧내려갈게요 님// 네 그렇네요. 질문+1권이 무섭긴 무섭군요.
곧내려갈게요
14/02/23 05:28
수정 아이콘
그런데, 단 한번의 검색에서 무조건 절반으로만 잘라내면 결과적으로 13회 혹은 14회 라는 결과밖에 나오질 않네요.
물론 13회만에 끝날 확률이 72%로 14회만에 끝날 확률(28%)보다 더 높긴 하지만 13회 혹은 14회 외에는 존재하지 않습니다.
(물론 이것은 2개의 번호가 남았을때 질문을 하는게 아니라 정답을 찍음으로 인해서 50%의 확률로 한번씩 횟수가 줄 수 있지만 계산상의 편의를 위해 그 경우는 고려하지 않겠습니다.)
제가 말한 도박수를 사용하면 무조건 절반으로 나누는것 보다 14회만에 정답으로 갈 확률이 조금 높아지지만,
10~11회만에 정답에 도달할 확률이 조금 이라도 생기니까, 어느정도 시점에서는 오히려 무조건 도박수를 거는데 더 나은거 아닌가 싶네요.
14/02/23 05:36
수정 아이콘
이 말은 마치 3등분해서 검색하면 9회 안쪽으로 검색할 확률이 생기기 때문에 도박을 걸어봐도 된다라는 말인데..
동의하기가 힘드네요
곧내려갈게요
14/02/23 05:38
수정 아이콘
그거랑은 다르죠. 제가 말하는 방법은 최악의 경우에도 14회보다 질문 횟수가 늘지 않습니다.

선공권이 없는상태 (혹은 뺏긴 상태) 에서는 이기려면 무조건 도박 걸어야죠.

그냥 똑같이 반으로 쪼개면 0.72*0.28=20%의 확률로 이기지만,

처음에 3000,7000으로 쪼개면 (상대가 반으로만 쪼갠다는 가정하에)

0.3*(0.45+0.55*0.28)+0.7*(0.23*0.28)= 0.23이므로

23%의 확률로 이깁니다.
14/02/23 06:23
수정 아이콘
제가 잘못 이해하고 반박을 했네요
처음 선택지에서 10000과 8192 사이의 차이가 얼마 나지 않기 때문에 처음 쪼개는 것 이후에는 차이가 없긴 했을겁니다.. 최선의 선택으로 나오더라도 시행횟수를 1회 줄이는데 그치구요~~
곧내려갈게요
14/02/23 06:41
수정 아이콘
후공이라면 그래도 1턴이라도 줄일 수 있는 시도를 하는게 낫죠.

실제로 확률계산을 해도 후공이라면 도박을 거는게 이길 확률이 3% 높아집니다... -_- 고작 3이긴 하지만
Legend0fProToss
14/02/23 18:40
수정 아이콘
해보니 처음에 8000 2000으로 쪼개고 그다음은 무조건 반반 전략이 꽤 괜찮네요
8000 2000은 20퍼센트확률로 두개를 줄이는게 가능하네요 80%는 그냥 그대로 14개구요
곧내려갈게요
14/02/24 21:01
수정 아이콘
실패했을때 리스크가 너무 큽니다.
실패하면 웬만하면 14번 다 질문해야합니다. 3,7000로 나누면 실패해도 다시한번 기회가 있습니다.
nearfield
14/02/25 00:37
수정 아이콘
글쓴님 생각에 전적으로 동의하구요. 저도 진실탐지기 게임에서 이진검색 알고리즘의 최대검색범위인 16384가 10000을 훌쩍 넘어감으로서 발생하는 손실을 고려했을때, 이 방법이 최적일 것으로 생각했었는데 의외로 아무도 그 부분을 짚고 넘어가지 않아서 조금 놀랐습니다. 이론적으로 계산된 검색횟수가 아무리 낮아도 소수점 이하는 아무런 의미가 없죠.
여유있을때 최적의 구간기준값을 계산해서 한번 올려보겠습니다.
곧내려갈게요
14/02/25 01:06
수정 아이콘
와우 정량적인 계산은 nearfield님께 부탁드리겠습니다.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
1354 [분석] 진실탐지기 바이너리보다 유리한 방법 [5] IdoIdoIdoIdo4913 14/02/23 4913
1353 [분석] 더 지니어스 시즌2 가장 지니어스했던 순간 BEST 10 [13] Duvet9316 14/02/23 9316
1349 [분석] 둘둘둘 형님께 직접 들은 필승법 [12] 로마네콩티6728 14/02/23 6728
1348 [분석] 제가 생각한 진실탐지기 필승법 [15] 카키스6738 14/02/23 6738
1347 [분석] 좀 더 빠른 바이너리 서치법 [19] 곧내려갈게요5437 14/02/23 5437
1346 [분석] 더 지니어스 시즌2 결승전 리뷰. [5] Leeka4910 14/02/23 4910
1343 [분석] 시즌2를 돌이켜보며... [14] 라라 안티포바4852 14/02/23 4852
1339 [분석] 임요환의 완벽히 실패한 2라운드 전략+제가 생각하는 필승법 [24] mille5252 14/02/23 5252
1337 [분석] 이상민씨 우승을 축하드립니다! 와 더불어 콰트로에서 임요환의 경우의 수 [8] chamchI4469 14/02/23 4469
1335 [분석] 마지막 게임에 대하여 [38] sonmal4806 14/02/23 4806
1329 [분석] 단두대 매치-시즌2 결승전 [4] K-DD4785 14/02/21 4785
1328 [분석] 결승전 이야기 [7] 라라 안티포바5196 14/02/21 5196
1322 [분석] 탈락자들은 누굴 지지할 것인가? [7] K-DD5223 14/02/18 5223
1318 [분석] 간만에 감탄한 이다혜의 판단 [7] 솔로9년차7493 14/02/17 7493
1317 [분석] 최종전엔 콰트로가 들어갈거라 예상합니다. [13] 캡슐유산균7418 14/02/17 7418
1314 [분석] 짧은 분석, 임요환의 가넷 0개 전략이 정말로 전략이었을까? [17] chamchI6373 14/02/17 6373
1313 [분석] 11화의 유정현 제안, 씨알도 안먹히는 소리였나 [9] be manner player5211 14/02/17 5211
1310 [분석] 더 지니어스 1회부터 11회까지 이상민, 임요환 활약상 [3] Duvet7052 14/02/17 7052
1304 [분석] 지니어스는 왜 지니어스하지 못한가... [11] 랑비6811 14/02/16 6811
1303 [분석] 더 지니어스 게임 11화까지의 순위. [25] Leeka6790 14/02/16 6790
1301 [분석] 지니어스 게임 11화 리뷰 [2] Leeka4524 14/02/16 4524
1298 [분석] 준결승 리뷰. 나는 임빠인가보다 ㅠ [5] 노래하는몽상가4885 14/02/16 4885
1297 [분석] 결승전도 할만한 임요환인듯요 [21] AyuAyu7689 14/02/16 7689
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로