GN⁺: 정규 표현식으로 구현된 미니맥스 체스 엔진
(nicholas.carlini.com)2-겹 미니맥스 체스 엔진
-
체스와 정규 표현식: 저자는 정규 표현식만을 사용하여 체스를 두는 프로그램을 만들었음. 이 프로그램은 체스판을 입력으로 받아 유효한 수를 두는 84,688개의 정규 표현식으로 구성됨.
-
정규 표현식 CPU 설계: 정규 표현식을 사용하여 조건 없는 실행과 단일 명령어 다중 데이터(SIMD) 명령어 집합을 설계함. 이를 통해 체스를 두는 프로그램을 작성할 수 있음.
-
데이터 구조: 컴퓨터의 현재 상태는 프로그램 "스택"과 모든 변수를 포함하는 단일 문자열로 표현됨. 각 명령어는 스택의 변수를 조작하거나 특정 변수에 읽기/쓰기 작업을 수행함.
-
기본 스택 연산:
- 푸시 명령어: 스택의 맨 위에 값을 추가함.
- 팝 명령어: 스택의 맨 위 요소를 제거함.
-
변수 <-> 스택 명령어:
- 변수 조회: 변수의 내용을 스택의 맨 위에 로드함.
- 변수 할당: 변수에 값을 할당하며, 변수의 존재 여부에 따라 업데이트하거나 새로 생성함.
-
조건문: 조건문을 통해 프로그램의 흐름을 제어함. 조건에 따라 프로그램의 특정 부분을 활성화하거나 비활성화함.
-
루프의 불가능성: 정규 표현식만으로는 루프를 구현할 수 없으므로, 모든 반복 계산은 미리 펼쳐져야 함.
-
다중 스레드 실행: 정규 표현식의 전역 대체 기능을 활용하여 여러 스레드를 동시에 실행할 수 있음.
-
체스 엔진 작성: 체스 엔진은 다른 프로그래밍 언어에서와 유사하게 작성되며, 병렬 처리를 통해 빠르게 동작함.
-
턴 플레이:
- 플레이어의 수 읽기: 입력된 수를 읽고 유효성을 검사함.
- 컴퓨터의 응답 생성: 가능한 모든 응답을 생성하고 최적의 수를 선택함.
-
미니맥스 탐색: 깊이 2의 미니맥스 탐색을 통해 최적의 수를 선택함. 이 과정은 병렬 처리를 통해 효율적으로 수행됨.
이 프로젝트는 정규 표현식의 독특한 사용을 통해 체스 엔진을 구현한 사례로, 정규 표현식의 강력함과 창의적인 컴퓨터 설계를 보여줌.
Hacker News 의견
-
이 개발자는 printf()가 튜링 완전함을 증명하고 13kB의 Javascript로 1인칭 슈팅 게임을 작성한 사람임
-
여러 가능한 위치의 계산이 병렬로 수행되는 점에서 이 프로젝트가 비범함을 보여줌
- 정규 표현식을 사용하여 여러 스레드를 동시에 실행할 수 있음
-
블로그 글의 결론에 대해 특별히 할 말은 없지만, 이런 무의미한 프로젝트를 더 많은 사람들이 시도했으면 좋겠음
- 재미있고, 완료 시간이나 성공 여부에 대한 부담이 없으며, 컴퓨터 과학의 다양한 분야에 대해 많은 것을 배울 수 있음
-
체스 게임에서 "불법 이동, 패배"라는 버그가 발생함
- 예시 게임에서 불법 이동이 아님에도 불구하고 게임이 종료됨
-
84,688개의 정규 표현식으로 체스를 하는 사람보다 하나의 정규 표현식으로 체스를 하는 사람이 더 두려움
-
이런 프로젝트를 보면 경의를 표하고 싶음
-
a-파일 이동 관련 버그가 수정됨
-
이 프로젝트는 체스 엔진일 뿐만 아니라 정규 표현식만으로 구축된 컴퓨터 및 어셈블리 언어임
-
이전에 sed로 작성된 체스 프로젝트가 있었음
- sed 버전은 제어 흐름 명령을 사용하고 1ply만 탐색함
-
a2a4로 시작할 때 이렇게 빨리 지지 않음
-
명확한 "생산적" 목표 없이 무언가를 시도하는 것이 새로운 방법을 발견하고 혁신을 이끌어낼 수 있음
- 엔진이 초반에 말을 잃음
- 대문자를 입력하면 불법 이동이라고 표시됨
-
혁신을 시도하고 생산적이 되려는 노력 중임