게임 AI의 진화와 역사

게임 AI의 진화와 역사

AI 인공지능의 발전은 게임에서도 이루어지고 있다

 

- [컴퓨터 사이언티스트(Computer Scientist, 컴퓨터 과학자)]는 게임 [AI(Artificial Intelligence, 인공지능)]에 대해 항상 높은 관심을 가지고 있습니다. 그것은 바둑과 장기에서 단순히 AI의 승률을 높이기 위한 것이 아닌, 인공지능 알고리즘과 복잡한 문제 해결 능력을 계속 높이기 위한 것입니다.

사실, 게임 AI는 AI 자체만큼이나 긴 역사가 있습니다. 그리고 AI에 관한 연구의 대부분은 게임을 플레이할 수 있는 [에이전트(Agent)]를 구축하기 위한 연구에서 유래했습니다. 즉, 게임 AI도 AI 자체 연구의 진전에 따라 진화해왔다고 볼 수 있습니다.

[백개먼(Backgammon, 둘이서 하는 전략 보드게임으로 기원전 3,000년경 중동에서부터 시작되었다고 한다)]이나 [체커(checkers, 체스판에 말을 놓고 움직여, 상대방의 말을 모두 따먹으면 이기는 게임)], 체스, 포커, 바둑 등과 같은 게임이 AI 연구의 대상이 된 것은 다음과 같은 특징이 있기 때문입니다.

---

▼단순하고 명확한 룰이 있고, 승부 판정과 행동의 기준이 명확할 것.
▼이러한 게임에 정통한 것은, [인간의 지능이 일정 이상 높은 것을 나타내고 있다]라는 일반적인 인식이 있는 것.

---

1956년, 강화 학습 알고리즘이 체커로 채택되다

- [앨런 튜링(Alan Turing, 1912~1954)]이 AI의 개념을 제창하기 전, 컴퓨터 사이언티스트는 이미 스스로 개발한 [지능] 프로그램을 게임을 통해 테스트하고 있었습니다.

1928년, 수학자 [존 폰 노이만(John Von Neumann, 1903~1957)]은 [미니맥스 정리(Minimax, A가 B로부터 이득을 수취하는 제로섬 게임에서 A는 A의 최소이득이 최대가 되는 전략을 선택하고, B는 A의 최대 이득이 최소가 되는 전략을 선택하는 것이 가장 견실한 행동)]의 알고리즘을 발표했습니다.

1949년, 수학자 [클로드 섀넌(Claude Shannon, 1916~2001)]에 의해 해당 알고리즘이 재구축되어 체커의 문제해결에 사용되었고, 1956년 [다트머스 회의(Dartmouth Conference)]에서는 AI를 학술 연구 분야로 확립했습니다.

같은 해 컴퓨터 인공지능 분야의 개척가 중 한 명인 [아서 새뮤얼(Arthur Samuel, 1901~1990)]은 스스로 배움으로써 체커를 플레이할 수 있는 알고리즘을 개발하고 있었는데, 그 알고리즘은 현재 [강화 학습(Reinforcement Learning)]이라는 이름으로 불리고 있습니다.

1992년, 백개먼의 브레이크 스루

- 백개먼의 AI [브레이크 스루(breakthrough)]는 AI 연구사의 획기적인 사건으로 꼽히고 있습니다. 1970년대 독일 체스 기사였던 [한스 벌리너(Hans Berliner, 1929~2017)]에 의해 백개먼 AI 프로그램 [BKG 9.8]이 개발되었습니다.

1992년에 들어서면, [제랄드 테사우로(Gerald Tesauro, 현 IBM AI Science의 수석 연구원)]에 의해 [TD-Gammon] 이라고 하는 프로그램이 개발됩니다. 이 프로그램은 [뉴럴 네트워크(neural network)]를 모델로 하여 훈련되었습니다.

자기 대전을 대량으로 반복함으로써 인간으로 쳐도 최고 수준에 도달한 TD-Gammon은 인간 플레이어를 필요로 하지 않는 훈련법을 사용하였기 때문에, 인간 플레이어와 다른 게임 플레이를 보여주었습니다.

TD-Gammon의 의의는 강화 학습을 사용하여 훈련하였을 뿐만 아니라, [특징량 엔지니어링(삶의 데이터를 통계학이나 기계 학습에서 성과를 낼 수 있는 데이터로 변환하는 방법)]을 필요로 하지 않으며, 말의 위치를 뉴럴 네트워크에 입력하는 것만으로 세계 챔피언 레벨의 인간 플레이어에 필적하는 에이전트를 훈련할 수 있다고 증명한 바 있습니다.

1990년대, 체커와 체스 AI의 인간 따라잡기

