[2017 삼성 육목대회] 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분 정도가 필요합니다. 밤새도록 돌려놓고 내일 결과를 확인해봐야겠네요.

여담이지만 구현이 썩 쉽지는 않았습니다. 제공된 대결프로그램을 통하지 않고 대결을 할 수 있게 하는 프로그램을 새로 짜고, 그러고 나서 유전알고리즘 또한 구현을 해야 했습니다.