알파고 바둑이 휩쓸고 지난 지금 해묵은 오목 알고리즘 개발했던 이야기

알파고 와 커제9단의 대국이 3:0으로 알파고의 승리로 끝난 가운데, 알파고는 바둑 대전에서 은퇴를 선언했다. 지금까지 바둑을 통해 컴퓨터 인공지능 AI의 가능성에 대해 시험해 보았고, 성과를 어느 정도 이루었다고 판단하였고, 센세이션을 일으킨만큼 지금까지 수행한 챕터는 마무리하고 다음 단계로 나아가기 위한 준비를 하겠다고 한다. 바둑에서 벗어나 보다 넓은 의미에서 컴퓨터 인공지능 AI가 인간의 삶의 실용적인 영역에가지 확대를 할 수 있도록 챕터2를 향해 나아가겠다고 하는 것이다. 이런 알파고의 행보가 무척이나 관심이 가고 궁금하기도 하다.

알파고 이야기를 조금 더 하자면 작년 이세돌 9단 , 올해 커제 9단과의 대국에 대해 혹자는 이렇게 재밌게 비유한다. 바둑의 신 알파고가 신선놀음에 지루해 미천한 인간들과 접바둑을 두기 위해 세상에 내려왔고, 혹시나 재미있는 경험을 할 수 있을까 싶어 인간세상에서 인간고수들과 바둑을 두며 유희를 즐기려 왔는데 역시 인간이군 하는 실망으로 인간과의 접바둑을 두지 않겠노라며 다시 돌아갔다고 한다. 인간과 앞으로는 바둑을 둘 의미가 없다며 돌아갔다고... 바둑은 이제 안한다고 했지만 혹시 인간들이 너무 졸라대면 가끔 이벤트로 접바둑 한두판씩은 둬줄지 모르니 열심히 바둑실력을 갈고닦아야겠다고.

이런 이야기들이 돌 정도로 최근 일주일 정도 알파고에 대해 이러쿵 저러쿵 이야기들이 많았다. 아무래도 중국기사 커제와의 대국인 만큼 작년 이세돌9단과의 대국처럼 핫이슈는 아니었지만 관심있는 바둑 동호인이나 인공지능 관심있는 사람들에게는 그래도 좋은 떡밥이 되었던 것이다.

오래 묵혀두었던 블로깅을 다시 하게 되면서 이 시점에 알파고 뉴스들을 보며 떠오르게 되는 것들이 내 관심사와 덧붙여져서 포스팅 하고싶은 주제가 생기는 게 자연스러운 현상이다. 바둑 알고리즘으로 이름을 날린 알파고를 보며 학창시절 오목 알고리즘을 만들어 게임을 만들었던 경험이 떠오르는 것은 자연스러운 현상이다. 

서론이 길었다.

2002년 제대후 복학하자마자 학과 수업 과제로 수행했던 오목 알고리즘 개발에 대한 이야기를 시작한다. 서론은 길었지만 본론은 매우 짧은 글이 될 것 같다. 과제를 수행하면서 그 과제에 푹 빠져 학교생활이 전체적으로 활력있고 재밌게 만들었던 기억이다. 하지만 15년이 지난 지금은 정말 개략적인 몇몇 내용만이 기억날 뿐이기 때문이다. 디테일하게 이야기를 적고 싶은 마음은 잠시 내려놓고 몇가지 history와 결과물을 첨부하는 것으로 마무리 하겠다.

첨부파일 Omok.7z

첨부파일을 받아서 실행해 보면 아래와 같이 오목판이 나온다.

오목 알고리즘은 평가함수를 만드는 게 사실상 전부이다. 각 좌표값에서 돌을 놨을 때의 점수를 계산해서 가장 높은 점수인 좌표값에 돌을 놓으면되는 것이다. 말은 굉장히 간단하다. 하지만 이런 평가함수를 만들기 위해서는 몇 가지 게임알고리즘 기술이 필요한데 가장 기본적으로 사용하는 알고리즘은 minimax 알고리즘이다. 

miniman 알고리즘은 이름대로 수많은 경우의 수에 대한 각 노드마다 유리한 정도를 최소, 최대값을 가지고 평가해서 그 값을 가지고 검색을 하는 알고리즘이다. 하지만 게임에서 경우의 수는 정말 어마어마하게 많을 수도 있다. 심지어 무한대일 수도 있다. 이 알고리즘은 모든 노드를 방문해서 다 계산을 하기 때문에 최적의 경우를 찾는 데 가지 시간이 많이 걸리고 불필요한 노드까지 계산을 하는 일이 많다. 이런 점을 휴리스틱으로 보완한 알고리즘이 Alpha-Beta Pruning 알고리즘이다.

