체스 컴퓨터를 라이브러리 없이 360줄로 만들기

2026년 11월 2일 · 기술

새 게임 체스는 컴퓨터와 두는 정통 체스다. 혼자 두는 체스 게임에는 컴퓨터 상대가 필요하다. 가장 쉬운 길은 이미 있는 엔진을 쓰는 것이다. 오픈 소스 엔진 중 가장 강한 Stockfish 는 WebAssembly 로 옮긴 판도 있어 브라우저에서 돌릴 수 있다.

쓰지 않았다. Stockfish 는 GPL 라이선스다. 이 사이트는 외부에서 가져온 그림·소리를 CC0·CC BY 처럼 조건이 가벼운 것만 쓰는데, GPL 은 그 기준에 맞지 않았다. 크기도 수 MB 라 미니게임 하나에 넣기에는 컸다.

그래서 직접 만들었다. 게임 파일 맨 위의 CHESS_ENGINE 하나가 규칙과 컴퓨터를 모두 맡고, 외부 라이브러리 없이 360줄 남짓이다. 체스 프로그래밍은 오래된 분야라 방법이 잘 정리되어 있다. 대부분 chessprogramming.org 에 있는 표준적인 방법을 골라 조합했다.

판: 0x88

판을 8×8 배열로 두면 기물이 판 밖으로 나갔는지 확인하기 번거롭다. 줄과 열을 따로 계산해 둘 다 0~7 인지 봐야 한다. 0x88 표현은 판을 가로 16칸으로 둔다. 칸 번호는 줄 × 16 + 열 이고, 오른쪽 8칸은 쓰지 않는 빈자리다.

이렇게 하면 판 밖 판정이 비트 연산 하나로 끝난다. 열이 8 이상으로 넘치면 3번 비트(0x08)가 켜지고, 줄이 넘치거나 음수가 되면 7번 비트(0x80)가 켜진다. 그래서 sq & 0x88 이 0 이 아니면 판 밖이다. 움직임은 칸 번호에 더할 값으로 둔다. 나이트는 여덟 방향, 룩은 위아래(±16)·좌우(±1), 비숍은 대각선(±15, ±17)이다.

const on = (sq) => !(sq & 0x88);                       // inside the board?
const KNIGHT = [-33, -31, -18, -14, 14, 18, 31, 33];
const ROOK = [-16, -1, 1, 16], BISHOP = [-17, -15, 15, 17];

for (const d of ROOK) {                                 // slide until blocked
  for (let to = from + d; on(to); to += d) {
    if (board[to]) { if (color(board[to]) !== me) add(from, to); break; }
    add(from, to);
  }
}

기물은 숫자 하나다. 종류(1 폰 ~ 6 킹)에 색(백 0, 흑 8)을 비트로 더한다.

수 만들기: 두어 보고 되돌린다

체스의 합법 수에는 까다로운 조건이 많다. 핀에 걸린 기물은 움직일 수 없고, 체크를 받으면 피하는 수만 둘 수 있다. 이것을 하나하나 계산하지 않고, 기물이 움직일 수 있는 수(의사 합법 수)를 모두 만든 뒤 실제로 두어 본다. 둔 다음 내 킹이 공격받고 있으면 그 수는 버린다.

function legal(st) {
  const out = [];
  for (const m of pseudoMoves(st)) {
    make(st, m);
    if (!attacked(st, myKing(st), opponent(st))) out.push(m);
    unmake(st);
  }
  return out;
}

make 는 수를 두면서 되돌리는 데 필요한 것(잡은 기물, 캐슬링 권리, 앙파상 칸, 50수 규칙 수)을 스택에 쌓고, unmake 는 그것을 꺼내 원래대로 돌린다. 판을 복사하지 않으니 빠르다. 게임의 무르기도 같은 스택을 쓴다. 캐슬링은 킹이 지나는 칸이 공격받지 않을 때만, 앙파상은 바로 앞 수가 폰 두 칸 전진일 때만 만든다.

같은 판이 세 번 나오면 무승부라, 판이 반복되는지도 알아야 한다. 판마다 Zobrist 해시를 둔다. 기물 종류×칸마다, 캐슬링 권리마다, 앙파상 칸마다, 차례마다 무작위 수를 하나씩 정해 두고, 판에 있는 것들의 무작위 수를 모두 XOR 한 값이다. 기물이 움직이면 떠난 칸과 도착한 칸의 값만 XOR 하면 되니 판 전체를 다시 볼 필요가 없다. JavaScript 의 비트 연산은 32비트라 해시를 두 개 두어 64비트처럼 썼다.

