Комбинаторные игры: теория крестиков-ноликов - Википедия - Combinatorial Games: Tic-Tac-Toe Theory

Комбинаторные игры: теория крестиков-ноликов монография по математике крестики-нолики и другие позиционные игры, написано Йожеф Бек. Он был опубликован в 2008 г. Издательство Кембриджского университета как том 114 их серии книг Энциклопедия математики и ее приложений (ISBN  978-0-521-46100-9).

Темы

А позиционная игра представляет собой игру, в которой игроки поочередно завладевают заданным набором элементов с целью формирования выигрышной конфигурации элементов; например, в крестики-нолики и гомоку, элементы - это квадраты сетки, а выигрышные конфигурации - это линии квадратов. Эти примеры симметричны: у обоих игроков одинаковые выигрышные конфигурации. Однако позиционные игры также включают в себя другие возможности, такие как творческие игры в котором один игрок («создатель») пытается сформировать выигрышную конфигурацию, а другой («нарушитель») пытается отложить этот результат на неопределенный срок или до конца игры.^[1] В симметричных позиционных играх можно использовать аргумент о краже стратегии чтобы доказать, что у первого игрока есть преимущество,^[2] но реализовать это преимущество с помощью конструктивной стратегии может быть очень сложно.^[3]

Согласно Теорема Хейлза – Джеветта, в играх, похожих на крестики-нолики, включающих формирование линий на сетке или решетке большего размера, сетки, которые малы по сравнению с их размером, не могут привести к ничьей: как только вся сетка разделена между двумя игроками, один из у них обязательно будет линия. Одним из основных результатов книги является то, что несколько более крупные сетки приводят к «слабому выигрышу», игре, в которой один игрок всегда может форсировать формирование линии (не обязательно до того, как это сделает другой игрок), но размер сетки превышает определенный порог приводит к «сильной ничьей», игре, в которой оба игрока могут помешать другому выстроиться в линию. Более того, порог между слабой победой и сильной ничьей часто можно определить точно. Доказательство этого результата использует комбинацию вероятностный метод, чтобы доказать наличие стратегии для достижения желаемого результата, и дерандомизация, чтобы сделать эти стратегии явными.^[4]

Книга длинная (732 страницы),^[4] состоит из 49 глав и четырех разделов. Часть A рассматривает различие между слабыми выигрышами (игрок может заставить существовать выигрышную конфигурацию) и сильными выигрышами (выигрышную конфигурацию можно заставить существовать до того, как другой игрок получит выигрыш). Он показывает, что для игр создателя-нарушителя над точками на плоскости, в которых игроки пытаются создать конгруэнтную копию некоторого конечного набора точек, производитель всегда имеет слабый выигрыш, но для этого иногда необходимо позволить нарушителю сформировать выигрышная конфигурация ранее. Он также включает обширный анализ симметричных игр с построением линий в стиле крестиков-ноликов и обсуждает Теорема Эрдеша – Селфриджа в соответствии с которым достаточно редкие наборы выигрышных конфигураций приводят к рисованным играм-победителям. В части B книги обсуждается основанный на потенциале метод, с помощью которого была доказана теорема Эрдеша – Селфриджа, и расширяется его до дополнительных примеров, включая те, в которых побеждает производитель. Часть C охватывает более продвинутые методы определения результата позиционной игры и знакомит с более сложными играми этого типа, включая игры с выбором типа, в которых один игрок выбирает два невыбранных элемента, а другой игрок выбирает, какой из них передать каждому игроку. Часть D включает в себя разложение игр и использование приемов из Теория Рамсея для доказательства теорем об играх.^[1] Сборник открытых проблем в этой области представлен в конце книги.^[2]

Аудитория и прием

Это монография, ориентированная не на широкую аудиторию, а на исследователей в этой области. Рецензент Уильям Гасарх пишет, что, хотя эта работа предполагает слабые базовые знания читателей, помимо низкоуровневой комбинаторики и вероятности, «материал все еще труден».^[1] Точно так же рецензент Кайл Берк жалуется, что «многие определения и объяснения неудобно« математически тяжелы »; неопределенные термины из продвинутой математики изобилуют небольшими примерами, где было бы достаточно более простых описаний».^[5]

Большая часть книги посвящена новым исследованиям, а не просто суммированию того, что было известно ранее.^[4][1] Рецензент Алесь Пультр называет эту книгу «наиболее тщательным и полезным изложение предмета (пока недостаточно представленного в литературе) с огромным запасом результатов, связями с другими теориями и интересными открытыми проблемами».^[3] Гасарх соглашается: «Пройдя через это, вы выучите много математики».^[1] Псевдонимный обозреватель Европейское математическое общество добавляет, что книга может стать «вехой в развитии комбинаторная теория игр ".^[2][5]

Рекомендации