markovjunior

MarkovJunior는 프로그램이 재작성 규칙의 조합으로 구성되고 추론이 제약 전파를 통해 수행되는 확률적 프로그래밍 언어입니다. 마르코프 알고리즘을 정의한 수학자 안드레이 안드레예비치 마르코프의 이름을 따서 명명되었습니다. 기본 형태에서 MarkovJunior 프로그램은 재작성 규칙의 정렬된 목록입니다. 예를 들어, MazeBacktracker 모델은 `RBB=GGR`과 `RGG=WWR` 두 가지 규칙을 사용합니다. 각 실행 단계에서 인터프리터는 그리드에서 일치하는 첫 번째 규칙을 찾고, 모든 일치 항목을 찾은 다음 무작위로 하나를 적용합니다. 인터프리터는 일치하는 규칙이 없을 때 중지됩니다. 확률적 추론은 미래 상태에 제약을 부과하여 제한된 미래로 이어지는 실행만 생성할 수 있게 합니다. 예를 들어, Sokoban 규칙의 추론은 에이전트가 상자를 지정된 모양으로 정리하도록 만듭니다. 저장소에는 던전, 건축, 퍼즐, 시뮬레이션을 위한 많은 확률적 생성기가 포함되어 있습니다. 주요 개념은 다음과 같습니다: - **재작성 규칙**: `(B=W)`와 같은 간단한 규칙은 무작위 검은색 사각형을 흰색으로 변환합니다. `(WBB=WAW)`와 같은 더 복잡한 규칙은 한 줄의 코드로 미로를 생성합니다. 와일드카드(`*`)는 입력에서 모든 색상 또는 변경되지 않은 출력을 허용합니다. - **규칙 노드**: 루프 지우기 무작위 걷기 또는 Aldous-Broder 미로 생성과 같은 여러 규칙을 결합합니다. - **시퀀스 노드**: 규칙 노드를 차례로 실행합니다. 예를 들어, 강 계곡을 위한 보로노이 다이어그램을 구성합니다. - **마르코프 노드**: 과거 노드로 돌아갈 수 있게 하여 Bob Nystrom의 던전 생성과 같은 알고리즘을 가능하게 합니다. - **추론**: 상태를 연결하기 위해 제약 전파(단방향 또는 양방향)를 사용하며, 엄격성을 위한 온도 매개변수가 있습니다. Sokoban과 같은 퍼즐을 풀거나 해밀턴 경로를 생성할 수 있습니다. 추가 자료에는 XML 구문 개요, 고해상도 스크린샷, 비공식 기술 노트가 포함됩니다. 이 프로젝트는 절차적 생성을 위한 프로그램 합성 및 예제에서 모델 합성과 같은 미해결 문제를 논의합니다. 마르코프 알고리즘, Imagegram, REFAL, Dijkstra 맵, A* 탐색과 같은 고전 알고리즘의 영향을 인용합니다. 인터프리터는 다차원 Boyer-Moore 알고리즘을 사용한 빠른 패턴 매칭을 사용하며, 경사 기반 최적화를 위한 확률적 완화를 지원합니다.