Alpha-Beta Pruning 알고리즘은 가지치기 알고리즘이라고 한다. 특정 노드에서 가능한 경우중의 최대값과 최소값을 각각 이용해서 그 노드 아래로는 나올 수 없는 최대값이 옆 노드의 최소값 보다 작다면 구지 그 아래의 노드를 검색할 필요가 없고, 이런 경우는 노드를 가지치기를 해서 검색할 경우의 수를 줄여주는 알고리즘이다. 이 정도의 가지치기만 하더라도 경우의 수는 획기적으로 줄어들게 되고 결국 평가함수의 속도가 빨라지게 되는 것이다. 대략의 알고리즘에 대한 설명은 이 정도만 설명하기로 한다.

시작하자마자 바둑판을 클릭하면 검은돌이 놓이면서 자동으로 컴퓨터와 대국이 시작이 된다.

참고로 학과 수업이었고, 오목 알고리즘을 라이브러리 형태로 인터페이스를 맞춰서 개발을 하여서 과제를 수행한 다른 동료들의 알고리즘과도 대국을 수행할 수 있었다. 알고리즘 끼리 누가누가 잘하나 경쟁도 할 수 있도록 해서 더 재밌었었던 과제였던 것이다.

알고리즘의 성능 평가를 위해 기준점을 교수님이 제공한 오목 알고리즘으로 삼았고. 프로그램에서 비교테스트하기 위해 우리 오목알고리즘과 교수님 알고리즘을 대결하는 메뉴를 넣어놨다.

교수님(선) vs 우리꺼는 교수님 오목 알고리즘이 흑돌로 시작하는 것을 의미한다.

그리고 두번째 메뉴의 (스페이스바)라고 붙인 것은 컴퓨터끼리 워낙 빨리 휘리릭 하고 오목을 끝내버리지 말고 과정을 하나하나 보고싶을 때 스페이스바를 클릭해야 다음 수를 놓는 메뉴이다.

우리꺼(선) vs 교수님은 우리 알고리리즘이 흑돌로 시작하는 것을 의미한다.

메뉴에 난이도 조절이 있는데 초급, 중급, 고급으로 의도하고 만들었지만 사실상 중급, 고급에서 어이없는 실책을 자주 하는 것이 보인다. 난이도 구현을 위해 초급은 3수 앞까지 파악한다면 중급은 4수앞, 고급은 5수앞까지 파악하는 알고리즘을 만들려고 했는데 생각했던 것처럼 동작하지 않아서 결국은 원인은 파악 못한채 마무리 되었다. 난이도 조정가지 완성하고 싶었지만 결국은 못하고 그 이후 손을 대지 않은 상태이다.

그냥 초급으로만 두는 것을 추천한다. 

포스팅을 위해 대국을 몇 번 수행했는데, 간만에 오목을 두니까 번번이 컴퓨터에게 패배해서 그냥 컴퓨터가 이긴 화면을 캡쳐했다. 

포스팅을 하며 과거 학창시절에 재밌었던 기억이 새록새록 기억이 나서 기분좋은 경험이었다. 이 알고리즘은 추후에 2008년인가 2009년에 윈도우모바일폰 App만드는 연습을 하면서 윈모바일용 게임으로도 재탄생시켰던 적이 있었는데 아쉽게 그 소스는 지금 잃어버려서 찾을 수가 없다.

자료를 잘 정리해놓는 습관이 참 필요한 것을 다시금 깨닿는다.

하지만 학교때의 자료들은 다 남아있어서 간만에 레포트도 몇 개 열어봤는데..... 한가지 또 놀라운 걸 발견했다.

학교 수업 과제 제출 때 만든 보고서가 생각보다 엄청 정성을 들여서 제출했던 걸 보고 아 예전에 열심히 했었나보구나 하는 걸 다시금 발견하게 되었다.

사실 열심히 했다는 생각은 나면서도 얼마나 열심히 했는지까지는 잘 기억이 안났는데, 레포트를 보니 아 내 기억보다 조금 더 열심히 했었구나 하는걸 발견하게 되었다. 과거를 훑으면서 나도 기억 못했던 것들을 다시 되살려주고 있다.

기념이니 그 때의 레포트를 캡쳐해서 첨부해본다. 아래와같은 목차로 11장을 빽빽하게 채워넣었었구나.. 그 때 참 뭘 할 짬도 안나고 당구도 끊고, 게임도 끊고 그랬었는데 20학점 꽉꽉 채워들으면서 이렇게 하느라 그랬구나 ㅎㅎㅎㅎㅎ  

참 옛날생각에 잠시 감성적이 되어본다.