Виграшна стратегія (математика)

Стратегія успіху (або виграшна стратегія) - в теорії ігор план гри, реалізація якого дозволяє гравцю одержати перемогу незалежно від дій суперника. Найбільш поширеними є симетричні й парні стратегії, а також стратегії, які будуються на основі аналізу ігрових позицій.

Аксіоми виграшу ред.

Складаючи свою виграшну стратегію, слід не забувати про ряд фундаментальних тверджень:

Якщо ваш хід виграшний то супротивник завжди зробить програшний хід

якщо ваш хід програшний то супротивник може походити або виграшним ходом або програшним

Симетрична стратегія ред.

Симетричними є стратегії, розроблені на основі симетрії стартової позиції. Аналіз розв’язувань таких задач показує, що в іграх із симетричною стартовою позицією здебільшого виграє той, хто не порушує її симетрію, а порушену суперником симетрію стартової чи ігрової позиції може поновити.

Приклад 1. Двоє гравців по черзі вписують у прямокутну таблицю розміром 1993x1994 (1994 стовпці) числа 0 або 1. Потім знаходять суми чисел кожного рядка й кожного стовпчика. Нехай $S_{c}$ – найбільша сума по стовпцях, а $S_{p}$ – по рядках. Якщо $S_{c}<S_{p}$ , то виграє перший. В іншому випадку виграє другий. Хто виграє за правильної гри?

Розв’язання. Задана таблиця симетрична відносно прямої, яка ділить її на дві однакові частини розміром 997x1993. Гравець, який починає гру, своїм першим ходом порушує симетрію. Другий гравець першим ходом може поновити її, але в обрану клітинку він повинен вписати число, відмінне від числа, що вписав перший гравець: якщо перший вписав 0,то другому треба вписати 1, і навпаки. Якщо другий до кінця гри буде діяти так, то сума чисел у кожному рядку таблиці складе 997, а тому $S_{p}=997$ . Оскільки сума чисел у кожних двох стовпцях, о симетричні відносно осі симетрії, завжди дорівнює 1993, то в одому з них сума буде не менша ніж 997, тому $S_{c}\geqslant S_{p}$ , тобто виграє другий гравець.

Приклад 2. Двоє гравців у виразі

        $a_{1}\sin x+a_{2}\cos 2x+a_{3}\sin 3x+a_{4}\cos 4x+\ldots +a_{1996}\cos 1996x+a_{1997}\sin 1997x$

по черзі вибирають ще не обрані $a_{i}$ та замінюють їх будь-якими дійсними числами. Коли всі $a_{i}$ замінені, утвориться функція $\gamma (x)$ . Якщо рівняння виду $\gamma (x)=0$ має корінь в інтервалі $\left(-{\frac {\pi }{2}};{\frac {\pi }{2}}\right)$ , то виграє той, хто починав гру. В іншому разі виграє його суперник. Хто з гравців може забезпечити собі виграш?

Розв’язання. Симетрія виразу відносно 999-го члена підказує, що повинен виграти гравець, котрий починає гру; симетрія інтервала відносно 0 наштовхує на думку, що коренем має бути це число. Якщо підставити $x=0$ у вираз, то одержимо суму:

                          $a_{2}+a_{4}+\ldots +a_{998}+a_{1000}+\ldots +a_{1996}$

Для того щоб 0 був коренем рівняння $\gamma (x)=0$ , досить, щоб здобута сума дорівнювала нулю. Цього легко досягнути, зробивши доданки, рівновіддалені від кінців суми, протилежними. Звідси випливає стратегія успіху гравця, який починає гру:

— першим ходом треба замінити

a_{999}

будь-яким числом;

— відповідати за ходи суперника ходами, симетричними відносно 999-го члена виразу;

— записувати коефіцієнти, протилежні коефіцієнтам, які ставить другий гравець.

Симетрія ігрових позицій забезпечує існування множини пар «прообраз – образ». У розглянутих задачах такими є пари клітинок, пари чисел виразу тощо. Гравець, дбаючи про симетрію ігровою позиції, повинен зберігати пари «прообраз-образ», давати можливість супернику під час виконання ходу використати «прообраз» і тим самим гарантувати можливість виконання свого наступного ходу, використовуючи симетричний «образ».

Парна стратегія ред.

Окрім симетричної стратегії існує ще одна, менш вживана, парна виграшна стратегія. Іноді пари, подібні симетричним парам типу «прообраз – образ», можна використовувати і в задачах, стартова позиція яких не є симетричною. Виграшну стратегію, яка передбачає використання пар, називають парною стратегією. Зазначимо, що конкретних порад щодо вибору «пар» не існує. Кожного разу виділення «пар» здійснюється, виходячи з умови конкретної задачі.

Приклад 1. Двоє гравців по черзі ставлять на клітинки шахівниці розміром 25×25 фішки – один білого, а другий чорного кольорів. Кожна нова фішка ставиться на вільну клітинку. Забороняється лише ставити фішку на таку клітинку, для якої на всіх сусідніх із нею уже стоять фішки цього кольору (сусідніми вважаються ті клітинки, які мають спільну сторону). Програє той, хто не зможе зробити свій черговий хід. Хто виграє за правильної гри – той, хто починає гру чи його суперник?

Рис.1

