arXiv:1907.02548

Procedural Generation of Initial States of Sokoban

Dâmaris S. Bento, André G. Pereira, Levi H. S. Lelis

제출 2019-07-04

원문 초록

Procedural generation of initial states of state-space search problems have applications in human and machine learning as well as in the evaluation of planning systems. In this paper we deal with the task of generating hard and solvable initial states of Sokoban puzzles. We propose hardness metrics based on pattern database heuristics and the use of novelty to improve the exploration of search methods in the task of generating initial states. We then present a system called Beta that uses our hardness metrics and novelty to generate initial states. Experiments show that Beta is able to generate initial states that are harder to solve by a specialized solver than those designed by human experts.

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2108.11204v4cs.AI공통 태그 Sokoban공식 코드 · Papers with Code

복잡한 추론 작업을 위한 서브골 탐색

Subgoal Search For Complex Reasoning Tasks

인간은 한 아이디어에서 관련된 다른 아이디어로 이동하는 정신적 과정을 통해 복잡한 추론(reasoning) 작업을 해결하는 데 뛰어납니다. 이에 영감을 받아, 본 논문에서는 서브골 탐색(Subgoal Search, kSubS) 방법을 제안합니다. 이 방법의 핵심 요소는 달성 가능하면서도 해결책에 더 가까운 다양한 서브골을 생성하는 학습된 서브골 생성기입니다. 서브골을 사용하면 탐색 공간을 줄이고 효율적인 계획 수립(planning)에 적합한 고수준 탐색 그래프를 유도할 수 있습니다. 본 논문에서는 트랜스포머 기반 서브골 모듈을 고전적인 최선 우선 탐색(best-first search) 프레임워크와 결합하여 kSubS를 구현합니다. $k$단계 앞의 서브골을 생성하는 단순한 접근 방식이 두 가지 인기 퍼즐 게임인 소코반(Sokoban) 및 루빅스 큐브(Rubik's Cube), 그리고 부등식 증명 벤치마크인 INT라는 세 가지 까다로운 도메인에서 놀라울 정도로 효율적임을 보여줍니다. kSubS는 적당한 계산 예산 내에서 INT의 최고 성능(SOTA)을 포함한 강력한 결과를 달성합니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.