GitHub 주소 (소스코드 공개 중)
https://github.com/levelstage/AutoMine
알고리즘으로 확률을 예측해서 정답 레이블로 쓴다고?
그렇다. 이를 통해 학습 데이터를 생성한다.
그럼 딥러닝을 하는 이유가 없지 않나?
맞는 말이다. 만약 에 대해 완벽한 를 딥러닝이 아닌 알고리즘으로 구할 수 있다면, 그냥 그것을 사용하면 되지 굳이 딥러닝을 할 이유가 없다. 그 알고리즘이야말로 '지뢰찾기 AI'라고 불려야 마땅하다.
그런데 왜 이런 시도를 했는가?
에 대해 완벽한 를 구하는 것이 현실적으로 어렵기 때문이다. 내가 AI에게 제공하는 학습 데이터는 완벽한 확률 매트릭스가 아니다. 그 원리는 아래와 같다.
도입: 지뢰찾기의 역학 분석
우선 지뢰찾기라는 게임의 역학을 분석해보자. 사람이 지뢰찾기를 할 때 보통 어떻게 플레이하는가?
처음 판을 마주하면 우리는 우선 아무 곳이나 누른다. 예를 들어 판에 지뢰가 10개 매설되어 있다면, 100칸 중 10칸이 지뢰이므로 아무 데나 눌러도 90%의 확률로 안전하다.
칸이 열리면 우리는 특정 영역에 주목하게 된다. 예를 들면 빨간색으로 표시한 영역 말이다. 어떤 칸에 '1'이라고 적혀 있고, 그 주변 8칸 중 7칸이 이미 열려 있다면(확정적 안전), 나머지 닫힌 한 칸은 반드시 지뢰일 수밖에 없다. 이제 해당 비공개 칸은 '지뢰 확정'이라는 공개 정보가 된다. 이 정보를 이용하면 인접한 다른 칸들의 상태도 연쇄적으로 밝혀낼 수 있다.
이처럼 지뢰찾기는 숫자 칸을 기준으로 주변의 공개 정보와 비공개 정보를 체크하며, 안전한 칸은 눌러서 열고 지뢰인 칸에는 깃발을 꽂으며 진행하는 게임이다.
확률 게임으로의 진입
일반적으로는 공개 정보만을 바탕으로 진행하지만, 간혹 비공개 칸 중 정보가 하나도 없는 순간이 온다. 이때부터는 확률 게임의 영역이다. 특정 비공개 칸이 지뢰일 확률은 수학적으로 다음과 같다.
문제는 연산량이다. 단순하게 어두운 칸이 50개, 지뢰가 10개라고 가정하면 분모를 계산하기 위해 회의 탐색을 거쳐야 한다. 이는 C++ 기준으로도 오래 걸리는 작업이며, 파이썬으로는 실시간 처리가 거의 불가능하다.
알고리즘적으로 이 문제를 해결하는 것도 분명 재미있겠지만, 내가 선택한 방법은 그리디(Greedy)한 탐색을 통한 근사 확률 계산 및 딥러닝이었다. 사실 딥러닝이 해보고 싶어서 완벽한 '선생님(알고리즘)'을 만드는 데 시간을 너무 많이 투자하고 싶지 않았다는 것이 솔직한 이유다.
선생님이 비록 근사 확률만을 제공하더라도, 모델이 선생님을 100% 똑같이 모방하는 것은 아니기에 모델이 선생님과는 다른 자신만의 '직관'을 가지는 것도 가능하리라 기대했다. 결과적으로 선생님과는 조금 다른 판단을 내리는 묘한 아이가 탄생했지만 나름대로 만족하기로 했다.
알고리즘 설명: 어떻게 만들었나?
아래는 MsTeacher.py에서 핵심 부분인 solve 함수의 일부이다. 전부 닫혀있는 지뢰찾기 판을 받아서 안전한 칸을 모두 찾을때까지 진행한 후, 확률을 계산한 다음 그걸 클릭 단위로 기록해서 반환하는 역할을 한다. 함수가 좀 긴 관계로, 가장 핵심인 확률 갱신 루프만 가져왔다. 처음에 큐에 들어가는 delta 변수에는 클릭으로 새롭게 열린 모든 칸들의 좌표 및 거기에 쓰인 숫자 정보가 튜플로 들어간다.
# 확률 변동이 사라질 때 까지 계속 루프를 돈다.
q = deque(delta)
while q:
# 큐에서 하나 꺼내 각 원소에 편의상 이름을 붙인다.
top = q.popleft()
x = top[0]
y = top[1]
# 엔진 내부에서는 각 숫자 칸을 1 더해서 관리하므로 다시 1 빼서 복호화
value = top[2]-1
# 우선 주변의 밝혀지지 않은 칸의 수와, 그 중에서도 완전히 안전한 칸, 지뢰 확정인 칸 수를 센다.
tot = 0
safe = 0
mine = 0
for dy in [-1, 0, 1]:
for dx in [-1, 0, 1]:
# 자기 자신은 어차피 밝혀진 칸이므로 넘긴다.
if dy==0 and dx ==0:
continue
nx = x + dx
ny = y + dy
# OutOfBounds 케어
if not (0 <= nx < self.width and 0 <= ny < self.height):
continue
# 이미 밝혀진 칸은 거른다.
if grid[ny][nx] > 0:
continue
tot += 1
if abs(safety[ny][nx]) < 1e-7:
mine += 1
elif abs(safety[ny][nx] - 1.0) < 1e-7:
safe += 1
# 구한 안전 칸과 지뢰 수를 통해 다른 칸들의 안전도 근사치를 구한다. (한 칸만 Greedy하게 보므로 정확한 확률은 아니다.)
# 어떤 모르는 한 칸에 지뢰가 있을 확률은 (value-mine)/(tot-safe-mine)이다.
# 0으로 나누기 방지 (tot-safe-mine이 0이면 계산 불필요)
unknowns = tot - mine - safe
if unknowns <= 0:
continue
prob_mine = (value - mine) / unknowns
prob_calculated = 1.0 - prob_mine
for dy in [-1, 0, 1]:
for dx in [-1, 0, 1]:
# 마찬가지로 자기 자신 패스
if dy==0 and dx ==0:
continue
nx = x + dx
ny = y + dy
# OutOfBounds 케어
if not (0 <= nx < self.width and 0 <= ny < self.height):
continue
# 여기도 마찬가지로 이미 밝혀진 칸은 거른다.
if grid[ny][nx] > 0:
continue
# unknown 칸에 대해서만 갱신한다.
if abs(safety[ny][nx] - 1.0) < 1e-7 or abs(safety[ny][nx]) < 1e-7:
continue
# 확률 변동이 일어난 칸이므로 자동 확률 갱신 구독을 취소한다.
mask[ny][nx] = 1
# 1. 확정된 정보(0.0, 1.0)는 무조건 덮어쓴다. (Fact > Estimate)
# 2. 둘 다 추측(Estimate)이라면 더 보수적인(작은) 값을 취한다.
# 3. 값이 '변했을 때만' 큐에 넣어서 전파한다.
prev_prob = safety[ny][nx]
new_prob = prev_prob # 초기화
# 확정 정보인 경우
if abs(prob_calculated - 1.0) < 1e-7 or abs(prob_calculated) < 1e-7:
new_prob = prob_calculated
# 추측인 경우 기존보다 더 위험하면 갱신
elif abs(safety[ny][nx]) >= 1e-7 and abs(safety[ny][nx] - 1.0) >= 1e-7:
if prob_calculated < safety[ny][nx]:
new_prob = prob_calculated
# 값이 변했다면 갱신하고 전파
if new_prob != prev_prob:
safety[ny][nx] = new_prob
# 만약 이번 갱신으로 '확정(Fact)'이 되었다면, 주변 숫자들을 깨워서 다시 계산시켜야 함
# (원래 추측이었는데 확정이 된 경우 -> 파급력이 큼)
if abs(new_prob - 1.0) < 1e-7 or abs(new_prob) < 1e-7:
if abs(new_prob - 1.0) < 1e-7:
# 안전 확정이라면 어두운 안전칸 카운트 증가
dark_safe += 1
else:
# 지뢰 확정이라면 지뢰 확정칸 카운트 증가
dark_mine += 1
# 4중 반복문이지만 하는 수 없음.
for ddy in [-1, 0, 1]:
for ddx in [-1, 0, 1]:
# 마찬가지로 자기 자신 패스
if ddy==0 and ddx==0:
continue
nnx = nx + ddx
nny = ny + ddy
# OutOfBounds 케어
if not (0 <= nnx < self.width and 0 <= nny < self.height):
continue
# 원래 칸으로는 돌아가지 않는다.
if nnx == x and nny == y:
continue
# 역으로 밝혀진 칸들로 가야 한다.
if grid[nny][nnx] > 0:
q.append((nnx, nny, grid[nny][nnx]))소스를 보면 알겠지만, 주변 8칸의 정보만을 활용하여 국소적인 확률을 갱신한다. 이 알고리즘의 핵심은 특정 칸이 지뢰일 확률을 다음과 같이 정의하는 데 있다.
어떤 숫자 칸에 대하여,
동작 원리
- 연쇄 갱신: 클릭으로 새롭게 열린 칸들의 정보를 큐(Queue)에 넣어 관리한다.
- 확정 정보의 우선순위: 계산 과정에서 확률이 0.0이나 1.0이 나오면, 해당 칸은 더 이상 추측이 아닌 새로운 '공개 정보(Fact)'가 된다.
- 파급 효과 전파: 새로운 공개 정보가 발생하면 주변 8칸에 이를 알려 확률을 연쇄적으로 다시 계산하게 한다.
알고리즘 자체는 매우 간단하여 제작에 하루밖에 걸리지 않았다.
그런데 왜 문제가 발생했는가? (안일함의 대가)
테스트를 제대로 거치지 않았기 때문이다. 코드의 동작을 확인하려면 세부적으로 로그를 출력해 봐야 하는데, 그 과정이 귀찮아 AI에게 오류 검토를 맡기고 "문제없다"는 답변에 안주하며 넘어갔다.
안일함이 불러온 결과
선생님(알고리즘)이 무너지면 신경망도 함께 무너진다. 아무리 정교하게 설계해도 데이터 자체가 잘못되면 답이 없다. 그야말로 GIGO(Garbage In, Garbage Out)다.
발견된 결정적인 문제는 다음과 같았다.
- 좌표계 혼동: 함수는
(y, x)를 기대하는데 입력으로(x, y)를 넣어버려 좌표계가 완전히 뒤엉켰다. - 예외 처리 누락:
이 단 두 줄.
# unknown 칸에 대해서만 갱신한다.
if abs(safety[ny][nx] - 1.0) < 1e-7 or abs(safety[ny][nx]) < 1e-7:
continue이미 확정된 칸을 건너뛰는 코드 두 줄을 빠뜨려 확률 테이블이 오염되었다. 이로 인해 음수나 1을 초과하는 말도 안 되는 확률이 발생했음에도, 예외 처리를 따로 하지 않아 전혀 모르고 있었다.
단순한 루프 중간 출력만 해봤어도 금방 찾았을 버그를 "귀찮으니까 직접 디버깅 안하고 대충 AI한테 컨펌받고 넘어가야지~" 하다가 평생 못찾을 뻔 했다.
교훈
버그를 발견하지 못해 애먼 신경망을 뜯어고치고, 엉뚱한 소리만 늘어놓는 AI와 입씨름하며 허비한 시간은 과장 좀 보태서 프로젝트 전체 기간의 절반에 가깝다.
시간을 아끼려 했던 약간의 안일함이 오히려 막대한 시간 낭비를 초래한다는 것을 뼈저리게 느꼈다. 중간 테스트와 예외 처리의 중요성을 다시금 깨닫는 계기가 되었다.
마무리
현재 수정된 MsTeacher 수준으로도 지뢰와 안전 칸을 충분히 잘 찾아내므로 추가적인 개선은 고려하지 않고 있다. 공개 정보를 충실히 활용하는 것만으로도 지뢰찾기는 충분히 클리어 가능하기 때문이다.
또한 딥러닝 특유의 성질 덕분에 모델이 선생님을 완벽히 복제하지 않고 독자적인 판단을 내리기도 하므로, 이 프로젝트가 아예 의미 없지는 않다고 생각한다. 이번 시행착오는 앞으로의 개발에 있어 소중한 경험이 될 것이다.
다음 포스트에서는 나를 애먹인 또 다른 주역인 Visualizer에 대해 다룰 예정이다. 이곳에서도 키워드는 역시 '안일함'과 'AI'다.