Розв’язання. Зважаючи на симетрію стартової позиції гри, перше, що спадає на думку гравцеві, який починає гру – використати симетричну стратегію: за першим ходом поставити свою фішку на клітинку, яка міститься на перетині діагоналей шахівниці, а далі відповідати на ходи суперника симетричними ходами. Але за такої гри другий гравець може і виграти, бо на клітинку X він може поставити свою фішку, а першому гравцеві ставити білу фішку на клітинку Y не можна. Однак перший гравець виграє в цій грі, якщо скористається парною стартегією. Для цього йому досить поставити першим своїм ходом білу фішку на будь-яку клітинку дошки, а всі інші фішки об’єднати в «пари», утворивши прямокутники розміром 1×2. Якщо, відповідаючи на хід суперника, гравець, який почав гру, буде ставити свою фішку на клітинку прямокутника, куди щойно поставив фішку його суперник, то він обов’язково виграє.

Приклад 2. Двоє грають у таку гру. Спочатку перший гравець ставить коня на довільну клітинку шахівниці 8×8, потім другий гравець робить хід цим конем, потім хід робить перший і т.д. При цьому забороняється ставити коня на клітинку, де він уже побував раніше. Програє той, хто не може зробити черговий хід. Хто виграє за правильної гри?

Розв’язання. «Пари» клітинок, які забезпечать другому гравцеві перемогу, містяться у прямокутниках розміром 2×4. Тому після першого ходу гравця, який почав гру, другий гравець подумки поділяє шахівницю на вісім прямокутників зазначених розмірів і виконує свій хід, залишаючи коня у виділеному прямокутнику. Відповідаючи у такий спосіб на кожний хід суперника, другий гравець досягне перемоги.

Використання парної виграшної стратегії є більш трудоємким процесом, і через це вона не набула такого широкого застосування в ігрових задачах, як симетрична стратегія. Проте, вона є вартою розгляду, оскільки у деяких типах задач,без неї складно досягти успіху.

Ігрові задачі з різними стратегіями ред.

Після застосування симетричної та парної стратегій успіху під час інтерактивних «настільних» ігор на двох, логічно було б навести ще декілька прикладів задач, які не підходять під даний макет. Це вкотре дозволить продемонструвати, що вибір стратегії гри залежить тільки від інтуїції, вмінь та складу мислення гравця, а різні типи стратегій, як-от розглянуті вище, тільки дозволять йому швидше і оперативніше класифікувати тип гри і на цій основі будувати свої подальші дії для перемоги.

Приклад 1. На шаховій дошці розміром 1000×1000 стоїть один білий король та 500 чорних тур. Гравці роблять хід по черзі (тобто білі – єдиною фігурою – королем, а чорні – однією зі своїх тур). Доведіть, що незалежно від того, як ходять чорні, король завжди може стати під удар однієї з тур. (Зрозуміло, що в даному випадку золоте правило гри в шахи не ставати «під шах» втрачає свою актуальність).

Доведення. Виграшна стратегія для короля в цьому разі полягає в тому, щоб добратися до одного з кутів, а після цього по діагоналі рухатися до протилежного кута. При такому розвитку подій легко довести, що король все одно попаде під удар однієї з тур, проте слід зробити невелике уточнення: якщо під час руху по діагоналі на шляху короля стане одна з тур, то йому не слід її збивати. Треба стати у сусіднє поле з нею, бо, як відомо, тура ніколи не б’є по діагоналі. Тепер безпосередньо доведемо істинність припущення, висунутого в умові задачі. Поки король йтиме по діагоналі з одного кута дошки в другий він зробить 999 ходів, а суперник – 998. Отже, принаймні 1 тура зробить всього лиш 1 хід, а це означає, що вона зміститься по горизонталі або ж по вертикалі, яку король перетнув на своєму шляху. При цьому дана тура весь час контролювала дану вертикаль (або ж діагональ), що стверджує правдивість припущення.

Приклад 2. Двоє гравців грають на нескінченному папері в клітинку гру «хрестики-нулики». При цьому перший гравець може за хід ставити 2 хрестики, а другий – тільки 1 нулик. Чи правда, що у будь-якому випадку через деякий час виявиться, що у 100 клітинках по одній вертикалі чи горизонталі поряд стоятимуть хрестики?

Розв’язання. Слід зауважити, що дана гра належить до розряду нескінченних. Про можливість виграшу 2-го гравця навіть не говориться, припускається тільки, що він нескінченно довго зможе оборонятись, а це є неправдивою здогадкою по відношенню о 1-го гравця, який дотримуючись певної стратегії зможе забезпечити собі перемогу. Отож, уявивши $N$ рамок розміром 100×1 у просторі 1-й гравець за $N/2$ ходів заповнить їх хрестиками в той час як за стільки ж ходів 2-й заповнить лиш $N/2$ рамок. Половина рамок залишиться незаповненими. Далі 1-й гравець заповнює дану половину рамок хрестиками за $N/4$ ходів, і за цю ж кількість ходів тільки $N/4$ рамок заповнюються хрестиками. І так далі, припустивши, що $N=2^{100}$ , можна стверджувати, що за останнім ходом залишиться принаймні одна рамка заданих розмірів, ущент заповнена одними хрестиками.

Джерела ред.

Вороний О.М. Готуємось до олімпіад з математики. — Харків : Вид.група "Основа", 2009. — 255 с.

Шень А. Игры и стратегии с точки зрения математики. — 2-е изд. — Москва : МЦНМО, 2008. — С. 40.

Мак-Кинси Дж. Введение в теорию игр. — 1-е изд. — Москва : ГИФМЛ, 1960. — 420 с.

Мазалов В.В. Математическая теория игр и приложения. — Санкт-Петербург - Москва - Краснодар : Лань, 2010. — 446 с. — ISBN 978-5-8114-1025-5.