예상치 못했는데, 운빨로 (라고 말하면 다들 -_- 하겠지만) 1등했다.

기록을 남길겸 해서 알고리즘을 어떻게 구상했는지 쌓아나간 방식을 적어본다.



1. 동작 Queue 작성
기본적으로 동작이 Action이라는 함수를 외부에서 호출해 줄때마다 하나의 동작을 하게 되는것으로 추정되었다.
(Action 결과 값으로 누를 키를 m_key에 돌려주면 그 동작을 수행함)

그래서 맨먼저 내가 결정한 동작을 기억하고 그걸 하나씩 넘겨주도록하기 위해 동작 큐를 만들었다. 기존에 있던 랜덤 동작을 Decide 함수로 옮겨서, Decide가 큐에 집어넣게 하고, 큐에서 맨처음 동작을 뽑아 그걸 m_key로 전달하도록 하였다. 일단 여기서 잘 도는지 DLL로 만들어 확인.

2. 다음에 어떤 동작을 할까?
동작을 선택하기 위해 브레인 스토밍을 통해 나열을 해본 후 일단 기존에 무엇이 구현되어있나 살펴보다가 Simul을 발견했다. 대충 위에 떨어지는 블럭을 포함해서 어떤 동작을 했을때 연쇄와 없어지는 블럭 수를 계산해 주는 녀석이었다.
"오 귀찮게 내가 안짜도 되겠네 ㄱㅅ"
그외 사소한 구현들을 확인하고 결정을 내렸다.

3. 한단계만 살펴봐 봅시다.
한단계에서 선택가능한 동작의 수가 7*14*(Left or Right) 해서 약 200개의 경우의 수가 있으므로 두 단계까지 탐색하기는 많을꺼 같아 한단계만 보고 해보자라고 판단했다. 7*14*2 의 경우에 대해 Simul해보고, 그 결과보드에 대해 점수를 계산해서 점수가 커지는 쪽의 이동을 하기.

4. 점수는 어떻게 계산할까?
코딩을 대충대충 하다가 옆에 있던 포항공대 팀원분이랑 (escamp는 팀을 학교를 섞어서 짜주니) 어떤걸 점수로 하는게 좋을까 이야기를 해보았다. 마침 지나가던 유키에게도 찔러서 "색깔"이란 키워드를 얻었다.
그래서 맨 처음엔 
(1) 색깔별 블록 개수의 표준 편차가 크게 (특정 색이 몰리면 좋아진다)
(2) 최대 연쇄의 길이가 길어지게 (당연)
(3) 각 위치별 가능한 연쇄의 표준 편차가 적어지게 (혹시나 방해블록이 생겨도 뒤에 피해가 적게)
(4) 방해블럭의 수가 적어지게
하는 방향으로 점수를 계산했다. (2)가 가장 가중치가 컸고, 나머지는 적당한 값을 줬던거 같다. 그리고 테스트.
했더니 완전 바보짓을 하는 AI 완성 ;ㅁ; 랜덤한테 진다!

4.1. 왜 바본가?
어떤 동작을 해서 연쇄수를 늘릴수 없을땐 아무 동작이나 하게 된다는 것을 조금만 생각해보니 알 수 있었다. 바보 orz
그래서 또 고민. 무엇을 하면 보통의 경우에 점수를 높일 수 있을까?
그래서 생각해낸게 같은 색깔들을 모으기.
6각형 모양에서 자길 중심으로 거리가 1인 곳에 있으면 2점 거리가 2인곳에 있으면 1점 이런 식으로 점수를 주려 했다.
하지만 귀찮으니까 대충대충 2차원 배열을 기준으로 계산을 했다. 머 근처에있으면 적당히 좋겠지.
그리고 DLL을 만들고 테스트.

4.2. 여전히 바보 orz
색깔 모으는 기능을 넣어줬더니 이젠, 색깔을 모으기만 한다. 그것도 터트리면 연쇄가 짧아지니까, 터지지 않도록 색깔만 모으고 있더라. 이때쯤 흥 버럭 쳇 이러면서 저녁을 먹으러 갔던것 같다. 그리고 저녁을 먹으면서 이런것과 저런것과 그런것을 넣으면 크고 훌륭해 질꺼야! 라고 했다가 밥먹고 올라오니 다 까먹었다.

5. 좀 터트려좀 봐라
그래서 이제 좀 터트리게 하는 쪽으로 성향을 만들도록 코드를 넣어봤다. 언제 블럭을 연쇄를 시작할까?

