패리티

Parity

패리티(Parity)란?

패리티는 한국어로 홀짝성, 우기성 정도로 번역될 수 있습니다. 일상에선 흔히 사용되는 말은 아니지만, 수학과 컴퓨터 분야에서 사용되는 용어입니다.

테트리스에서는 테트리스 블록과 필드의 칸수가 모두 짝수라는 특성을 이용한 수학적인 법칙으로 응용됩니다. 실전이나 스프린트의 스태킹에서도 물론 적용 가능하지만 특히 퍼클 이론에서 자주 쓰이는 원리입니다.

퍼클에 적용되는 대표적인 법칙은 체커보드 패리티와 버티컬 패리티가 있으며, 버티컬 패리티에서 확장된 개념인 4색 패리티도 있습니다.

체커보드 패리티 (Checkerboard Parity)

우선 필드를 체스판처럼 밝은 칸과 어두운 칸이 교차되게 칠했다고 생각해봅시다.

동일한 개수로 이뤄진 밝은 칸과 어두운 칸이 생겼습니다. 우리가 어떤 방법으로 퍼클을 하든, 반드시 같은 개수의 밝은 칸과 어두운 칸을 채워야 한다는 뜻입니다.

이런 필드 위에 4칸을 차지하는 모든 테트리미노를 올려보면 T미노만이 갖는 한 가지 특징을 발견할 수 있습니다. 다른 모든 미노는 어떻게 놓아도 밝은 칸과 어두운 칸을 각각 2칸씩 동일하게 차지하는 반면, T미노는 예외적으로 밝은 칸과 어두운 칸을 각각 1칸/3칸 혹은 3칸/1칸씩 차지합니다. 체커보드 패리티는 바로 이 차이에서 도출되는 법칙입니다.

법칙
퍼클에 쓰이는 T미노 갯수와 홀수칸 라인클리어* 횟수의 총합은 반드시 짝수이다.
(*홀수칸 라인클리어: 중간 줄을 지웠을 때 그 줄 아래 공간의 '빈 칸'이 홀수인 라인클리어)

우리가 다루는 4줄 퍼클 범위 안에서 조금 쉽게 말하면 다음과 같습니다.

T가 홀수(1개 혹은 3개)라면, 밑에 홀수개의 빈칸이 있는 줄을 한 번은 스킴해줘야 퍼클이 가능합니다.(4줄 퍼클 안에서는 홀수칸 라인클리어를 세 번 하는 것이 성립되지 않으므로)
T가 짝수(2개 혹은 드물지만 4개)거나 없다면 그런 줄을 지우는 횟수가 없거나 두 번이어야 합니다.

버티컬 패리티 (Vertical Parity)

세로방향 패리티, 컬럼 패리티(Columnar Parity)라고도 불립니다. 이번에는 필드를 밝은 세로줄과 어두운 세로줄이 번갈아 나타나는 줄무늬 형태로 칠했다고 생각해봅시다.

체커보드 패리티와 마찬가지로, 여기서도 중요한 것은 밝은 칸과 어두운 칸을 모두 홀수로 차지하는 미노를 구분하는 것입니다. 여기서는 모든 방향의 L과 J, 그리고 세로 방향으로 세워진 T가 그런 경우에 해당합니다.

법칙
퍼클에 쓰이는 L과 J, 그리고 세로 방향 T의 총 갯수는 반드시 짝수이다.

체커보드 패리티보다 직관적이므로 좀 더 고려하기 쉬울 것입니다. O, S, Z와 가로 방향 T, 가로 방향 I는 차지하는 칸의 균형을 깨지 않으므로 이 법칙과 무관합니다.

한편 세로 방향 I는 조금 특수한 경우로, 별도의 원리 때문에 이 법칙에는 영향을 미치지 않습니다. 단적으로, 필드 자체가 홀수칸 너비를 가져도 이 법칙은 성립합니다.

4색 패리티 (4-Color Parity)

버티컬 패리티가 필드를 2열 단위로 나눠서 도출된다면, 4색 패리티는 4열 단위로 나눠 생각했을 때 도출되는 법칙입니다. 따라서 앞서 설명한 버티컬 패리티는 논리적으로 4색 패리티 안에 포함되는 개념으로 볼 수 있습니다. 4열 단위의 반복을 이용해 미노의 '방향'에 따른 고유한 특성을 얻는 것이 목적이기 때문에, 필드 너비가 4배수가 아니라는 것은 문제가 되지 않습니다.

우선은 바로 적용 가능한 형태로 정리된 법칙부터 보여드리겠습니다. 구체적인 원리를 이해하려면 모듈러 계산에 대해 알아야 하지만, 결론 자체는 간단한 덧셈과 뺄셈만 할 수 있으면 충분히 적용 가능합니다.

법칙
4줄(혹은 4배수 높이의 필드) 퍼클에 쓰이는 모든 미노들의 고유값을 더한 결과가 반드시 4의 배수(-4, 0, 4, 8...)이다.

각 미노의 고유값은 아래와 같이 부여됩니다.

세로 방향 T와 모든 L/J
→ 꼭지 위치가 블록의 중심 기준에서 왼쪽이면 -1, 오른쪽이면 +1

