6목 백업

=======================================================================================
[삼성 육목대회] 1. 대회 소개
이 대회의 공식 명칭은 삼성전자 DS부문 SW 알고리즘 대회네요. 개인적으로 작명센스가 좀 아쉽습니다. 이 대회에서는 육목(Connect6) AI 프로그램을 개발해 다른 사람과 경쟁합니다.

기존의 15*15 판에서 진행되는 오목의 경우 흑 필승입니다. 이를 보완하기 위해 렌주룰, RIF룰, 야마구치룰 등이 있지만 그나마 초심자들이 쉽게 접근할 수 있는 렌주룰의 경우, 흑에게 수많은 제한을 걸었음에도 불구하고 흑이 굉장히 유리합니다.(필승으로 알고 있는데 확실하지는 않습니다.)

RIF룰, 야마구치룰 같은 경우에는 규칙이 많이 복잡해서 초심자가 쉽게 하기 힘듭니다. 이에 비해 육목의 경우에는 규칙이 굉장히 쉽습니다. 돌 6개를 이으면 승리하고, 착수하는 방식은 흑 1개 -> 백 2개 -> 흑 2개 -> 백 2개 -> ... 이렇게 진행이 됩니다. 이 외의 제한조건은 없습니다. 비교적 최근에 나온 게임이라 연구는 많이 되어있지 않지만 흑백 밸런스가 그럭저럭 잘 맞는것 처럼 보입니다.

5/8에 SW 알고리즘 예제파일, 가이드, 자세한 규칙 및 FAQ를 배포하고 5/15까지 알고리즘을 제출해야하기 때문에 개발 일정이 굉장히 촉박합니다. 그렇기 때문에  자세한 규칙을 알지 못함에도 불구하고 일단 알고리즘을 만들기로 했습니다. 제발 규칙에 큰 변화가 없으면 좋겠습니다. 이제부터 어떤 과정을통해서 알고리즘을 만들어가는지를 블로그에 포스팅해보겠습니다.

=======================================================================================
[삼성 육목대회] 2. 전략 조사 & 코딩 방향 잡기
막연하게 AI를 쓰면 좋겠다고 생각이 들어 알파고의 원리를 찾아봤습니다. 올해 1월달 쯤에 인공지능을 아주 잠깐 공부했던 적이 있어서 다행히 엄청 낯설지는 않았습니다. 그런데 현실적으로 개발 기간이 너무 촉박하기 때문에 찾아만 보고 딱히 이걸 통해 무언가 하지는 못했습니다.

이후 찾아본 것은 육목(Connect6, 앞으로 Connect6로 쓰겠습니다.)에 대한 논문이었습니다. 구글에서 마구잡이로 뒤져 한 6편 정도의 논문을 볼 수 있었고 이들을 통해 어느 정도 전략에 대한 감을 잡을 수 있었습니다.

그리고 NCTU6이라는 프로그램을 다운받아 실제로 컴퓨터와 Connect6를 둬보았습니다. 오목을 엄청 깊게 공부하지는 않았지만 꽤 잘한다고 생각했기 때문에(오목의 달인이라는 어플에서 최대 4단인가 5단까지 찍어봤습니다.) Connect6를 좀만 하면 금세 게임을 잘하게 될 줄 알았는데 막상 해보니까 굉장히 어려웠습니다. 뭐라고 말로 설명하기가 참 힘든데 돌을 2개 놓을 수 있다는게 굉장히 사람을 헷갈리게 만들었습니다. 그래도 계속 지다보니 어느 정도 게임에 대한 이해도가 생겼습니다. 오목을 예로 들면 내가 흑일 때 세 수 앞의 3-4를 내다보는 느낌? 그 느낌을 받을 수 있었고 이 이해를 바탕으로 일단 굉장히 초보적인 프로그램을 만들어보기로 했습니다. 이 프로그램은 다음과 같은 기능을 합니다.

