리버스 체스 ( 3 ) - '그 긴 거'

게임 링크 : https://reversechess.perfect.ai.kr/

리버스 체스

리버스 체스 기록 처음부터 보기 : https://helloworld.ai.kr/29

오늘의 교훈

복잡한 알고리즘을 구현할 때는

• 간단한 구조부터 단계적으로 확장할 것
• 각 단계마다 불변식을 확인하며 디버깅할 것

나는 알고리즘을 구현할 때 좋지 않은 습관이 있다.

기본 알고리즘에 여러 아이디어를 한꺼번에 얹어 완성된 구조를 머릿속에 먼저 그린 뒤,
그것을 통째로 코드로 옮긴다.
그리고 구현이 끝난 다음에 디버깅을 시작한다.
이렇게 하면 어디서 틀렸는지 찾기가 매우 어려워진다.

여러 단계로 나누어 구현하고, 각 단계의 신뢰성을 확보한 뒤 다음 단계로 넘어가는 방식이 맞는 것 같다.

---

1인 플레이 구현 이유

앞서 말했듯, 이 콘텐츠를 즐기기 위해 두 사람이 반드시 모여야 한다는 조건은 두고 싶지 않았다.
그래서 PvE 콘텐츠 구현에 공을 들였다.

---

1차 버전 알고리즘 구상

미니맥스

턴 기반 1:1 게임에서 널리 쓰이는 탐색 알고리즘이다.

• 각 상태에는 평가 함수 값이 존재한다.
• 나는 그 값을 최대화하려 한다.
• 상대는 그 값을 최소화하려 한다.

이 가정 아래 다음 순서로 탐색을 진행한다.

1. 탐색 깊이 설정
2. DFS 방식으로 게임 트리 탐색
3. 리프 노드에서 평가 함수 적용
4. 상위 노드로 올라오며
   • 내 턴 → 최대값 선택
   • 상대 턴 → 최소값 선택
5. 현재 상태에서 점수가 가장 높은 수 선택

---

평가 함수

리버스 체스는 일반 체스와 목표가 반대다.
상대 기물이 많을수록 유리하고, 내 기물이 많을수록 불리하다.

평가 함수는 단순하게 다음과 같이 정의했다.

(상대 기물 가치 합) - (내 기물 가치 합)

기물 가치는 종류별로 다르게 두었다.
퀸 9점, 폰 1점 등.

---

알파베타 프루닝

미니맥스에서 불필요한 경로를 미리 제거하는 최적화 기법이다.

• 알파 : Max 플레이어가 확보한 최소 보장 점수
• 베타 : Min 플레이어가 확보한 최대 허용 점수

탐색 중 알파 ≥ 베타가 되는 순간, 해당 경로는 더 이상 볼 필요가 없다.

---

Move Ordering

탐색 순서를 조정해 알파베타 프루닝 효율을 높이는 방법이다.

• Max 기준 : 높은 점수를 낼 가능성이 큰 수부터
• Min 기준 : 낮은 점수를 낼 가능성이 큰 수부터

리버스 체스에서는 다음 수의 우선순위를 높였다.

• 강제 캡처 유도 수
• 체크 수

---

Zobrist Hash

특정 체스 포지션을 하나의 64비트 정수로 표현하는 기법이다.

각 위치–기물 조합에 대해 랜덤 값을 만들고 XOR 연산으로 보드 상태를 표현한다.

장점:

• 보드 상태를 빠르게 비교 가능
• 증분 업데이트 가능

예를 들어 기물 이동 시:

1. 기존 위치 XOR
2. 잡힌 기물 XOR
3. 새 위치 XOR
4. 턴 변경 XOR

이렇게 계산해 새 해시를 만든다.

Zobrist Hash 값을 TT의 키로 활용했다.

---

TT (Transposition Table)

이미 계산한 포지션 정보를 캐싱한다.

저장 정보:

• 합법 수
• move ordering 정보

---

시간 제한 + Iterative Deepening

미니맥스 탐색이 끝났는데 시간이 남아 있으면 depth를 1 늘려 다시 탐색한다. 이 과정을 시간 제한까지 반복한다.

특정 depth 탐색 도중 시간이 초과되면, 그 depth 결과는 버리고 이전 depth 결과만 사용한다.

또 adaptive 방식도 적용했다.

• 이전 턴에서 추가 탐색 성공 → 시작 depth +1
• 기본 탐색도 시간 내 실패 → 시작 depth -1

게임이 진행될수록 가능한 수가 줄어들기 때문에 자연스럽게 시작 depth가 증가한다.

난이도 설정은 다음과 같다.

• 쉬움 : 최대 depth 6 / 제한시간 1초
• 어려움 : 최대 depth 9 / 제한시간 10초

---

