페어링 전략

Pairing strategy

포지셔닝 게임에서 페어링 전략은 플레이어가 승리를 보장하거나 최소한 무승부를 강요하기 위해 사용할 수 있는 전략입니다.이것은 게임 보드의 위치를 분리된 쌍으로 나누는 것에 기초한다.상대가 한 쌍의 위치를 선택할 때마다 플레이어는 같은 쌍의 다른 위치를 선택합니다.

예

Tic-tac-toe의 5x5 배리언트를 검토해 주십시오.아래 [1]: 3 1,...12로 표시된 12쌍의 보드 위치를 만들 수 있습니다.

11 1 8 1 12
6 2 2 9 10
3 7 * 9 3
6 7 4 4 10
12 5 8 5 11

중앙 요소(*로 표시)는 어느 쌍에도 속하지 않으므로 이 전략에서는 필요하지 않습니다.

각 수평, 수직 또는 대각선은 적어도 한 쌍을 포함한다.따라서 "상대가 페어 i의 요소를 선택할 때마다 페어 i의 다른 요소를 선택하십시오."라는 페어링 전략을 사용할 수 있습니다.게임이 끝나면 각 우승 라인의 요소가 생깁니다.따라서 상대방이 이길 수 없다는 것을 보증합니다.

두 선수 모두 이 전략을 사용할 수 있기 때문에 무승부입니다.

이 예는 임의의 Maker-Breaker 게임에 대해 다음과 같이 일반화되어 있습니다.이러한 게임에서 메이커의 목표는 위닝 세트 전체를 점유하는 것이며 브레이커의 목표는 각 위닝 세트에 요소를 소유함으로써 이를 방지하는 것이다.

제조사의 페어링 전략

제조업체를 위한 쌍 구성 전략에는 다음과 [1]: 119 같은 요소 쌍이 필요합니다.

  • 모든 쌍은 쌍으로 분리되어 있다.
  • 각 쌍의 요소를 적어도1개 포함하는 모든 세트에는 몇 가지 당첨 세트가 포함되어 있습니다.

Breaker가 쌍의 요소를 선택할 때마다 Maker는 동일한 쌍의 다른 요소를 선택합니다.마지막으로, Maker의 세트에는 각 페어에서 적어도 1개의 요소가 포함되어 있으며, 조건 2에 의해 그는 전체 위닝 세트를 점유한다(Maker가 2번째 플레이를 하는 경우에도 마찬가지).

예를 들어 루트를 제외한 완벽한 이진 트리의 모든 정점을 포함하는 게임보드를 생각해 보십시오.우승 세트는 잎에서 뿌리의 두 아이 중 하나까지의 모든 경로입니다.각 요소를 형제 요소와 쌍으로 구성함으로써 요소를 쌍으로 분할할 수 있습니다.페어링 전략은 2등을 해도 메이커의 승리를 보장한다.Maker가 먼저 플레이하면 게임 보드에 루트도 포함되어 있어도 이길 수 있습니다.첫 번째 단계에서는 루트만 골라서 그 이후로는 위의 페어링 전략을 수행합니다.

차단기 페어링 전략

브레이커의 페어링 전략에는 다음과 같은 일련의 요소 페어가 필요합니다.

  • 모든 쌍은 쌍으로 분리되어 있다.
  • 모든 우승 세트에는 적어도 한 쌍이 포함됩니다.

Maker가 쌍의 요소를 선택할 때마다 Breaker는 동일한 쌍의 다른 요소를 선택합니다.마지막에 브레이커는 각 페어에 요소를 가지고 있으며, 조건 2에 따라 각 위닝 세트에 요소를 가지고 있습니다.

5 x 5 틱택토에 대한 이러한 페어링 전략의 예를 위에 나타냅니다.[1]: 2–3 에 4x4 및 6x6 tic-toe의 다른 예를 나타냅니다.

브레이커가 페어링 스트래티지를 갖는 또 다른 간단한 경우는 모든 당첨 세트가 페어링으로 분리되고 그 크기가 최소 2인 경우입니다.

레퍼런스

  1. ^ a b c Hefetz, Dan; Krivelevich, Michael; Stojaković, Miloš; Szabó, Tibor (2014). Positional Games. Oberwolfach Seminars. Vol. 44. Basel: Birkhäuser Verlag GmbH. ISBN 978-3-0348-0824-8.