알파고와 항공검색 그리고 FltGraph

알파고와 항공검색 그리고 FltGraph

알파고와 항공검색 그리고 FltGraph

최근 ‘AlphaGo’(알파고)라는 프로그램이 프로바둑선수(유럽 바둑 챔피언이자 중국 프로바둑 기사인 판 후위 2단)를 이겼다는 소식과 함께, 3월에 이세돌 9단과 대결한다는 소식이 전해졌다. 1997년 체스에서 IBM의 딥블루가 카스파로프에게 승리한 이후 들려온 또 하나의 큰 사건이다.

어차피 체스든 바둑이든 컴퓨터가 ‘완전히 풀어내’는 것은 불가능에 가깝다. 인용글을 잠시 보자.

 

“체스에서 컴퓨터가 사람을 이긴 것이 20년 전이고 컴퓨터의 연산 능력은 그 뒤로도 지금까지 매 2년마다 두 배씩 발전해왔지만 컴퓨터가 아직도 체스를 ‘완전히 풀어내’지는 못했다. 완전히 풀어낸다는 것은, 종국까지 모든 경우의 수를 따져서 각 장면에서의 최선의 수를 특정할 수 있다는 것이다. 즉, “흑백 모두가 최선으로 두면 몇 번째 수에 이르러 어느 쪽이 이긴다(또는 비긴다)”고 말할 수 있다는 것이다. 예를 들어, 15줄 바둑판에서 두는 (3-3, 4-4 제한 없는) 오목에서는 이미 1993년에 백이 어떻게 응수하더라도 선착하는 흑이 무조건 이길 수 있는 수순을 찾아냈다. 체스는 오목보다 경우의 수가 훨씬 많아서 이제 겨우 기물이 흑백 합해 6개 남아있을 때 배치에 관계 없이 모두 풀렸고, 7개 남은 경우가 일부 풀린 정도다. 체스도 32개의 기물로 처음 시작할 때부터 풀기에는 아직 까마득한 시간이 필요하고, 하물며 체스보다 경우의 수가 훨씬 많은 바둑에서는 정말로 요원한 일이다.
물론 알파고의 계산(수읽기) 속도는 사람(일류 프로라고 하더라도)을 압도하지만, 프로는 착수를 결정할 때 수읽기에만 전적으로 의존하지는 않는다. 즉, 프로는 바둑 이론, 형태에 따른 급소 또는 흔히 ‘감각’이라고 부르는 직관을 통해서 안될 법한 수는 일찌감치 가지치기하고 될 법한 수만 집중적으로 따져본다.”
‘AlphaGo’(알파고)와 이세돌 대결에 부쳐, Dong Kam,

결론적으로 알파고는 월등한 계산 능력에 딥러닝, 즉 학습을 통해 ‘감각’이나 ‘직관’을 보완하여 이세돌 9단에게 도전하는 것이다. 이번 3월 대결에서든 아니면 몇년 후에든 알파고가 이세돌을 이기는 날이 온다면 그것은 전적으로 딥러닝의 승리라고 할 수 있을 것이다.

그럼 거대 문제를 해결하는 방법이 딥러닝에만 있는 것일까? 샤이암 생커(Shyam Sankar)는 인간과 컴퓨터간 협력 시대의 개막(The rise of human-computer cooperation)이라는 TED 강연에서 거대 문제를 해결하는 가장 효과적인 방법은 인간과 컴퓨터의 올바른 협력이라고 역설하였다.

https://embed-ssl.ted.com/talks/lang/ko/shyam_sankar_the_rise_of_human_computer_cooperation.html

이제 본론으로 들어가자. 항공검색(Air Search)은 거대 문제이다. 아무리 빠른 컴퓨터를 가지고 찾아도 정답을 찾을 수 없는 문제다. (이전 글 항공권 검색 기술 분석 과 Computational Complexity of Air Travel Planning, Carl de Marcken, Public notes on computational complexity, Fall, 2003 참고.)

하지만 기존의 항공검색은 전적으로 시스템에만 의존한다. 고객이 입력한 초기 조건, 즉 “출발지/목적지/출발일”을 만족하는 항공권들을 찾아서 나열하고 고객은 이 중에서 고를 수 있을 뿐이다. 당연히 못 찾는 항공권이 있을 수 밖에 없다. 특히 다구간에서는 형편 없는 검색 결과가 나오는 경우가 많다. 심지어는 단순 왕복 여정에서도 스케줄도 가장 좋고 가격도 가장 싼데도 불구하고 못 찾는 경우가 심심치 않게 발견된다. (물론, 동일하지 않은 조건, 즉 특정 여행사에서만 팔 수 있는 항공권 등은 논외다.)