- 컴퓨터 계산능력이 크게 향상되면서 AI 알고리즘이 점차 발전하는 가운데, 체커용 알고리즘을 새뮤얼이 개발한 지 38년이 지난 1994년, 캐나다 [앨버타 대학(UAlberta)]의 [조나단 쉐퍼(Jonathan Schaeffer, 1957~)] 교수는 팀을 이끌고 [치누크(Chinook)]를 개발했습니다.

이 프로그램의 코어로서 탐색목 알고리즘도 사용되고 있습니다. 탐색목 계산의 복잡도를 낮추고 예측함수의 정확도를 높이기 위해 전 세계 체커 마스터들의 게임 시작할 때 행동과 막판 판면, 승부 정황 등을 포함한 데이터베이스를 만들었으며 수동 조정에 기초한 [알파 베타 가지치기(Alpha-Beta Pruning)]도 사용하고 있습니다.

1994년 치누크는 체커 세계타이틀전에서 당시 세계 챔피언인 [마리온 틴슬리(Marion Tinsley, 1927~1995)]를 만났습니다. Chinook과 6국 연속 비긴 후, 틴슬리는 몸이 아파 경기를 포기했고 Chinook는 인간 플레이어와의 싸움에서 체커 세계 챔피언 타이틀을 거머쥔 최초의 AI 프로그램이 되었습니다.

쉐퍼 교수는 2007년에 발표한 논문에서 이 경기를 통해 AI가 체커의 문제를 풀 수 있다는 것을 증명했다고 말합니다.

한편, 체스 AI 분야에서도 [펭슝수(Feng-hsiung Hsu, 1959~)]가 주도하는 [딥소트(Deep Thought, 깊은 생각)] 연구팀이 브레이크 스루를 보였습니다. 딥소트에는 검색을 가속하기 위한 특별한 하드웨어 디자인이 적용되었고 [싱귤러 익스텐션(Singular Extensions)] 알고리즘도 도입됐습니다.

핵심 아이디어는 여러 방법 중에서 다른 방법보다 일정 이상 뛰어나다고 평가받은 방법이 있으면, 그것에 관해 더 깊이 있는 탐색을 하는 것입니다.

그 후, 딥소트 팀은 IBM에 입사해 지금까지의 연구를 계승하는 형태로 슈퍼컴퓨터 [Big Blue(빅 블루, 후에 딥 블루/Deep Blue로 개칭)]의 개발을 시행, 1997년 딥블루는 당시 체스 세계 챔피언인 [가리 카스파로프(Garry Kasparov, 1963~)]와의 경기에서 3.5 : 2.5의 스코어로 승리합니다.

딥 블루는 대국 시에 당시로써는 매우 높은 계산능력을 가진 전용으로 설계된 슈퍼컴퓨터에 의해 1초에 2억 수를 읽을 수 있었고, 그다음 12수(Singular Extensions 를 사용한 경우는 40수)를 찾는 것을 실현했습니다.

마침내, 딥블루는 토너먼트의 조건으로 인간 체스 세계 챔피언을 이긴 첫 컴퓨터 프로그램이 되었습니다.

바둑 AI 진화, 역사적 쾌거 달성

- 지금까지 봐왔던 게임과 비교해서 한 수에 19×19개의 선택지가 있는 바둑은 훨씬 복잡하고 체스 등보다 더 어려운 게임으로 여겨지고 있었습니다.

1968년, 첫 인공지능 바둑 프로그램이 [앨버트 린제이 조브리스트(Albert Zobrist, 1942~)]에 의해 개발되었지만, 승리할 수 있었던 것은 초급 수준의 플레이어들뿐이었습니다.

1993년, [베른 부르크만(Bernd Brügmann)]은 평가 함수 대신 [몬테카를로 방법(Monte Carlo method, 난수를 이용하여 함수의 값을 확률적으로 계산하는 알고리즘을 부르는 용어)]을 쓰는 [Monte Carlo Go]라는 프로그램을 개발했습니다.

Monte Carlo Go는 주의 깊게 설계된 평가함수값 대신, 몬테카를로 방법을 사용했기 때문에 Monte Carlo Go는 임무에 따라 결과로 이끄는 평가함수를 설계하지 않고 결과예측치 대신 롤아웃 막판까지 자기대전의 평균치를 사용하고 있습니다.

이 알고리즘은 후에 [알파고(AlphaGo)]를 성공으로 이끈 중심 알고리즘 중 하나로도 여겨지고 있습니다.

2006년 프랑스 [국립정보학자동제어연구소(INRIA)] 연구원 [실반 젤리(Sylvain Gelly)]는 Monte Carlo Go를 바탕으로 UCT 알고리즘을 도입, [MoGo]라는 프로그램을 개발하였습니다.

2008년 MoGo는 9점 접바둑으로 [김명완(1978~)] 프로 8단 기사에게 승리했습니다. MoGo의 승리로 MCTS(UCT) 알고리즘의 바둑 문제 해결 중요성이 충분히 입증되었습니다.

 

2015년, [딥마인드(DeepMind)] 팀은 상기 프로그램을 기초로 심층 강화 학습에 근거한 프로그램인 알파고를 개발했습니다. 유럽 바둑 챔피언에 승리한 AlphaGo는 핸디캡 없이 프로기사를 이긴 최초의 바둑 프로그램이 된 것입니다.

더욱 복잡도 높은 불완전 정보 게임 AI, 역사의 무대로 등장

- 포커와 브리지, 마작 등은 지금까지 본 체스나 바둑 등의 기류 게임과 종류가 다른 게임으로 되어 있습니다. 이러한 게임을 플레이 할 때 플레이어들은 서로의 정보를 모두 파악할 수 없기 때문에 [불완전 정보 게임(imperfect information game)]이라 불립니다.

[텍사스 홀덤(Texas hold 'em, 포커의 규칙 중 하나)] 같은 불완전 정보게임에서는, 정보의 불완전성을 이용해 [블러프(Bluff)]로 상대를 현혹할 수 있는데, 톱 레벨의 인간 플레이어는 이러한 스킬을 잘 구사하고 있습니다.

텍사스 홀덤 AI는 앨버타 대학에서 성능 향상을 위해서 계속적으로 계속 개발하고 있는데, 1984년 프로 포커 플레이어 [마이크 카로(Mike Caro, 1944~)]가 [Orac]를 개발하고 나서 1997년, 전출의 쉐퍼는 텍사스 홀덤 플레이어의 블러핑 행위를 시뮬레이트 하는 [Loki]를 개발했습니다.

Loki는 2001년에 [PsOpti]로 개칭되었으며, 게임이론에 기반을 둔 기법이 도입되었습니다. 그리고 2015년 [Cepheus]가 발표되었고, 이것에 가세해 CFR+ 알고리즘을 사용한 Cepheus에 의해서 [헤즈업 리미트 텍사스 홀덤(heads-up limit texas hold’em, 1대 1, 베팅 상한액 있음)]에서 컴퓨터가 베팅 상한액이 있는 룰에서 인간을 이길 수 있음이 증명되었습니다.

2017년 [카네기 멜론 대학교(Carnegie Mellon University)]와 앨버타 대학교는 연이어 [Libratus]와 [Deep Stack]을 발표하며 [헤즈업 논 리미트 텍사스 홀덤(heads-up no-limit hold 'em, 1대 1, 베팅 상한액 없음)]에서 세계 챔피언을 차지했습니다.

2019년 카네기 멜론 대학은 페이스북 AI와 함께 Libratus의 진화판으로써 [Pluribus]를 개발, 논 리미트 텍사스 홀덤으로 전문 포커플레이어를 물리치고 있습니다.

한편, 게임 전략은 이 정보의 불완전성으로 인해 더욱 복잡해졌으며 탐색목과 CFR 알고리즘을 기반으로 한 계산도 더욱 복잡해지고 있습니다.

그중 트럼프 게임의 일종인 브리지는 복잡한 규칙이 있어 AI의 연구 대상이 되고 있습니다. 1980년대부터 [Bridge Baron] 프로그램 개발을 추진한 미 해군의 연구 시설에 소속된 [토마스 a. 트룹(Thomas A. Throop)]은 십수 년에 걸친 개발로, 1997년에 열린 세계 최초의 컴퓨터 브리지 시합에서 우승을 차지합니다.

이듬해 [오리건 대학(University of Oregon)] [매튜 L. 긴스버그(Matthew Ginsberg)]가 개발한 GIB 프로그램이 우승을 차지합니다. GIB 프로그램은 같은 해 세계 브리지 챔피언십 참가에 초청되어 35명의 참가자 중 12위의 성적을 거두었습니다.

십수 년 후 몬테카를로 법에 근거한 잭과 Wbridge5도 각각 세계 브리지 챔피언십에 참가해 우승했습니다.

마작 분야에서는 2015년 [도쿄대학(東京大学)] 대학원생인 [미즈카미 나오키(水上直紀)]가 [폭타(爆打)]라는 AI 프로그램을 개발하였고, 2018년 주식회사 [디왕고(ドワンゴ)]도 딥러닝 모델을 기반으로 한 마작 AI [NAGA]를 개발하고 있으나, 아직 정상급 인간 플레이어와의 차이가 있는 상황입니다.

장기나 바둑과 같은 [완전 정보] 게임이나 텍사스 홀뎀과 같은 [불완전 정보] 포커 게임보다, 브리지나 마작에서 AI를 개발하는 것이 더 도전적이라고 말할 수 있을지도 모릅니다.

불완전 정보의 특징뿐 아니라 불완전 정보 게임 중에서도 관측할 수 없는 상태 공간이 특히 넓어 현실세계에서 인간이 의사결정을 하는 과정에 더 가까워지고 있기 때문입니다.

따라서 이러한 게임 AI의 브레이크 스루는 다음 게임 AI 연구의 획기적인 사건이 될 수 있습니다.