천재 광장 크래킹

요약: 저는 The Genius Square 게임을 계산적으로 풀었습니다.

최근 샌디에이고 여행에서 이 게임을 배웠습니다. 날씨 때문에 밖에 많이 나가진 않았지만 보드 게임을 많이 했어요. 저는 The Genius Square 라는 게임에 정말 매료되었습니다 .

게임은 다음과 같이 간단합니다. 6X6 슬롯이 있는 보드가 주어지면 7개의 슬롯이 무작위로 차단되고 2명의 플레이어가 9개의 고정된 모양의 다채로운 Tetris 블록으로 나머지 슬롯을 채우려고 시도하면 더 빠른 플레이어가 승리합니다. 비디오 규칙 링크는 여기 .

지금까지 The Genius Square를 몇 라운드 플레이했습니까? 사실 현재까지는 그렇게 많지 않습니다. 아마도 80%는 제가 만난 그 날 아침에 플레이되었을 것입니다. 하지만 게임의 디자인에 너무 집착하게 되었어요. 플레이하는 모든 라운드에서 사람들은 항상 서로 다른 솔루션을 얻었고 때로는 사람들이 갇히기도 했다는 단순한 사실 때문이었습니다. , 그러나 다른 사람에게 아무리 어려워도 항상 누군가는 몇 분 안에 해결할 수 있습니다.

"일반적인 괴짜 마음"에서 이것은 200개 이상의 리뷰가 있지만 BGG에서 6.8점 이라는 사실을 감안할 때 필수품은 아닐 수 있지만 개인적으로 이 게임은 확실한 10점의 가치가 있다고 생각합니다: 가족 중심의 재미있는 경험, 빠른 게임이지만 전략의 깊이는 적습니다. 한 가지 추가 사항은 계산 솔루션을 얻을 수 있다는 것입니다.

"항상 해결책이 있습니다." 게임 상자 표지에서 알 수 있듯이 게임에 포함된 7개의 주사위/블로커에 대한 해결책이 항상 있습니까? 이 7가지 차단기의 단일 임의 세트로 얼마나 많은 솔루션을 얻을 수 있습니까? 이 7가지 중 가장 어려운 조합은 무엇입니까? 친구들과 2, 3번 플레이한 이후로 내 마음은 이런 질문들로 가득 차 있다. 그래서 명확하고 크게 들리므로 이 게임을 크랙하겠습니다! 컴퓨터 공학으로!

기본적으로 컴퓨터 과학으로 해결할 수 있는 모든 것을 해결하려면 모델이 필요합니다. 한 컴퓨터에서 이 문제를 설명하고 모델링하는 방법은 무엇입니까?

보드는 6X6의 정수 배열로 나타낼 수 있습니다(실제로는 향후 "업그레이드"를 위해 내 프로그램에서 조정 가능한 행 및 열과 같은 모든 매개 변수를 만들었습니다). 이 보드에서 하나의 빈 공간은 0으로, 차단기는 -1로 나타낼 수 있습니다. 따라서 임의의 차단기 세트로 채워진 간단한 보드는 다음과 같을 수 있습니다.

0  0 -1  0 -1  0
 0  0  0  0  0  0
 0  0 -1  0  0 -1
-1  0  0  0 -1  0
 0  0  0  0  0  0
-1  0  0  0  0  0

한편, Tetris 블록은 하나의 id와 보드의 빈 0을 채울 하나의 모양으로 나타낼 수 있습니다. 예를 들어 id = 2인 2X2 정사각형 모양을 할당하고 이 정사각형을 상단 위 보드의 왼쪽 모서리에 L 모양을 지정하고 오른쪽 하단 모서리에 id = 9를 지정하면 결과는 다음과 같이 표시됩니다.

2  2 -1  0 -1  0
 2  2  0  0  0  0
 0  0 -1  0  0 -1
-1  0  0  0 -1  9
 0  0  0  0  0  9
-1  0  0  0  9  9

4  8 -1  7 -1  3
 4  8  8  7  7  3
 4  8 -1  5  7 -1