입력 - 판의 상태(19*19 2차원 배열, 빈칸은 0, 검정은 1, 하양은 2로 표기), 플레이어의 색깔
출력 - 해당 플레이어의 최선의 수

이 때 "최선의 수"라는 것을 어떻게 판단하냐가 굉장히 중요한데, 저는 아래와 같은 기준으로 만들었습니다.

i) 6목이 있는지 없는지
ii) 상대의 4목이 있는지 없는지(연속한 4목이 아니더라도 상대가 2개를 놓아서 게임을 끝낼 수 있는 경우가 있는지 없는지)
iii) 상대가 나의 승리를 막기 위해 다음 턴에 써야하는 돌의 갯수(관련 논문에서는 Threat이라고 부름)
iv) Factor가 높은 순

우선순위는 i) -> ii) -> iii) -> iv)이고 Threat의 수를 구하는 방법, 그리고 Factor의 계산 식은 "A defensive Strategy Combined with Threat-Space Search for Connect6"이라는 논문을 참고했습니다.

즉, 모든 빈칸에 대해 임의로 2개를 골라 돌을 놓아본 뒤 위의 기준대로 판단하여 가장 좋은 수를 찾아냅니다. 굉장히 비효율적이고(대략 45000가지에 대해 테스트를 해봐야겠죠.) 여러 수 앞을 내다볼 수 없지만 일단 한 번 만들어보기로 했습니다.
=======================================================================================
[삼성 육목대회] 3. 정확한 룰 확인
상세한 룰을 안내받았습니다.

경기규칙은

1. 최초 1회 1수 후, 2수씩 놓음
2. 정확히 6개의 돌을 직선/대각선으로 만들면 승리(7,8,.. 목은 착수할 수 있지만 인정되지 않음)
3. 제한시간 7초/Turn, 메모리 6GB 제한
4. 아무도 돌을 놓을 수 없는 Block이 랜덤하게 존재

였습니다. 7, 8목이 렌주룰의 그것처럼 아예 착수가 불가능했다면 처리하기 까다로웠을 텐데 착수할 수 있지만 인정되지 않는 상황이면 처리하기 비교적 간단할 것 같네요. 코딩 방향은 맞게 가고 있는 것 같습니다.
=======================================================================================
[삼성 육목대회] 4. 프로토타입 완성
정말 간단한 기능을 가지는 프로토타입을 만들었습니다. 제가 이 프로그램과 둬보니 아직 부족한 점이 꽤 있지만 그래도 PlyaerFactor, OpponentFactor 값을 조절하고, 또 지금과 같이 단 한 수 앞을 내다보는 것에서 그치지않고 세 내수 앞을 내다볼 수 있게끔 수정한다면 꽤 좋은 성능의 프로그램을 만들 수 있을 것 같습니다.

최선의 수 후보군을 대여섯개 정도 만든 다음에 계속 depth를 늘려나가는 식으로 처리하면 여러 수 앞을 내다볼 수 있을 것입니다. 구체적으로 어떻게 구현할지 이제 또 논문들을 찾아보며 방향을 잡을 것입니다.

https://pastebin.com/tUAnSw1a

=======================================================================================
[삼성 육목대회] 5. 계수 조정 및 여러 수 앞을 보게끔 수정
Connect 6 어플을 참고해서 어플 내의 묘수풀이 문제를 저의 프로그램으로 풀게끔 명령을 줘보니 계수를 어떻게 조정해야할지 감이 조금 왔습니다. 그리고 코드의 짜잘한 버그를 잡았습니다. 그렇게 이것저것 손을 봐서 세 수 앞도 볼 수 있게 만들었고 또 이제 어느 정도는 잘 돌아가는데, 현재 제 프로그램의 문제는

