체스는 매우 단순한 게임임. 대각선으로 움직이는 비숍, 직선으로 움직이는 룩, 모든 방향으로 움직이는 퀸, 모든 방향으로 한 칸 씩만 움직이는 킹, 잡을 땐 대각선, 움직일 땐 직선으로만 움직일 수 있는 폰. 물론 앙파상, 캐슬링, 승격, 스테일메이트 등 몇몇 좀 복잡한 룰이 있긴 하지만 어쨌든 체스 그 자체는 7살짜리도 이해할 수 있을 정도로 쉬운 게임임. 하지만 그 경우의 수는 무한에 가깝다고 해도 무방할 정도야. 체스의 가능한 포지션 개수가 우주의 원자 개수보다 많다는 이야기도 있으니까. 그런데 이렇게 체스의 경우의 수를 생각해보면 문득 드는 생각이 있지. 체스는 다른 게임과 비교했을 때 어느 정도로 복잡할까? 물론 우리가 감히 범접할 수 없는 엄청난 숫자겠지만, 그래도 서열이 궁금하잖아. 과연 체스는 장기보다 경우의 수가 많을까? 혹은 체커와는? 오셀로는 어떨까? 오목은? 오늘 글은 이에 대해서 알아보려고 함.

1. 복잡함을 정의해보자

복잡한 게임과 복잡하지 않은 게임은 일견 단순해 보임. 틱택토는 누가 봐도 단순한 게임이고, 바둑은 누가 봐도 복잡한 게임임. 하지만 복잡함의 정도는 이렇게 축이 하나만 존재하는 수직선상의 개념이 아님. 오목을 예로 들어보자. 오목은 어떻게 보면 바둑만큼 복잡한 게임임. 바둑판보다 조금 작은 판을 쓰고, 바둑만큼 무궁무진한 포지션이 가능함. 근데 오목이 바둑만큼 경우의 수가 많냐고 물어보면 그건 아님. 왜냐? 오목은 강제수가 많거든. 바둑도 물론 강제수가 나올 때가 있지만 오목은 해보면 알겠지만 강제수가 빈번하게 나옴. 오히려 강제수가 아닐 때가 더 적다고 느낄 정도로. 이처럼 강제수가 얼마나 많이 나오냐는 게임이 얼마나 복잡한지에 영향을 줌. 강제수가 적으면 적을수록 복잡하고, 많으면 많을수록 단순한 게임이겠지. 또한 게임 길이 역시 복잡도에 영향을 준다는 걸 알 수 있음. 체스는 기본적으로 체스류 게임 중에서 가장 빨리 끝나는 편임. 보드는 작고, 기물은 빠르니까. 당연히 게임이 길면 길수록 경우의 수 역시 늘어나는 걸 알 수 있음. 이처럼 게임이 복잡하다는 건 기본적으로 1차원적으로 정의하는 것이 아니라 몇 개의 변수를 고려해야 함. 그리고 이미 무엇을 고려해야할지 수학자들이 정리해놨음. 바로 상태공간 복잡도, 게임트리 복잡도임. 그래서 먼저 이것들이 뭔지에 대한 설명을 하고 글을 진행할께

1) 상태공간 복잡도(state-space complexity)

상태공간 복잡도는 간단하게 말하면 포지션의 개수를 의미함. 체스를 예를 들어보자면 폰은 백랭크가 아닌 이상 어디에든 있을 수 있음. 또한 나이트 역시 어디에나 있을 수 있고. 하지만 비숍은 반드시 다른 색 칸에 있어야 하고, 흑 차례일 때는 백 킹이 잡히는 곳에 있으면 안되고 반대의 경우도 마찬가지임. 이처럼 가능한 모든 포지션의 개수가 바로 상태공간 복잡도임. 참고로 체스는 7개 기물이 있는 경우에 한해서 모든 포지션과 그 포지션일 때의 최선수가 풀렸음. 이걸 엔드게임 테이블베이스라고 하는데 7개 기물일 때의 엔드게임 테이블베이스의 용량은 100TB임ㅋㅋ 체스 기물이 1개씩 더 늘어날 때마다 경우의 수가 폭증하기 때문에 32개가 다 있는 체스가 풀리기 까지는 아직 한~~~참 남았다고 생각하면 됨.

2) 게임트리 복잡도(game-tree size)

