God-Blessed Blackjack

블랙잭 여부는 초기 두 장만으로 결정된다. 양쪽 중 적어도 한쪽이 블랙잭이면 규칙에 따라 즉시 $0$, $1.5R$, $-R$ 중 하나가 답이다.

이후 일반 게임에서는 보상을 $R$로 나누어 승리 $+1$, 무승부 $0$, 패배 $-1$로 정규화한다. 마지막에 얻은 기댓값에 $R$을 곱하면 된다.

현재 덱의 $N$장에 $0,1,\cdots,N-1$의 번호를 붙인다. jtw7913가 추가로 받은 카드 집합을 비트마스크 $P$, 딜러가 추가로 받은 카드 집합을 비트마스크 $D$라 하자. jtw7913의 차례에는 $$이고, jtw7913가 한 뒤에는 가 고정된 채 만 증가한다.

각 카드는 아직 덱에 남아 있거나, jtw7913가 받았거나, 딜러가 받은 세 상태 중 하나이다. 따라서 가능한 $(P,D)$ 상태 수는 최대 $3^N$이다.

모든 비트마스크 $M$에 대해 다음 점수를 전처리한다.

• $\mathrm{playerScore}[M]$: jtw7913의 초기 두 장과 $M$의 카드를 합친 점수.
• $\mathrm{dealerScore}[M]$: 딜러의 초기 두 장과 $M$의 카드를 합친 점수.

에이스를 모두 1점으로 계산한 합을 $s$라 하자. 에이스가 하나 이상 있고 $s+10\leq21$이면 에이스 하나를 11점으로 바꾸어 $s+10$을 사용한다. 그렇지 않으면 $s$를 사용한다.

$G(P,D)$를 jtw7913가 이미 Stay했고 추가 카드 집합이 $P$, 딜러의 추가 카드 집합이 $D$일 때 이후 결과의 정규화된 기댓값이라 하자. 딜러 점수가 21을 초과하면 $G(P,D)=1$이다. 딜러 점수가 17 이상이거나 덱이 비었다면 두 사람의 점수를 비교하여 중 하나를 반환한다.

그 외에는 딜러가 반드시 Hit한다. 남은 카드 집합을 $U$라 하면

$$G(P,D)=\frac{1}{|U|}\sum_{i\in U}G(P,D\cup\{i\}).$$

메모이제이션 인덱스는 각 카드의 상태를 3진수 한 자리로 표현하여 만들 수 있다. 카드 $i$가 덱에 남아 있으면 0, $P$에 있으면 1, $D$에 있으면 2를 사용한다. 이렇게 하면 길이 $3^N$의 배열 하나로 모든 딜러 상태를 저장할 수 있다.

이제 $F(P)$를 jtw7913가 추가 카드 집합 $P$를 가진 상태에서 최적으로 행동할 때의 최대 정규화 기댓값이라 하자. 지금 Stay하는 값은

$$S(P)=G(P,0)$$

이다.

현재 점수가 21이거나 덱이 비었다면 자동으로 Stay하므로 $F(P)=S(P)$이다. 그렇지 않으면 Hit도 선택할 수 있다. 남은 카드 집합을 $U$라 할 때

$$H(P)=\frac{1}{|U|}\sum_{i\in U} h_i,$$

여기서 카드 $i$를 뽑고 버스트하면 $h_i=-1$, 그렇지 않으면 $h_i=F(P\cup\{i\})$이다. 따라서

$$F(P)=\max(S(P),H(P)).$$

일반 게임의 답은 $F(0)\cdot R$이다.

점수 전처리는 $O(N2^N)$이고, 딜러 상태는 최대 $3^N$개이며 각 상태에서 최대 $N$장을 순회한다. 따라서 시간 복잡도는 $O(N3^N)$, 공간 복잡도는 이다.

Solution written by GPT5.6