1. 세 수 앞을 보는 프로그램이 백을 잡고 depth 탐색 없이 보는 프로그램이 흑을 잡은 상태로 경기를 했을 떄 세 수 앞을 보는 프로그램이 졌습니다. 이건 좀 말이 안되는 상황인 것 같아서 프로그램을 다시 확인해야할 것 같습니다.

2. 세 수 앞 정도는 사람도 충분히 확인할 수 있는 수 이기 때문에 적어도 대여섯 수 앞 정도는 확인할 수 있으면 좋을텐데 그렇게 되면 착수 시간이 굉장히 느려집니다. 코드에서 시간을 절약할 수 있는 부분이 있는지 다시 확인해야합니다.

3. 그 외 버그가 있을 수도 있습니다.

금토일 동안 완성도를 확 끌어올려야 할 것 같습니다.
=======================================================================================
[삼성 육목대회] 6. 중간 성과
엄청난 성과가 있었습니다. 다른 것은 하나도 안 건드린 채로 Factor를 살짝 조정하고 나서 NCTU6-level3과 대결을 했을 때, 저의 프로그램이 흑을 잡으면 NCTU6-level3 프로그램을 이겼습니다.(백을 잡을 경우에는 졌습니다.)

제가 직접 둘 때에는 NCTU6 프로그램을 단 한 판도 이기지 못했는데 이 프로그램을 이기게 된 것은 제 프로그램이 꽤 높은 성능에 도달했다는 의미일 것입니다.
=======================================================================================
[삼성 육목대회] 7. 교내 대회용 최종 프로그램
최종적으로
PlayerFactor[6] = { 0.0, 1.0, 2.0, 6.0, 0.0, 0.0 };
OpponentFactor[6] = { 0.0, 1.05, 5.0, 11.05, 0.0, 0.0 };
Breadth = 4
MaxDepth = 5
로 설정했습니다. 사실 3일 사이에 수많은 삽질을 했는데, 나의 Move와 상대의 Move를 저장하고 있다가 Is_Conn6 함수, Count_Threat 함수에서 계산할 때 기존의 코드보다 조금 더 효율적으로 짜려고 했습니다. 하지만 잘 짜지지 않았고 어쩔 수 없이 다 롤백했습니다.
Depth는 얼추 충분해보이지만 Breadth가 약간 아쉽습니다. 코드를 조금 더 효율적으로 짰으면 아마 Breadth = 6 정도까지는 가능하지 않았을까 싶습니다.
한 수당 시간제한이 7초이므로 6.2초가 지난 후에는 강제적으로 Depth를 따라 더 들어가지 못하도록 코드를 손봤습니다. 그런데 아마 이것저것 다 켜놓은 제 컴퓨터에서 돌려도 대충 5초 이내로 계산이 완료되는걸 보면 6.2초라는 한계선에 도달하는 일은 없을 것 같습니다.(만약 대회가 이루어지는 컴퓨터의 성능이 매우 안좋을 경우에도, 최적의 해를 내지는 못할지언정 시간초과로 인한 실격을 막기 위해서 꼭 필요한 제한이었습니다.)

시간이 더 있었다면 효율적인 Factor를 내부적으로 계속 대결하면서 찾아나갈 수 있었을텐데 그것까지 짜기에는 시간이 좀 부족했습니다. 1인팀이어서 그런 것일 수도 있겠네요. 또 Block의 존재 때문에 기계학습을 전혀 이용하지 못했습니다. 지금도 딱히 어떻게 학습을 해야할지에 대해서는 별 아이디어가 없습니다.

