[129] 미니맥스 알고리즘을 사용하여 틱택토 게임 만들기

1. 틱택토 게임

3 X 3 판에 빈 칸을 골라, 플레이어가 번갈아가며 O와 X를 적습니다.

먼저 가로, 세로, 대각선 상에 3개를 연달아 놓으면 이기는 게임입니다.

오목의 간단한 버전이라고 생각해도 좋습니다.

https://ko.wikipedia.org/wiki/틱택토

틱택토 - 위키백과, 우리 모두의 백과사전

2. 미니맥스 알고리즘

미니맥스 알고리즘은 상대방과 자신의 모든 경우의 수를 탐색해서 최선의 수를 찾아내는 알고리즘입니다.

기본적인 아이디어는 상대방이 항상 나에게 가장 불리한 선택을 할 것이라고 가정하는 것입니다.

미니맥스 알고리즘은 DFS를 활용하여 가능한 모든 수를 탐색합니다.

이 후 깊이에 따라 내 차례인지 상대방 차례인지 파악한 후, 가치를 평가해 선택을 부모 노드에 적습니다.

이 과정을 다 마친 후 부모 노드에 기록되는 값이 최선의 선택을 했을 때 가치가 됩니다.

예를 들어 모든 경우의 수와 해당 경우의 가치를 위와 같이 트리로 나타냅니다.

깊이가 깊어질수록 몇 수 앞을 내다 본다고 이해하면 쉽습니다.

맨 아랫줄은 3수 앞(상대방 차례)입니다.

상대방은 각각 숫자가 적힌 선택을 할 수 있습니다.

그 윗줄은 2수 앞(내 차례)입니다.

이전에 상대방이 어떤 수를 낼 지 예측했으니, 나는 상대 수에서 더 큰 가치를 선택하면 됩니다.

그 윗줄(1수 앞)의 상대방은 내가 했던 선택에서 가장 낮은 가치를 선택(자신에게 유리하게)할 것입니다.

마지막으로 나는 가장 큰 가치를 선택(루트 노드)합니다.

총 11가지 중에 더 큰 가치들이 있었지만, 상대방이 방해를 하기 때문에 내가 가져갈 수 있는 가장 큰 가치는 3입니다.

3. 틱택토 게임 코드 만들기

가. 게임 상황 나타내기

우선 게임판의 빈 칸과 채워진 칸은 9자리 2진수로 나타내겠습니다.

따라서 빈 게임판은 \(000000000_{(2)}\)와 같고, 모든 칸이 채워졌을 때는 \(111111111_{(2)}\)와 같습니다.

O

편의상 위의 상황은 \(000000001_{(2)}\)라고 하고,

		O

위의 상황은 \(100000000_{(2)}\)입니다.

나. 게임 상황 출력하기

내가 놓은 자리와, 상대방이 놓은 자리를 가지고 현재 상황을 출력합니다.

작성된 자리를 확인하기 위해 2진수 논리연산의 쉬프트 연산과 마스크 연산을 사용했습니다.

내가 놓은 자리는 O, 상대방이 놓은 자리는 X로 표시했습니다.

그 외 게임판을 그리기 위해 조건문과 반복문을 적절히 사용합니다.

# 게임판 그리기
def paint_board(p1, p2):
  board = [" "] * 9
  for i in range(9):
    if (p1 >> i) & 1 == 1:
      board[i] = "O"
    elif (p2 >> i) & 1 == 1:
      board[i] = "X"
  for i in range(7):
    if i % 2:
      for j in range(3):
        print(f"|{board[i//2*3+j]}", end="")
      print("|")
    else:
      print("-------")
  return board

다. 승리 상황 파악하기

틱택토 게임은 가로, 세로, 대각선으로 연속해서 놓이면 이기므로, 이기는 상황은 다음 8가지 밖에 없습니다.

# 게임 승리 조건
goal = [
  0b111000000, 0b000111000, 0b000000111, # 가로로 3개 완성
  0b100100100, 0b010010010, 0b001001001, # 세로로 3개 완성
  0b100010001, 0b001010100 # 대각선으로 3개 완성
]