-1  9  9  5 -1  1
 6  6  9  5  2  2
-1  6  9  5  2  2

어떤 알고리즘을 선택해야 할까요? n-queens 문제에 대해 들어본 적이 있습니까? 아니면 전형적인 8퀸 문제입니까 ? 즉, 체스판에 여왕 8명을 배치하여 여왕들이 서로 방해하지 않도록 하는 것입니다. 컴퓨터 과학에서는 검색 알고리즘이 이 문제를 해결할 수 있고 복잡하게 들리지만 실제로는 계산 시간을 줄이기 위해 때로는 약간의 암기를 포함하여 모든 가능성을 시도하는 무차별 대입 스타일의 한 유형일 뿐입니다. 반면 The Genius Square 게임에서는 n-queens 문제의 솔루션과 매우 유사한 DFS( 깊이 우선 검색 ) 를 사용할 것입니다 .

인간 언어 번역에서 — 저는 컴퓨터가 보드에서 빈 슬롯 하나를 볼 때마다 가능한 모든 채우기를 시도하도록 할 것입니다. 그리고 예, 컴퓨터는 왼쪽 상단 모서리에서 오른쪽 하단까지 빈 슬롯을 찾고 아직 사용 가능한 모든 모양으로 채워지지 않은 슬롯을 하나씩 채우려고 합니다. 나중에 어느 단계에서 9개의 도형을 채우면 빙고! 솔루션을 기록한 후 컴퓨터는 " 역추적 "하여 이전에 채워진 모양 중 일부를 제거하고 다른 조합을 시도합니다.

하나의 모양이 보드에 있을 수 있는 가능한 방향은 무엇입니까? hunman이 빈 슬롯을 채우려고 하면 인간이 방향을 돌려 이 테트리스 모양도 뒤집습니다. 모양을 관찰하면 이 문제에 많은 차이가 있습니다.

예를 들어, 1X1 정사각형과 2X2 정사각형은 모두 하나의 모양만 보드에 놓을 것입니다. 그러나 L 모양(위 채우기 예의 '9'와 마찬가지로)에는 8가지 방향이 있습니다!

1 <- 1X1 square


2 2 <- 2X2 square
2 2


9 9 9   9 9 9  <- L shape
    9   9

9           9  <- L shape
9 9 9   9 9 9

  9     9 9    <- L shape
  9       9
9 9       9

9       9 9    <- L shape
9       9
9 9     9

그러나 더 구체적일 수 있습니다. L 모양의 한 방향을 예로 사용하여 이러한 모양에 대한 "앵커"의 개념을 고려해 보겠습니다.

9 <- anchor position 0
9 <- anchor position 1
9  9 <- anchor position 3
^
|
anchor position 2

따라서 아이디어는 더욱 정확해졌습니다. 컴퓨터가 상단에서 오른쪽 하단으로 쓸고 있는 동안 하나의 빈 슬롯을 발견할 때마다 모든 모양의 모든 방향의 모든 앵커를 시도하여 빈 슬롯에서 앵커를 정확히 채우도록 할 것입니다. 모양은 해당 앵커 위치의 해당 방향에 맞을 수 있습니다.

물론 채우기 시도 프로세스가 빠르게 종료될 것입니다. 하나의 모양이 튀어나오거나 같은 행에서 왼쪽으로 튀어나오면(위의 모든 행과 왼쪽의 동일한 행은 이미 채워지거나 차단된 것으로 간주됨), 보드의 해당 방향 및 앵커로 해당 위치에서 도형을 채울 수 없으므로 직접 false를 반환합니다.

그리고 다른 간단한 종료가 있을 것입니다. 빈 위치에 남은 것이 아무것도 채울 수 없다면 이전 모양을 잘못 배치한 것입니다.

우리는 그것을 얻었다. 보드 표현 모델 + DFS 알고리즘 + 빙고/종료 고려 사항이 모두 준비되었습니다. 단일 게임을 해결하기 위한 의사 코드는 다음과 같습니다.