뭐 어찌됐든 거의 20시간? 30시간? 가까이 쏟아부어서 프로그램을 만들어냈습니다. 또 일주일 내내 계속 육목에 대해 고민을 많이 했습니다. 정말 오랜만에 나의 모든 것을 털어넣어 집중할 수 있었던 대회였습니다. 이제 밀린 학교숙제들을 처리해야겠네요.
=======================================================================================
[삼성 육목대회] 8. 교내 대회 후기
고려대학교 내 삼성 육목대회 교내대회가 6월 2일(오늘) 1시에 공학관에서 열렸습니다. 11시 반쯤 공학관에 가보니 삼성 AI와 육목 대결을 하는 사전 이벤트가 있었습니다. 한 판 해봤는데 당연히 졌고, 떨리는 마음을 가지고 차분하게 대회를 기다렸습니다. 대충 12시 10분부터는 삼성 DS에 대해 설명을 했습니다. 저는 아직 취업과는 거리가 한참 먼 상황이고 하드웨어에 대한 지식이 별로 없었기 때문에 아쉽게도 크게 흥미는 없었습니다.

1시부터는 육목 대회를 했습니다. 제 프로그램의 이름이 사람들의 이목을 끄는 이름이라 아주 조금 부끄러웠습니다. 고려대에서는 15팀이 출전했고 토너먼트로 진행되었습니다. 우승 상금은 150만원, 준우승 상금은 100만원이었습니다. 그리고 각 대학의 우승/준우승팀은 삼성 본사에서 하는 대회에 출전할 수 있었습니다.

1차전이 진행되는 중 다른 팀들의 AI를 보니 예상했던 것과 다르게 막강한 AI는 딱히 없어보여서 내색은 안했지만 무난하게 준우승이나 우승을 하겠다는 생각을 했습니다.  최종적으로 16강부터 결승까지 전승했고 모든 판을 대략 20수? 30수? 정도 이내로 무난하게 이겼습니다. 하지만 삼성 사내대회에서 1등/4등을 한 프로그램과 번외로 붙었을 때에는 다 졌습니다.

최종적으로 우승을 해 150만원을 받았고 1인 팀이었기 때문에 상금을 독식했습니다. 매우 기뻤습니다. 다만 조금 아쉬운게 있다면, 대회가 진행되는 컴퓨터의 처리 능력을 제대로 안내받지 못해 혹시 시간초과가 발생할까봐 탐색의 범위를 비교적 많이 제한했는데 실제로 돌려보니 늦어도 2초 내로 탐색을 종료했습니다. 만약 코드 제출 전에 한번이라도 돌려볼 수 있었거나 처리 능력을 안내받았다면 탐색범위를 조금 더 늘렸을텐데 그렇지 못했다는 아쉬움이 조금 있었습니다. 그것 이외에는 정말 만족스러웠습니다. 우승을 했으니 당연히 아무런 불만이 없습니다 :)
=======================================================================================
[삼성 육목대회] 9. 효율적인 계산을 위한 함수 수정
각 대학별 상위 2팀을 모은 결승전이 8월 23일에 진행되는 걸로 결정되었습니다. 또한 이전에 제출한 프로그램으로 그대로 경쟁해야하는 것이 아니라, 일주일의 시간 동안 수정할 수 있게 되어서 예전에 시간이 없어서 못했던 것을 급하게 수정하고 있습니다.

Threat의 갯수를 판단하는 CountThreat 함수 / 놓으면 6목을 만들 수 있는 수가 있는지 확인하는 Find_Conn6Move / 상대의 승리를 막기 위해 반드시 두어야하는 자리들의 목록을 반환하는 Get_ForcedMove 함수

이 세 함수의 경우 이전에는 놓을 수 있는 모든 361개의 자리에 대해 Threat window를 확인하는 방식으로 계산했지만 사실 직전에 둔 수의 주변 window에 대해서만 계산을 하면 됩니다. 이렇게 될 경우 계산이 빠르게 됩니다.

CounThreat, Find_Conn6Move, Get_ForcedMove 함수가 추가로 직전의 나의 수, 상대의 수를 인자로 입력받게끔 수정해서 조금 더 빨리 계산할 수 있게 했습니다.