위의 상태공간 복잡도가 포지션의 개수를 의미한다면, 게임트리 크기는 둘 수 있는 리걸 무브의 개수를 생각하면 됨. 바둑을 예로 들면, 흑이 맨 처음 둘 때 합법적으로 둘 수 있는 경우의 수는 19*19=361개임. 그리고 그 다음 백이 합법적으로 둘 수 있는 경우의 수는 아까 흑이 둔 곳을 제외한 360개이고, 그 다음은 350개, 그 다음은 349개... 이렇게 나아가는 거임. 이 때 게임트리 복잡도는 361*360*359*... 이렇게 나아가겠지. 반면 체스의 경우에 첫 수로 둘 수 있는 모든 경우의 수는 총 20가지임(첫 수에서 움직일 수 있는 기물은 폰과 나이트 밖에 없으니) 흑 역시 마찬가지지. 하지만 체스는 2번째 수부터는 조금 달라지는데 e4를 뒀을 경우는 비숍과 퀸의 길이 열리기 때문에 가짓수가 28가지로 늘어남. 하지만 a3를 뒀다면 경우의 수는 오히려 18가지로 줄게 되지. 이처럼 각각의 경우의 수가 다르기 때문에 일괄적으로 묶어서 계산할 수가 없음. 수학에서는 이런 경우의 수를 표기하는 방법이 있음. 혹시 고등학교 때 배운 수형도 기억남? 그 수형도를 조금 고급스러운 말로 트리라고 함.

바로 요렇게 생긴 놈임. 이렇게 생긴 트리에서 저 동그란 걸 보고 노드라고 함. 저 노드가 화살표로 연결되어있지? 저걸 보고 간선이라고 함. 그리고 저 간선이 다른 노드랑 연결되어있는데 밑으로 내려갈수록 노드의 개수가 늘어나는 걸 볼 수 있음. 저 화살표로 이어져 있는 노드 중에서 위에 있는 놈을 부모 노드, 밑에 있는 놈을 자식 노드라고 함. 자식 노드는 여려개일 수 있지만 부모 노드는 하나밖에 없음. 그리고 맨 위의, 부모가 없는 최상위 노드를 루트라고 함. 그리고 반대로 트리 구조의 맨밑, 자식 노드가 없는 최하위 노드를 잎 노드라고 함. 이러한 트리 구조를 이용하면 체스의 경우의 수를 다 세아릴 수 있음. 그리고 체스의 경우의 수 트리는 매우매우매우 크지만 어쨌든 경우의 수는 유한할 테고, 그러면 결국 잎 노드가 있을 거임. 그 잎 노드의 개수가 바로 게임트리 복잡도임.

기본적으로 게임트리 복잡도는 상태공간 복잡도보다 경우의 수가 더 많은 편임. 왜냐하면 같은 포지션이더라도 예를 들어 퀸즈 갬빗 디클라인드는 클로즈드 게임으로 들어가는 경우가 있고, 인디언 디펜스로 우회해서 들어가는 경우도 있음. 이 경우 포지션은 결국 똑같아지지만, 순서는 달라지지? 이처럼 포지션이 같더라도 순서가 다른 경우가 있기 때문에 기본적으로 게임트리 복잡도가 상태공간 복잡도보다 많은 편임. 다만 오목 같은 건 예외인데, 강제수가 많아서 게임트리 복잡도는 낮지만 포지션은 매우 다양하게 나올 수 있다보니 게임트리 복잡도가 상태공간 복잡도보다 더 적음.

2. 복잡도 순위

자, 이제 복잡도를 고려할 때 저 두개를 고려해야하는 것을 알 수 있음. 그러면 과연 우리가 아는 게임의 복잡도는 어느정도일까?

Game complexity - Wikipedia 영어 위키피디아에서 이미 순위를 살펴볼 수 있음. 각각 상태공간 복잡도, 게임트리 복잡도, 가짓수, 그리고 복잡도 종류에 따라 유명한 추상전략게임을 정리해놓음. 그리고 위의 표는 위 사이트를 토대로 만든 표임. 저 숫자의 의미는 실제 숫자의 상용로그값으로, 자릿수랑 똑같다고 생각하면 됨. 다시 말해, 체스의 게임트리 복잡도는 123자리라고 생각하면 됨. 우리가 잘 아는 바둑, 쇼기, 장기, 샹치만을 일단 비교해보면 누구나 예상했듯이 바둑이 1등임. 게임트리 복잡도, 상태공간 복잡도 모두 압도적임. 그리고 쇼기가 게임트리 복잡도, 상태공간 복잡도 2위임. 소환이라는 개념이 있기 때문에 당연한 거라 볼 수 있음. 3위부터는 게임트리 복잡도냐 상태공간 복잡도냐에 따라 달라지는데, 상태공간 복잡도를 따지면 체스가 3위임. 보드 사이즈는 비교대상 중에서 가장 작지만, 기물의 개수가 많고 대다수의 기물이 움직임이 큰 데다가 킹이 움직임의 제약이 없다는 게 아무래도 포지션의 개수를 늘린 게 아닐까 싶음. 4위는 장기고 5위는 샹치임. 사실 샹치 룰을 몰라서 방금 나무위키에서 보고 왔는데 장기보다 샹치가 좀 더 기물 움직임에 제약이 많은 편이라서 그런듯. 반면 게임트리 복잡도의 경우에는 체스가 5위임. 기본적으로 게임 시간이 샹치와 장기에 비해 짧고 보드가 작아서 그런듯. 3위는 장기고 4위는 샹치임. 종합적으로 봤을 때, 체스는 샹치 다음으로 체스류 게임과 바둑 중에서는 단순한 게임이라고 할 수 있음.