*꼭지(Tail): T/L/J에서 일렬로 된 3칸을 제외한 1칸 (이 이미지에서 밝은 부분)

세로 방향 S/Z와 수평 I, O
→ ±2 (덧셈 뺄셈 무관)

1회차 6p 셋업인 그레이스 시스템을 이루는 IOSZ 모양이 모두 ±2라고 생각하시면 편합니다. 편의상 이를 '그레이스 IOSZ'라고 칭하겠습니다.

그 외(가로 방향 T/S/Z, 수직 I)
→ 0 (영향 없음)

홀수 값이 T/L/J에서만 나오므로 그 미노들 간의 계산 결과는 반드시 짝수여야 합니다. 이 점을 단순화한 것이 L/J와 세로 방향 T의 총 개수가 짝수라는 버티컬 패리티 법칙입니다. 여기서 더 나아가면 꼭지가 오른쪽에 있는 블록과 왼쪽에 있는 블록의 개수 차이도 필연적으로 짝수일 수밖에 없습니다. 그 차이가 0을 포함해 4배수일 땐 ±2로 계산되는 '그레이스 IOSZ'가 짝수개 있어야 합니다. 반면 그 차이가 2, 6처럼 4의 배수가 아닌 짝수라면 그레이스 IOSZ가 홀수 개 있어야 2 차이를 보정할 수 있습니다. 다음과 같이 정리할 수 있습니다.

T/L/J의 좌우 꼭지 개수 차이가 4의 배수(4줄 퍼클에서는 일반적으로 0개나 4개) → 그레이스 IOSZ는 짝수 개
T/L/J의 좌우 꼭지 개수 차이가 4의 배수가 아님(4줄 퍼클에서는 일반적으로 2개) → 그레이스 IOSZ는 홀수 개

이 조건을 만족해야 최종 계산값이 4의 배수가 되어 퍼클이 가능합니다.

이 법칙의 구체적인 원리를 살펴보자면 다음과 같습니다.

우선 해야 할 일은 어떤 미노를 필드 위에 올려본 후 그 미노가 차지하는 칸들의 값을 더해 4로 나눈 나머지를 구하는 것입니다. 그러면 모든 수에 대응되는 값이 0, 1, 2, 3, 0, 1, 2, 3...으로 시계처럼 반복됩니다. 즉, 4만큼 차이 나는 숫자들은 모두 같은 위치로 취급할 수 있습니다. 이때 중요한 것은 미노와 방향이 정해져 있을 때 나올 수 있는 결과값이 위치와 관계없이 동일하다는 것입니다.

예를 들어 아래 방향 T미노를 우선 아무 자리에 둬본다고 가정하면, 어떤 위치에서는 T가 (0, 1, 1, 2) 칸을 차지할 수 있고, 이때 해당하는 값은 0+1+1+2=4를 4로 나눈 나머지인 0입니다. 그런데 만약 이 미노가 옆으로 옮겨진다 해도 그 미노가 차지하는 모든 칸이 나머지 계산에서 동일한 변화량을 갖기 때문에 어디에 놓든 4로 나눈 나머지는 항상 같게 됩니다. 아래 방향 T미노를 다른 위치에 놓았을 때 (1, 2, 2, 3)의 합은 8, (2, 3, 3, 0)의 합은 8, (3, 0, 0, 1)의 합은 4이므로 모두 4로 나눈 나머지가 0입니다. 따라서 이 0은 특정 위치에만 나오는 값이 아니라 위치와 관계없이 아래 방향 T미노 자체에 항상 주어지는 고유한 값이 되는 것입니다.

4줄 퍼클에 들어가는 필드 모든 칸의 합은 4의 배수이므로 4로 나눈 나머지가 0입니다. 따라서 4줄 퍼클이 되려면 그 필드에 들어갈 모든 미노들의 고유값의 합이 4의 배수인지 확인하는 것이 관건입니다.(2줄 퍼클과 6줄 퍼클에서는 4로 나눈 나머지가 2인 합이 나와야 합니다.) 이때 0을 만드는 계산의 편의를 위해 미노의 고유값이 3이면 반복 단위인 4를 뺀 -1로 취급하고, 2는 4를 뺀 -2가 동일한 절대값을 가지므로 계산 편의에 따라 더하거나 뺄 수 있도록 정리한 것이 위에 설명된 법칙입니다.

따라서 애초에 칸에 부여된 값을 아래와 같이 이해해도 상관 없습니다.

미노의 고유값 자체는 오히려 이렇게 봤을 때 더 쉽게 도출 가능

박스 룰 (Box Rule)

엄밀히 따지면 이것은 패리티에 속하는 개념은 아닙니다. 하지만 한정된 직사각형 공간을 테트리미노로 채우는 과정에서 필연적으로 나타나는 성질이라는 점에서 패리티와 함께 퍼클을 판단하는 데 유용합니다.

