전략 게임들을 이기는 방법

넷플릭스 오리지널 시리즈로 화제가 된 퀸스 갬빗(Queen's Gambit). 예고편과 썸네일을 보고 음~ 체스랑 관련된 얘기겠구나 라는 생각을 했고, 첫 화를 보기 시작했어. 체스는 사실 이전부터 여러 영화나 드라마에서 언급된 소재이기도 해. 음, 해리포터와 마법사의 돌에서는 볼드모트를 만나기 전에 해리, 헤르미온느, 론이 움직이는 체스판 위에서 스스로 말이 되어 게임을 하기도 했지? 체스를 일종의 흑과 백으로 싸우는 보드게임으로 보면, 바둑이나 장기랑 비슷한 성격을 띄기도 하고. 바둑은 특히 한국 영화에서 종종 다뤄지기도 했고, 드라마로 방영된 웹툰 미생에서도 바둑 용어가 많이 언급되지. 

  제목이기도 한 '퀸스 갬빗' 또한 체스 용어로 언급되기도 했어. 잠깐, 퀸스 갬빗이 어떤 뜻이냐고? 먼저 그 전에, 체스 오프닝에 대해 알아보자. 

체스 오프닝 

퀸스 갬빗에서도 베스는 '모던 체스 오프닝' 이라는 책을 읽어. 체스 오프닝이란 체스 게임 초반부에 두는 수들을 종류별로 나눈 것을 말해. 예를 들면, 맨 앞줄에 폰을 이용해서 수를 두는 것을 위주로 할 수도 있고, 아니면 전략에 따라 아니면 나이트나 룩, 비숍, 퀸 등을 게임 초반부 부터 내세울 수 있기도 하고. 

이런 '오프닝'을 말할 때, 이름을 붙인 사람이나 지명, 국적의 고유 명사를 많이 이용해. 모든 이름들이 그렇다는 건 아니지만. [고유 명사] + [게임의 종류 명명법] 의 조합으로 오프닝의 이름을 붙여. 각각 오프닝의 성격에 따라 게임, 오프닝, 바리에이션, 디펜스, 어택, 갬빗, 카운터갬빗, 시스템, 안티, 리버스 등의 이름을 붙이면 아래와 같은 예시들이 만들어지지. 

이때, 갬빗 이라는 말은, 폰을 희생하면서 뒤의 기물들에게 길을 열어주는 것을 말해. 즉, 퀸스 갬빗은 보통 폰을 D4, D5 나 C4 로 이동시키면서 뒤의 퀸이 갈 수 있는 길을 열어주는 게임 초반의 전략 방법이야.

이처럼 맨 처음 게임에서 첫 수를 둘 때, 처음 시작하는 플레이어가 선택한 폰이 갈 수 있는 경우의 수만 구해도, 8x2 즉 16가지가 나와. (폰은 처음에 한번에 두 칸을 갈 수 있으니까) 체스에서 한 기물이 갈 수 있는 룰이 정해져 있으니까, 몇번의 이동 안에 나타날 수 있는 체스판의 종류는 한정적이야. 그럼 어떤 체스판이 주어 졌을 때, 승리하기까지 걸리는 최소의 이동 횟수도 알 수 있을까? 아니면, 상대방이 어떤 수를 놓느냐에 상관 없이 항상 승리할 수 있는 체스판의 수도 알 수 있을까? 

체스처럼 어떤 유한하고 틀을 벗어나지 않는 규칙이 있고, 한 시행을 셈으로써 시행의 횟수를 잴 수 있을 때, 위처럼 주어진 어떤 문제를 풀수 있어. '어떤 체스판이 주어졌을 때, 흑의 플레이어가 승리할 수 있는 최소의 이동 횟수는 얼마인가?' 라는 문제를 푼다고 하자. 이 때, 이 문제를 푸는 절차나 방법을 알고리즘이라고 불러. 사실 알고리즘은 내가 평소에 일을 할 때도 엄~청 많이 쓰는 단어인데, 생각보다 주변에서 '도대체 알고리즘이라는 단어의 뜻이 뭐야?' 라고 물어본 경험이 많았어. 더 간단하게 생각해보면, 내가 배가 고프고, 냉장고 안에 바나나가 있다는 것을 인지하고 있고, 끝내 냉장고 안에 바나나를 어떻게 먹지? 라는 질문을 가진다고 하자. 

1. 냉장고 앞으로 가서 선다.
2. 냉장고의 문을 연다.
3. 냉장고 안의 바나나를 손으로 집는다.
4. 바나나의 껍질을 깐다.
5. 바나나 속 알맹이를 입에 넣는다.

이런식으로 작은 행동이나 절차를 명확하고 간단하게 나타낸 방법을 알고리즘이라고 말해. 보통 일상생활에서 부딪치는 문제들은, 예상치 못한 변수나 고려해야할 주변 상황들이 엄청 많잖아? 알고리즘화 하려면 이런 것들을 단순화하여 절차로 나타낼 수 있어야 해. 

체스와 알고리즘

체스는 유한한 공간에서 갈 수 있는 경우의 수가 정해져 있기 때문에, 알고리즘과 관련된 문제가 많아. 예를 들면, 나이트의 여행 (Knight's tour) 라고 불리는 문제를 풀기 위해 다양한 알고리즘을 생각해낸 수학자들이 있었어. 체스에서 기사를 뜻하는 나이트는 한 이동에서 총 두 칸을 이동할 수 있는데, 한 칸은 직선으로, 다른 한 칸은 대각선으로만 이동할 수 있어. 그럼, 나이트가 체스 말의 모든 칸을 딱 한 번씩이라도 들르기 위해서는, 어떻게 이동하여야 할까? 이를 어떻게 계산할 수 있을까? 바로 이 질문이 기사의 여행이라는 문제가 던지는 물음이야. 

 또 다른 예시를 들어보자면, 여덟 퀸의 문제(혹은 N 퀸의 문제, N-queens problem) 라는 문제도 있어. 체스판에 8개 혹은 N개의 퀸을 배치하여, 서로가 서로를 잡아먹지(?) 않을 수 있게 배치하는 거야. 퀸은 체스판에서 수직/대각선으로 양 끝까지 이동할 수 있는데, 이를 어떻게 배치하면 서로가 서로의 이동 경로에 위치하지 않을까? 물어보는 문제야. 

나이트의 여행 같은 경우, 프루트 포스, 분할 정복 알고리즘 등이 쓰일수 있고, 여덟 퀸의 문제 같은 경우 백트래킹이 쓰일 수도 있어. 아마 알고리즘 이름을 들으면 다들 처음 들어보네? 싶지만, 내용을 실상 들어보면 머릿속으로 생각해 볼 수 있는 방법들일거야. 이처럼, 이미 사람들이 많이 사용하고 논리를 정립해놓은 알고리즘 같은 경우에는 이름을 붙이기도 해. 

이번 주에는 체스와 함께 알고리즘이 도대체 뭐람? 하는 내용을 간단히 다뤄봤어. 다음 주에는 오늘 언급한 알고리즘과, 우리가 생활 속에서 많이 들어본 알고리즘에 대해 한번 조금 더 자세히 살펴볼까해. 더 생각해보고 싶은 주제가 있으면, 그리고 글에 대한 의견이 있다면 인스타그램으로 피드백을 줘! 

매주, 매월, 글을 받아보고 싶다면? 👉🏻 구독자가 되어주세요!
읽고 싶은 주제가 있나요? Instagram DM으로 알려주세요! 👉🏻 @the_toilet_papers