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

2-겹 미니맥스 체스 엔진

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

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

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

• 기본 스택 연산:

  • 푸시 명령어: 스택의 맨 위에 값을 추가함.
  • 팝 명령어: 스택의 맨 위 요소를 제거함.

• 변수 <-> 스택 명령어:

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

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

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

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

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

• 턴 플레이:

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

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

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