자료구조 기말, 오목 프로그램 대전에 대한 기록
1. 서론
본 포스트는 한국산업기술대 게임공학부 2학년 1학기
장지웅 교수님의 자료구조 수업을 수강할 예정이거나
또 이미 듣고 있는 상태에서 프로젝트를 진행하고 있는 학우가 있을 경우
프로젝트 진행에 대해 참고를 할 수 있도록 하는 것에 그 목적을 두고 있다.
필자의 필력이 매우 낮으니 먼저 이 점 이해 바란다.
2. 프로젝트 진행 과정
2016년 1학기 당시 자료구조 기말 프로젝트의 내용은 각자의 방법대로 오목 AI를 만든 후
조를 배정받아 서로 대전을 치러 승률을 도출해 이를 성적에 반영하는 형식이었다.
당시 오목 대전 조는 학번 끝자리가 무엇인지에 따라 배정되었는데
조원 중에서 내가 가장 고학번이었기에 자연스럽게 내가 조장이 되었다.
사실 기말프로젝트로 오목 하나만 짜는 것이었으면
조금만 시간을 투자하면 되는 문제였기 때문에 무난하게 프로젝트를 완료할 수 있었을 테지만
같이 진행하던 다른 프로젝트 와 일정이 정확하게 겹쳤기 때문에 낙오하는 학우들이 발생하였고.
그래서 AI가 바둑판에 돌을 성공적으로 두기만 해도 승률이 30% 이상이 나오는 기적이 벌어졌다.
 |
| 선택과 집중의 시간 , 이 학우분은 다른 프로젝트를 위해 신속하게 자료구조 프로젝트를 포기하셨다. |
프로젝트 마감 당일 나는 나름의 공정성 확보를 위해
아프리카 TV 계정을 생성했고 이 채널을 통해 모든 대진 진행을 생중계하였다.
 |
| 오직 오목 생중계만을 위해 개설한 방송국, 모든 대전 내용을 방송하고 모든 내용을 녹화 했다. |
 |
| 당시 대진 결과 표 |
모든 인원이 서로 흑, 백 역할을 바꾸면서 서로 4번씩 대전해야 했기 때문에
조원들의 AI를 전부 맡붙이려면 대전용 프로그램을 4*(n)*(n-1) 번 돌려야 했지만
다행히도 프로젝트를 포기한 인원이 3명이 나와주었기 때문에 대전을 4시간만에 끝낼 수 있었다.
3. 대전 진행
심판 프로그램에 각자의 프로그램 코드를 첨부하고 실행하면
프로그램에 따라 서로 돌을 두는 과정을 보여주고
승부가 결정되면 어떤 수가 마지막으로 놓여졌는지 ★모양으로 표기되었다.
 |
| 대전 진행 화면 |
 |
| 결과 이미지 |
이런 프로그램은 매 주 진행되는 실습만 진행해도 충분히 만들 수 있었지만
본 대전에선 렌주룰이 적용되었기 때문에 33 자리에 돌을 놓으면
반칙패를 하게 되어, 프로그램이 이를 판별할 수 있도록 만들어야 했고
최대한 많이 이겨서 승률을 높이기 위해서도 프로그램의 개선이 필요했다.
↖
|
↑
|
↗
| ||||||
↖
|
↑
|
↗
| ||||||
↖
|
↑
|
↗
| ||||||
↖
|
↑
|
↗
| ||||||
←
|
←
|
←
|
←
|
●
|
→
|
→
|
→
|
→
|
↙
|
↓
|
↘
| ||||||
↙
|
↓
|
↘
| ||||||
↙
|
↓
|
↘
| ||||||
↙
|
↓
|
↘
|
:: 나의 오목 프로그램의 기본 컨셉 그림
하지만 당시 다른 프로젝트도 같이 진행하고 있었기 때문에
오목 프로그램을 고차원적으로 코딩할 여유가 없었다.
그래서 각 칸마다 돌을 놓았을 때 위험수치를 계산하고
가장 위험수치가 높은 곳에 돌을 놓는 프로그램을 급하게 서술했다.
다행히도 시간 없는건 다른 조원들도 마찬가지였기 때문에
결과적으로 누가 프로젝트를 '덜' 던졌는지가 승률을 결정짓게 되었다.
 |
