[프로젝트] 꼬들 AI (Kordle AI)
꼬들이 뭔가요?
Wordle이라는 유명한 영단어 야구 게임 사이트가 있습니다. 매일 특정한 5자 단어가 선정되고, 우리는 그것을 맞춰야 하죠. 5자 단어를 전달하면, 각 자리의 글자가
- 정답 단어와 완전히 일치하는 글자인지,
- 정답 단어에 포함되지만 위치를 틀린 글자인지,
- 정답 단어에 전혀 포함되지 않는 글자인지
여부를 알려줍니다. 유저에게 주어진 기회는 단 6번 뿐이죠.
 |
| <Kordle> |
이에 누군가가 질세라, 한국형 Wordle인 꼬들(Kordle) 서비스를 열었습니다. 초성, 중성, 종성이 결합되는 한국어의 특성상 Wordle과는 사뭇 다른 느낌을 선사합니다. 그래서, 어렵습니다. 연속 정답을 50일, 100일 쌓고 싶은데 말이죠! 우리에게 좋은 방법이 없을까요?
프로그램은 언제나 옳습니다..
꼬들은 단순한 게임입니다. 정답의 개수는 한정적이고, 주어진 정보를 얼마나 잘 활용하느냐에 따라 달려있죠. 그 중 가장 핵심적인 특징 중 하나는, 완벽하게 예측 가능한 게임이라는 것입니다! 난수는 존재하지 않습니다. 그러니 꼬들 문제를 프로그램으로 멋지게 풀어낼 수 있는 방법이 있지 않을까요?
먼저, 꼬들부터 만들어봅시다.
하루에 한 번밖에 할 수 없는 꼬들 사이트에 들어가서 여러 번 하게 시켜달라고 떼를 부릴 순 없죠. 대신 우리의 전략을 시험해볼 수 있는 가짜 꼬들을 만들어봅시다. 저는 KordleMachine이라는 멋진 이름을 지어봤습니다.
KordleMachine은 정답만을 꽁꽁 감싸고 있는 블랙박스와 같습니다. 우리가 KordleMachine에게 단어를 전달해주면, 그 단어와 정답을 비교해서 결과를 반환해주죠!
 |
