В качестве последнего и самого эффектного сюжета из алгоритмической теории
игр — Гексагон.
Ну ещё она имеет название
«Земля — вода».
Игра.
Играют двое.
Они ведут свои армии на поле боя.
Поле боя выглядит так: это классическое шестиугольное замещение...
замощение плоскости,
некоторый квадратный его кусок.
Точнее, ромбический, потому что вот такой вот.
Направление под 45°.
Давайте нарисуем пример.
Игра, как и многие детские игры,
параметризуется некоторым N.
Игра параметризуется параметром N.
Ну, например, игра один на один, когда поле из одного шестиугольника,
совершенно неинтересно, понятно.
Два на два, это когда вот такой ромбик.
Три на три я нарисовал.
Теперь что на самом деле происходит?
Вот отсюда, отсюда, соответственно,
значит, отсюда и отсюда заходят армии.
Армии первого вот здесь и здесь,
ну и условно называется «земля».
Армии второго называются «вода».
Заходят отсюда и отсюда.
Вот здесь всюду вода, вот тут всюду вода, H₂O.
Здесь земля.
Здесь всюду земля.
За эту территорию предстоит война.
Значит, последовательно первый, потом второй, первый,
потом второй и так далее входят своими войсками в какие-то квадратики.
Причем можно перепрыгивать через пустые территории, то есть занять территорию.
Первый землёй занимает вот эту территорию.
Потом второй водой, например, занимает вот эту территорию.
Первый землёй, скажем, занимает вот эту территорию.
Ну пока это немножко похоже на крестики-нолики, но только из-за того,
что здесь три на три, никакой схожести на самом деле нет.
Если бы я нарисовал четыре на четыре, это уже была бы совершенно другая ситуация.
Вот.
Значит, ну давайте, значит, земля, скажем,
земля, земля, вода,
земля, вода, земля.
Первый победил независимо от того, что здесь уже заполнено.
ну давайте дозаполним до конца.
Первый побеждает в том случае, если он свои армии соединил.
Второй побеждает в том случае, если соединил он.
Утверждение: любая финальная позиция,
любое заполнение клеточек землёй, либо водой приводит либо к победе первого,
либо к победе второго, то есть тут не бывает ни одновременной победы их двух,
но и не бывает также ситуации, что никто не победил.
Давайте я вкратце скажу, почему этого не бывает, хотя это должно быть,
в принципе, очевидно.
Значит, почему не может быть одновременной победы?
Ну, по лемме Жордана, на самом деле, в её дискретном аналоге.
Ну ясно, что не может быть кривой отсюда сюда непрерывной, причём ломаной,
и отсюда сюда тоже, которые бы не пересеклись, а пересекаться им нельзя,
потому что иначе соответствующая точка пересечения — ни земля и ни вода.
С другой стороны, если все клетки заполнены, то посмотрите,
как нам понять, кто победил и вообще понять, что кто-то обязательно победил.
Давайте вот этот уровень опустим, а вот этот поднимем.
Вот это вода ведь, правильно?
И это вода.
Давайте поднимем вот этот уровень над этим.
Так вот, если армии соединены, да?
Если армии соединены, значит тут есть река, которая течёт.
Если реки нет, очевидно, что есть дамба, которая преграждает, но если есть дамба,
значит можно пройти по земле отсюда сюда.
То есть это такое чисто физическое доказательство,
я не буду углубляться в какие-то там эти самые казуистические
доказательства по индукции или что-то в этом духе.
Очевидно из физических соображений, что либо вода в водой соединилась,
если есть река, либо нет реки, но тогда есть дамба.
Соответственно, тогда земля с землёй,
то есть каждый исход этой игры — это выигрыш либо первого, либо второго.
Далее.
По принципу Цермело,
на самом деле у одного из двух игроков есть выигрышная стратегия.
То есть либо верно то, что ещё до самого начала игры первый может играть так,
что земля соединится с землёй, либо, если это не так,
то на любой ход первого могут быть какие-то соответствующие ходы второго
в каждый момент времени продуманные в соответствии с ходами первого,
так, что второй может добиться того, что вода соединится с водой.
Либо то, либо то.
Теория игр говорит только это.
Теория игр говорит что-то такое не очень существенное в данной ситуации, что
либо верно, что есть у первого стратегия выигрышная, либо есть, что у второго.
Вроде как мы должны это понимать.
Но следующий шаг будет неожиданным.
Теорема: у первого игрока
существует выигрышная стратегия.
Именно у первого, а не у второго.
Доказательство.
[БЕЗ СЛОВ] Доказательство состоит в копировании поведения игрока.
То есть доказательство проводится от противного.
Предположим, что у второго игрока
есть выигрышная стратегия.
Заодно, когда мы будем обсуждать выигрышные стратегии,
мы немножко получше поймём, что вообще такое стратегия.
Что означает выигрышная стратегия второго игрока, если бы она была?
То есть мы предполагаем, что у второго есть выигрышная стратегия.
Доказательство от противного.
Это значит, что какой бы ход ни сделал первый игрок,
то есть куда бы он ни поставил землю на первом шаге,
у второго есть заготовленный правильный ответ.
Ну вот, скажем, если земля поставлена сюда, надо ставить сюда.
Если бы земля поставлена была вот сюда, например, надо было бы ставить вот сюда.
И так далее.
То есть есть в каждом случае, куда бы первый ни поставил З,
у второго есть заготовленный правильный ответ на этот ход.
Далее.
Более того, после того, как земля ответит во второй раз, есть опять
из всех возможностей, ну здесь два на два, ну понятно, я имею в виду большую доску.
Значит, земля пошла.
У второго есть какой-то выигрышный ответ.
Потом как бы ни пошла земля, опять будет какой-то выигрышный ответ,
нужно будет куда-то поставить это В.
И так далее.
Предположим, что такая ситуация имеет место.
Тогда давайте ходить за первого следующим образом:
мы будем копировать поведение второго.
А именно делаем так.
Ставим землю куда попало.
Первый ход первого игрока.
Ставим землю куда попало.
Поставили, да?
Поставили землю, например, вот сюда.
Ждём, что делает второй.
Второй куда-то ходит.
[СТУК] Стираем вот эту землю мысленно,
исключительно мысленно стираем эту землю и смотрим,
какой ответ, если бы здесь стояла земля, был бы у воды?
Есть два варианта, либо он будет где-то вот здесь,
либо он будет прямо здесь, где сейчас стоит.
В первом случае, ставим туда, где он должен быть,
во втором случае ставим в абсолютно произвольную снова клетку поля.
Дальше опять ждём В.
И опять смотрим, какой из наших ходов был последним,
этот или этот, стираем последний, и применяем
стратегию ответную на вот эти две земли против этой одной воды, то есть меняем
опять землю и воду местами и совершаем ход, который будет оптимальный с точки
зрения вот этой вот якобы существующей стратегии победы у второго на вот эти два.
Опять, если он попал в одно из существующих мест, ставим куда угодно,
а если нет, то туда, куда требуется.
Утверждение, которое вы сами осмыслите, дальше уже тут, так казать,
ничего говорить не надо: понятно, что действуя так, мы выиграем раньше.
То есть, если действительно у второго этот способ поведения был
бы выигрышной стратегией, то первый, копируя его, победил бы раньше,
но это и есть противоречие тому, что у второго есть выигрышная стратегия.
То есть этот сам факт, что первый может использовать копию стратегии второго,
может победить раньше, он является просто противоречием к исходной предпосылке.
А значит у второго нет выигрышной стратегии.
А значит она есть у первого по теореме Цермело.
Поэтому для игры Гексагон на любом поле,
хоть 100 на 100, у первого игрока есть выигрышная стратегия.
Удивительный факт состоит в том, что она неизвестна.
Никто не знает, как играть.
То есть все знают, что первый вот по этим теоремам, согласно этим теоремам первый
игрок выигрывает в эту игру всегда при правильной игре.
Но никто не знает как играть.
То есть эта игра, ну как бы в каком-то смысле типа шахмат.
Единственное, что в отличие от шахмат, мы здесь точно знаем, кто должен победить.
И ничего не можем сделать.
Мы точно знаем, что побеждает первый, но мы не знаем как ему нужно играть.
