Mahjong-Solitaire Solver 알고리즘

Question

나는 Mahjong-Solitaire 솔버를 개발하고 있으며 지금까지는 꽤 잘하고 있습니다. 그러나, 내가 원하는만큼 빠르지 않기 때문에 여러분이 알고있는 추가 최적화 기술을 요구합니다.

모든 타일은 레이아웃에서 알려져 있지만 솔루션은 아닙니다. 현재, 나는 같은 타일의 특정 쌍을 안전하게 제거 할 수있는 규칙이 거의 없습니다 (가능한 해결책에 장애가 될 수 없음).

명확성을 위해, 타일은 언제라도 선택할 수 있고 타일은 다른 타일이 전혀 묶이지 않을 때 느슨합니다.

• 무료 무료 타일이 4 개있는 경우 즉시 제거하십시오.
• 픽업 할 수있는 3 개의 타일이 있고 그중 하나 이상이 느슨한 타일이라면, 비 루즈를 제거하십시오.
• 픽업 할 수있는 3 개의 타일이 있고 1 개의 프리 타일 (2 개의 느슨) 만 있으면 자유롭고 무작위로 느슨해집니다.
• 사용 가능한 세 개의 느슨한 타일이 있으면 두 개의 타일을 제거하십시오 (어느 쪽이든 상관 없습니다).
• 정확히 같은 타일의 4 배가 있으므로 두 타일이 남아 있으면 남은 유일한 타일이 남아 있으므로 제거하십시오.

내 알고리즘은 여러 스레드에서 솔루션을 재귀 적으로 검색합니다. 분기가 완료되면 (더 이상 움직이지 않는 위치로) 솔루션으로 이어지지 않으면 나쁜 것들이 포함 된 벡터에 위치를 배치합니다. 이제 새 지점이 시작될 때마다 특정 위치가 이미 확인되었는지 확인하기 위해 나쁜 위치를 통해 반복 할 것입니다.
이 프로세스는 솔루션이 발견되거나 가능한 모든 위치가 점검 될 때까지 계속됩니다.

이것은 36 또는 72 타일을 포함하는 레이아웃에서 잘 작동합니다. 그러나 더 많은 경우,이 알고리즘은 검색 할 수있는 많은 양의 위치로 인해 거의 쓸모가 없습니다.

따라서 안전한 타일 제거에 대한 더 많은 규칙을 구현하는 방법이나 알고리즘과 관련된 다른 특정 속도를 구현하는 방법이 좋은 아이디어가 있는지 다시 한 번 묻습니다.

안부, NHAA123

Answer 1

솔버가 어떻게 작동하는지 완전히 이해하지 못합니다. 움직임을 선택할 때 어떤 가능성을 먼저 탐색 할 가능성을 어떻게 결정합니까?

임의의 것을 선택하면 충분하지 않습니다. 기본적으로 무차별 검색입니다. 먼저 "더 나은 가지"를 탐색해야 할 수도 있습니다. 어떤 분기가 "더 나은"지를 결정하려면 위치를 평가하는 휴리스틱 기능이 필요합니다. 그런 다음 인기있는 휴리스틱 검색 알고리즘 중 하나를 사용할 수 있습니다. 이것을 확인하십시오 :

• 검색
• 빔 검색

(Google은 친구입니다)

Answer 2

몇 년 전, 나는 엿보기로 Solitaire Mahjongg 보드를 해결하는 프로그램을 썼습니다. 나는 그것을 사용하여 백만 거북이를 검사하는 데 사용했으며 (하루가 걸렸거나 컴퓨터의 절반에 걸쳐 : 두 개의 코어가있었습니다) 약 2.96 %를 해결할 수없는 것으로 보입니다.

http://www.math.ru.nl/~debondt/mjsolver.html

좋아, 그것은 당신이 요청한 것이 아니었지만, 당신은 지금까지 당신의 마음을 가로 지르는 가지 치기 휴리스틱을 찾기 위해 코드를 살펴볼 것입니다. 이 프로그램은 몇 메가 바이트 이상의 메모리를 사용하지 않습니다.

Answer 3

"나쁜"위치를 포함하는 벡터 대신 선형 조회 시간 대신 일정한 조회 시간을 갖는 세트를 사용하십시오.