[2018 삼성 육목대회] 1. 이전 대회 코드 점검 및 개발 방향 잡기

http://www.samsungsemiconstory.com/1819?category=734711

올해에도 대회가 다시 열립니다. 작년에 상금을 쓱싹하고 올해는 대회가 대체 언제쯤 열릴까 기대하고 있었는데 시기 적절하게 방학에 열리네요. 작년처럼 학기 중에 열렸으면 참가하는게 굉장히 부담이었을텐데 방학이라 그래도 조금 낫습니다. 학기중보다 방학이 조금 더 한가하긴 하지만 ACM ICPC를 준비하느라 시간을 많이 쓰는건 매한가지여서 기존의 프로그램을 아예 갈아엎는건 힘들 것 같고 적절하게 수정만 해야할 것 같습니다.

룰이 달라졌는데,

- 착수 시간이 매번 2-7초 사이에 랜덤하게 주어진다 -> 이건 기존의 함수에서 6.5초로 고정해둔 time limit 값만 바꿔주면 되므로 큰 상관이 없습니다.

- Block이 내 턴에 나의 돌로 취급이 됩니다. -> 이게 정말 큰 변수입니다. 이 조건으로 인해 evaluation 함수도 변경이 필요하고, 다른 육목 인공지능들과 테스트를 해볼 수도 없습니다.

- 7목 이상을 두면 실격패입니다. -> 이것 또한 evaluation 함수의 변경이 필요합니다. 금수유도도 가능합니다.

일단 당장 생각나는 개선할 점은 아래와 같습니다.

- evaluation 함수를 새로 고안해야 합니다.

- minimax algorithm을 사용했는데, alpha beta pruning으로 한정된 시간에 더 깊게 보도록 할 수 있습니다. 사실 정확하게는, 이전에 minimax algorithm / alpha beta pruning을 모르는 상태로 야매로 minimax algorithm 비스무리하게 만들어놓은거라 좀 많이 손을 대야합니다.

- 좌표를 pair<int, int>와 pair<pair<int,int>, pair<int,int>>로 처리했는데 각 좌표의 값이 0~18 범위를 가지므로 각 좌표의 x, y 하나에 5개의 bit씩을 할당하면 그냥 int 하나로 가지고다닐 수 있습니다. 이렇게 수정하면 시간 면에서는 이득을 취하겠지만 이것 또한 코드를 갈아엎어야 합니다.

- DFS로 최선의 수를 찾은 다음에 그냥 끝내는 것이 아니라, 아예 tree를 만들면서 진행하면 이전에 했던 연산을 계속 활용할 수 있습니다. 단 Tree의 Node를 잘 생성하고 또 잘 삭제해야합니다. 그렇지 않으면 심각한 메모리누수가 발생할 수 있습니다.

- 쓰레드를 사용해 병렬적으로 돌립니다.

우선순위는 위에 적힌 순서입니다. 일단 evaluation 함수를 고안해야 변경된 룰에서 굴러갈 수 있는 프로그램이 나올 것이고, 그 이후의 작업들은 성능을 향상시키는 작업이기 때문입니다.

예전 코드부터 찾아서 기억을 상기해봐야겠습니다. 예전 코드는 집 컴퓨터 기준 1초에 대략 8000번 정도 DepthSearch 함수를 실행할 수 있습니다.