이전에는 Breadth = 4, Depth  = 5로 대략 5초 내로 계산이 이루어졌는데 지금은 Bradth = 4, Depth = 5의 경우 1초 내로 계산이 이루어지고 Breadth = 5, Depth = 6으로 계산했을 때 대략 10초 정도만에 답이 나왔습니다. 아주 조금만 더 수정하면 Breadth = 5, Depth = 6으로 탐색할 수 있을 것 같습니다.

다만 게임이 많이 길어질 경우 뜬금없이 프로그램이 오류를 냈습니다. 파일 입출력으로 착수를 로그로 찍어보니 Y의 좌표로 -1을 입력해서 발생한 오류로 보입니다. 코드를 다시 보며 버그를 바로 잡아야합니다.
=======================================================================================
[삼성 육목대회] 10. 버그 수정 및 적절한 Factor를 찾기 위한 유전 알고리즘
어제 자기 전에 발견한 버그를 거의 하루 종일 수정했습니다. 게임이 어느 정도 이상으로 길어지게 되면 허용되지 않는 곳에 계속 착수를 시도했고(4, -1과 같이 판을 벗어난 곳) 파일 입출력으로 착수한 곳을 로그로 남겨놨지만 그닥 쉽게 찾아지지가 않아 어쩔 수 없이 잡다한 정보를 전부 로그에 남겨본 결과 threat이 1개가 있을 때 발생하는 문제임을 발견했습니다. 그래서 threat이 1개일 때 계산하는 코드를 중점적으로 살펴보았고 오류를 잘 해결해 판을 전부 채우는 것에 성공했습니다. 반드시 외부 프로그램을 통해 내 AI를 실행시켜야하기 때문에 디버깅이 너무 까다롭습니다.

이제는 적절한 Factor를 찾기 위한 유전 알고리즘을 고안했습니다. 현재 사용하고 있는 Factor는 double PlayerFactor[6] = { 0.0, 1.0, 2.0, 6.0, 0.0, 0.0 };
double OpponentFactor[6] = { 0.0, 1.05, 5.0, 11.05, 0.0, 0.0 }; 인데 합리적인 이유가 있는 것이 아니고 그냥 감으로 찍어맞춘것이기 때문에 개선의 여지가 있다고 생각했습니다.

유전 알고리즘은 아래와 같이 구현했습니다.
일단 각 세대에 다양한 Factor를 가지는 16개의 개체를 만들었습니다. 그 후 모든 개체들이 리그전 방식으로 10번씩 게임을 해서 결과를 저장했습니다. (빠른 진행을 위해 Depth = 2, Breadth = 2로 제한. 이렇게 했을 때 한 게임에 대략 0.3~1초 정도의 시간이 소비되었습니다.)
- 승률이 높은 순으로 4개의 개체는 그대로 보존
- 1위와 2위의 교배로 자손 4개를 생성
- 1위와 3위의 교배로 자손 3개를 생성
- 2위와 3위의 교배로 자손 2개를 생성
- 1위와 4위의 교배로 자손 1개를 생성
- 1위와 5~7위의 평균의 교배로 자손 1개를 생성
- 2위와 8~11위의 평균의 교배로 자손 1개를 생성
이렇게 다음 세대로 16개의 개체를 넘겼습니다. Local maximum으로 빠지는 것을 막기 위해 자손을 생성할 때 단순히 평균을 내는 것이 아니라 표준편차 = 0.2 * 평균으로 두어 정규분표의 확률대로 자손을 생성하도록 했습니다.

한 세대에 총 16*16*10 = 2560게임을 해야하기 때문에 세대가 진화하기 위해서는 30~50분 정도가 필요합니다. 밤새도록 돌려놓고 내일 결과를 확인해봐야겠네요.

여담이지만 구현이 썩 쉽지는 않았습니다. 제공된 대결프로그램을 통하지 않고 대결을 할 수 있게 하는 프로그램을 새로 짜고 그러고나서 유전알고리즘 또한 구현을 해야 했습니다.
=======================================================================================
[삼성 육목대회] 11. 유전 알고리즘 중간 결과 및 추가 개선 사항
67세대에 도달했을 때 승률 1위는

