# 정규 표현식으로 구현된 미니맥스 체스 엔진

> Clean Markdown view of GeekNews topic #18623. Use the original source for factual precision when an external source URL is present.

## Metadata

- GeekNews HTML: [https://news.hada.io/topic?id=18623](https://news.hada.io/topic?id=18623)
- GeekNews Markdown: [https://news.hada.io/topic/18623.md](https://news.hada.io/topic/18623.md)
- Type: GN+
- Author: [neo](https://news.hada.io/@neo)
- Published: 2025-01-08T09:52:50+09:00
- Updated: 2025-01-08T09:52:50+09:00
- Original source: [nicholas.carlini.com](https://nicholas.carlini.com/writing/2025/regex-chess.html)
- Points: 4
- Comments: 1

## Topic Body

### 2-겹 미니맥스 체스 엔진

- **체스와 정규 표현식**: 저자는 정규 표현식만을 사용하여 체스를 두는 프로그램을 만들었음. 이 프로그램은 체스판을 입력으로 받아 유효한 수를 두는 84,688개의 정규 표현식으로 구성됨.

- **정규 표현식 CPU 설계**: 정규 표현식을 사용하여 조건 없는 실행과 단일 명령어 다중 데이터(SIMD) 명령어 집합을 설계함. 이를 통해 체스를 두는 프로그램을 작성할 수 있음.

- **데이터 구조**: 컴퓨터의 현재 상태는 프로그램 "스택"과 모든 변수를 포함하는 단일 문자열로 표현됨. 각 명령어는 스택의 변수를 조작하거나 특정 변수에 읽기/쓰기 작업을 수행함.

- **기본 스택 연산**:
  - **푸시 명령어**: 스택의 맨 위에 값을 추가함.
  - **팝 명령어**: 스택의 맨 위 요소를 제거함.

- **변수 <-> 스택 명령어**:
  - **변수 조회**: 변수의 내용을 스택의 맨 위에 로드함.
  - **변수 할당**: 변수에 값을 할당하며, 변수의 존재 여부에 따라 업데이트하거나 새로 생성함.

- **조건문**: 조건문을 통해 프로그램의 흐름을 제어함. 조건에 따라 프로그램의 특정 부분을 활성화하거나 비활성화함.

- **루프의 불가능성**: 정규 표현식만으로는 루프를 구현할 수 없으므로, 모든 반복 계산은 미리 펼쳐져야 함.

- **다중 스레드 실행**: 정규 표현식의 전역 대체 기능을 활용하여 여러 스레드를 동시에 실행할 수 있음.

- **체스 엔진 작성**: 체스 엔진은 다른 프로그래밍 언어에서와 유사하게 작성되며, 병렬 처리를 통해 빠르게 동작함.

- **턴 플레이**:
  - **플레이어의 수 읽기**: 입력된 수를 읽고 유효성을 검사함.
  - **컴퓨터의 응답 생성**: 가능한 모든 응답을 생성하고 최적의 수를 선택함.

- **미니맥스 탐색**: 깊이 2의 미니맥스 탐색을 통해 최적의 수를 선택함. 이 과정은 병렬 처리를 통해 효율적으로 수행됨.

이 프로젝트는 정규 표현식의 독특한 사용을 통해 체스 엔진을 구현한 사례로, 정규 표현식의 강력함과 창의적인 컴퓨터 설계를 보여줌.

## Comments



### Comment 33122

- Author: neo
- Created: 2025-01-08T09:52:50+09:00
- Points: 1

###### [Hacker News 의견](https://news.ycombinator.com/item?id=42619652) 
- 이 개발자는 printf()가 튜링 완전함을 증명하고 13kB의 Javascript로 1인칭 슈팅 게임을 작성한 사람임
  - [GitHub 링크: printf() 튜링 완전성](https://github.com/HexHive/printbf)
  - [GitHub 링크: 13kB Javascript 게임](https://github.com/carlini/js13k2019-yet-another-doom-clone)

- 여러 가능한 위치의 계산이 병렬로 수행되는 점에서 이 프로젝트가 비범함을 보여줌
  - 정규 표현식을 사용하여 여러 스레드를 동시에 실행할 수 있음

- 블로그 글의 결론에 대해 특별히 할 말은 없지만, 이런 무의미한 프로젝트를 더 많은 사람들이 시도했으면 좋겠음
  - 재미있고, 완료 시간이나 성공 여부에 대한 부담이 없으며, 컴퓨터 과학의 다양한 분야에 대해 많은 것을 배울 수 있음

- 체스 게임에서 "불법 이동, 패배"라는 버그가 발생함
  - 예시 게임에서 불법 이동이 아님에도 불구하고 게임이 종료됨

- 84,688개의 정규 표현식으로 체스를 하는 사람보다 하나의 정규 표현식으로 체스를 하는 사람이 더 두려움

- 이런 프로젝트를 보면 경의를 표하고 싶음

- a-파일 이동 관련 버그가 수정됨
  - [GitHub 링크: 버그 수정](https://github.com/carlini/regex-chess/issues/1)

- 이 프로젝트는 체스 엔진일 뿐만 아니라 정규 표현식만으로 구축된 컴퓨터 및 어셈블리 언어임

- 이전에 sed로 작성된 체스 프로젝트가 있었음
  - sed 버전은 제어 흐름 명령을 사용하고 1ply만 탐색함

- a2a4로 시작할 때 이렇게 빨리 지지 않음

- 명확한 "생산적" 목표 없이 무언가를 시도하는 것이 새로운 방법을 발견하고 혁신을 이끌어낼 수 있음
  - 엔진이 초반에 말을 잃음
  - 대문자를 입력하면 불법 이동이라고 표시됨

- 혁신을 시도하고 생산적이 되려는 노력 중임