파란색이 state-space complexity, 주황색이 game-tree complexity임. 로그 스케일이기 때문에 저 숫자 300은 실제로는 300자리라고 생각하면 됨.

그러면 이제 순위 매기는 게임의 개수를 좀 늘려서, 우리가 잘 아는 게임으로 한정지으면 어떨까? 단순히 체스류 게임과 바둑 뿐만 아니라, 오목이나 리버시 같은 유명한 추상전략게임을 다 포함해보면 먼저 상태공간 복잡도 1등은 당연히 바둑... 이라고 생각할 수 있는데 놀랍게도 바둑보다 경우의 수가 많은 게임이 있음. 바로 육목이라는 게임인데, 오목과 룰이 거의 똑같고 6개로 이으면 됨. 다만 다른 점이 있다면 한번에 돌을 2번 둠. 그래서 그런지 바둑보다도 더 상태공간이 크다는 특징이 있음. 2등은 당연히 바둑이고, 오목 역시 체스나 쇼기 보다 상태공간 경우의 수는 훨씬 많음. 반면 게임트리 복잡도에서는 1위가 arimaa라는 게임인데, 이 게임은 체스의 변형 게임임. 이 게임은 한턴에 기물을 4개 움직일 수 있는데, 아마 이것 때메 복잡도가 엄청 올라간 게 아닐까 생각이 듬. 3위는 바둑이고, 쇼기가 5위임. 그리고 대망의 꼴찌는 당연히 틱택토이고, 그 다음은 펜토미노와 사목이 뒤를 따름. 체커 역시 많이 낮은데 영미식 룰은 아예 최선의 수가 이미 풀린 걸로 알고 있음.

p.s. 복잡도의 의미

사실 이렇게 엄청나게 분석한 것 처럼 보이지만, 실상 저런 내용은 의미가 하나도 없음. 당장 오목을 예로만 들어봐도 상태공간 복잡도는 체스를 압도하고 게임트리 복잡도 역시 체스에 비해 엄청나게 낮은 것도 아님. 어? 말로만 들으면 갓겜이네? 라고 생각하겠지만 정작 그 오목은 무적수 회피 때메 온갖 괴상한 룰들이 추가되고 있음. 체커는 체스에 비해 복잡도가 엄청 낮지만, 그게 체커가 체스에 비해 쉽다는 걸 의미하진 않음. 오히려 게임의 재미는 이런 복잡도가 아닌 다른 거임. 선후간 밸런스, 게임의 역동성, 게임 시간 등등... 내가 체스를 좋아하는 이유는 체스가 앞서 말한 바둑, 샹치, 장기, 쇼기에 비해 훨씬 게임 시간이 짧고, 기물 파워가 훨씬 세서 게임하는 맛이 좀 더 좋고, 기물 움직임이 직관적이라 이해하기 쉽고, 플레이하는 사람들과 컨텐츠가 엄청 많기 때문임. 반대로 체스의 단점도 많음. 선후수 밸런스가 좋지 못하고, 최고 레벨에서 무승부가 너무 자주 나온다는 거. 다른 게임들 역시 장단점이 많음. 쇼기는 선후수밸런스와 무승부가 낮다는 장점이 있지만 체스류 게임 중에서 게임 시간이 제일 길고 기물이 너무 많아 진입장벽이 높다는 단점이 있고, 바둑은 매우 깊이 있고 매력적인 게임이지만 어마어마하게 진입장벽이 높지. 게임은 우열이 있는 것이 아닌 장단점이 있는거니 제발 이글을 보고 바둑 미만 잡이라던가, 쇼기가 체스 상위호환이라던가 그런 말을 안했으면 좋겠음.

세줄요약

1. 체스는 체스류 게임 중에서 샹치 다음으로 가장 경우의 수가 적은 게임이다.

2. 우리가 접할 수 있는 게임 중에서는 바둑이 1등, 쇼기가 2등이다.

3. 어차피 우리 영역 밖의 이야기니까 걍 각자 재밌는 거 하면서 살자.