2048게임 AI 만들기 with Python

제작동기

 💡 2048게임 어떻게 하면 쉽게 깰수 있을까 생각하다 공략집을 보게 되었는데 이 공략대로 코드를 짜면 2048게임을 혼자서 깰수 있는 AI를 만들수 있을것 같다 생각해서 제작하게 되었습니다.

 

2048이란?

상하좌우로 움직여가며 같은 라인에 있는 숫자들을 합쳐 2048을 만드는것이 목표인 게임입니다.

 

---

📟Expectimax알고리즘

Expectimax 알고리즘은 게임 트리를 평가하고 최적의 수를 결정하는 데 사용되는 기술적인 알고리즘입니다.

미니맥스 알고리즘의 확장 버전으로 미니맥스는 플레이어와 상대 플레이어의 교대로 게임 트리를 탐색하여 최선의 수를 결정하는 반면, Expectimax는 확률적인 요소를 포함한 게임에서 트리를 탐색합니다. 이로인해 high risk high return입니다.

📜Heuristic(문제를 해결할 수 있는 방법)

Big - 다음 행동이 더 큰 숫자를 만들수 있는지

Emptiness(공허함)- 다음 행동이 얼마나 많은 빈칸들을 만들어낼 수 있는지

Monotonicity(단조로움) - 큰 타일들이 구석에 있는지

Smoothness(부드러움) - 옆 타일들과 숫자가 비슷한지

📝순서도

1. Pygame 초기화 및 게임 화면 설정: Pygame 라이브러리 초기화, 게임 창의 제목과 아이콘 설정, 게임 화면 크기 설정.
2. 게임 매니저 초기화: 게임 상태 관리, 게임 데이터(점수와 상태) 저장 디렉토리 설정.
3. 게임 루프 시작: 게임이 실행되는 동안 반복적으로 수행되는 부분. 게임 상태 업데이트, 화면 다시 그리기, 사용자 입력 처리.
4. 자동 플레이 알고리즘 실행: 현재 게임 상태 기반으로 최적의 움직임 계산 및 실행.
5. 게임 종료 조건 체크: 사용자 게임 종료 요청 또는 게임 오버 조건 충족 시.
6. Pygame 정리 및 게임 종료: 게임 루프 종료 후 Pygame 리소스 정리 및 프로그램 종료.

📋코드 설명

# grid sum
  big_t = np.sum(np.power(grid, 2))

Big에 해당하는 코드이며 grid 배열의 각 요소를 제곱한 후, 그 결과의 총합을 big_t에 저장합니다.

smoothness = 0
  s_grid = np.sqrt(grid)

  smoothness -= np.sum(np.abs(s_grid[:, 0] - s_grid[:, 1]))
  smoothness -= np.sum(np.abs(s_grid[:, 1] - s_grid[:, 2]))
  smoothness -= np.sum(np.abs(s_grid[:, 2] - s_grid[:, 3]))
  smoothness -= np.sum(np.abs(s_grid[0, :] - s_grid[1, :]))
  smoothness -= np.sum(np.abs(s_grid[1, :] - s_grid[2, :]))
  smoothness -= np.sum(np.abs(s_grid[2, :] - s_grid[3, :]))

Smoothness에 해당하는 코드이며 s_grid에 grid를 루트씌운값을 저장합니다.

smoothness에 세로 0행-1행, 1행-2행…해서 옆에 있는 배열과 빼준값을 smoothness에 저장해줍니다

smoothness값이 클수록 더 부드러운 배열입니다

# monotonicity
  monotonic_up = 0
  monotonic_down = 0
  monotonic_left = 0
  monotonic_right = 0
#가로
  for x in range(4):
    current = 0
    next = current + 1
    while next < 4:
      while next < 3 and not grid[next, x]:
        next += 1
      current_cell = grid[current, x]
      current_value = math.log(current_cell, 2) if current_cell else 0
      next_cell = grid[next, x]
      next_value = math.log(next_cell, 2) if next_cell else 0
      if current_value > next_value:
        monotonic_up += (next_value - current_value)
      elif next_value > current_value:
        monotonic_down += (current_value - next_value)
      current = next
      next += 1
#세로
  for y in range(4):
    current = 0
    next = current + 1
    while next < 4:
      while next < 3 and not grid[y, next]:
        next += 1
      current_cell = grid[y, current]
      current_value = math.log(current_cell, 2) if current_cell else 0
      next_cell = grid[y, next]
      next_value = math.log(next_cell, 2) if next_cell else 0
      if current_value > next_value:
        monotonic_left += (next_value - current_value)
      elif next_value > current_value:
        monotonic_right += (current_value - next_value)
      current = next
      next += 1