public void dfs(board, remaining_shapes, shapes, boardIndex, used) {
  // we get one solution, save it to solution set
  if (remaining_shapes == 0) {
    // use a set to de-dupe, but there is no duplication in this algorithm
    solutionSet.add(board.serialize());    
    return;
  }

  // no solution case
  if (boardIndex == board.BOUNDARY)
    return;

  // just go to next slot
  if (board.at(boardIndex).isNotEmpty()) {
    dfs(board, remaining_shapes, boardIndex + 1, used);
    return;
  }

  // read deal, filling shapes here
  for (shape : shapes) {
    if (used.contains(shape)) continue;
    for (orientation : shape.orientations) {
      for (anchor : orientation.anchors) {
        if (tryFillShape(board, boardIndex, shape, orientation, anchor)) {
          // yes, use this shape
          used.add(shape);
          dfs(board, remaining_shapes - 1, shapes, boardIndex + 1, used);
          // backtracking, for other possibilities at this boardIndex
          used.remove(shape);
          cleanUp(board, boardIndex, shape, orientation, anchor);
        }
      }
    }
  }
}

private void tryFillShape(board, boardIndex, shape, orientation, anchor) {
  // test if board has empty spaces at this boardIndex
  // for this shape
  // -> at this shape's orientation
  // -> and at this shape's orientation's anchor
  
  ...
  if (fillable) doFill();
}

private void cleanUp(board, boardIndex, shape, orientation, anchor) {
  // clean up the shape in the board
  // re-fill all 0 to the shape slots at board
  ...
}

solutionSet = new Set<>();
dfs([6X6 board], 9, [all 9 shapes in the game], (0, 0), [none])
print(solutionSet)

Solving:
  0  0 -1  0 -1  0
  0  0  0  0  0  0
  0  0 -1  0  0 -1
 -1  0  0  0 -1  0
  0  0  0  0  0  0
 -1  0  0  0  0  0
Solution Found:
printing board:
  1  5 -1  8 -1  7
  3  5  8  8  7  7
  3  5 -1  8  7 -1
 -1  5  2  2 -1  4
  6  6  2  2  9  4
 -1  6  9  9  9  4
Solution Found:
printing board:
  1  5 -1  8 -1  7
  3  5  8  8  7  7
  3  5 -1  8  7 -1
 -1  5  9  9 -1  4
  6  6  9  2  2  4
 -1  6  9  2  2  4

...

Solution Found:
printing board:
  9  6 -1  5 -1  7
  9  6  6  5  7  7
  9  9 -1  5  7 -1
 -1  8  1  5 -1  4
  8  8  8  2  2  4
 -1  3  3  2  2  4
Solution Found:
printing board:
  9  6 -1  7 -1  3
  9  6  6  7  7  3
  9  9 -1  4  7 -1
 -1  2  2  4 -1  8
  1  2  2  4  8  8
 -1  5  5  5  5  8
Solution Found:
printing board:
  9  6 -1  7 -1  3
  9  6  6  7  7  3
  9  9 -1  5  7 -1
 -1  8  4  5 -1  1
  8  8  4  5  2  2
 -1  8  4  5  2  2

Total solutions: 316

Process finished with exit code 0

잠시만 요, 아래는 실제로 당신을 놀라게 할 수 있습니다.

나는 문자 그대로 게임에 포함된 기본 7개의 주사위, 즉 62,208개의 조합을 사용하여 가능한 모든 단일 조합을 반복하여 다음을 확인합니다. A). 모든 조합에 대한 솔루션이 항상 존재합니까? B). 솔루션의 통계는 무엇입니까?

답: 아). 사실 맞아요. 비). 아래 참조:

combination count    62208
average solutions    1936
min solutions        11
max solutions        22317

그리고 로그-로그 스케일의 분포(히스토그램):

로그 선형 척도의 분포(히스토그램):

예, 수치에서 알 수 있습니다. 솔루션 수가 거의 없는 몇 가지 경우가 있지만 솔루션 수가 500개 이상으로 매우 빠르게 증가합니다.