(1) 상대방이 나한테 방해블럭을 보냈을때 (이때 안 막으면 내 연쇄 다 깨진다)
(2) 점수차가 많이 날때
(3) 시간이 얼마 안남으면 단타를 해서라도 점수를 올려야할 것 같다.

여기까지 같이 포항공대 분이랑 이야기를 했었다. 근데 주최측 AI 작성자 분이 게임 남은시간은 알아낼 수 없다고 하길래 이런저런 꽁수를 부릴까 하다가 그냥 랜덤신을 믿기로 했다.

기본 전략을 이렇게.

(1) 방해블럭이 있는가? -> 최대 연쇄 만들어 둔 것을 반드시 터트린다.
(2) 내가 100점이상 지고 있으면 터트리는 경우에 가산점을 준다.
(3) 나랑 상대방이 거의 비슷하면 1/3의 확률로 터트리는 것에 가산점을 준다.
(4) 내가 앞서고 있는데 100점 밑인 경우 1/6의 확률로 터트리는 것에 가산점은 준다.

시간을 얻을 수 없어서 점수만 기준으로 하되, 확률을 이용해서 비슷하게 동작하기를 기대했고 그리 나쁘지 않았다.
가산점은 그냥 연쇄수랑 터트리는 개수를 이용해서 적당한 값을 더해줬다.

여기서 테스트를 했더니 먼가 막 모양을 만들다가 혼자서 구석에가서 특정 위치를 빙글빙글 혼자서 돌리고 있었다. 그러다 상대방이 (랜덤으로 테스트 중이었음) 먼가 연쇄를 해서 방해블럭을 보내면 이쪽도 갑자기 연쇄를 하는 이상한 동작을 보였다. 이때까지는 왜 그러는지, 뭐가 문제인지 잘 몰랐다.

어쨌든 아직까지는 먼가 삽질만 하는 AI.

6. 폭탄 기능 안넣으면 섭하지
이 게임은 조금 변형이 있어서 방해 블럭을 다 날려주는 폭탄이 게임상에 존재했다. 둘이서 이야기하면서 (분명 팀은 세명이었던거 같은데?) 대충 24개 정도면 폭탄을 써도 되지않을까? 라고 대화를 하고, 그렇게 코딩을 집어넣었다. (한시간 남긴 시점) 그리고 랜덤과 대전을 하다가 한번 20개 정도 맞았는데 잘 플레이를 못하길래 이 부분도 수정해야 겠다고 판단하고, 인생 만사 주사위신의 뜻이라 믿고 10개부터 24개인 경우 linear한 확률로 폭탄을 터트리고 24개 이상부터는 100%로 터트리도록 코딩을 했다.

이걸 아래 7번과 함께 하면서 동작하는지 확인을 못했었는데, 결승전에서 상대편이 14개 짜리 방해 블럭을 보내주시는 덕분에 이 AI 처음으로 폭탄을 사용했다 >ㅁ< (결승에서 처음..)

7. 했던 짓 또 하지 말기
5번 마지막 부분에서 이야기한, 혼자서 한곳에서 계속 돌리고 있는 문제.
이경우는 이전에 했던 행동을 기록하고 있으면 쉽게 발견할 수 있다. (x, y, 돌린방향)을 저장해서 체크를 했는데, 어떻게 할까? 라는 브레인 스토밍 시간을 잠시 가졌다. 랜덤한 동작을 여러번 해버리고 그 이후에 다시 AI를 돌리자! 라고 대충 의견이 모아졌었는데 랜덤과 대전 중에 중간에 계속 돌리는 상태에 놓였을때를 좀 살펴봤다. 그랬더니 손으로 살펴봐도 대략 4콤보 이상이 있음을 확인.
"아, 이미 연쇄를 다 준비해 놓고 더 이상 추가를 못해서 삽질하나보다"
그리고 회전을 반복하는게 발견된 경우, 현재까지 준비해둔 최대 연쇄를 골라서 터트리도록 코딩을했다. 이상황에서 30분이 남았고, 나의 AI는 괴물이 되었다. 10콤보가 뭐야 ㅠㅠ

그리고 최종 DLL을 만들고, 대회를 했고, 발랐다. ^ㅁ^ xbox ㄱㅅㄱㅅ

* 이미지는 저작권 같은 문제가 왠지 있을꺼 같아서 안 넣음 ( --)