GA - 오델로 - 유전자설계

오델로(Othello)라는 게임이 있습니다. 8×8의 칸에 교대로 돌을 놓으며, 내 돌 사이에 상대방의 돌을 끼워넣으면 내 돌로 바뀌는 것이죠. 물론 오델로게임을 하는 AI는 많이 나와 있습니다. 그런데 이 오델로게임을 하는 AI를 유전자알고리즘으로 진화시킬 수 있을까요?

1. 유전자설계 및 작동방식
일반적으로 이런 게임에서는 놓을 수 있는 자리를 탐색 후 각 자리에 가중치를 계산, 가장 높은 가중치를 갖는 장소를 찾는 것이 일반적입니다. 이를테면 다음과 같은 상황에서 흰돌이 놓을 차례라면
흰돌을 놓을 수 있는 '가'~'마'까지 다섯군데의 가중치를 계산합니다.
오델로에서 가장 중요한 것은 직선으로 상대방 돌을 포위할 수 있는가 없는가입니다. 그러므로 '나' 위치의 가중치를 계산한다면 다음과 같은 네 방향의 패턴을 추출합니다.
이때 주의할 것은 흰돌이냐 검은돌이냐가 아니라 내돌이냐 상대방돌이냐로 구분을 해야 합니다. 흑돌이냐 백돌이냐로 구분하면 흑의 입장이냐 백의 입장이냐에 따라 가중치가 달라지기 때문이죠.
그러므로 빈칸을 '.', 상대방돌을 'E', 내돌을 'M', 가중치를 계산할 장소(여기서는 '나' 칸을 의미)를 '+'로 한다면, 붉은색선 방향으로는 '..+EMM..', 노란색선 방향으로는 '...+....', 녹색선 방향은 '..+EE..', 보라색선은 '..+E..'이란 패턴이 추출됩니다. 이렇게 추출된 패턴으로부터 가중치를 구하면 됩니다.

그렇다면 여기서 만들려는 '오델로플레이어'의 유전자는 이러한 '패턴과 가중치의 묶음'으로 할 수 있을 것입니다. 만약 이 오델로플레이어의 유전자가 다음과 같다면

('.M+.E.', 0.7235)
('...+....', 0.798)
('..+EMM..', 0.37)
('..EE+..', 0.625)
('..M+EM.', 0.012)

각 방향에서 찾은 패턴을 이 '유전자 묶음'으로부터 찾아 가중치를 더합니다. '..+EMM..'의 경우는 0.37, '...+....'의 경우는 0.798이 되겠군요. '..+EE..'은 이 묶음에 없지만 대신 '..EE+..'은 존재하는군요. 그 값은 0.625입니다.
그런데 '..+E..'의 경우는 뒤집힌 '..E+..'도 존재하지 않습니다. 이것은 이 오델로플레이어가 이와 같은 패턴을 처음 만난다는 뜻입니다. 이럴 경우는 이 패턴을 끼워넣고 랜덤값을 추가합니다. 즉

('.M+.E.', 0.7235)
('...+....', 0.798)
('..+EMM..', 0.37)
('..EE+..', 0.625)
('..M+EM.', 0.012)
('..+E..', 0.152)

랜덤으로 발생된 0.152라는 가중치를 가지고 '..+E..'라는 패턴이 추가되었습니다. 결국 '나' 위치의 가중치는 0.37 + 0.798 + 0.625 + 0.152 = 1.945가 되겠죠. 이런 식으로 '가'~'마'까지의 가중치를 계산한 후 가장 높은 가중치의 위치를 선택하는 방식으로 만들었습니다.