[2015_TrendMicro_CTF] (Programming 500) BlackJack

최종 수정: 2015-10-26

hackability@TenDollar

안녕하세요. Hackability 입니다.

이번 포스팅 할 내용은 2015 TrendMicro CTF 에서 있었던 프로그래밍 문제인 BlackJack 에 대해 포스팅 합니다.

이번 문제는 블랙잭 특정 상황에서 Hit이나 Stand 를 했을 경우 이길 확률이 어떻게 되는지 구하는 문제입니다.

I'm playing heads up blackjack. I'm dealt Ace-2 and the dealer has 3 showing. What's the probably of winning if: 1) I stand or 2) I kept playing.

시작은 플레이어가 Ace와 2를 갖고 있고 딜러는 3이 펼쳐 졌을 경우

1) stand 를 했을 때 이길 확률

2) 계속 플레이를 했을 때 이길 확률

을 계산하는 문제 입니다.

추가적으로 플레이어는 플레이에 제약이 없지만 (더블 다운이나 슬플릿은 없음) 딜러의 경우 17 이상일 경우 무조건 stand 한다는 조건이 있습니다.

먼저, 이런 문제를 풀기 위해서 확률 모델을 설계를 해야 하는데 확률 모델에는 deterministic (확정형) 모델과 stochastic (추계형) 모델이 존재합니다. 확정형 확률 모델은 변수들의 관계가 확실하여 예측을 정확히 할 수 있는 경우에 쓸수 있는 확률 모델이고 추계형 확률 모델은 프로세스의 부분 부분이 특정 확률에 의해 계속 변하게 되어 예측할 수 없을 경우 사용됩니다.

따라서, 일반적으로 확정형 모델에서는 분석적 해를 찾을 수 있지만 추계형 모델에서는 이런 분석적 해를 찾기 힘든 경우가 많습니다. 따라서 이런 문제를 해결하기 위해서는 수치적 난수를 크게 발생 시켜 시뮬레이션을 통해 해에 근접하는 결과를 도출하는 것이 일반적입니다.

따라서, 이 문제를 해결하기 위해 추계형 확률 모델에서 시뮬레이팅을 하기 위해 사용되는 Monte Carlo 기법을 이용하여 해결을 합니다.

번외로 Monte Carlo 기법은 통계 자료가 많고 입력값의 분포가 고를수록 정밀한 시뮬레이션이 되기 때문에 일반적으로 컴퓨터를 이용해 난수를 생성하여 시뮬레이션을 합니다. 또한 이론적 배경이나 복잡한 수식을 계산해야 하는 경우, 근사치를 계산하기 위해서도 몬테카를로 기법이 많이 사용되고 있는데 몬테 카를로 이름의 부터 몬테 카를로라는 유명한 도박 도시에서 도박사들이 여러번의 임의 추출을 바탕으로 특정 카드 조합이 나올 때까지 계산을 하여 붙여진 이름이라고 합니다. 또한 폰 노이만은 원자폭탄 개발 계획인 맨하탄 프로젝트에서 중성자 확산 시뮬레이션에 이 기법을 사용했고, 최근에는 위험관리, 품질 관리, 금융공학 등에서도 이 기법이 사용되고 있다고 합니다.

기본적으로 몬테 카를로 시뮬레이션은 다음의 절차를 따릅니다.

1. 입력 값의 범위를 정함

2. 확률 분포에 따라 입력값을 랜덤하게 만듬

3. 입력값에 대한 계산

4. 계산 결과를 통합

wiki 에서 원주율을 구하는 몬테 카를로 기법으로 다음과 같이 정의하고 있습니다.

1. 정사각형을 그리고 그 안에 원을 그린다.

2. 정사각형 안에 수 많은 점을 고르게 분포 한다.

3. 분포한 전체 점의 개수와 원 안에 분포한 점의 개수를 센다.

4. 전체 점의 개수와 원 안의 점 개수의 비율로 원주율 파이를 계산한다.

이제 우리가 풀려고 하는 문제를 몬테 카를로 시뮬레이션 절차로 만들어 봅니다.

1. 카드가 2 Deck 사용되는데 초반에 3장이 오픈 되었기 때문에 (52 * 2 - 3)의 카드가 존재

2. 

  - 플레이어가 Hit 을 하는 경우 한장 가져옴

  - 만약 플레이어가 Stand를 하는 경우, 딜러가 한장 가져옴

  - 딜러는 최소 17이 될 때 까지 Hit을 함

3. 확률을 계산

4. 소수점 4자리까지 반복

한 가지 더 추가 사항으로 딜러가 특정 상황일 때 플레이어가 해야 할 플레이에 대해 다음과 같습니다.

검은색으로 칠한 부분이 딜러가 처음에 3 일경우 플레이어가 플레이 해야 될 테이블 입니다. 이를 이용하여 Monte Carlo Simulation 을 구현해 봣습니다.

import random
 
# 0: Stand, 1: Hit
DEBUG = 1
 
