m , n , k -gra
Gra m , n , k gra to abstrakcyjna planszowa , w której dwóch graczy na zmianę umieszcza kamienie w swoim kolorze na planszy m na n , a zwycięzcą zostaje gracz, który jako pierwszy ułoży k kamieni w swoim kolorze rząd, poziomo, pionowo lub ukośnie. Tak więc kółko i krzyżyk to gra 3,3,3, a gomoku w stylu dowolnym to gra 15,15,5. Gra m , n , k nazywana jest także a k -w-rzędzie na planszy m -by- n .
Gry m , n , k mają głównie znaczenie matematyczne . Poszukuje się teoretycznej gry , wyniku gry z doskonałą grą . Jest to znane jako rozwiązanie gry.
Argument dotyczący kradzieży strategii
Standardowa strategia kradnąca argument z kombinatorycznej teorii gier pokazuje, że w żadnej grze m , n , k nie może istnieć strategia, która zapewnia wygraną drugiego gracza ( strategia wygrywająca drugiego gracza ). Dzieje się tak, ponieważ dodatkowy kamień przyznany któremukolwiek z graczy na dowolnej pozycji może tylko zwiększyć szanse tego gracza. Argument dotyczący kradzieży strategii zakłada, że drugi gracz ma zwycięską strategię i demonstruje zwycięską strategię pierwszemu graczowi. Na początek pierwszy gracz wykonuje dowolny ruch. Następnie gracz udaje drugiego gracza i przyjmuje zwycięską strategię drugiego gracza. Mogą to zrobić, o ile strategia nie wymaga postawienia kamienia na „dowolnym” polu, które jest już zajęte. Jeśli jednak tak się stanie, mogą ponownie wykonać dowolny ruch i kontynuować jak poprzednio zwycięską strategię drugiego gracza. Ponieważ dodatkowy kamień nie może im zaszkodzić, jest to zwycięska strategia dla pierwszego gracza. The sprzeczność oznacza, że pierwotne założenie jest fałszywe, a drugi gracz nie może mieć zwycięskiej strategii.
Argument ten nie mówi nic o tym, czy dana gra jest remisem, czy wygraną pierwszego gracza. Ponadto nie podaje strategii dla pierwszego gracza.
Stosowanie wyników do różnych rozmiarów planszy
Przydatnym pojęciem jest „słaba ( m , n , k ) gra”, w której k -w-rzędzie drugiego gracza nie kończy gry wygraną drugiego gracza.
Jeśli słabe ( m , n , k ) jest remisem, to zmniejszenie m lub n lub zwiększenie k również spowoduje remis.
I odwrotnie, jeśli słaby lub normalny ( m , n , k ) jest wygraną, to każdy większy słaby ( m , n , k ) jest wygraną.
Należy zauważyć, że dowody remisów przy użyciu strategii parowania również dowodzą remisu dla słabej wersji, a zatem dla wszystkich mniejszych wersji.
Wyniki ogólne
Poniższe stwierdzenia odnoszą się do pierwszego gracza w grze słabej, przy założeniu, że obaj gracze stosują optymalną strategię.
- 00000000000000 Jeśli określony ( m , n , k ) jest remisem, to ( m , n , k ) z k ≥ k jest remisem, a ( m , n , k ) z m ≤ m i n ≤ n jest remisem. Podobnie, jeśli ( m , n , k ) jest wygraną, to ( m , n , k ) z 0000 k ≤ k to wygrana, a ( m , n , k ) gdzie m ≥ m i n ≥ n to wygrana.
- k ≥ 9 to remis: gdy k = 9, a szachownica jest nieskończona, drugi gracz może dobierać za pomocą „strategii parowania”. Remis na nieskończonej planszy oznacza, że gra będzie trwała wiecznie z doskonałą grą. Strategia dobierania w pary polega na podzieleniu wszystkich pól planszy na pary w taki sposób, że grając zawsze parą pól pierwszego gracza, drugi gracz ma pewność, że pierwszy gracz nie zdobędzie k w linii. Strategia parowania na nieskończonej planszy może być zastosowana również na dowolnej skończonej planszy – jeśli strategia wymaga wykonania ruchu poza planszą, drugi gracz wykonuje dowolny ruch wewnątrz planszy.
- k ≥ 8 to remis na nieskończonej szachownicy. Nie jest jasne, czy ta strategia ma zastosowanie do dowolnych skończonych rozmiarów planszy. Nie wiadomo, czy drugi gracz może wymusić remis, gdy k wynosi 6 lub 7 na nieskończonej szachownicy.
- k ≥ 3 i albo k > m , albo k > n to remis, również przy zastosowaniu strategii dobierania w pary w wymiarze nie mniejszym niż k (lub trywialnie niemożliwe do wygrania, jeśli oba są mniejsze)
Konkretne wyniki
- k = 1 i k = 2 to trywialne wygrane, z wyjątkiem (1,1,2) i (2,1,2)
- (3,3,3) jest remisem (patrz Kółko i krzyżyk ), a ( m , n ,3) jest remisem, jeśli m < 3 lub n < 3. ( m , n , 3) jest wygraną, jeśli m ≥ 3 i n ≥ 4 lub m ≥ 4 i n ≥ 3.
- (5,5,4) to remis, co oznacza, że ( m , n ,4) to remis dla m ≤ 5 i n ≤ 5, a (6,5,4) to wygrana, co oznacza, że ( m , n ,4) to wygrana dla m ≥ 6 i n ≥ 5 lub m ≥ 5 i n ≥ 6. ( m ,4,4) to wygrana dla m ≥ 30 (Lustenberger, 1967) i remis dla m ≤ 8. Nie wiadomo, czy ( m ,4,4) jest wygraną czy remisem dla 9 ≤ m ≤ 29.
- Wyszukiwanie komputerowe przeprowadzone przez Wei-Yuan Hsu i Chu-Ling Ko wykazało, że zarówno (7,7,5), jak i (8,8,5) są remisami, co oznacza, że ( m , n , 5) jest remisem dla m ≤ 8 i n ≤ 8. Wyszukiwanie komputerowe przeprowadzone przez L. Victora Allisa wykazało, że (15,15,5) jest wygraną, nawet przy jednej z restrykcyjnych reguł Gomoku .
- (9,6,6) i (7,7,6) to remisy w parach.
Wariant wielowymiarowy
Możliwe jest rozważenie wariantów rozgrywanych na planszy wielowymiarowej zamiast planszy dwuwymiarowej.
W przypadku k -w-rzędzie, gdzie plansza jest n -wymiarowym hipersześcianem ze wszystkimi krawędziami o długości k , Hales i Jewett udowodnili, że gra jest remisowa, jeśli k jest nieparzyste i
- k ≥ 3 n - 1
lub jeśli k jest parzyste i
- k ≥ 2 n +1 − 2.
Przypuszczają , że gra jest remisowa również wtedy, gdy liczba pól jest co najmniej dwukrotnie większa niż liczba linii, co ma miejsce wtedy i tylko wtedy, gdy
- 2 k n ≥ ( k + 2) n .
Zobacz też
| Warianty |  |
|
|---|---|---|
| Pojęcia pokrewne | ||
| Podobne gry | ||