perft 로 수 만들기 검증하기

수 만들기는 틀려도 겉으로 잘 드러나지 않는다. 앙파상이 한 경우에 빠지거나 승진 중 하나가 빠져도 게임은 대부분 잘 돌아간다. 이것을 잡는 표준 방법이 perft 다. 어떤 판에서 깊이 n 까지 가능한 수의 순서를 모두 세는 것이다. 시작 판에서 백이 두는 수는 20개, 흑까지 두면 400개, 네 수(백·흑·백·흑) 뒤에는 197,281개다. chessprogramming.org 의 Perft Results 에 여러 판의 정답이 있다.

정답이 알려진 5판으로 검사 스크립트를 만들었다. 시작 판 깊이 4 = 197,281, 캐슬링·앙파상·승진이 뒤섞인 판으로 유명한 Kiwipete 깊이 3 = 97,862 등이다. 다섯 판의 모든 깊이에서 수가 일치했다. 같은 스크립트에서 판을 FEN(판을 한 줄 글자로 적는 형식)으로 읽고 다시 썼을 때 그대로인지, 체크메이트·스테일메이트·기물 부족·50수·3회 반복을 맞게 판정하는지, 한 수 메이트를 찾는지도 본다. 엔진을 고칠 때마다 돌린다.

평가: 기물 가치와 칸별 가중치

컴퓨터가 수를 고르려면 판이 누구에게 얼마나 좋은지 숫자로 매겨야 한다. 기본은 기물 가치다. 폰 100, 나이트 320, 비숍 330, 룩 500, 퀸 900 이다. 여기에 기물마다 어느 칸에 있으면 더하고 빼는지를 적은 8×8 표를 더한다. 나이트는 가운데가 좋고 구석이 나쁘다. 폰은 앞으로 나갈수록 좋다. 킹은 중반에는 캐슬링한 자리가 좋다. 이 값들은 Tomasz Michniewski 의 Simplified Evaluation Function 을 그대로 썼다. 간단한 엔진을 위한 출발점으로 널리 쓰이는 표다.

킹은 끝판에 표를 바꾼다. 기물이 줄어 퀸과 룩이 적어지면(폰과 킹을 뺀 기물 가치 합이 1300 이하) 킹이 가운데로 나와 싸우는 쪽이 좋기 때문이다.

하나를 더 넣었다. 킹과 퀸으로 킹 하나를 상대하는 판은 이긴 판이지만, 메이트하려면 상대 킹을 가장자리로 몰아야 한다. 메이트가 탐색 깊이 밖에 있으면 어느 수나 점수가 비슷해서, 엔진이 상대 킹을 가장자리로 몰아가지 못할 수 있다. 그래서 끝판에 기물로 400점 넘게 앞서고 상대에게 폰이 없으면, 상대 킹이 가장자리에 가까울수록, 내 킹이 상대 킹에 가까울수록 점수를 더했다.

// endgame mop-up: drive the lone king to the edge and bring my king close
const edge = Math.max(3 - lr, lr - 4) + Math.max(3 - lf, lf - 4); // 0 in the center, 6 in a corner
const close = 14 - (Math.abs(lr - wr) + Math.abs(lf - wf));
score += edge * 10 + close * 4;

탐색: 알파-베타와 잡기 정리

수 고르기는 negamax 알파-베타 탐색이다. 내 수, 상대 수, 다시 내 수를 정해진 깊이까지 모두 펼쳐 보고, 상대도 최선을 둔다고 보고 가장 좋은 수를 고른다. 알파-베타는 이미 본 것보다 나쁠 게 확실한 가지를 끝까지 보지 않고 잘라 낸다.

function negamax(st, depth, alpha, beta, ply) {
  if (depth <= 0) return quiesce(st, alpha, beta);
  let moved = 0;
  for (const m of ordered(st, ply)) {
    make(st, m);
    if (kingAttacked(st)) { unmake(st); continue; }
    moved++;
    const score = -negamax(st, depth - 1, -beta, -alpha, ply + 1);
    unmake(st);
    if (score >= beta) return beta;   // opponent won't allow this line
    if (score > alpha) alpha = score;
  }
  if (!moved) return inCheck(st) ? -MATE + ply : 0; // mate or stalemate
  return alpha;
}