def generate_decks(n_decks):
    lst_tmp = []
 
    for i in range(0, n_decks):
        for j in range(1, 10):
            lst_tmp.append(j)
            lst_tmp.append(j)
            lst_tmp.append(j)
            lst_tmp.append(j)
 
        # 10, J, Q, K
        for j in range(0, 4):
            for k in range(0, 4):
                lst_tmp.append(10)
 
    random.shuffle(lst_tmp)
    return lst_tmp
 
n_iter  = 1000000
n_decks = 2
 
p_win  = 0.0
p_lose = 0.0
p_draw = 0.0
 
if DEBUG == 0:
    for i in range(0, n_iter):
 
        if (i+1) % 10000 == 0:
            print "[%6d] : %f" % (i, (p_win / (p_win+p_lose)))
 
        lst_deck = generate_decks(n_decks)
 
        player = [1, 2]
        dealer = [3]
 
        sum_d  = 0
 
        lst_deck.remove(1)
        lst_deck.remove(2)
        lst_deck.remove(3)
 
        j = -1
        while sum_d < 17:
            j = j + 1
 
            dealer.append(lst_deck[j])
 
            if 1 in dealer:
                sum_d = 0
                count_a = 0
                for k in range(0, len(dealer)):
                    if dealer[k] == 1:
                        count_a = count_a + 1
                    else:
                        sum_d = sum_d + dealer[k]
 
                if count_a >= 1:
                    if (sum_d + 11) + (count_a-1) <= 17:
                        sum_d = sum_d + 11 + count_a
                    else:
                        sum_d = sum_d + count_a
            else:
                sum_d = sum(dealer)
 
        if sum_d > 21:
            p_win = p_win + 1
        else:
            p_lose = p_lose + 1
 
    print "result : %f" % (p_win / (p_win+p_lose))
 
else:
    bj_table_with_a = {
        '3': 'H',
        '4': 'H',
        '5': 'H',
        '6': 'H',
        '7': 'S',
        '8': 'S',
        '9': 'S',
        '10': 'S'
    }
 
    bj_table_without_a = {
        '12': 'H',
        '13': 'S',
        '14': 'S',
        '15': 'S',
        '16': 'S',
        '17': 'S',
        '18': 'S',
        '19': 'S',
        '20': 'S',
        '21': 'S'
    }
 
    for i in range(0, n_iter):
 
        if (i+1) % 10000 == 0:
            print "[%6d] : %f" % (i, (p_win / (p_win+p_lose+p_draw)))
 
        lst_deck = generate_decks(n_decks)
 
        player = [1, 2]
        dealer = [3]
 
        sum_p  = 0
        sum_d  = 0
 
        lst_deck.remove(1)
        lst_deck.remove(2)
        lst_deck.remove(3)
 
        turn_player = True
 
        for j in range(0, len(lst_deck)):
 
            if turn_player :
                player.append(lst_deck[j])
 
                sum_p = sum(player[1:])
 
                if sum_p >= 2 and sum_p <= 10:
                    if sum_p <= 6:
                        continue
                    else:
                        sum_p = sum_p + 11
                        turn_player = False
                        continue
                else:
                    if sum_p == 11:
                        continue
                    else:
                        sum_p = sum_p + 1
                        turn_player = False
                        continue
 
            else :
 
                dealer.append(lst_deck[j])
 
                if 1 in dealer:
                    sum_d = 0
                    count_a = 0
                    for k in range(0, len(dealer)):
                        if dealer[k] == 1:
                            count_a = count_a + 1
                        else:
                            sum_d = sum_d + dealer[k]
 
                    if count_a >= 1:
                        if (sum_d + 11) + (count_a-1) <= 17:
                            sum_d = sum_d + 11 + (count_a-1)
                        else:
                            sum_d = sum_d + count_a
                else:
                    sum_d = sum(dealer)
 
                if sum_d >= 17:
                    break
 
        if sum_p > 21:
            p_lose = p_lose + 1
        elif sum_d > 21:
            p_win = p_win + 1
        elif sum_p > sum_d:
            p_win = p_win + 1
        elif sum_p == sum_d:
            p_draw = p_draw + 1
        else:
            p_lose = p_lose + 1
 
    print "result : %f" % (p_win / (p_win+p_lose+p_draw))

100 만번 씩 시뮬레이션 결과 (원래는 특정 소수점 밑 까지 수렴할 때까지 해야 함) 

처음에 Stand 할 경우의 이길 확률은 result : 0.3756

처음에 Hit 할 경우 이길 확률은 result : 0.5106

정답으로 인증한 팀의 경우 처음 Stand 할 경우 이길 확률이 0.3770, 처음에 Hit 할 경우 이길 확률이 0.5094 로 나왓는데 저랑 조금 차이가 나는 이유는 정확히 계산하는 알고리즘 차이도 있지만 난수 생성에도 있습니다. 제가 사용한 난수는 python random 모듈의 shuffle을 사용했는데 python의 random 모듈이 난수 생성 성능이 그다지 좋지 않다고 나와 있습니다. python document 에서는 random 모듈 보단 urandom 을 사용하라고 권장을 합니다.

좀 아쉽긴 하지만 추후에 이런 Monte Carlo 시뮬레이션 문제가 나오면 numpy나 matlab 같은 전문 툴을 이용해서 좀 더 정확히 구현을 해야 할 것 같습니다.