Strategia parowania
W grze pozycyjnej strategia parowania to strategia, której gracz może użyć, aby zagwarantować zwycięstwo lub przynajmniej wymusić remis. Polega ona na podzieleniu pozycji na planszy na rozłączne pary. Ilekroć przeciwnik wybiera pozycję w parze, gracz wybiera drugą pozycję w tej samej parze.
Przykład
Rozważ wariant 5 na 5 w kółko i krzyżyk . Możemy stworzyć 12 parami rozłącznych par pozycji na planszy, oznaczonych poniżej przez 1,...,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 |
Zauważ, że środkowy element (oznaczony *) nie należy do żadnej pary; nie jest to potrzebne w tej strategii.
Każda linia pozioma, pionowa lub ukośna zawiera co najmniej jedną parę. Dlatego do wymuszenia remisu można zastosować następującą strategię parowania: „kiedy twój przeciwnik wybierze element pary i , wybierz drugi element pary i ”. Na koniec gry masz element każdej zwycięskiej linii. Dlatego gwarantujesz, że drugi gracz nie może wygrać.
Ponieważ obaj gracze mogą korzystać z tej strategii, gra kończy się remisem.
Ten przykład jest uogólniony poniżej dla dowolnej gry Maker-Breaker . W takiej grze celem Maker jest zajęcie całego zwycięskiego zestawu, podczas gdy celem Breaker jest zapobieganie temu poprzez posiadanie elementu w każdym zwycięskim zestawie.
Strategia parowania dla Makera
Strategia parowania dla Maker wymaga zestawu par elementów, takich jak:
- Wszystkie pary są parami rozłączne;
- Każdy zestaw, który zawiera co najmniej jeden element z każdej pary, zawiera jakiś wygrywający zestaw.
Ilekroć Breaker wybiera element z pary, Maker wybiera drugi element z tej samej pary. Na koniec zestaw Makera zawiera co najmniej jeden element z każdej pary; zgodnie z warunkiem 2 zajmuje cały wygrywający set (jest to prawdą nawet wtedy, gdy Stwórca gra jako drugi).
Jako przykład rozważ planszę do gry zawierającą wszystkie wierzchołki doskonałego drzewa binarnego z wyjątkiem korzenia. Zestawy wygrywające to wszystkie ścieżki od liścia do jednego z dwojga dzieci korzenia. Możemy podzielić elementy na pary, łącząc każdy element z jego rodzeństwem. Strategia parowania gwarantuje, że Maker wygrywa nawet wtedy, gdy gra jako drugi. Jeśli Stwórca zagra jako pierwszy, może wygrać nawet wtedy, gdy plansza zawiera również korzeń: w pierwszym kroku po prostu wybiera korzeń, a następnie stosuje powyższą strategię parowania.
Strategia parowania dla Breakera
Strategia parowania dla Breakera wymaga zestawu par elementów takich, że:
- Wszystkie pary są parami rozłączne;
- Każdy zwycięski zestaw zawiera co najmniej jedną parę.
Ilekroć Maker wybiera element z pary, Breaker wybiera drugi element z tej samej pary. Na koniec Breaker ma element w każdej parze; zgodnie z warunkiem 2 ma element w każdym wygrywającym secie.
Przykład takiej strategii parowania dla gry w kółko i krzyżyk 5 na 5 pokazano powyżej. pokaż inne przykłady kółko i krzyżyk 4x4 i 6x6.
Innym prostym przypadkiem, w którym Breaker ma strategię parowania, jest sytuacja, w której wszystkie zwycięskie zestawy są rozłączne parami, a ich rozmiar wynosi co najmniej 2.