| <Kordle Machine> |
이런 기능을 갖기 위한 헤더를 구성해봅시다:
소스코드: KordleMachine.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | class KordleMachine { private: wstring answer; int count; public: static const int KORDLE_LENGTH = 6; public: KordleMachine() = delete; KordleMachine(wstring answer) : answer(answer), count(0) {} KordleResult queryKordle(wstring queryString); static KordleResult queryKordle(wstring answer, wstring queryString); int getCount(); }; | cs |
KordleMachine은 생성자로 정답을 입력받습니다. 그리고 해당 KordleMachine에게 몇 번 질문하였는지 알려줄 수도 있죠. 가장 중요한 것은 질문에 대한 결과를 알려주는 것입니다. 이는 queryKordle() 함수를 통해서 수행할 수 있습니다.
다만 우리는 queryKordle() 함수를 조금 더 분리해볼 수 있습니다. 질문에 대한 결과를 낸다는 것은, 결국 정답과 질문 두 개를 비교하는 것입니다. 따라서 정답과 질문이 주어지면 결과를 반환하는 queryKordle(string, string) 정적 함수를 만들고, KordleMachine은 자신이 생성자의 인자로부터 부여받은 정답을 이용해 해당 정적 함수를 호출해주기만 하면 되죠!
질문에 답변하기
KordleMachine은 어떻게 질문에 대한 답변을 할 수 있을까요? 단순히 질문과 정답의 글자가 같은 자리에 있다면 초록색, 다른 자리에 있다면 노란색, 아무것도 아니라면 검은색을 던지면 되는 것이라고 생각한다면 오산입니다. 우리가 조심히 다뤄야할 예외 경우들이 존재합니다. 다음의 경우를 생각해보죠:
- 정답: ㄱㅜㄴㄷㅏㅣ
- 질문: ㄱㅜㄱㄱㅜㄴ
- 결과: ■■■■■■
질문의 앞쪽 ㄱ이 이미 정답의 ㄱ을 알아맞추어 초록색으로 표기되었기 때문에, 뒤의 ㄱ들은 검은색으로 표기됨에 주의하세요!
- 정답: ㅈㅏㄱㄷㅏㅇ
- 질문: ㄱㅗㄹㅁㅗㄱ
- 결과: ■■■■■■
이는 노란색의 경우에도 마찬가지입니다. 뒤쪽 ㄱ은 검은색으로 표기됨에 주의하세요.
따라서 우리는 이미 결과로 정보가 나타난 글자들의 목록을 유지해야 합니다. 또한 정보를 표기하는 것에는 순서가 중요합니다. 이는 초록색과 노란색의 조건이 포함 관계에 있기 때문입니다. 초록색(정답에 포함되며, 위치까지 일치)인 글자는 노란색의 조건(정답에 포함됨)도 만족합니다. 따라서 초록색인지 아닌지의 여부를 먼저 판단하고, 그 다음에 노란색인지의 여부를 판단해야 합니다.
queryKordle()은 주어진 query 단어에 대해, 객체가 갖고 있는 answer와 비교해 result를 반환합니다. 의사코드는 다음과 같습니다:
의사코드: queryKordle()
1 2 3 4 5 6 7 8 9 10 11 | for i = 0 to 5: if answer[i] = query[i]: resullt[i] = green visited[i] = true for i = 0 to 5: if visited[i]: continue; for j = 0 to 5: if answer[i] = query[j] & result[j] = black: result[j] = yellow visited[i] = true | cs |
소스코드: KordleMachine.queryKordle()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | KordleResult KordleMachine::queryKordle(wstring queryString) { count++; return queryKordle(answer, queryString); } KordleResult KordleMachine::queryKordle(wstring answer, wstring queryString) { bool visited[KordleMachine::KORDLE_LENGTH]; array<KordleColor, KordleMachine::KORDLE_LENGTH> result; for (int i = 0; i < KordleMachine::KORDLE_LENGTH; i++) { result[i] = KordleColor::BLACK; visited[i] = false; } for (int i = 0; i < KordleMachine::KORDLE_LENGTH; i++) { if (answer[i] == queryString[i]) { result[i] = KordleColor::GREEN; visited[i] = true; } } for (int i = 0; i < KordleMachine::KORDLE_LENGTH; i++) { if (visited[i]) continue; for (int j = 0; j < KordleMachine::KORDLE_LENGTH; j++) { if (answer[i] == queryString[j] && result[j] == KordleColor::BLACK) { result[j] = KordleColor::YELLOW; visited[i] = true; break; } } } return KordleResult(result, queryString); } | cs |
이제는 전략을 생각해야 할 때입니다.
구조 설계하기
전략을 생각하기에 앞서 중요한 것은, 클래스들의 책임을 분리해야 한다는 것입니다. KordleMachine은 단순히 질문에 대한 답변만을 하는 클래스입니다. KordleMachine이 최적의 질문 단어를 찾아내야 할 책임은 없죠.
따라서 KordleMachine을 이용해 최적의 해를 알아내는 KordleSolver를 분리하도록 합시다. KordleSolver는 질문할 수 있는 단어, 정답이 될 수 있는 단어들을 객체 내 상태로 유지합니다. 현재 문맥에서 최적의 단어를 반환해주기도 하며, 결과를 받아들여 새롭게 상태를 갱신하기도 합니다.
소스코드: KordleSolver.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | class KordleSolver : public Cloneable { private: KordleMachine* machine; KordleStrategy* strategy; vector<wstring> validWords; vector<wstring> queryableWords; int countQueried; private: bool isValid(wstring target, KordleResult result); public: KordleSolver() = delete; KordleSolver(KordleStrategy* strategy); ~KordleSolver(); wstring calculateNextWord(); void inputResult(KordleResult result); }; | cs |
우리는 주어진 문맥에서 가장 최적의 단어를 고를 수 있는 전략을 선택해야 합니다. 목적을 달성하기 위해서, '전략'이라는 것을 정의해보죠.
'꼬들 전략'이라는 것은 곧 후보 단어들 중에서 가장 최적의 질문 단어를 선택하는 것입니다. '후보 단어'란 정답이 될 수 있는 단어들의 집합이고, '질문 단어'는 질문할 수 있는 단어 집합 중 하나이죠.
또한 우리가 질문으로부터 얻은 결과를 통해서 후보 단어의 집합을 축소시킬 수 있습니다. 결과에 근거해 정답이 될 수 없는 단어를 쳐내는 것으로 말이죠. 이는 질문으로부터 결과를 생성해내는 것의 반대입니다.
- 결과의 글자가 초록색일 경우, 후보 단어들은 해당 자리에 그 글자가 있어야 합니다.
- 결과의 글자가 노란색일 경우, 후보 단어들은 해당 자리에 그 글자가 있으면 안 됩니다.
- 결과의 글자가 노란색일 경우, 후보 단어들은 나머지 자리 중 하나에 그 글자가 있어야 합니다. (또한, 같은 글자 여러 개가 노란색일 경우, 후보 단어는 그 글자가 해당 개수만큼 있어야 합니다!)
- 결과의 글자가 검은색일 경우, 후보 단어들은 해당 글자가 있으면 안 됩니다. 단, 결과에 같은 글자의 노란색이나 초록색이 포함되어 있다면, 그 개수 만큼은 있을 수 있습니다.
isValid()는 주어진 결과에 대해 target 단어가 유효한지, 아니면 더 이상 후보가 될 수 없는지를 판단합니다. 의사코드는 다음과 같습니다:
의사코드: isValid()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | for i = 0 to 5: if result[i] = green: if result[i] != target[i] return false; visited[i] = true; for i = 0 to 5: if result[i] = yellow: if result[i] == target[i]: return false flag = false for j = 0 to 5 if result[i] == target[j] & !visited[j] flag = true visited[j] = true break if !flag: return false if result[i] = black for j = 0 to 5: if result[i] = target[i] & !visited[j] return false return true | cs |
소스코드: KordleSolver.isValid()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 | bool KordleSolver::isValid(wstring target, KordleResult result) { array<bool, KordleMachine::KORDLE_LENGTH> visited; for (int i = 0; i < KordleMachine::KORDLE_LENGTH; i++) visited[i] = false; for (int i = 0; i < KordleMachine::KORDLE_LENGTH; i++) { if (result.result.at(i) == KordleColor::GREEN) { if (result.queriedString.at(i) != target.at(i)) { return false; } visited[i] = true; } } for (int i = 0; i < KordleMachine::KORDLE_LENGTH; i++) { if (result.result.at(i) == KordleColor::YELLOW) { if (result.queriedString.at(i) == target.at(i)) return false; bool flag = false; for (int j = 0; j < KordleMachine::KORDLE_LENGTH; j++) { if (target.at(j) == result.queriedString.at(i) && !visited[j]) { flag = true; visited[j] = true; break; } } if (!flag) return false; } if (result.result.at(i) == KordleColor::BLACK) { for (int j = 0; j < KordleMachine::KORDLE_LENGTH; j++) { if (result.queriedString.at(i) == target.at(j) && !visited[j]) return false; } } } return true; } | cs |
완벽한 전략: Brute-Force
꼬들을 해결하기 위한 가장 완벽한 전략은 모든 경우의 수를 계산하는 것이죠. 가령 제가 "ㅈㅓㄴㄹㅑㄱ"이라는 단어를 질문했을 때, 어떤 결과가 나올 수 있는지를 전부 계산하고, 또 그 결과에서 특정한 단어를 질문했을 때, 어떤 결과가 나오는지를 재귀적으로 계산해나가 그 확률을 계산하는 것입니다.
- 52만 개의 단어를 이용한 질문에 대해,
- 1000개의 단어들로부터 나오는 결과를 계산하고
- 도출된 각 결과들에 대해서 각각의 경우에 후보 단어 집합이 어떻게 변하는지를 추적하며,
- 추적된 각각의 후보 단어 집합으로부터 다시 각각 52만 개의 단어를 제시하였을 때
- 어떠한 결과들이 나오는지를..
계산하는 방식으로 총 6번이 되도록 재귀적으로 수행하면 됩니다! 하지만 이를 해결하기 위해서는 계산해야 할 양이 너무나도 많은 것 같습니다. 고작 꼬들 하나를 위해 소중한 컴퓨팅 자원을 몇 년간 희생시킬 수는 없죠. 혹자는 말했습니다. "좋은 컴퓨터를 구하는 것보다, 좋은 알고리즘을 구하는 것이 훨씬 더 경제적이다." 우리도 이 이념을 받아들이고, 대안을 찾아봅시다.
우리의 전략: 불확실성을 최소화하자
한 가지 좋은 방법은, 최대한 많은 단서를 던져줄 수 있는 단어를 선택해 질문하는 것입니다. 쉽게 말하면 앞서 설명한 Brute-Force 방법을 한 단계의 깊이로만 수행하는 것이죠. 질문할 수 있는 52만 개의 각 단어들이, 각각의 후보 단어들로부터 평균적으로 얼마의 초록색과 노란색을 얻을 수 있는지 계산해보는 것입니다.
제 꼬들 AI는 초록색과 노란색의 중요도를 5:1로 두었습니다. 초록색의 경우, 나머지 5칸의 글자에 대한 불확실성을 제거합니다. 반면 노란색의 경우, 해당 한 칸에 대한 불확실성을 제거합니다. 따라서 초록색을 5배 더 중요하다고 보았습니다. 물론 노란색은 해당 글자가 반드시 포함된다는 근거도 제공하기는 합니다만, 넘어가도록 합시다.
위와 같은 방식으로 각 단어들로부터 받을 수 있는 점수를 계산합니다. 노란색과 초록색이 하나씩 나왔다면, 6점을 얻은 셈이죠! 평균적으로 얻는 점수가 가장 높은 단어를 선택해서 질문을 하도록 합니다. 그렇게 했을 때, 우리는 평균적으로 많은 초록색과 노란색을 얻을 수 있게 됩니다. 이는 곧 정답에 훨씬 빨리 가까워질 수 있다는 의미이죠!
소스코드: KordleEntropyStrategy.calculateNextWord()
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | wstring KordleEntropyStrategy::calculateNextWord(vector<wstring> validWords, vector<wstring> queryableWords, int countQueried) { if (validWords.empty()) return wstring(); if (validWords.size() < MAGIC_NUMBER) { queryableWords = validWords; } double max = 0; int maxIndex = 0; for (vector<wstring>::iterator iter = queryableWords.begin(); iter != queryableWords.end(); iter++) { int score = 0; for (vector<wstring>::iterator iter2 = validWords.begin(); iter2 != validWords.end(); iter2++) { KordleResult result = KordleMachine::queryKordle(*iter, *iter2); for (KordleColor color : result.result) { if (color == KordleColor::YELLOW) { score++; } if (color == KordleColor::GREEN) { score += 5; } } } double average = score / validWords.size(); if (average > max) { max = average; maxIndex = distance(queryableWords.begin(), iter); } } return queryableWords.at(maxIndex); } | cs |
조금 더 최적화를 해봅시다.
첫 단어 사전계산(precomputation)하기
아무 단어도 입력하지 않았을 때의 상황은 언제나 같습니다. 날이 흐리거나 맑다고 해서 단어들의 불확실성이 변하지는 않죠. 저의 꼬들 AI가 선택한 첫 단어는 'ㅇㅏㄴㄱㅓㅣ'입니다. 이게 무슨 단어인지는 모르겠습니다만(안개의 오타인가요?), 어쨌거나 꼬들 사이트에서 질문할 수 있는 단어입니다. 이 단어는 평균적으로 많은 정보를 얻어낼 수 있습니다.
글자가 중복되는 단어들을 생각하지 말기
그럼에도 52만 개의 단어를 전부 질문의 후보로 두는 것은 미련한 일입니다. 우리는 불확실성을 최소화하는 것이 목표이므로, 같은 글자가 중복해서 나타나는 경우는 생각하지 않아도 어느 정도 비슷한 결과를 낼 것 같습니다. 따라서 이러한 글자들을 질문 후보 집합으로부터 삭제하도록 하였습니다.
결과
우리의 꼬들 AI의 성과는 어땠을까요? 꼬들 웹사이트에서 나올 수 있는 997개의 단어를 이용해 실험했습니다. 이를 전부 푸는데 걸린 시간은 약 4분 16초이며, 문제 당 평균 0.26초를 소모하였습니다. 또, 평균 2.79238회의 질문으로 해결했습니다. 성공률이 몇 퍼센트인지도 중요하겠죠? 최대 5회의 질문으로 모든 문제들을 끝마쳤습니다. 즉, 100%의 성공률을 보였습니다.
끝.
댓글
댓글 쓰기