9.16 예제 : 틱택토(Python)

문제 출처 : algospot.com :: TICTACTOE

algospot.com :: TICTACTOE

---

1. 문제 분석

(1) 문제 정의

• canWin(board) = 틱택토 게임판이 현재 board일 때, 이번 차례인 사람이 이길 수 있는지 반환

(2) 메모이제이션 방법 구상하기

• board를 표현하고 이를 cache에 저장하기 위한 방법을 구상해야 한다.
• 게임판을 정수로 표현할 수 있다면 cache에 저장할 수 있다.
• 가장 간단한 방법으로 9자리의 3진수로 board를 표현한다.
• 3^9 = 19683이므로 시간과 공간에 제약없이 충분히 계산이 가능하다.

• 0 = 아무런 표시가 없다.
• 1 = O가 표시되어 있다.
• 2 = X가 표시되어 있다.

board의 9자리 3진수 표현의 예시

(3) 비기는 경우

1) 게임 결과는 총 3가지

• 틱택토는 두 플레이어가 비기는 경우가 존재한다.
• 따라서 문제 정의에서 참, 거짓을 통해 승패만을 반환하는 것은 불가능 하다.
• 따라서, 3가지 경우를 고려하여 그 값을 표현하는 방법으로 반환해야 한다.

1. 이번 차례인 참가자가 이길 수 있는 경우
2. 이길 수는 없지만 최선을 다하면 비길 수 있는 경우
3. 최선을 다해도 상대가 실수하지 않으면 질 수 밖에 없는 경우

2) 문제를 다시 정의하기

• canWin(board) = 틱택토 게임판이 현재 board 일 때, 이번 차례인 사람이 이길 수 있으면 1, 비길 수 있으면 0, 질 수 밖에 없으면 -1을 반환

 

• 이제 현재 차례인 사람이 다음 board의 상태(상대 플레이어 차례의 board)에 따라 -1이면 우선적으로 그 쪽을 택한다.(상대 플레이어가 질 수 밖에 없는 경우)
• -1이 나오지 않는다면 0이라고 선택하고 그 마저도 안될 경우 1을 택해야 한다.
• 문제 정의만 본다면 1이 나오도록 우선 선택해야 할 것 같지만, 상대 차례의 board를 보고 하는 것이기 때문에 -1을 우선적으로 봐야 한다.
• 그리고 마지막에 이 값의 양음수를 변환하면 비로소 내가 이길 수 있으면 1, 지게 되면 -1을 반환하게 된다.

2. 구현

(1) 설계

• 기저 사례는 게임이 끝난 상태이다.
• 이를 통해, 입력 받은 board가 게임이 끝난 상태인지 혹은 한 수만에 게임이 끝나는지 확인하기 용이하다.
• cache 테이블의 초기값은 -2가 되야한다.(초기 값은 메모이제이션 할 때 저장될 수 없는 값을 선택해야 하기 때문에 자명한 이야기)
• 구현에 있어서 직관성을 높이기 위해 누구의 turn인지 canWin( )에 함께 전달한다.(문제에서 항상 X가 선 플레이어라고 이야기했으므로 board만 봐도 사실 누구의 차례인지 알 수 있지만 누구의 턴인지 넘기므로 한 눈에 확인할 수 있다. 그리고 turn은 메모이제이션에 적용되지 않는다.)

(2) 코드

1) isFinished( ) : 게임의 종료여부를 검사

# turn에 해당하는 사람이 한 줄을 완성했는지 검사
def isFinished(board, turn):
    # 가로줄 확인
    for r in range(3):
        for c in range(3):
            if board[r][c] != turn:
                break

            # c가 2가 될 때 까지 반복문을 중단하지 않았다면 해당 가로줄은 모두 turn과 같은 모양
            if c == 2:
                return True
            
    # 세로줄 확인
    for c in range(3):
        for r in range(3):
            if board[r][c] != turn:
                break

            # r이 2가 될 때 까지 반복문을 중단하지 않았다면 해당 세로줄은 모두 turn과 같은 모양
            if r == 2:
                return True

    # 우하향 대각선 확인
    for r in range(3):
        if board[r][r] != turn:
            break

        if r == 2:
            return True
    
    # 좌하향 대각선 확인
    for r in range(3):
        if board[r][2-r] != turn:
            break

        if r == 2:
            return True

    return False

