Комбінаторна теорія ігор

Математики грають у Конане на семінарі з теорії комбінаторних ігор

Комбінаторна теорія ігор — це розділ математики та теоретичної інформатики, який зазвичай вивчає послідовні ігри з повною інформацією.

Історія

Теорія комбінаторних ігор виникла у зв'язку з теорією неупереджених ігор, у якій будь-яка гра, що доступна одному гравцеві, повинна бути доступна й іншому. Однією з таких ігор є Нім, яку можна розгадати повністю. Нім — це неупереджена гра для двох гравців, яка підлягає звичайним умовам гри, де гравець програє, якщо не може рухатись. У 1930-х роках теорема Спраг-Ґранді показала, що всі неупереджені ігри еквівалентні купам у Нім.

У 1960-х роках Елвін Берлекамп, Джон Конвей і Річард Ґай спільно представили теорію партизанської гри, у якій послаблена вимога, щоб гра доступна одному гравцеві, була доступною для обох гравців. Їх результати були опубліковані в книзі «Виграшні шляхи для ваших математичних ігор» у 1982 році. Однак першою роботою, опублікованою на цю тему, була книга Конвея 1976 року «Про числа та ігри», яка представила концепцію сюрреалістичних чисел і узагальнення ігор. Книга «Про числа та ігри» також стала результатом співпраці між Берлекемпом, Конвеєм і Гаєм.

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

Конвей заявив у «Про числа та ігри», що натхнення для теорії партизанських ігор ґрунтувалося на його спостереженні за грою в ендшпілях Ґо, які часто можна розкласти на суми простіших ендшпілів, ізольованих одна від одної в різних частинах дошки.

Приклади

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

Комбінаторні ігри включають до себе відомі ігри, такі як шахи, шашки та ґо, які вважаються нетривіальними, і хрестики-нулики, які вважаються тривіальними в сенсі «простоти рішення». Деякі комбінаторні ігри також можуть мати необмежену ігрову зону, наприклад, нескінченні шахи. В комбінаторної теорії ігор ходи у цих та інших іграх представлені у вигляді дерева гри.

Комбінаторні ігри також включають до себе комбінаторні головоломки для одного гравця, такі як судоку, і автоматичні ігри не для гравців, такі як гра «Життя» (хоча в найсуворішому визначенні для «ігор» потрібно більше одного учасника, таким чином, з'являються позначення «головоломка» та «автомат»).

Порівняння

Може бути корисно розрізнити комбінаторні «математичні ігри», цікаві в першу чергу математикам і вченим для роздумів і вирішення, і комбінаторні «ігри», які цікавлять широке населення як форма розваги та змагання.

Комбінаторна теорія ігор має інший акцент, ніж «традиційна» або «економічна» теорія ігор, яка спочатку була розроблена для вивчення ігор із простою комбінаторною структурою, але з елементами випадковості. По суті, комбінаторна теорія ігор внесла нові методи для аналізу ігрових дерев, наприклад, використовуючи сюрреальні числа, які є підкласом усіх ігор з ідеальною інформацією для двох гравців. Тип ігор, які вивчає теорія комбінаторних ігор, також становить інтерес для штучного інтелекту, зокрема для автоматизованого планування та диспетчеризації. У комбінаторній теорії ігор менше уваги приділялося вдосконаленню практичних алгоритмів пошуку (таких як відсічення альфа-бета), але більше уваги приділялося описовим теоретичним результатам (таким як вимірювання складності гри або докази оптимального рішення).