double PlayerFactor[6] = { 0.0, 1.0, 37.05, 158.25, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 1.73, 36.24, 266.28, 0.0, 0.0 };  이었습니다.(같은 세대의 다른 개체들과 대결했을 때 승률 대략 60%)

맨 처음에 사용하던
double PlayerFactor[6] = { 0.0, 1.0, 2.0, 6.0, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 1.05, 5.0, 11.05, 0.0, 0.0 }; 와 비교했을 때 많은 변화가 있었네요.

유전 알고리즘은 일단 계속 돌릴 계획이고 이외에도 추가적으로 일정한 시간(현재는 6.2초로 두었는데 6.7초 내지는 6.9초로 앞당길까 생각하고 있습니다.)이 지날 경우 탐색을 중단하는 것과 더불어 아예 후보에서 제하도록 코드를 수정했습니다.(이전에는 탐색은 중단하지만 운이 나쁘면 후보로 들어갈 수도 있었습니다.)

전반적으로 Threat을 계산할 떄 매 (x, y)에 대해서 (x, y)부터 (x+5*dx[dir], y+5*dy[dir])까지 6칸을 전부 확인하는 대신 DP를 이용하면 계산을 줄일 수 있을 것 같긴 하지만 그렇게 될 경우 코드를 너무 많이 고쳐야해서 포기했습니다.

두 수를 착점할 때 Score를 계산하는 Get_ScoreOfDoubleMoves 함수를 여러 번 호출할 때 계산한 것을 또 계산하는 문제점이 있는 것으로 보입니다. 내일 이 함수를 잘 손봐서 계산을 조금 더 효율적으로 하도록 만들 계획입니다.
=======================================================================================
[삼성 육목대회] 12. 하루종일 삽질
속도를 조금 더 개선하기 위해 myBoard를 함수 내의 지역 변수로 copy해서 작업하는 대신 함수의 인자로 받은 2차원 포인터를 통해 직접 myBoard를 건드리고자 했습니다. 이러면 copy하는 시간(361개를 copy해야하고 생각보다 빈번해서 시간을 꽤 많이 잡아먹는다고 생각함)을 절약하니까 더 빨라질 줄 알았는데 전혀 그렇지 않고 도리어 속도가 4배에서 심하게는 10배 가까이 느려졌습니다. 구현에서 실수를 했나 싶어서 코드를 꼼꼼히 살펴보았는데 딱히 그런 것도 없었습니다.

현재 스택에서 멀리 떨어진 곳의 변수를 다룰 때 속도가 급격하게 느려지는 것 같다는 심증만 있을 뿐 정확히 왜 이런 일이 발생했는지는 잘 이해가 가지 않습니다. 어쩔 수 없이 코드를 싹 밀고 원상태로 되돌렸습니다.

그리고 승리조건이 만족될 때 턴을 줄이는 것, 시간을 넘겼을 때 현재 보고있는 탐색 대상은 무시하는 것 등을 짰는데 (-1, -1), (-1, -1)을 기록하라는 명령이 계속 발생했고 왜 이런 오류가 발생했는지 도저히 찾을 수가 없어서 어쩔 수 없이 Find_BestDoubleMovesByDepthSearch 함수도 갈아엎었습니다.

결국 하루종일 한거라고는 유전 알고리즘 결과를 본 것과, 이것저것 짰다가 오류나서 되돌린 것 밖에 없네요. 멘탈 잡고 내일부터는 다시 개선을 해나가야겠습니다.

-------------------------------------------

자기 전에 마지막으로 시도해본다는 생각으로 Find_BestDoubleMovesByDepthSearch를 다시 확인해봤는데 잘못된 점을 찾았습니다. tmpMax의 초기값을 -10000000으로 뒀는데 현재 내가 필패일 때 계산 과정에서 -10000000보다 값이 작아질 수 있어서  (-1, -1), (-1, -1)이 반환되었습니다. 기분 좋으면서도 살짝 허탈하네요.