• 단순하게 게임판의 가로줄, 세로줄, 좌하향 대각선, 우하향 대각선을 모두 검사하면서 같은 모양의 표식이 3가지 존재하는지 검사하는 역할을 수행
• 표식의 개수를 확인하기보다는 반복문의 iterator가 중간에 끊이지 않고 마지막까지 도달했다면 어떤 표식이 3가지 연속으로 존재한다는 것을 알 수 있음

2) bijection( ) : 3*3 크기의 게임판을 9자리의 3진수 숫자 구성으로 표현하고 다시 이를 10진수 숫자로 변환

# 3*3 크기의 board 상태를 9자리의 3진수 숫자 구성으로 표현하고
# 이를 십진수 숫자로 변환하는 함수
# ex) board : 010/020/100 -> 2358
def bijection(board):
    result = 0

    for r in range(3):
        for c in range(3):
            result *= 3
            
            if board[r][c] == 'o':
                result += 1
            elif board[r][c] == 'x':
                result += 2

    return result

• board를 9자리 3진수로 표현하고 이를 메모이제이션에 사용할 수 있도록 10진수로 변환하는 함수
• 게임판이 아래와 같을 때, 9자리 3진수로는 010020100으로 표현되고 bijection( )을 거쳐 2358이 된다.
• borad[0][0]=0인 경우 0*3+0=0 부터 시작함을 생각하고 전개하면 아래와 같이 10진수로 표현할 수 있다.

bijection( ) 함수의 진행 과정 예시

3) canWin( )

# 내가 이길 수 있으면 1, 비길 수 있으면 0, 질 수 밖에 없으면 -1
def canWin(board, turn):
    # 기저 사례 : 마지막에 상대가 이기는 수를 둘 경우(패배)
    if isFinished(board, ('o'+'x').replace(turn, "")):
        return -1

    # 메모이제이션
    if cache[bijection(board)] != -2:
        return cache[bijection(board)]

    # 모든 반환 값의 min 값을 취함
    minValue = 2
    for r in range(3):
        for c in range(3):
            if board[r][c] == '.':
                # python에서 문자열의 일부를 직접 변환하는 것은 불가능하기 때문에 문자열 자체를 바꿔야 한다.
                temp = list(board[r]) # 원 문자열을 리스트로 변환하고
                temp[c] = turn # 바꾸고자 하는 부분의 원소를 변경하고
                board[r] = ''.join(temp) # 다시 문자열로 만들어 기존 문자열을 대체

                minValue = min(minValue, canWin(board, ('o'+'x').replace(turn, ""))) # 상대방의 수에 대한 재귀 호출 진행
                
                # 원래 게임 보드판 형태로 복원
                temp[c] = '.'
                board[r] = ''.join(temp)

    if minValue == 2 or minValue == 0:
        cache[bijection(board)] = 0
        return cache[bijection(board)]

    # minValue(상대방의 수)가 -1이면 cache는 1이 저장되어 이길 수 있다는 의미가 되고
    # minValue가 1이면 cache에는 -1이므로 진다는 의미가 된다.
    cache[bijection(board)] = -minValue
    return cache[bijection(board)]

• cache에 저장할 때 bijection(board)로 반드시 10진수 형태로 변환하는 것에 유의해야 한다.

 

• C++를 사용하는 교재와 달리 Python으로 해당 문제를 해결하기 위해서는 문자열 변환에 대해 조금 다른 방법을 사용해야 한다.
• 문제를 입력할 때 행을 통째로 문자열로 입력해 직접적으로 borad[r][c]의 값을 교체할 수 없다.
• 미래의 수를 예측하기 위해 표식을 바꾸는 과정에서 행에 입력된 문자열을 리스트로 바꾸고 열에 해당하는 표식을 교체하고 다시 행을 문자열로 바꾸는 과정이 필요하다.

 

• 또한, turn을 확인하는 과정도 C++와는 방법이 조금 다르다.
• turn에 사용되는 인수는 문자 'o'와 'x'인데 문자열 함수인 replace( )를 통해 'ox'문자열에서 turn의 문자를 빈 문자로 교체해 다음 차례 플레이어의 수를 계산할 수 있다.

 

