[=] 게임 인공지능 비교: 체스vs바둑vs포커,스타크래프트

1. 우선 컴퓨터가 전략을 학습하는 방법에 대해.

여기에는 두 가지 접근 방법이 있습니다.
첫 번째로, 해당 게임의 규칙과 각 상황에 대한 전략을 사람이 직접 프로그래밍해주는 방법입니다.
오목같은 경우가 이 방법이 잘 먹히는 예인데, 가로 15칸 세로 15칸 이내의 공간에서 선수(흑)가 무조건 승리하는 전략이 존재하기 때문입니다. 인공지능에서 이런 식의 접근을 top-down이라고 합니다. 원리를 가르쳐줘서 실전에 써먹게 하는 연역적인 방법을 의미합니다. 고전적인 AI 기술이 바로 이런 쪽이죠.
하지만, top-down 방법은 미처 프로그래밍하지 못한 예외적인 상황에 매우 취약하다는 단점이 있습니다. 영화나 만화에서, 고도로 발달된 컴퓨터가 주인공의 기발한 대응에 대해 "입력되지 않은 상황. error"를 외치며 패배하는 상황이 바로 이런 상황이라고 할 수 있죠.

두 번째 방법은 통계 자료를 이용하는 방법입니다. 수백 수천만 번의 게임 기록을 가지고 있으면, "이런 상황에서 내가 이런 선택을 하면 최종적으로 몇 퍼센트의 확률로 승리를 하더라" 라는 것을 계산할 수 있습니다. 이를 바탕으로, 통계적으로 가장 승리 확률이 높은 선택을 하도록 하는 거죠.
이런 접근을 bottom-up이라고 합니다. 이 경우 프로그래머는 컴퓨터에게 해당 게임에 대한 사전 정보(규칙이나 전략 등)를 전혀 줄 필요가 없습니다. 컴퓨터는 단지, 수많은 게임 기록을 통해 통계적으로 가장 승률이 높았던 행동을 선택하게 됩니다. 이는 '기계학습'으로 대표되는 근대 AI 기술의 개요라고 할 수 있습니다. 논리 기반이 아닌 데이터 기반의 AI이죠.
bottom-up 방법은, 아직 분석이 덜 되었거나 예외적인 상황이 빈번하게 일어나는 게임에 대해 좋은 승률을 보일 수 있지만, 전적으로 통계 기록에 의존하기 때문에 막대한 갯수의 게임 기록을 필요로 합니다.


2. 바둑 vs 체스

실제로 게임 인공지능을 구현할 때는 위의 두 가지 접근 방법을 혼용해서 쓰게 됩니다.
우선 top-down 방법만으로는 분명한 한계가 존재한다는 것을 잘 알 수 있고, 두 번째 방법 역시, 대부분의 게임들(체스, 바둑 등등)이 경우의 수가 워낙 많기 때문에(주1) 엄청난 양의 대전 기록을 필요로 하게 됩니다. 물론 체스의 경우의 수가 바둑보다 훨씬 적긴 하지만, 경우의 수로 따지고 들자면 체스든 바둑이든 현재의 컴퓨터로는 처리가 불가능합니다.

주석 보기

(주1) 참고로 바둑의 경우의 수는 3^361 입니다. (각 점마다 흰 돌을 놓거나, 검은 돌을 놓거나, 아니면 빈 칸, 즉 3가지 경우가 존재) 많은 분들이 361*360*359*... 내지는 이보다 좀 더 큰 값으로 생각하고 계시는데, 이 값은 3^361에 비하면 터무니없이 작은 수입니다.

그럼, top-down과 bottom-up을 어떻게 혼용할 수 있는지 생각해보죠...
우선, 현재 상황이 나에게 얼마나 유리한가를 나타내는 함수를 정의합니다.
이 함수를 결정하는 것이 바로 프로그래머의 몫, 즉 top-down이 됩니다.
그리고, 주어진 상황에 대해 함수값이 가장 큰 선택(즉, 나에게 가장 유리한 선택)이 무엇인지 학습하는 역할을 bottom-up이 맡게 됩니다.

여기서 바둑과 체스의 결정적인 차이가 나타나게 됩니다.
체스는, 현재 상황이 나에게 얼마나 유리한지를 파악하기가 상대적으로 쉽습니다. 퀸,비숍,나이트,폰 등등 각각의 말에 대해 일정한 점수를 부과하고, 현재 남아있는 말들에 대해 점수의 총합을 계산하는 방식으로 유리한 정도를 파악할 수 있습니다.
그러나... 바둑은 어떨까요? 내가 현재 상대에게 몇 집 이기고 있는지 예상하기는 커녕(신산 이창호좌께서 이걸 매 순간마다 해내신다고 하죠..;;), 지금 내가 유리한지 아닌지조차 정의하기 어렵죠. "컴퓨터는 두터움이란 개념조차 이해할 수 없을 것이다" 라는 말이 결코 틀린 말이 아닙니다.
하지만, 만약 바둑에서 현재 상황이 나에게 유리한지 불리한지 정도만이라도 어느 정도 정확히 가려내 줄 수 있는 함수가 개발이 된다면, 인간 고수에 대한 컴퓨터의 승률은 비약적으로 향상될 겁니다.
물론 반집 차이까지 계산해내는 절정의 경지에 이른 사람을 상대로 하려면 더 정확한 함수가 필요하겠죠...


