|
:: 게시판
:: 이전 게시판
|
- tvN '더 지니어스' 관련 게시글을 위한 임시 게시판입니다.
- 방송 기간 한정 임시로 운영됩니다. (선거, 올림픽, 월드컵 게시판과 같음)
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
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:44
실제로 3000을 했으면 1928 이었으니 성공했을거고... 기대값상으로 0.7회 정도를 줄이니 이상민 템빨 1.0회 만은 아니겠지만 그래도 불리하지만 충분히 싸워볼만하죠. 논외로 1928 비하인드 스토리는 정말 짠했습니다...
14/02/23 05:04
둘다 바이너리서치를 하면 임요환이 불리한게 맞습니다. 이상민이 아이템을 쓰면 임요환의 선공권을 가져가는것과 같은 효과를 내니까요.
14/02/23 05:28
그런데, 단 한번의 검색에서 무조건 절반으로만 잘라내면 결과적으로 13회 혹은 14회 라는 결과밖에 나오질 않네요.
물론 13회만에 끝날 확률이 72%로 14회만에 끝날 확률(28%)보다 더 높긴 하지만 13회 혹은 14회 외에는 존재하지 않습니다. (물론 이것은 2개의 번호가 남았을때 질문을 하는게 아니라 정답을 찍음으로 인해서 50%의 확률로 한번씩 횟수가 줄 수 있지만 계산상의 편의를 위해 그 경우는 고려하지 않겠습니다.) 제가 말한 도박수를 사용하면 무조건 절반으로 나누는것 보다 14회만에 정답으로 갈 확률이 조금 높아지지만, 10~11회만에 정답에 도달할 확률이 조금 이라도 생기니까, 어느정도 시점에서는 오히려 무조건 도박수를 거는데 더 나은거 아닌가 싶네요.
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이긴 하지만
14/02/23 18:40
해보니 처음에 8000 2000으로 쪼개고 그다음은 무조건 반반 전략이 꽤 괜찮네요
8000 2000은 20퍼센트확률로 두개를 줄이는게 가능하네요 80%는 그냥 그대로 14개구요
14/02/24 21:01
실패했을때 리스크가 너무 큽니다.
실패하면 웬만하면 14번 다 질문해야합니다. 3,7000로 나누면 실패해도 다시한번 기회가 있습니다.
14/02/25 00:37
글쓴님 생각에 전적으로 동의하구요. 저도 진실탐지기 게임에서 이진검색 알고리즘의 최대검색범위인 16384가 10000을 훌쩍 넘어감으로서 발생하는 손실을 고려했을때, 이 방법이 최적일 것으로 생각했었는데 의외로 아무도 그 부분을 짚고 넘어가지 않아서 조금 놀랐습니다. 이론적으로 계산된 검색횟수가 아무리 낮아도 소수점 이하는 아무런 의미가 없죠.
여유있을때 최적의 구간기준값을 계산해서 한번 올려보겠습니다.
|
||||||||||