• 함수의 마지막에 값에 양음수 전환을 해서 현재 turn인 사람의 승무패 결과를 메모이제이션 한다.

4) 문제 입-출력

for tc in range(int(input())):
    board = []
    x_num = 0
    o_num = 0
    for r in range(3):
        board.append(input())
        # 현재 게임판에 존재하는 x와 o의 개수를 저장
        for c in range(3):
            if board[r][c] == 'x':
                x_num += 1
            elif board[r][c] == 'o':
                o_num += 1

    # 틱택토는 항상 x가 선플레이어이므로 x가 더 많으면 o 차례, 같은 경우는 x 차례
    if x_num > o_num:
        turn = 'o'
    else:
        turn = 'x'
    
    # cache 초기화
    # 19683 = 3^9
    # 게임판이 모두 x여서 3진수 222/222/222로 표현될 때 이를 10진수로 변환하면 19682이 된다.
    cache = [-2] * 19683

    answer = canWin(board, turn)
    # 비기는 경우
    if answer == 2 or answer == 0:
        print("TIE")
    # 이기는 경우
    elif answer == 1:
        print(turn)
    # 지는 경우
    else:
        print(('o'+'x').replace(turn, ""))

• x가 선플레이어인 점을 감안해 문제 입력 당시 x와 o의 수 비교를 통해 게임판을 통해 누가 지금 차례인지 알 수 있다.
• o의 수가 적으면 무조건 o의 차례가 되고 그 나머지 경우는 x의 차례가 된다.

5) 시간 복잡도

• 전체 게임판의 경우의 수는 3^9이고 한 부분 문제를 해결하는데 3^2의 시간이 걸린다.
• 따라서 해당 문제의 시간 복잡도는 O(3^11)가 되는데 실제로 게임판에 존재할 수 없는 경우(한 가지 표식이 9칸을 모두 차지한 경우 등)를 제외하면 실제로는 이보다 빠른 시간이 소요된다.

---

3. 게임 트리

• 게임 트리 : 게임의 모든 상태를 트리의 형태로 그린 것
• 게임 트리를 그릴 수 있는 문제들은 지난 상태로 돌아갈 수 없는 게임들 뿐이다.
• 더 자세한 내용은 교재의 333~336 페이지를 통해 확인할 수 있습니다.

---

4. 후기

  예전에 인공지능 강의에서 팩맨 게임을 통해 게임 트리에 대한 개념을 공부한 적이 있었는데 이를 알고리즘 문제를 해결하는 과정에서 다시 마주하게 되었다. 다행히도 직접 게임 트리를 구현하는 것은 아니고 개념을 통해 문제를 접근하는 방법(?)을 응용하는 문제였다. 다른 교재에서 이렇게 미래의 경우의 수를 확인하는 문제를 푼 적이 있었는데 그 문제는 메모이제이션이 아니었던 것으로 기억한다. 왜냐면 이렇게 진수 변환을 통해 메모이제이션을 하는 문제들은 이 교재에서 처음 접했기 때문이다.

  어떻게 보면 이 문제도 정수 이외의 값을 메모이제이션 하는 방법의 연장선이다. 이전에는 집합을 비트 마스크 기법을 통해 메모이제이션 했다면 이 문제는 2차원의 집합을 메모이제이션하는 방법에 대한 문제다. 따라서, 이 메모이제이션 기법 역시 반드시 기억하고 있다가 써먹어야 할 필요성이 있다고 생각된다.

  이 책을 공부하면서 기업의 코딩 테스트 자체 보다는 대회와 실제 알고리즘의 사용에 있어서의 요소들을 정말 깊게 파고들고 있다는 생각이 든다. 그래서 아마 언젠가 뒷 부분을 공부하고 포스팅할 때는 그냥 내 입맛에 맞춰서 내용을 건너뛰게 되는 경우가 있을 것 같다. 혹은 내가 다른 방향으로 진로를 걷게 된다면 취미 삼아 공부하는 뜻으로 그 부분도 공부하고 포스팅하게 되지 않을까 싶다...

---

github : Algorithmic_Problem_Soving_Strategies/example9_16.py at main · LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies (github.com)

LeeSeok-Jun/Algorithmic_Problem_Soving_Strategies