체스 엔진 세계에는 꽤 유명한 개발자가 한 명 있어요. 게리 린스콧(Gary Linscott)이라는 사람인데요. 세계 최강 체스 엔진인 스톡피시(Stockfish)의 개선안을 전 세계 자원봉사자들의 컴퓨터로 검증하는 분산 테스트 시스템 '피시테스트(Fishtest)'를 만들었고, 딥마인드의 알파제로를 오픈소스로 재현한 리라 체스 제로(Leela Chess Zero) 프로젝트도 초기에 이끌었던 개발자예요. 말하자면 현대 체스 엔진의 양대 산맥에 모두 깊이 관여했던 사람인데, 이번에는 그 둘 어느 쪽도 아닌 제3의 접근을 실험한 프로젝트를 공개했어요. 이름부터 직관적인 'Beam Engine', 빔 서치(beam search) 기반 체스 엔진이에요.
체스 엔진은 원래 수를 어떻게 읽냐면요
지금까지 체스 엔진의 탐색 방식은 크게 두 갈래였어요. 첫 번째는 스톡피시로 대표되는 알파베타(alpha-beta) 탐색이에요. 이게 뭐냐면, 가능한 수를 트리 형태로 쭉 펼쳐놓고 “내가 최선을 두면 상대도 최선으로 받는다”는 가정으로 계산하되, 결과에 영향을 못 주는 가지는 미리 잘라내는(pruning) 방식이에요. 같은 탐색 깊이 안에서는 최선의 수를 보장해주는 대신, 깊이가 늘어날수록 계산량이 폭발적으로 커져요. 두 번째는 알파제로와 리라가 쓰는 몬테카를로 트리 탐색(MCTS)이에요. 신경망이 “이 수가 유망해 보인다”는 직관을 제공하면, 그 직관을 바탕으로 유망한 가지를 집중적으로 파고드는 방식이죠.
빔 서치는 뭐가 다르냐면요
빔 서치는 발상이 훨씬 단순해요. 매 단계마다 후보들을 평가해서 가장 유망한 상위 K개만 남기고, 나머지는 미련 없이 전부 버려요. 이 K를 '빔 폭(beam width)'이라고 부르는데, 손전등 빔처럼 좁은 범위만 비추면서 앞으로 나아가는 그림을 떠올리면 돼요. 사실 개발자들에게 빔 서치는 낯선 알고리즘이 아니거든요. 기계번역이나 LLM이 문장을 생성할 때 다음 단어 후보를 몇 개씩만 유지하면서 이어가는 디코딩 기법이 바로 빔 서치예요. 계산량과 메모리 사용량이 예측 가능하고 구현이 단순하다는 게 큰 장점이고요.
그런데 체스에서는 빔 서치가 전통적으로 금기에 가까웠어요. 왜냐하면 빔 서치에는 '완전성'이 없거든요. 어떤 수가 지금 당장은 평범해 보여서 빔 밖으로 잘려나가면, 그 수 뒤에 숨어 있던 결정적인 전술 콤비네이션은 영영 발견할 수 없어요. 체스는 조용해 보이는 수 한 방에 판이 뒤집히는 게임이라서, 후보를 일찍 쳐내는 건 굉장히 위험한 도박이에요. 알파베타가 수십 년간 왕좌를 지킨 이유가 바로 이 안전성 때문이고요.
그런데 왜 지금 다시 빔 서치일까요
흥미로운 건 시대가 바뀌었다는 점이에요. 요즘 체스 엔진에는 NNUE라고 부르는 효율적인 신경망 평가 함수가 들어가요. 예전처럼 사람이 손으로 짠 규칙이 아니라 학습된 신경망이 국면을 평가하니까, “어떤 수가 유망한가”를 고르는 눈 자체가 비교할 수 없이 좋아졌거든요. 후보를 고르는 눈이 정확해질수록, 상위 K개만 남기고 버리는 빔 서치의 약점은 줄어들고 장점은 살아나요. 사실 리라의 정책망(policy network)이 하는 역할도 결국 '볼 가치가 있는 수 몇 개로 추려내기'라서, 학습된 직관으로 탐색 폭을 좁힌다는 철학은 빔 서치와 맞닿아 있어요. Beam Engine은 이 아이디어를 극단까지 밀어붙이면 어디까지 갈 수 있는지 확인해보는 실험인 셈이에요.
한국 개발자에게는요
이 프로젝트가 재미있는 건 체스 그 자체보다 탐색 알고리즘의 트레이드오프를 생생하게 보여준다는 점이에요. 완전 탐색과 휴리스틱 탐색 사이에서 무엇을 얻고 무엇을 포기하는지, 그리고 평가 함수의 품질이 탐색 전략의 선택을 어떻게 바꾸는지를 실제 동작하는 프로젝트로 확인할 수 있거든요. 빔 서치는 LLM 디코딩, 경로 탐색, 스케줄링 같은 조합 최적화 문제에서 지금도 현역으로 쓰이는 기법이라, 게임 AI에 관심이 없는 분에게도 배워둘 가치가 충분해요. 코딩 테스트에서 BFS에 우선순위를 얹은 변형 문제를 만났을 때도 이 감각이 그대로 도움이 되고요.
정리하면, 검증된 두 개의 왕도 대신 '버리는 탐색'으로 체스에 도전한 흥미로운 실험이에요. 여러분은 어떻게 생각하세요? 평가 함수가 충분히 똑똑해지면 탐색은 단순해져도 될까요, 아니면 체스처럼 전술적인 게임에서는 결국 안전한 완전 탐색이 이길까요?
🔗 출처: Hacker News