이 틈새를 파고 든 서비스가 메타서치 엔진 기반의 가격비교 서비스이다. 물론 동일하지 않은 조건 때문에 사이트마다 가격이 달라지는 것도 있지만, 시스템이 어디에 초점이 맞추어져 있느냐에 따라 검색을 할 수 있고 없고가 결정되는 경우가 있기 때문이다.

그럼 이 정도면 된 것일까? 말콤 글래드웰(Malcolm Gladwell)은 스파게티 소스에 관하여(Choice, happiness and spaghetti sauce)라는 TED 강연에서 “마음은 혀가 무엇을 원하는지 모른다”는 것을 역설했다.

https://embed-ssl.ted.com/talks/lang/ko/malcolm_gladwell_on_spaghetti_sauce.html

항공검색을 하는 고객들은 구체적인 결과물이 눈앞에 보이기 전에는 자신들이 그것을 원하는지 알 수 없다. 스케줄이 나쁘지만 싼 것을 고를지, 스케줄은 좋지만 비싼 것을 고를지, 오전에 출발하는 항공권을 고를지, 오후에 출발하는 항공권을 고를지는 구체적으로 가격과 항공편이 제시되어야만 판단할 수 있다. 항공 검색이 체스나 바둑과 다른 점이 이것이다. 체스나 바둑은 정답만을 찾으면 되는 문제지만 항공검색은 고객의 마음까지 헤아려야 하는 것이다. 다시 말해 정답은 고객도 모르는 저 마음 깊숙한 곳에 있다는 것이다.

이쯤 되면 머리가 터진다. 정답도 찾을 수 없는 문제에, 딥러닝에, 고객의 마음 깊은 곳에 있을지 모르는 정답을 어찌해야 찾을 수 있을까?

FltGraph는 두 가지 해결 방안을 제시한다.

첫번째는 휴리스틱 서치(Heuristic Search)다. 휴리스틱 서치의 기본 개념은 간단하다. 시스템은 각 단계별로 정보를 요약 정리해서 보여주고, 고객은 각 단계별로 자신이 원하는 것을 선택한다. 이 선택에는 두 가지 의미가 있다. 하나는 앞에서 언급된 컴퓨터가 할 수 없는 ‘직관’이나 ‘감각’에 의한 선택이고, 다른 하나는 개인의 ‘선호’다. 고객이 단계별로 선택해 줌으로써 컴퓨터는 연산해야할 대상을 줄일 수 있다. 결과적으로 노트북으로 슈퍼컴퓨터를 이길 수 있는 것이다. (참고로 휴리스틱 서치 서비스는 아직은 오픈 전이다.)

두번째는 Follow On(따라하기)이다. 예를 들어보자. 이미 알파고는 프로 2단을 이길 수 있는 실력이다. 아무리 좋은 프로그램이 협력을 해줘도 바둑을 전혀 모르는 사람이나 입문한지 얼마 안되는 사람들은 알파고를 이길 수 없다. 어느 정도 바둑에 대한 지식과 노하우가 있어야 프로그램의 협력을 받아 알파고를 이길 수 있는 것이다. 휴리스틱 서치를 이용한 항공검색도 마찬가지다. 항공검색에 대한 노하우와 시행착오 없이는 좋은 결과를 내기 어렵다. Follow On은 바둑에 대한 지식과 노하우가 없어도 따라하기를 통해 알파고를 이길 수 있게 만들어주는 인터페이스이다. 결과적으로 집단지성의 힘으로 알고리즘이 찾지 못하는 항공권을 일반인이 자신의 ‘선호’대로 찾을 수 있도록 도와주는 서비스다.

모든 서비스에는 철학이 있어야 한다. 알파고와 이세돌 9단의 대결 소식을 빌려 FltGraph가 추구하는 가치와 방향에 대해 언급해 보았다. FltGraph는 휴리스틱과 집단지성으로 보다 좋은 항공권을 찾을 수 있다고 믿고, 한발 한발 전진하고 있다.

 


FltGraph