문제 : 유저 UI 상호작용 차단

AI 탐색이 시작되면 사용자 입력이 몇 초 동안 막혔다.
브라우저 JS가 기본적으로 단일 스레드이기 때문이다.

해결 : Web Worker 도입

• 메인 스레드 → UI 렌더링
• 워커 스레드 → AI 탐색

메인 스레드와 워커 스레드 간 통신 방식은 웹소켓과 매우 유사하다.

덕분에 AI가 계산 중일 때도 사용자 상호작용이 정상적으로 동작하게 되었다.

---

시도 : AI warm up

유저 턴에도 AI가 계속 탐색하면 TT 캐시가 쌓여 다음 턴 계산이 빨라질 것이라 기대했다.

구조는 다음과 같다.

1. 유저 턴에도 warm-up 탐색 진행
2. AI 턴 시작 시 interrupt 호출
3. warm-up 중간에 interrupt 확인 → 있으면 탐색 종료
4. 실제 AI 턴 탐색 시작

---

Heisenbug 등장

warm-up 구현 중 다음 문제가 발생했다.

1. warm-up 탐색 중 interrupt 발생 → 보드 롤백
2. 동시에 AI 턴 탐색 시작 → 새 보드로 탐색 진행
3. 두 과정이 충돌하며 보드 상태가 꼬임

원인은 AI 플레이어가 보드 인스턴스를 하나만 공유하고 있었기 때문이었다.

버그 추적을 위해 진입점에 console.log를 추가했더니…
타이밍이 미묘하게 밀리면서 버그가 사라졌다.

이처럼 관찰하면 사라지는 버그를 Heisenbug라고 한다.

Lock을 추가해 해당 문제는 잡았지만, 새로운 비동기 버그가 계속 발생했다. 결국 시간 관계상 warm-up은 포기했다.

---

문제 : AI가 너무 멍청함

여기까지 구현하고 테스트해보니 두 난이도 모두 너무 쉬웠다.

원인 분석:

• 탐색 깊이가 얕음
• iterative deepening에서 낭비 발생
• TT 활용 부족

---

개선 아이디어

중요 수를 더 깊게 탐색

리버스 체스를 휴리스틱 관점에서 보면 최적 수가 다음 상황에서 자주 나온다.

• 강제 캡처
• 체크

이 경우를 더 깊게 탐색하도록 조정하면 성능 개선 여지가 있다.

---

부분 탐색 활용

depth=3 탐색을 끝내지 못했더라도,
그 결과는 depth=2보다는 신뢰도가 높다.

부분 결과도 활용하는 방향을 검토했다.

---

TT 정보 확장

TT에 다음 정보까지 함께 저장하도록 확장했다.

• depth (엔트리 신뢰도)
• 알파 / 베타
• 평가 점수
• best move
• 유일 수 여부

이미 충분히 깊게 탐색된 노드는 재탐색하지 않는다.

예:

• 필요 depth = 3
• TT에 depth = 3 정보 존재

→ 탐색 생략 가능

---

2차 버전 알고리즘 구상

비균일 깊이 탐색

이 프로젝트를 하면서 가장 흥미로웠던 아이디어다.

기존에는 수를 한 번 둘 때마다 depth를 1씩 소모했다.
하지만 중요한 수에 대해서는 depth를 덜 소모하게 만들면 어떨까?

다음과 같이 설정했다.

1. 강제 유일 수 → depth 소모 0
2. 강제 캡처 유도 / 체크 수 → depth 소모 1
3. 그 외 수 → depth 소모 2

이를 통해 중요한 수만 더 깊게 탐색할 수 있게 했다.

---

TT 역할 확대

TT에 저장하는 정보를 대폭 확장했다.

• depth
• 알파 / 베타
• 평가 점수
• best move
• 유일 수

또한, 이미 충분히 깊게 탐색된 노드는 재탐색하지 않도록 했다.

---

Anytime Iterative Deepening

시간 종료 시 탐색을 강제 폐기하지 않는다.

대신 다음 중 신뢰도가 가장 높은 결과를 채택한다.

1. 현재 보드 평가 (depth 0)
2. 자식 노드 부분 탐색 결과 (depth n-0.5)
3. TT 캐시 결과

이로 인해 캐시 효율과 탐색 품질이 모두 개선됐다.

---

훨씬 똑똑해졌음, 그러나…

2차 버전을 적용하니 어려움 난이도가 체감상 꽤 올라갔다.
어려움 기준 승률은 대략 30~50% 수준.

만족스러운 결과였지만, 여전히 간헐적인 버그로 판이 터지는 문제가 남아 있었다.

다음 글 보러가기 : https://helloworld.ai.kr/32

리버스 체스 ( 4 ) - 구글 애널리틱스, 모바일 UI