현재까지 Breadth = 5, Depth = 6까지 시간 내에 통과됩니다. 유전 알고리즘 결과가 어느정도 수렴하는 것으로 보여지면 Factor를 확정하고 Breadth, Depth를 얼마로 할지 고민해봐야겠네요. 아직까지는 1위가 승률 60~70%, 16위가 승률 40%여서 편차가 큰 편입니다.
=======================================================================================
[삼성 육목대회] 13. 유전 알고리즘 결과 확인
거의 이틀에 걸쳐 유전 알고리즘으로 200세대 넘게 진행한 결과

double PlayerFactor[6] = { 0.0, 1.0, 3.96, 14.20, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 4.40, 9.46, 22.85, 0.0, 0.0 };

을 얻었습니다. 이것과 예선에 쓴

double PlayerFactor[6] = { 0.0, 1.0, 2.0, 6.0, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 1.05, 5.0, 11.05, 0.0, 0.0 };

을 대결시켜보았을 때 당연히 유전알고리즘으로 얻은 facotr가 압승할 것으로 예상했지만 흑/백 각각으로 25판씩 해본 결과 거의 반반이었습니다. 굉장히 당혹했습니다. 어쩔 수 없이 각 세대의 1위들을 차례로 예선에 쓴 factor와 대결을 계속 해본 결과

double PlayerFactor[6] = { 0.0, 1.0, 3.83, 14.37, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 2.40, 4.40, 26.44, 0.0, 0.0 };

가 거의 승률 75%를 기록하며 강한 모습을 보여줬습니다. 결론적으로 말하면 유전알고리즘 자체로는 그다지 좋은 factor를 건지는 것에 실패했지만 좋은 factor의 후보군들을 많이 획득할 수 있었습니다.

이제 각 세대의 1등과

double PlayerFactor[6] = { 0.0, 1.0, 3.83, 14.37, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 2.40, 4.40, 26.44, 0.0, 0.0 };

를 대결시켜 승률을 저장할 계획입니다. 도전자 factor는 총 37개이고 Depth = 3, Breadth = 3으로 할 계획입니다. 대충 4~5시간 정도 걸릴 것 같습니다. 자고 일어나면 결과가 나와있겠네요.
=======================================================================================
[삼성 육목대회] 14. Factor 확정 및 합리적인 Breadth, Depth 정하기
Breadth = 3, Depth = 3인 환경에서 흑/백을 번갈아 100판씩 대결해본 결과

double PlayerFactor[6] = { 0.0, 1.0, 3.96, 12.05, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 1.33, 6.79, 19.52, 0.0, 0.0 };

일 때 승률이 가장 괜찮았습니다.(다른 후보 37개와 붙었을 때 단 2개의 후보 빼고 전부 50% 이상의 승률을 기록, 50% 아래인 2개에 후보에 대해서도 47%, 49.25%로 충분히 합리적인 승률을 기록)

그래서 Factor는

double PlayerFactor[6] = { 0.0, 1.0, 3.96, 12.05, 0.0, 0.0 };

double OpponentFactor[6] = { 0.0, 1.33, 6.79, 19.52, 0.0, 0.0 };

로 확정했습니다. 참고로 기존에 쓰던 Factor와의 대결에서는 61%의 승률을 기록했네요. 그러면 이제 Breadth와 Depth를 어떻게 할지 정해야합니다.

우선 집의 컴퓨터를 기준으로(i5-7500)

Breadth = 5, Depth = 5 => 대략 3.5~4초
Breadth = 4, Depth = 6 => 대략 4~4.5초
Breadth = 3, Depth = 7 => 대략 2.5~3.5초