라. 이겼는지 판단하기

2진수의 논리연산 중 마스크 연산(AND)을 활용하여 현재 상황이 이겼는지, 아닌지 확인합니다.

any 함수는 요소 중 하나라도 참이면 참을 반환합니다.

# 이겼는지 확인
def is_win(player):
  return any(player & mask == mask for mask in goal)

마. 미니맥스 알고리즘 구현하기

내 상황과 상대방의 상황을 보고 한 수, 한 수 DFS 방법으로 거슬러 올라가며 상황을 평가합니다.

모든 칸에 작성이 되었는지 확인하는 것에 2진수 논리연산의 선택적 세트 연산(OR)을 사용했습니다.

놓을 수 있는 자리를 확인하는 것에는 마스크 연산(AND)과 쉬프트 연산을 사용했습니다.

# 미니맥스 알고리즘
def minmax(p1, p2, turn):
  if is_win(p2):
    if turn:
      return 1 # 이기는 상황의 가치(1)
    else:
      return -1 # 지는 상황의 가치(-1)
  board = p1 | p2
  if board == 0b111111111:
    return 0 # 비기는 상황의 가치(0)
    
  w = [i for i in range(9) if board & (1 << i) == 0] # 놓을 수 있는 자리
  if turn:
    # 내 차례였으면 다음엔 상대방이 최소값을 선택
    return min([minmax(p2, p1 | (1 << i), not turn) for i in w])
  else:
    # 상대방 차례였으면 다음엔 내가 최대값을 선택
    return max([minmax(p2, p1 | (1 << i), not turn) for i in w])

바. 게임 완성하기

위에서 만든 변수와 함수를 사용하여 게임을 완성합니다.

# 번갈아 두기
def play(p1, p2, turn):
  # 게임 종료 여부 확인
  if is_win(p2):
    print("졌습니다!") if turn else print("이겼습니다!")
    return
  board = p1 | p2
  if board == 0b111111111:
    print("비겼습니다!")
    return

  if turn:
    print("당신 차례!!")
    pos = int(input("위치를 입력하세요.: "))
  else:
    print("컴퓨터 차례!!")
    # 놓을 수 있는 위치 찾기
    w = [i for i in range(9) if board & (1 << i) == 0]
    # 미니맥스 알고리즘으로 위치별 가치 판단
    r = [minmax(p2, p1 | (1 << i), not turn) for i in w]
    # 최고 가치 위치 선택
    pos = w[r.index(max(r))]
    print(f"컴퓨터는 {pos} 위치를 선택했습니다.")
  p1 |= 1 << pos
  paint_board(p1, p2) if turn else paint_board(p2, p1)
  play(p2, p1, not turn)

사. 게임 초기화

위에서 만든 함수를 초기값으로 실행시킵니다.

play(0, 0, True)

4. 실제로 해보기

replit에 위 코드를 작성하여 만들었습니다.

입력에 대한 유효성 검사 기능은 없기 때문에 올바르지 않은 입력은 에러가 나올 수 있습니다.

https://replit.com/@teacher-kiwi/tic-tac-toe?v=1

tic-tac-toe

기능 상의 미흡한 점은 있지만, 미니맥스 알고리즘을 이용하여 게임을 만들어보았습니다.

코드를 수정하여 더 개선해봐도 재밌을 것 같습니다.

5. 자바스크립트로 구현하기

웹 브라우저는 프로그래밍 언어인 자바스크립트를 실행시킬 수 있습니다.

따라서 위에서 만든 코드를 자바스크립트로 코드로 만들면 웹 페이지로 배포할 수 있습니다.

예전에 뷰.js 공부를 하며 만든 틱택토 게임입니다.

개발자 모드에서 script 태그를 확인하면 자바스크립트 코드를 확인할 수 있습니다.

 

https://teacher-kiwi.github.io/study-data//vue_study/2%EC%A3%BC%EC%B0%A8/index2.html

틱택토