2KB로 구현한 1200 Elo 체스 엔진: Sameshi와 코드 골프의 미학
요즘 프론트엔드 앱 하나를 띄우려면 node_modules가 수백 메가바이트를 차지하는 세상입니다. “Hello World”를 출력하기 위해 수십 개의 레이어를 거쳐야 하는 현대 소프트웨어 엔지니어링의 복잡성에 지쳐갈 때쯤, Hacker News에서 제 눈을 사로잡은 프로젝트가 하나 있었습니다.
바로 Sameshi 라는 체스 엔진입니다. 실행 파일도 아니고, 헤더 파일 하나(sameshi.h)가 고작 1.95KB 입니다. 그런데 Elo 레이팅이 약 1200점대라고 합니다. 이게 어느 정도 수준이냐면, 체스 룰만 아는 초보자는 가볍게 이기고, 어느 정도 두는 동호인과도 비등하게 싸울 수 있는 실력입니다.
Principal Engineer로서 수많은 최적화 프로젝트를 이끌어봤지만, 이런 극단적인 ‘Code Golf(코드 골프)’ 프로젝트는 언제나 신선한 충격을 줍니다. 오늘은 이 초소형 엔진이 어떻게 작동하는지, 그리고 기술적으로 어떤 타협과 통찰이 있었는지 깊게 파보겠습니다.
기술적 심층 분석: 2KB에 무엇을 담았나?
코드를 뜯어보면(물론 minified 버전 말고 readable 버전을 봐야 정신 건강에 좋습니다), 이 엔진은 체스 엔진의 교과서적인 알고리즘을 아주 컴팩트하게 구현했습니다.
1. 120-cell Mailbox Board 표현
체스판은 8x8=64칸이지만, 엔진들은 보통 0x88 방식이나 120-cell mailbox 방식을 씁니다. Sameshi는 후자를 택했습니다. 64칸만 쓰면 나이트(Knight) 같은 기물이 보드 밖으로 나갔는지 계산하기 위해 복잡한 경계 체크 로직이 필요한데, 120칸 배열을 잡아두고 보드 밖을 ‘벽(off-board)‘으로 채워두면 인덱스 체크만으로 유효성 검사가 끝납니다. 메모리를 조금 더 쓰고 CPU 사이클과 코드 라인 수를 줄이는 전형적인 트레이드오프입니다.
2. 탐색 알고리즘: Negamax와 Alpha-Beta Pruning
이 작은 코드 안에 Negamax 알고리즘이 들어있습니다. Minimax의 변형으로, 백(White)과 흑(Black)의 평가 함수 부호만 반대로 뒤집어 코드를 하나로 합치는 기법입니다. 여기에 Alpha-Beta Pruning 까지 구현되어 있습니다. 불필요한 탐색 가지(Branch)를 쳐내지 않으면 체스 같은 게임 트리는 절대 깊게 탐색할 수 없으니까요.
3. 평가 함수 (Evaluation): Material Only
여기가 가장 흥미로운 부분이자 한계점입니다. 현대적인 엔진(Stockfish 등)은 기물의 위치(Positional play), 킹의 안전, 폰 구조 등 수많은 Heuristics를 사용합니다. 하지만 Sameshi는 오직 기물 점수(Material) 만 봅니다. 즉, “내가 폰 하나 잡으면 이득”이라는 단순 무식한 계산입니다. 그런데도 1200 Elo가 나온다는 건, 전술적 탐색 깊이(Search Depth)가 얕은 전략적 판단을 어느 정도 커버해준다는 뜻입니다.
치명적인 타협: 이것은 ‘현대 체스’인가?
Hacker News 댓글 창이 뜨거웠던 이유는 바로 구현되지 않은 기능들 때문입니다.
- Castling (캐슬링)
- En Passant (앙파상)
- Promotion (프로모션)
- 50수 무승부 규칙
한 HN 유저는 “캐슬링과 프로모션이 없다면 이건 모던 체스라고 부를 수 없다”고 강하게 비판했습니다. 저도 동의합니다. 특히 엔드게임에서 폰이 퀸으로 변하는 프로모션이 없다면 승패가 뒤집힐 수 있는 상황이 너무 많습니다.
개발자는 Stockfish와의 대결에서 Stockfish가 캐슬링이나 프로모션을 하지 못하도록 강제한 상태에서 1170 Elo를 측정했다고 밝혔습니다. 즉, ‘제한된 룰셋’ 하에서의 성능 인 셈입니다. 하지만 2KB라는 제약을 고려하면, 이 정도 타협은 엔지니어링 관점에서 ‘기능 명세 축소’로 이해해 줄 만합니다.
커뮤니티의 발견: 버그와 철학
이 프로젝트가 재미있는 건 커뮤니티의 반응입니다. 한 유저가 즉각적으로 버그를 찾아냈습니다.
“폰이 이미 한 번 움직였는데도 두 칸 전진이 가능합니다 (b6 -> b4).”
체스 룰에서 폰은 처음에만 두 칸 갈 수 있는데, 이 상태 추적 로직이 빠져있거나 오류가 있었던 거죠. 이런 edge case는 unit test 없이 코드 골프를 할 때 흔히 발생하는 문제입니다.
또 다른 흥미로운 토론은 “Elo per Byte” 비율이었습니다. 1 바이트당 1 Elo를 달성할 수 있을까요? 4KB로 늘리면 3000 Elo(초인 수준)가 가능할까요? 실제로 TCEC(Top Chess Engine Championship)에는 4KB 리그가 있고, 거기서 우승하는 엔진들은 상상을 초월합니다. 이는 “지능”이라는 것이 생각보다 아주 짧은 코드로 압축될 수 있다는 섬뜩하면서도 매혹적인 사실을 상기시켜 줍니다.
엔지니어의 시선: 왜 이런 짓을 하는가?
솔직히 말해, 실무에서 이런 코드를 짠다면 저는 코드 리뷰에서 Request Changes를 날릴 겁니다. 가독성은 제로에 가깝고, 유지보수는 불가능하니까요. 하지만 Sameshi 같은 프로젝트는 우리에게 중요한 환기를 줍니다.
- 복잡도의 본질: 우리는 너무 쉽게 라이브러리를 추가합니다. 핵심 로직은 사실 몇 줄 안 될 수도 있는데 말이죠.
- 제약의 미학: 리소스가 무한대인 클라우드 환경에서는 잊기 쉬운 ‘최적화의 즐거움’을 상기시킵니다.
- 알고리즘의 힘: 머신러닝 모델이 수 기가바이트씩 하는 시대에, 고전적인 Alpha-Beta Pruning이 여전히 강력하다는 것을 보여줍니다.
결론: 장난감 그 이상
Sameshi는 실전용 엔진은 아닙니다. 룰도 완벽하지 않고 버그도 있습니다. 하지만 2KB라는 제약 속에서 체스의 핵심 로직을 우겨넣은 그 솜씨는 경이롭습니다. 주말에 심심한 엔지니어라면, readable/sameshi.h 코드를 열어보세요. 비트 연산과 배열 인덱싱의 묘기를 보며 잃어버렸던 코딩의 야성을 되찾을지도 모릅니다.
참고 링크: