안녕하세요.

몇년동안 제대로 돌파고에 대해 알고 쓰는 분이 없었는데 
아무튼 자동 돌깎이 나와서 참 다행이라고 생각합니다.

앞으로는 쓸모 없는 내용이겠지만 그래도 어떻게 확률이 개선되는지,
돌파고와 자동 돌깎은 어떤 근거로 세공하는지를 설명해볼게요.

공지에 이렇게 명시한 이상, 아래에 설명하는 알고리즘대로 동작하는 것이 거의 확실시되었습니다.

로아온 때 설명한 것과 달리, 항상 97돌에 최적화된 확률로 동작합니다

자동 세공 시에는 특정 각인을 우선하지 않고, 아래 목표 레벨 달성 확률을 최대화한 방식이 적용됩니다.
  • 세공 기회 10회 어빌리티 스톤: 증가 능력 각인의 각인 효과 레벨 합산 Lv.5 이상

4년 전에 팁게에 쓴 게시글을 조금 다듬어서 쓰는 내용입니다



3줄요약
1. 돌 세공 문제는 확률에 대한  DP(동적계획법) 문제이다.
2. 시도 횟수가 n번 남은 돌의 확률로 n+1번 남은 돌의 확률을 계산할 수 있다.
3. 최적으로 세공했을 때 97돌 확률은 0.136%이다. 어떤 방법을 써도 이 확률보다 높게 깎을 수 없다. 
돌파고와 다른 선택을 하면 확률이 떨어진다.

===========================================================================================




수식이 좀 복잡해 보이는데, 사실 우변 3개의 내용은 똑같습니다.
각각 1번각인, 2번각인, 디버프를 선택했을 때 어떻게 확률이 계산되는지를 나타내므로, 맨 위의 하나만 보시면 되겠습니다.
2번, 3번 문단을 통해 그림과 함께 수식에 대해 설명했으므로 참고하시면 될 것 같네요.


1. 기본적인 선택지와 확률
예시를 하나 들어 보겠습니다.
다음과 같은 돌이 있습니다.  이 돌이 97돌 이상이 될 확률은 얼마일까요?


보면 바로 아시겠지만, 75%입니다.
선택할 수 있는 경우의 수는 1번 옵션인 원한을 누르는 것 1가지밖에 없습니다.
75%의 확률로 97돌이 되고, 25%의 확률로 87돌이 됩니다.

이 경우 돌파고는 당연히 75%의 선택지를 추천합니다.
75%를 추천했는데 실패했다면, 시도하신 분이 단순하게 운이 없어서지 돌파고의 잘못이 아니예요.


2. 확률과 상태가 같다면, 이전 시도의 세공의 성공/실패 순서는 상관없다
다음 2개의 돌이 97돌 이상이 될 확률은 얼마일까요?



당연히 둘 다 45%입니다.
성공한 순서는 달랐지만, 선택지가 1개만 남았고, 그 확률이 45%니까요.

앞으로 돌 세공 수치를 많이 언급할 예정이어서, 돌의 상태를 다음과 같이 표기할게요
(1번옵션 성공 횟수 / 1번옵션 실패횟수, 
2번옵션 성공 횟수 / 2번옵션 실패횟수, 
3번옵션 성공 횟수 / 3번옵션 실패횟수
, 현재 세공 성공확률)

예를 들면, 방금 2개의 돌은 동일하게 (8/1, 7/3, 4/6, 45%) 돌입니다.
첫 번째 옵션에서 
이 표기법을 쓰면 1번 문단에서 보여드렸던 돌은 (8/1, 7/3, 4/6, 75%) 돌입니다.

중요한 것은, 현재 돌의 상태는 단 7개의 숫자로 나타낼 수 있다는 점입니다.
(1번옵션 성공 횟수 / 1번옵션 실패횟수, 2번옵션 성공 횟수 / 2번옵션 실패횟수, 3번옵션 성공 횟수 / 3번옵션 실패횟수, 현재 세공 성공확률)