패리티 법칙은 기본적으로 필드의 칸을 짝수 쌍으로 구분할 수 있다는 성질만을 이용합니다. 필드의 '벽'과 '범위'까지 고려하진 않습니다. 때문에 패리티상 문제 없어도 퍼클은 되지 않는 경우가 생길 수 있습니다. 예를 들어 S미노만 10개 있으면 패리티 법칙에 위배되지 않게 놓을 수 있지만, 이것으로 한정된 직사각형 공간을 채울 수 있는 것은 아닙니다. 즉, 패리티는 퍼클의 필요조건이지만 충분조건은 아닙니다. 박스 룰은 이 틈을 보충하기 위한 개념입니다.

법칙
한정된 높이의 직사각형 필드 양쪽 벽에는 각각 L/J 혹은 세로 방향 T가 최소 하나씩 있어야 한다. (단 자체적으로 벽을 채울 수 있는 I와 O는 예외)

이 법칙은 중간 스킴을 포함해도 적용됩니다. I와 O만으로 벽 쪽을 쌓았어도 그 다음 안쪽에는 반드시 L/J나 세로 방향 T가 최소 하나 존재할 것입니다. 가장 간단히 확인하는 방법은 S나 Z, 가로 방향 T만으로 높이가 한정된 벽을 채우는 것이 가능한지 보는 것인데, 사실 직관적으로도 안 된다는 걸 쉽게 알 수 있습니다.

게다가 가방 구조상 11개 미노 중 T/L/J가 2개 미만인 경우를 볼 일은 없기 때문에 얼핏 보면 큰 의미 없는 규칙으로 보일 수도 있지만, 존재하는 T/L/J 중 최소 2개가 벽 혹은 적어도 I나 O 옆에 붙어야 한다는 정보만으로 경우의 수를 좁힐 순 있을 것입니다.

패리티가 미노 간의 홀짝을 검사하는 도구라면, 박스 룰은 그 미노들이 실제로 한정된 공간 안에서 벽을 포함해 배치될 수 있는지를 검사하는 도구라고 생각하면 됩니다.

실용성 있는 법칙들은 이 정도이고, 추가적으로 아래와 같은 법칙들이 더 존재하나 여기부터는 굳이 적용하려 신경쓰기보단 이론적으로 존재한다는 것만 참고하시면 됩니다. (작성 중)

로우 패리티 (Row Parity)

가로방향 패리티라고도 할 수 있습니다. 필드를 세로줄 단위로 나누는 버티컬 패리티와 달리 가로줄 단위로 밝은 칸과 어두운 칸을 구분합니다.

법칙

퍼클에 쓰이는 L과 J, 그리고 세로 방향 T의 총 갯수와 퍼클에서 발생하는 클리어시프트(clearshift)의 합이 짝수이다.

클리어시프트: 어떤 라인클리어가 발생했을 때 그 행이 맨 아래로 '이동'하고 다른 줄들은 그만큼 밀려 올라온다고 가정하고, 이때 라인클리어 전과 후에 밝은 칸의 지정값 1과 어두운 칸의 지정값 0의 합계가 어떻게 바뀌었는지에 대한 계산값

버티컬 패리티와 달리 라인 클리어의 영향을 매 순간 매 경우마다 고려하는 것이 현실적으로 어렵기 때문에 실제로 활용하긴 어렵습니다.

도미노 패리티 (Domino Parity)

필드를 세로 방향 도미노(2칸 묶음) 단위로 나누고 L/J와 S/Z도 모양을 2개의 도미노로 구분했을 때 적용 가능한 법칙입니다.

법칙

필드의 어느 도미노에 자신의 도미노를 맞출 수 있는 L/J/S/Z의 갯수 + 짝수번째 행에 놓이는 가로 방향 T의 갯수 = 짝수

이 법칙도 라인 클리어에 따른 변동성이 크기 때문에 실용적이진 않습니다. 이 법칙은 본 사이트 편집팀 일원 Bibii가 S/Z 관련 패리티 가능성을 탐구하다 직접 발견한 것인데, 어떤 방식으로든 필드 칸을 규칙적으로 구분할 수만 있다면 그 안에서 법칙을 찾아낼 수 있다는 것을 보여주는 한 예시 정도로 보시면 됩니다. 어쩌면 여러분이 또다른 패리티 법칙을 찾아낼 수도 있을 것입니다.

참고 자료:

Intro to PC Theory https://docs.google.com/document/d/1udtq235q2SdoFYwMZNu-GRYR-4dCYMkp0E8_Hw1XTyg/edit#

Four Color Parity https://docs.google.com/document/d/14RSnAN4tnQ2x37y4rLbicVn1Eim8_repuvHqRpcVJqY/edit?tab=t.0

"Box rule" (PC Gang 디스코드 서버 가입 필요)
https://discord.com/channels/569728778985537585/853373880579522590/1033170253947093132

Mino distance (PC Gang 디스코드 서버 가입 필요) https://discord.com/channels/569728778985537585/569730931544293395/832431747219718164

Domino Parity https://docs.google.com/spreadsheets/d/1bxhx4N0tbOkdWyMIBVjzKorAOSY1yWtxwlRTdQ_Nq1k/edit?gid=1234966416#gid=1234966416

Page updated

Google Sites

Report abuse