#단조로움 계산
  monotonic = max(monotonic_up, monotonic_down) + max(monotonic_left, monotonic_right)

위아래양옆 방향으로 단조로운지 확인한다. 4개의 행방향으로 반복문을 돌며 현재 cell의 값과 다음 cell의 값을 비교한다. 그 차이값을 monotonic_up/down/left/rigt에 더해준다. 그 후 다음 행으로 넘어갑니다.

윗방향과 아랫방향 중 더 큰 값과 왼쪽과 오른쪽 방향중 더 큰 값을 더해서 단조로움을 계산합니다.

# weight for each score
  empty_w = 100000
  smoothness_w = 3
  monotonic_w = 10000

  empty_u = n_empty * empty_w
  smooth_u = smoothness ** smoothness_w
  monotonic_u = monotonic * monotonic_w

  score += big_t
  score += empty_u
  score += smooth_u
  score += monotonic_u

  return score

각각의 계산결과에 가중치를 곱해서 score에 저장해줍니다.

def maximize(grid, depth=0):
  best_score = -np.inf
  best_action = None

  for action in range(4):
    moved_grid = deepcopy(grid)
    moved_grid, moved, _ = move(moved_grid, action=action)

    if not moved:
      continue

    new_score = add_new_tiles(moved_grid, depth+1)
    if new_score >= best_score:
      best_score = new_score
      best_action = action

  return best_action, best_score

maximize함수는 게임보드에서 가능한 모든 움직임을 고려하여 최적의 움직임을 찾는 알고리즘을 구현한다. grid랑 depth를 입력 매개변수로 받고 새로운 움직임이 이전 최고 점수보다 높은 점수를 가져올 경우, 최고 점수와 최적의 액션을 업데이트 합니다. 그 후 best_action, best_score를 반환합니다.

# early stopping
  if n_empty >= 6 and depth >= 3:
    return evaluation(grid, n_empty)

  if n_empty >= 0 and depth >= 5:
    return evaluation(grid, n_empty)

  if n_empty == 0:
    _, new_score = maximize(grid, depth+1)
    return new_score

빈칸이 6개 이상 있으면 여유로우니까 3수 앞만 보고 빈칸이 6개 이하면 5수 앞을 보게해서 더 좋은 선택을 하게 해줍니다. 만약 빈칸이 없으면 maximize 함수를 호출하여 가능한 다음 움직임 중 최적의 움직임을 찾고 그에 따른 점수를 반환합니다.

이렇게 했을때의 점수는 new_score에 저장해줍니다.

for x, y in fcs:
    for v in [2, 4]:
      new_grid = deepcopy(grid)
      new_grid[y][x] = v

      _, new_score = maximize(new_grid, depth+1)

      if v == 2:
        new_score *= (0.9 / n_empty)
      else:
        new_score *= (0.1 / n_empty)

      sum_score += new_score

  return sum_score

빈칸이 있는곳의 위치마다 2, 4를 넣어보면서 보드의 성능을 계산해봅니다. 2가 나올 확률이 90%이므로 0.9를 곱해주고 4가 나올 확률이 10%이므로 0.1을 곱해줍니다. 이렇게 했을때의 총 점수를 sum_score에 더해준후 총 점수를 반환합니다.

이렇게 계속해서 깊이를 늘려가며 maximize를 호출하다가 가장 큰 값을 가진 행동을 행하도록 해줍니다.

📊시연 영상

https://www.youtube.com/watch?v=-JPwb8R_8Eg

느낀점

💡 프로젝트를 진행하는 동안 어려움이 많았는데 프로젝트를 무사히 끝내서 뿌듯하고 기분이 좋습니다. 2048게임을 할때는 아무런 생각없이 했는데 여러 공략들을 보니 생각이 많이 필요한 게임이란것을 느꼈고 그런 공략들을 python으로 구현할수 있다는게 신기했습니다. 사람이 깰려면 꽤 시간이 걸리지만 AI 하면 5분도 안걸리고 깰 수 있는다는것에서 AI가 대단하다고 느끼면서도 경각심이 생기는 프로젝트였습니다. 다음번에는 실력을 더 키운다음에 더 높은 최고점수에 도달할 수 있는 AI를 만들어보고 싶습니다.

 

코드

https://github.com/chaeheetae/2048-AI

참고

https://stackoverflow.com/questions/22342854/what-is-the-optimal-algorithm-for-the-game-2048/22389702#22389702

https://www.youtube.com/watch?v=w8cClCa069E

https://velog.io/@j_aion/CS-188-Note3-Expectimax

https://pypi.org/project/2048/