이 사실은 확률을 계산하는 알고리즘을 구현하는 데 사용합니다.


3. 돌의 상태와 목표가 정해졌다면, 최적의 선택지는 정해져 있다.
이번엔 횟수가 2번 남은 돌을 보죠.

(8/1, 7/3, 3/6, 45%)
세공 횟수가 2번 남은 돌입니다.
이 돌이 97돌이 될 확률은 얼마일까요?

만약 45%의 확률로 세공을 누를 경우, 
45%의 확률로 (9/1, 7/3, 3/6, 35%) 돌이 되며, 
55%의 확률로 (8/2, 7/3, 3/6, 55%) 돌이 됩니다.

그렇다면 유효 각인 세공을 눌렀을 때 97돌이 될 확률은 다음과 같습니다.

0.45(성공 확률) * (9/1, 7/3, 3/6, 35%)돌이 97돌 이상이 될 확률
+
(1-0.45)(실패 확률) * (8/2, 7/3, 3/6, 55%)돌이 97돌 이상이 될 확률


만약 45%의 확률로 디버프를 누를 경우, 
45%의 확률로 (8/1, 7/3, 4/6, 35%) 돌이 되며, 55%의 확률로 (8/1, 7/3, 3/7, 55%) 돌이 됩니다.
따라서 디버프 세공을 눌렀을 때 확률은 다음과 같습니다.
0.45(성공 확률) * (8/1, 7/3, 4/6, 35%)돌이 97돌 이상이 될 확률
+
(1-0.45)(실패 확률) * (8/1, 7/3, 3/7, 55%)돌이 97돌 이상이 될 확률

여기서 파악해야 하는 점이 2가지 있습니다.

첫 번째. 
특정 상태(남은 세공 횟수, 성공 횟수, 확률)의 돌이 목표에 달성할 확률은 
다음 상태의 돌의 확률 * 다음 상태로 도달할 수 있는 확률 중 최대값이다.
방금 보여드렸던 돌(8/1, 7/3, 3/6, 45%)의 확률을 계산해보면 45% vs 46%입니다.
그러므로 앞으로도 최선의 선택지만을 택한다면 , 즉, 디버프를 먼저 누른다면 
해당 돌이 97돌 이상이 될 확률은 46%겠죠.


두 번째.
시도 횟수가 1번 남은 돌의 성공률을 가지고 횟수가 2번 남은 돌의 성공률을 계산했다는 것인데요.
이 글에 증명을 작성하기는 어려우니 약간의 논리적 비약이 있지만
시도 횟수가 n번 남은 돌의 확률로 n+1번 남은 돌의 확률을 계산할 수 있다는 것입니다.
귀납적으로 30번 남은 돌도 계산이 가능하겠죠?

4. 기저 조건
남은 횟수가 0인 경우 97돌 이상인 돌의 확률은 1,
남은 횟수가 0인 경우 97돌 이상인 돌의 확률은 0입니다.
이 값을 이용하여 점화식으로 계산하면 됩니다.

5. 계산량
Q. 그러면 모든 경우의 수를 계산해야 하니까 3^10번을 계산해야 하는 것이 아닌가요?
A. 각 세공마다 1,724,976 개의 경우만 계산하면 됩니다.
3개의 옵션 각각의 성공/실패의 합은 10을 초과할 수 없습니다.
따라서 옵션 성공/실패에서 나올 수 있는 경우는
(0,0), (0,1), ... , (0,10) => 11개
(1,0), (1,1), ... (1,9) => 10개
...
(10,0) => 1개 
이므로 66개이며 옵션이 3개, 확률의 가짓수가 6개(25%, 35%, ... , 75%)이며
전부 곱하면 66 * 66 * 66 * 6 = 1,724,976 입니다.

6. Q&A
Q. 자동 세공은 시간이 지날수록 학습하나요?
A. 아니요. 애초에 정답이 정해져 있는 문제이며, AI가 학습하여 문제를 풀어야 할 이유가 없습니다.