그래서 솔루션 개수가 특정 숫자보다 적은 조합이 몇 개인지 확인하기 위해 다른 그림을 그립니다. 여기서 [얼마나 많은 조합]은 Y축이고, [특정 수보다 적은 솔루션 수]는 X축입니다.

흥미로운 곡선. 여기에 맞는 수학적 모델이 있어야 하지만, 나는 그 영역을 건드리지 않고 "경험적 취미 과학자"로 머무르는 것이 좋습니다.

좀 더 자세히 말하자면, 컴퓨터가 정말 어렵다고 생각하는 두 가지 조합이 있습니다. 각각 11개의 솔루션만 있습니다.

A6, B1, B5, D1, E3, F2, F4
->
  0  0  0  0  0 -1
 -1  0  0  0 -1  0
  0  0  0  0  0  0
 -1  0  0  0  0  0
  0  0 -1  0  0  0
  0 -1  0 -1  0  0

A3, A5, B4, C6, E2, E6, F1
->
  0  0 -1  0 -1  0
  0  0  0 -1  0  0
  0  0  0  0  0 -1
  0  0  0  0  0  0
  0 -1  0  0  0 -1
 -1  0  0  0  0  0

그리고 컴퓨터가 정말 쉽다고 생각하는 두 가지 조합이 있습니다. 각각 22317개의 솔루션이 있습니다.

B3, B4, F1, F2, F3, F4, F6
->
  0  0  0  0  0  0
  0  0 -1 -1  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
 -1 -1 -1 -1  0 -1

A1, A3, A4, A5, A6, E3, E4
->
 -1  0 -1 -1 -1 -1
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0  0  0  0  0
  0  0 -1 -1  0  0
  0  0  0  0  0  0

Symmetrical!

결론적으로 아마도 소수(> 50 & < 200) 솔루션과의 조합이 좋은 방법으로 인간에게 도전할 수 있습니다. 그러나 현실에서 주사위를 던질 때 이러한 경우는 드뭅니다(평균 솔루션 ~2000). 이것을 더 어렵게 만드는 방법은 무엇입니까? 보드 및 모양, 차단기 및 주사위를 변경하여 일반적으로 몇 가지 솔루션(아마도 > 50 및 < 200)이 한 방향이 될 수 있도록 합니다. 그러나 너무 적은 수의 솔루션 사례가 인간에게 고유할 수 있습니다. 우리는 약간 정교한 기계이므로 "A3, A5, B4, C6, E2, E6, F1" 사례와 같은 일부 모양이 있어야 한다는 것을 쉽게 알아낼 수 있습니다. .

더 큰 보드, 더 많은 모양, 더 많은 블로커, 다른 주사위, 일부 모양을 블로커로 사용하여 계산하는 것과 같이 이것을 다른 수준으로 언제 가져갈지 확실하지 않습니다. 2D 보드 자체는 실제로 3D 보드(또한 모양 및 차단기)로 확장될 수 있지만, 이 경우 아인슈타인이 아닌 한 인간은 게임을 할 수 없습니다.

내 말은, 좋은 기계와 코딩할 시간이 있는 한 계산적 접근 방식으로 시뮬레이션하고 계산할 수 있다는 것입니다.

그리고 실제로 The Genius Square 게임은 환상적인 게임입니다. 저는 디지털이든 물리적이든 꽤 많은 게임을 소유하고 있습니다. 이것은 제가 1-2일 동안 컴퓨팅하고 글을 쓰는 데 보내는 유일한 게임입니다. 가족/친구들과 함께 속도를 겨루는 것도 정말 재미있습니다. 가족 게임 플레이어에게 적극 권장합니다.

게임 설정: The Genius Square의 한 상자.
컴퓨터 설정: AMD 1920X, 64GB RAM, SSD.
소프트웨어 설정: Java, 일부 멀티스레딩, Python.
계산 시간: 62,208 조합의 모든 솔루션에 대해 ~2시간.