Strategie párování - Pairing strategy

V poziční hra, a párovací strategie je strategie, kterou může hráč použít k zajištění vítězství nebo přinutit alespoň vynutit remízu. Je založen na rozdělení pozic na herním plánu do disjunktních párů. Kdykoli si soupeř vybere pozici ve dvojici, vybere si hráč druhou pozici ve stejné dvojici.

Příklad

Zvažte variantu 5 x 5 Piškvorky. Můžeme vytvořit 12 párů disjunktních párů pozic desky, označených níže 1, ..., 12:^[1]:3

Všimněte si, že centrální prvek (označený *) nepatří žádnému páru; v této strategii to není nutné.

Každá horizontální, vertikální nebo diagonální čára obsahuje alespoň jeden pár. K vynucení remízy lze tedy použít následující strategii párování: „kdykoli si váš soupeř vybere prvek dvojice i, vyberte další prvek páru i". Na konci hry máte prvek každé výherní linie. Proto zaručujete, že druhý hráč nemůže vyhrát."

Jelikož oba hráči mohou tuto strategii použít, hra je remízou.

Tento příklad je zobecněn níže pro libovolné Hra Maker-Breaker. V takové hře je cílem Tvůrce obsadit celý výherní set, zatímco cílem Breakeru je tomu zabránit tím, že vlastní prvek v každé výherní sadě.

Strategie párování pro Maker

Strategie párování pro Maker vyžaduje sadu párů prvků, která:^[1]:119

• Všechny páry jsou párově disjunktní;
• Každá sada, která obsahuje alespoň jeden prvek z každé dvojice, obsahuje výherní sadu.

Kdykoli Breaker vybere prvek z páru, Maker vybere druhý prvek ze stejného páru. Na konci Maker's set obsahuje alespoň jeden prvek z každé dvojice; podmínkou 2 obsadí celý výherní set (to platí, i když Maker hraje druhý).

Jako příklad zvažte herní plán obsahující všechny vrcholy v a dokonalý binární strom kromě kořene. Vítězné sady jsou všechny cesty od listu k jedné ze dvou dětí kořene. Můžeme rozdělit prvky do párů spárováním každého prvku s jeho sourozencem. Strategie párování zaručuje, že Maker vyhrává, i když hraje druhý. Pokud Maker hraje jako první, může vyhrát, i když herní plán obsahuje také kořen: v prvním kroku si pouze vybere kořen a od té doby hraje výše uvedenou strategii párování.

Strategie párování pro Breaker

Strategie párování pro Breaker vyžaduje sadu párů prvků, která:

• Všechny páry jsou párově disjunktní;
• Každá výherní sada obsahuje alespoň jeden pár.

Kdykoli si Maker vybere prvek z páru, Breaker vybere druhý prvek ze stejného páru. Na konci má Breaker v každé dvojici prvek; podmínkou 2 má prvek v každé výherní sadě.

Příklad takové strategie párování pro 5-by-5 ​​tic-tac-toe je uveden výše. ^[1]:2–3 ukázat další příklady pro tic-tac-toe 4x4 a 6x6.

Dalším jednoduchým případem, kdy má Breaker strategii párování, je situace, kdy jsou všechny výherní sady párově disjunktní a jejich velikost je alespoň 2.

Reference