안녕하세요.
눈팅만 하다가 돌 깎는 팁 글이 올라와서 보고 적습니다.
먼저 알려드리는데 저는 돌파고 제작자나 그분과 관련된 사람은 아닙니다.

전산학 전공인 분들은 바로 보일 거예요.  어빌리티 스톤 세공은 간단한 DP(동적계획법) 문제입니다.
반응이 좋으면 알고리즘의 구현과, 수식을 이용한 증명에 대해서 추가로 작성해 보겠습니다.
이 글에 기호나 수식은 일부러 쓰지 않았습니다.

(모든 사진은 합성입니다)

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


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

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


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



당연히 둘 다 45%입니다.
받아들일 수 없다면... 뒤로가기 누르고 가던 길 가시면 됩니다.

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

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

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

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


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

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

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

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

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


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

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

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


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

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


5. 구현에 대한 예상 질문 몇가지
Q. 그러면 모든 경우의 수를 계산해야 하니까 3^10번을 계산해야 하는 것이 아닌가요?
A. 2번 항목에서 말씀드렸듯이 돌의 상태는 단 7개의 변수로 표현 가능합니다. 
각 변수가 가질 수 있는 값의 가짓수가(10,10,10,10,10,10,6)이기 때문에 동적계획법을 사용하면 최대 6,000,000만 정도의 계산으로 가능합니다.
남은 횟수 + 성공 횟수 <= 10 이기 때문에 실제로는 더 줄겠죠.

Q. 돌파고가 이 알고리즘인가요?
A. 제가 제작자는 아니지만, 제작자분 블로그 웹 소스코드를 보면 그렇게 구현되어 있습니다.
프로그램에 버그가 없다면 이 확률이 맞아요.

Q. 확률 조작이 있으면 어떻게 하나요.
A. 팁게에 이미 몇몇 분들이 충분히 신뢰성있는 표본을 제시했고, 금강선 디렉터도 로아온에서 확률이 맞다고 얘기했습니다.
의심을 하시려면 개인의 경험이나 느낌이 아닌 신뢰성있는 표본을 제시해서 의심해주세요.

Q. 돌파고 안써도 97돌 깎았는데요?
A. 이 알고리즘으로 계산했을 때 97돌(or106돌)이 깎일 확률은 0.136%입니다.
어떤 방법을 써도 이보다 높게 나올 수 없으며, 최적의 방법으로 세공해도 10000명 중 13등 안에 들어야 합니다.
안 쓰고 97돌 깎으신 분들은 정말 운이 좋으시네요. 축하드립니다.

Q. 그래서 돌파고 쓰면 얼마나 좋은지 정확한 수치를 가져오라구요.
A. 자신이 "어떤 패턴으로 돌을 깎았는지를 정확히" 말씀해주시면 계산이 가능합니다.
예를 들어 45% 이상을 유효 각인에, 35% 이하를 디버프에 넣는 패턴으로 돌을 세공하면 약 0.09%의 확률로 97돌이 뽑힙니다. 돌파고가 1.5배 정도 좋습니다.


쓰고 나니 그냥 점화식으로 쓰는 게 더 편할 것 같네요.


3줄요약
1. 돌 세공 문제는 확률에 대한 DP문제이다.
2. 돌파고는 DP로 최적 확률을 계산해준다.
3. 최적으로 세공했을 때에도 97돌 확률은 0.13%밖에 안 된다.