“알고리즘이란 무엇인가?”라는 질문에서 시작한 알고리즘 여행은 지금까지 풀어 본 열여덟 개의 문제를 끝으로 마무리 짓겠습니다.

우리가 풀어 본 문제들은 알고리즘의 기초를 설명하기 위해 고른 대체로 쉬운 문제였습니다. 하지만 현대 컴퓨터 과학이 풀고 있는 수많은 알고리즘 난제들도 주어진 문제를 풀어 입력에 대해 최적의 답을 찾아가는 과정이라는 점에서 우리가 배운 문제와 일맥상통합니다.

예를 들어, 2016년에 이세돌 9단과 바둑 대결을 하여 뜨거운 화제를 모았던 인공지능 바둑 프로그램 알파고의 알고리즘도 (많이) 단순화하면 다음과 같이 설명할 수 있습니다.

 

• 문제: 바둑 게임에서 이길 확률을 가장 높일 수 있는 바둑 수 찾기

• 입력: 현재까지 바둑 게임의 상태(바둑판에 놓인 돌의 상태, 바둑돌이 놓인 순서)

• 출력: 다음 바둑돌을 놓을 위치 (x, y)

 

결국 알파고는 이 알고리즘을 계속 수행하면서 바둑 게임에서 이길 확률을 가장 높일 수 있는 바둑 수를 출력하는 컴퓨터 프로그램인 것입니다(알고리즘의 출력 값을 확인하고 실제로 이세돌 9단 앞에서 바둑돌을 놓는 건 아자 황이라는 ‘사람’이었습니다).

한편, 인공지능 바둑 알고리즘이 인간 챔피언을 이기는 것이 체스보다 19년이나 늦어진 이유는 바둑 알고리즘의 계산 복잡도가 체스 알고리즘의 계산 복잡도보다 훨씬 더 높기 때문입니다.

체스가 8 × 8 = 64칸 보드 위에서 펼쳐지는 게임이라면, 바둑은 19 × 19, 무려 361칸 보드 위에서 펼쳐지는 게임이라는 것만 생각해도 바둑의 계산 복잡도가 훨씬 더 높을 거라 짐작할 수 있습니다. 실제로 바둑은 계산 복잡도가 엄청나게 높은 문제입니다. 지금까지 아무리 빠른 컴퓨터로도 바둑 게임의 제한 시간 안에 제대로 된 출력을 낼 수 없었습니다. 제한 시간 안에 겨우 답을 내는 알고리즘이 있다 해도 그 결괏값의 품질이 프로 기사의 바둑 실력을 이기기에는 역부족이었습니다.

알파고의 승리는 매 대결을 통해 얻은 경험으로 자신을 스스로 발전시키는 ‘기계 학습 알고리즘’, 수천 개의 컴퓨터 프로세서를 동시에 사용해서 빠른 계산을 하는 ‘병렬 처리 알고리즘’ 등 수많은 첨단 알고리즘이 고성능 최신 컴퓨터 시스템의 도움을 받아 얻어낸 결과입니다.