정도의 시간이 소요됐습니다. 각 Depth에 대해 Breadth가 저것보다 1 증가하게 될 경우 7초를 훌쩍 넘겨버려서 이제 오늘 밤새도록 이 3가지 경우에 대해 대결을 시켜서 결과를 살펴본 후 가장 좋은 것으로 제출하고 마무리할 계획입니다.


=======================================================================================
[삼성 육목대회] 15. 최종 프로그램
Depth 5, 6, 7 끼리 자가대결을 했을 때 Depth 5 vs Depth 6 / Depth 5 vs Depth 7 은 승률이 반반이었으나 Depth 6 vs Depth 7에서 Depth 7이 압도적으로(승률 80% 이상) 이기는 것을 보고 Depth = 7로 정했습니다.

앞의 게시글에 적어두었듯이 Breadth = 3, Depth = 7로 설정하면 지금 쓰는 데스크탑에서 매 턴마다 대략 3초 내외를 사용했고 주어진 시간을 최대한 다 활용하기 위해서

i) 현재 보드에서 맨 처음 내가 둘 수 있는 수의 후보는 3개로 제한하지 않고 시간이 허락하는 한 최대한 많이 트리를 만듬
ii) i에서 계산한 현재 보드에서 맨 처음 내가 둘 수 있는 수의 후보 각각에 대해 상대의 대응수 후보 중에 점수가 높은 4개를 계산
iii) ii에서 계산한 상대의 대응수에 대한 나의 대응수를 3개 계산
iiii) iii에서 계산한 나의 대응수에 대한 상대의 대응수를 3개 계산
.
.
.
이렇게 총 7단계를 들어갑니다.

즉 제일 상위 레벨에서는 Breadth에 제한을 두지 않고 시간이 허락하는 한 최대한 크게 잡고, 바로 밑의 레벨에서는 Breadth = 4이고, 그 이후로는 Breadth = 3입니다.

예선과 비교했을 때
1. 예선떄는 Breadth = 4, Depth = 5였지만 지금은 Breadth = 3, Depth = 7이다. 여러 함수들을 최적화시켜서 두 수를 더 내다볼 수 있게 되었다.
2. 예선때는 Factor를 주먹구구식으로 정했지만 지금은 합리적인 방법으로 최적의 Factor를 정했다.
3. 대회에 쓰이는 컴퓨터의 연산이 예상보다 많이 느리거나 많이 빠르더라도 주어진 시간을 최대한 활용해서 최적의 답을 얻어낼 수 있도록 코드를 수정했다.

정도가 큰 차이라고 볼 수 있겠습니다. 결선용 최종 프로그램과 예선때 제출한 프로그램을 대결시켜보았을 때 결선용 프로그램이 거의 승률 90% 정도는 나오는 것 같습니다. 매우 만족스럽네요.

예선떄와 비슷하게 일주일만에 정말 모든걸 쏟아부어서 만들어냈습니다. 개발기간동안 진짜 하루종일 어떻게 하면 더 개선할 수 있을까 그 생각만 한 것 같습니다. 맨날 해떠오를 때쯤 자고(지금이 오전 8시경인데 아직까지 안자고있네요. 빨리 끝내고싶어서ㅠㅠ) 잘 때에도 프로그램을 돌려놓고 일어나자마자 결과 확인하고 코드 수정하고 그런 생활의 반복이었습니다.

그래도 정말 좋은 경험이었습니다. 대체 어디서부터 어떻게 해야하나 막막했었는데 어느 순간부터 제 실력을 훌쩍 뛰어넘어버린 제 프로그램을 보는게 꽤 재밌었습니다. 또 "육목에서 최적의 수 찾기"라는 다소 추상적인 큰 문제를 해결하기 위해 이런저런 알고리즘들을 적절하게 변형해서 적용시켜보고 실패도 해보는 과정들이 좋았습니다.

https://github.com/blisstoner/Connect6AI_SamsungDSCompetition