3. 체스,바둑 vs 포커,스타크래프트

우선 결론부터 말씀드리면, 게임 인공지능에 있어서 포커나 스타크래프트같은 게임이 체스나 바둑보다 더 어려운 게임이라고 할 수 있습니다. 물론 사람에게는 포커나 스타크래프트보다는 체스,바둑이 일반적으로 훨씬 어려운 게임이지만 말이죠.

체스나 바둑은, 가령 현재보다 수조배 빠른 컴퓨터가 개발이 된다고 하면, 현재 상황에서 가능한 모든 경우의 수를 탐색하는 방법으로 필승의 수를 찾을 수 있습니다. 모든 경우의 수를 짧은 시간 안에 탐색할 수 있는 컴퓨터가 있다면, 애초에 알고리즘이니 인공지능이니 하는 이야기가 의미가 없는 게임들이죠.

하지만 포커나 스타크래프트는 다릅니다. 현재 상황에 대해 완벽한 정보를 얻을 수 없기 때문입니다. 포커의 경우는 상대의 패를 일부만 확인할 수 있고, 스타크래프트의 경우는 상대의 자원 상황이나 시야를 정찰을 통해 일부만 확인할 수 있기 떄문이죠...
요는, 아무리 빠른 컴퓨터가 나온들, 속도만으로 풀 수 있는 문제가 아니란 겁니다. 예를 들어 수퍼컴퓨터 100대를 들여놓은들, 우수한 하드웨어만으로는 기상 예보를 할 수 없죠. 예측을 위한 소프트웨어가 필요합니다. 마찬가지로, 전체 상황을 다 파악할 수 없는 상태에서, 관측되지 않은 부분까지 최대한 정확히 예측해낼 수 있는 인공지능 기술이 필요합니다.
현재 인공지능 분야에서 주로 연구하는 주제가 바로 이런 쪽입니다. 필요로 하는 정보가 충분히 갖춰지지 않았을 때 어떻게 해야 가장 최적의 의사결정을 할 수 있는가 하는...

게임 인공지능의 경우, 최근에 주로 연구되는 접근법은 상대의 플레이스타일을 학습하는 방법입니다. 포커를 예로 들자면 상대가 블러핑을 얼마나 자주하는지, 내가 블러핑을 했을 떄 얼마나 잘 속아주는지... 스타를 예로 들자면 프로토스가 더블넥을 갈 때 상대 저그가 어떤 전략을 즐겨 사용하는지 등등...

이런 거 예측해 내는 것이 얼핏 보면 쉬워보이지만, 절대 쉬운 일이 아닙니다. (물론, 사람은 이걸 비교적 쉽게 해냅니다. 그래서 인간에게는 포커나 스타크래프트가 바둑,체스보다 더 쉽게 느껴지는 거겠지요. 인간은 참 대단해요;)

여튼, 이런 기술은 일단 개발이 되면 게임 인공지능 뿐 아니라 수많은 분야에 있어서 유용하게 활용될 수 있죠. 예측하기 어려운(하지만 완전히 랜덤은 아닌) 어떤 대상의 패턴을 학습하고 예상하는 것이 목적이라면 어디에든 쓰일 수 있겠죠.
그런 의미에서 아래 기사에 실린 연구 결과는 여러 가지로 의미가 있습니다. (사실 이 글은 해당 기사 밑에 리플로 달았던 것을 수정하여 블로그에 올린 것입니다;)

-------

인간과 컴퓨터의 포커 대결, 인간이 승리
http://news.naver.com/news/read.php?mode=LOD&office_id=092&article_id=0000014762

...컴퓨터 프로그램이 인간 프로 선수를 이긴 첫 사례를 기록했기 때문이다.

그는 이번 시합이 우리와 인공지능(AI)에 중요한 이정표가 된다며 하지만 세계 챔피언에게 이기기 위해서 앞으로 가야 할 길이 멀다고 말했다.

앨버트 대학 팀은 AI 연구에서 체스가 아닌 포커를 선택했다. 스채퍼 교수는 그 이유를 포커가 인간의 생활처럼 불완전한 정보에 근거하는 게임이기 때문이라고 설명했다. 즉 플레이어는 상대가 어떤 카드를 가지고 있는지 모르기 때문에 운과 기술 모두가 필요한 게임이라는 것이다.


[=]  http://markov.tistory.com/9