Изменения

Городки Города (Geography) - игра, в которой игроки по очереди называют города со всего мира. Каждый город должен начинаться с той буквы, на которую заканчивается предыдущий. Повторы , повторы запрещены. Игра начинается с любого города, и заканчивается, когда игрок проигрывает и не может назвать новый город.

Для визуализации задачи можно построить ориентированный граф, где каждая вершина - имя города, а ребро из А в Б означает, что город Б начинается на ту же букву, на которую заканчивается город А. Ход игрока - переход из текущей вершины в новую, ранее не посещенную, по соответствующему ребру. Проигрывает тот, кто не может сделать ни одного перехода. Ниже приведен пример такого графа Например, граф для игры в городки в штате Мичиган.может выглядеть так:

В обобщенных городках (игре Generalized Geography(Обобщенные города) используется любой мы заменяем граф с городами на некоторый абстрактный ориентированный граф. Игроки по очереди переходят из вершины в вершину, и проигрывает тот, кто не может сделать новый ход.Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. В приведенном ниже примере первый игрок имеет следующую выигрышную стратегию(изначально находится перейти в вершине 1ранее не посещенную вершину): переходит в вершину 2, после чего второй игрок переходит в вершину 4, так как это единственный вариант. Первый игрок переходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора второго игрока, первый переходит в вершину 9, откуда второй игрок никуда не может пойти.

РисунокРассмотрим пример такой игры. Пусть P1 - игрок, который ходит первым, и P2 - игрок, который ходит вторым. Здесь первый игрок обладает следующей выигрышной стратегией(игра начинается с первой вершины): делает ход в вершину 2, после чего второй игрок переходит в вершину 4, так как это единственный вариант. Первый игрок ходит в вершину 5, и второй выбирает между вершинами 3 и 7. Но независимо от выбора второго игрока, первый может перейти в вершину 9, откуда второй игрок никуда не может пойти. [[Файл:Generalized_geography_2.png]]