| 나름 비비고 있는 나의 프로그램, 위 두 이미지는 둘다 내가 패배한 게임이다. |
위와 같이 강자들도 있었지만 그럼에도 불구하고
내가 운좋게도 높은 승률을 기록할 수 있었던 것은
기말프로젝트를 버티지 못하고 고통상태에 빠진 다른 학우들의 프로그램 덕분이었다.
4. 고통받는 프로그램들
유형 A :: 반칙 패
흑돌 플레이어의 프로그램은 나름 강했으나,
반칙패가 되는 자리를 검사를 하지 않는 치명적인 문제가 있었다.
33을 만들 수 있는 자리를 가장 유리한 수라고 판단해 거침없이 돌을 놓고
그대로 패배하였다.
유형 B :: 다른 차원의 바둑돌
다음은 서로 나름대로 정상적으로 대전을 진행하다가 흑돌이 바둑판 '밖' 에 놓아서 패배한 그림이다.
본 대전에서 사용한 바둑판의 크기는 19X19 였지만
흑 돌 플레이어의 프로그램 코드는 20X20 바둑판을 기준으로 계산하고 있었다.
유형 C :: 중복 수
음은 이미 돌이 있는자리에 돌을 놓아서 패배한 그림이다.
본 플레이어는 대전 내내 똑같은 이유로 패배했으며,
이 프로그램의 코드는 총 1707 줄에 육박헤다.
하지만 기존에 놓여진 돌을 체크하지 않는 안일함때문에
다른 플레이어에게 공짜로 승을 안겨주는 안타까운 모습을 보여주었다.
유형 D :: RANDOM
시간이 부족할 때 가장 빠르게 짤 수 있는 코드는 다음 두가지 유형이 있다.
a. 상대방의 돌을 막지 않고 무조건 5개를 일렬로 나열하는 것을 시도
b. 랜덤
이번 프로젝트에선 a유형은 나오지 않았고
b유형을 선택한 플레이어만 두명이 나왔다.
다음 두명의 프로그램이 어떻게 되었는지 보도록 하자.
매 턴마다 바둑돌을 무작위로 두면서 기적을 바랐지만
가장 무난했던 프로그램에게도 100% 확률로 패배하는 모습이다.
랜덤으로 놓여진 흑돌을 막아선 백돌이었으나
곧 이어 흑돌이 랜덤으로 돌을 둔다는것을 인지한 백돌은
일직선으로 거침없이 5개를 나열하였다.
랜덤 프로그램과 랜덤 프로그램간의 대전 모습이다.
지금까지 진행한 대전중 가장 치열한 모습을 보여주었으나
그 와중에 누구도 5개를 완성하지 못하고 중복 수를 놓아 승패를 결정짓는 모습이다.
이들은 대전이 끝나는 그 순간까지 단 한번도 5개를 완성하지 못했다.
하지만 위에서 서술한 프로그램 유형 B와 C, 그리고 포기자들 덕분에
랜덤 프로그램이 놀랍게도 승률 50%이상을 기록하였다.
5. 마치며
이번 오목 프로젝트의 의의는 스스로 특정 문제에 대한 해결방법을 생각해본다는 것에 있다.
최종적으로 만들어 낸 프로그램이 아무리 약하더라도,
어떻게든 구현을 위해 코드를 날림으로 짰다 하더라도,
프로그램을 구현하는데 자료구조가 단 하나도 쓰이지 않았다 하더라도,
최소한 이 프로젝트는 스스로 해결방법을 생각하는 기회가 돼주었다.
다음은 지금 현재 이 프로젝트를 진행하고 있는 다른 학우분들과 후배분들에게 하고 싶은 말이다.
결과물이 약할 것 같더라도
혹시 프로젝트를 중간에 포기하고 싶더라도
끝까지 놓지 않길 바란다.
댓글