깊이에서 바로 멈추고 평가하면 문제가 생긴다. 마지막 수가 퀸으로 폰을 잡는 수라면 평가는 폰 하나를 얻었다고 하지만, 다음 수에 퀸을 잃을 수 있다. 그래서 정해진 깊이에 닿으면 잡는 수만 계속 따라가는 잡기 정리 탐색(quiescence search)을 한다. 더 잡을 것이 없는 조용한 판이 되어서야 평가한다. 체크를 받은 판에서는 깊이를 하나 늘려 체크를 피하는 수까지 본다.

알파-베타는 좋은 수를 먼저 볼수록 많이 잘라 낸다. 그래서 수를 정렬한다. 잡는 수는 싼 기물로 비싼 기물을 잡는 것부터(MVV-LVA), 그다음 승진, 그다음 같은 깊이에서 가지를 잘라 냈던 조용한 수(킬러 수)다.

깊이는 미리 정하지 않는다. 깊이 1 로 찾고, 2 로 찾고, 3 으로 찾으며 시간이 다할 때까지 늘린다(반복 깊이 늘리기). 앞 깊이에서 좋았던 순서대로 다음 깊이를 보니 정렬도 좋아진다. 시간이 다하면 그 깊이를 멈추고, 마지막으로 끝까지 본 깊이의 수를 둔다. 멈춘 깊이에서 이미 더 좋은 수를 찾았다면 그 수를 둔다. 많은 엔진이 쓰는 트랜스포지션 테이블(이미 본 판의 결과를 기억하는 표)과 오프닝 책은 넣지 않았다.

난이도는 생각 시간

난이도는 컴퓨터가 생각하는 시간이다. 쉬움은 시간과 상관없이 한 수 깊이와 잡기 정리만 보고, 첫 수마다 ±120점(폰 하나 남짓)의 무작위 값을 더해 가끔 손해 보는 수를 둔다. 보통은 한 수에 0.5초, 어려움은 1.5초까지 생각한다. 같은 점수의 수가 여럿이면 무작위로 골라 매번 같은 대국이 되지 않게 했다.

개발하는 Mac 의 Node 에서 중반 판 하나로 시간을 재 보니, 다섯 반수(백·흑을 합쳐 다섯 수) 깊이까지 보는 데 0.23초, 여섯 반수 1.4초, 일곱 반수 8.7초가 걸렸다. 기물이 적은 룩 끝판은 일곱 반수가 0.3초였다. 그러니 중반에 보통은 다섯 반수, 어려움은 여섯 반수 깊이까지 본다. 시간으로 끊기 때문에 휴대폰처럼 느린 기기에서는 한 반수쯤 얕아질 수 있다.

실력은 엔진끼리 두게 해서 봤다. 보통과 쉬움은 8판 모두 보통이 이겼다. 쉬움은 8~35수 만에 메이트당했는데, 한 수 깊이라 상대의 메이트 위협을 보지 못한다. 어려움과 보통은 6판에 2승 1패 3무였다. 무승부 중 한 판은 어려움이 기물로 두 배 앞서고도 240반수를 두고 비겼다. 끝판을 마무리하는 힘이 약하다는 뜻이다. 한편 한 수 메이트, 나이트 포크 같은 전술 문제는 쉬움도 모두 맞혔다. 잡기 정리 탐색 덕분에 쉬움도 기물을 공짜로 내주지 않아서, 초보에게는 생각보다 단단한 상대다.

사람 기준의 레이팅(Elo)은 재지 않았다. 레이팅을 알려면 레이팅이 알려진 상대와 많이 두어 봐야 하는데, 그런 기준 엔진을 붙여 보지 않았다.

생각하는 동안 화면이 멈춘다

탐색은 게임과 같은 메인 스레드에서 돈다. 그래서 컴퓨터가 생각하는 0.5~1.5초 동안은 화면이 멈춘다. 내가 수를 두자마자 생각을 시작하면 내 기물이 움직이는 연출도, 차례 표시가 바뀌는 것도 그동안 멈춰 버린다.

그래서 순서를 정했다. 내 기물이 미끄러져 도착하고 화면 위 차례 표시가 컴퓨터로 바뀐 것을 먼저 그린다. 그 뒤 0.26초를 기다렸다가 생각을 시작한다. 멈춰 있는 동안 화면에는 컴퓨터 차례라는 표시가 떠 있다. 탐색을 Web Worker 로 옮기면 화면이 아예 멈추지 않겠지만, 지금은 옮기지 않았다.

360줄로는 강한 엔진을 만들 수 없다. 그래도 수 만들기를 perft 로 맞춰 두고, 표준적인 방법 몇 가지를 쌓으니 초보부터 어느 정도 두는 사람까지 상대할 수 있는 컴퓨터가 되었다. 다만 끝판 마무리는 아직 약하다.

참고