Уже известно, что спастись от смерти на виселице можно с помощью жижи и цацки. Давайте попробуем узнать, как лучше играть в другую игру — в города.

Правила можно прочитать в википедии: игроки по очереди называют города, каждый следующий начинается с последней буквы предыдущего. Там же предлагают стратегию:

По не до конца выясненным лингвистическим причинам многие города мира начинаются и/или заканчиваются на букву «А», в связи с чем можно предполагать, что выиграет игрок, знающий больше городов на эту букву (Анапа, Алушта, Аделаида и т. д.).

Для проверки этого утверждения потребуется список городов мира и немного кода на питоне.

Получение списка городов

Города — такая игра, в которую невозможно играть, не зная названий городов. Поэтому для анализа требуется словарь с городами на русском языке.

В интернете есть базы, которые в основном предназначены для использования на сайтах для указания города при регистрации. Но все они не понравились мне. Некоторые из них, обещая список полностью на русском языке, внезапно переходили на родной язык для городов из других стран. Для сайта это нормально, но играть в города так нельзя. А в остальных базах городов было слишком мало. Для проверки полноты я придумал «тест Аддис-Абебы», и ни одна из них его не прошла.

Пришлось вытаскивать названия из википедии. Там последней проблемы нет, и даже наоборот: уже на первой странице категории можно увидеть XVI Партсъезд и 25 км Железной Дороги Мончегорск-Оленья, а где-то дальше есть больше всего впечатливший меня Посёлок Абонентного Ящика 001. Но это не так страшно, удалить всегда можно.

И сразу же код.

import mwclient

def get_page_names():
    site = mwclient.Site('ru.wikipedia.org')
    category = site.Pages[u'Категория:Населённые пункты по алфавиту']
    return (page.name for page in category)

Для получения списка страниц категории будем обращаться к апи википедии, используя библиотеку mwclient.

def is_letter(c):
    return u'а' <= c.lower() <= u'я'


def starts_and_ends_with_letter(name):
    first = name[0]
    last = name[-1]
    return is_letter(first) and is_letter(last)

Так будем выбрасывать названия, которые начинаются или заканчиваются не на букву.

def remove_braces(name):
    return name.split('(')[0].strip()

Хорошее название для города придумать трудно, поэтому они иногда повторяются. В таких случаях в википедии пишут в скобках пояснение, о каком городе эта статья. Нас это не интересует, поэтому скобки и всё, что после них, будем обрезать.

def get_cities():
    used_cities = set()
    for name in get_page_names():
        city = remove_braces(name)
        if starts_and_ends_with_letter(city) and city not in used_cities:
            used_cities.add(city)
            yield city

Получим список городов, выбрасывая повторяющиеся и те, которые нам не подходят.

import codecs

with codecs.open('cities.txt', 'w', 'utf8') as f:
    for city in get_cities():
        f.write(city + '\n')

Этот список сохраним в файл.

Полностью скрипт получился таким.

Извлеченный словарь содержит 130 тысяч городов. В нем еще мог остаться какой-то единичный мусор, который общую картину менять не должен.

Анализ

В отличие от виселицы, где можно было полностью перебирать словарь, здесь так сделать не получится. Есть 130 тысяч вариантов первого хода, потом в среднем 4 тысячи вариантов второго, потом еще 4 тысячи третьего... Все эти числа надо перемножить, и в итоге получится совершенно астрономическое количество вариантов. Но самое обидное, что если даже получится построить оптимальные стратегии для всех игроков, они окажутся бесполезными для игры с другим словарем. А словари вообще у каждого человека разные. Поэтому самое полезное, что можно сделать, — вычислить букву, на которую стоит обратить особое внимание (как в википедии).

Начнем с упрощения модели. В названиях городов для нас значимыми являются только первая и последняя буквы. Так список из 130 тысяч городов уменьшается до маленького ориентированного графа. Вершинами его будут буквы, а ребро из x в y будет иметь вес, равный количеству названий, начинающихся с x и заканчивающимися на y.

Может быть, в графе уже можно решать полным перебором? Там же всего 30 вариантов начала, 30 вариантов второго хода, 30 вариантов третьего, четвертого, пятого, шестого... Нет, тоже многовато.

Просто сравнить сумму весов исходящих и входящих ребер? Если на какую-то букву начинается мало городов, а заканчивается ею много, то ее можно хорошо использовать против соперника. Но реальность игры в города сложнее: ведь надо учитывать, из каких вершин надо попадать в эту вершину, как попадать в них и так далее. Поэтому используем более хитрый алгоритм.

У каждой буквы будет рейтинг, который зависит от ее связей. Входящие ребра будут передавать часть рейтинга от вершины, из который они выходят, и часть этого рейтинга будет уходить дальше через исходящие ребра. Вычисляется такой рейтинг с помощью алгоритма PageRank, про который я однажды уже рассказывал.

Перейдем к коду.

def get_cities():
    with open('cities.txt') as f:
        for line in f:
            yield line.strip().decode('utf8').lower()

Достаем список городов из файла.

def get_edge(city):
    return city[0], city[-1]

Определяем функцию для получения из города ребра (то есть начальной и конечной вершин).

from collections import Counter

def get_weighted_edges(cities):
    counter = Counter(get_edge(city) for city in cities)
    return ((a, b, float(weight)) for (a, b), weight in counter.iteritems())

И еще одну, которая получает список городов и возвращает ребра в виде списка кортежей из начальной вершины, конечной вершины и веса. Здесь используется удобная способность контейнера Counter сразу же пересчитывать всё, что передается в него при инициализации.

import networkx as nx

def get_graph():
    cities = get_cities()
    edges = get_weighted_edges(cities)
    g = nx.DiGraph()
    g.add_weighted_edges_from(edges)
    return g

Создаем ориентированный граф из этих ребер с использованием уже известной библиотеки networkx.

def add_final_vertices(g):
    g.add_weighted_edges_from((v, v + u'_finish', 1.0) for v in g.nodes())

Пейджранки вершин будут показывать, насколько активно буква используется в процессе обычной игры. Чтобы оценить шансы каждой буквы завершить игру, создадим еще по одной вершине для каждой буквы, в которую будет идти ребро только из нее.

def evaluate_letters():
    g = get_graph()
    add_final_vertices(g)
    pr = nx.pagerank(g)

    for a, b in sorted(pr.items(), key=lambda x: x[1]):
        if a[1:] == '_finish':
            print a[0], b

Посчитаем пейджранки и выведем результат. Результат получился таким:

б 0.0047940481766
п 0.00479409201359
м 0.00479468124255
л 0.00479518712277
в 0.00479519556089
к 0.00479524573281
с 0.00479536849038
з 0.00479577419979
э 0.00479586689975
г 0.00479595151747
ч 0.00479598047734
д 0.00479609383531
т 0.00479638754244
ф 0.00479694481314
ш 0.00479694980713
х 0.0047970864409
ж 0.00479821870855
р 0.00479830237913
у 0.00480167551917
н 0.00480336443514
ю 0.00480600994751
ц 0.00480935947044
а 0.00480975757728
и 0.00481506621565
щ 0.00481612997918
о 0.00481980791183
я 0.00482062139306
е 0.00486013871912
й 0.00491924389476
ы 0.00593319978398
ь 0.0278309795176

Ой. Будем считать, что алгоритм прошел проверку на разумность: победил мягкий знак, на который некоторые города заканчиваются, но ни один не начинается. Поправим код, чтобы обрезать мягкий знак на конце слов. (А заодно и ы. Ыспарты и еще нескольких городов не достаточно, чтобы можно было нормально играть с ней.)

def get_edge(city):
    return city[0], city.strip(u'ъыь')[-1]


def get_weighted_edges(cities):
    counter = Counter(get_edge(city) for city in cities if not city.startswith(u'ы'))
    return [(a, b, float(weight)) for (a, b), weight in counter.iteritems()]

Полностью код выглядит так, и он выдал такой результат:

б 0.00450930556033
п 0.00450944258223
м 0.00451008313833
к 0.00451058888306
в 0.00451067983318
с 0.00451093647496
э 0.00451113552385
з 0.00451128722349
ч 0.00451135271873
г 0.00451146651546
д 0.0045119188442
х 0.00451228788221
т 0.00451237835021
ф 0.00451246102843
ш 0.0045125190597
л 0.00451323505599
ж 0.00451361765873
р 0.00451425487076
у 0.00451717313258
н 0.00451985073145
ю 0.00452106046281
а 0.0045266942414
щ 0.00453027578976
и 0.00453275391185
ц 0.00453579724983
о 0.00453796965795
я 0.00453843101065
е 0.00458125968474
й 0.00463979500792

Самой востребованной буквой оказалась й. На нее в использованном словаре заканчиваются 4093 слова, а начинаются с нее всего 187 слов.

Проблема длиннейшего сиритори

В ходе анализа я пытался найти чужие решения подобной задачи. За рубежом эта игра называется Geography и является частным случаем игры Word Chain. Но результаты нашлись только для японского названия — сиритори (не путать с упоротым авангардистом).

От него получила имя задача, которая называется проблемой длиннейшего сиритори: построить из заданного словаря как можно большую цепочку в соответствии с правилами игры. Есть несколько японских статей об этой задаче. Вот эта, например. Ничего, кроме абстракта не понятно, но по картинкам видно, что у них тоже какие-то графы.

К счастью, есть статья Даики Каваками (надеюсь, правильно транскрибировал) на английском, которая написана позднее и учитывает накопленный опыт по этому вопросу. Там предлагается интерактивный алгоритм, способный решить проблему длиннейшего сиритори.

Даики Каваками представляет словарь в виде такого же ориентированного графа, как у нас, а игру — как перемещение между вершинами с уменьшением веса использованного ребра на единицу. Решение задачи находится в процессе игры с использованием алгоритмов, называемых итераторами, которые оценивают текущее состояние и выбирают следующую вершину. В статье приводится три итератора:

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

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

Полученная с его помощью цепочка содержала 50% словаря, тогда как более ранние методы могли покрыть словарь только на 46%. (Из этого почему-то сделали вывод, что проблему длиннейшего сиритори теперь можно считать решенной. Не очень понял, почему результат нельзя улучшить еще, заглядывая вперед на два шага, например, ну да ладно.)

Этот алгоритм предлагает самый альтруистичный вариант игры: ходить так, чтобы у соперника был максимальный выбор ходов. Нас же интересует противоположная стратегия, которую можно получить из этой. Начнем с реализации исходного алгоритма.

def get_out_weight(graph, vertex):
    return sum(d['weight'] for u, v, d in graph.out_edges(vertex, data=True))

Эта функция вычисляет вес всех ребер, исходящих из вершины.

def choose_next_vertex(graph, vertex):
    possible_moves = [n for n in graph.neighbors(vertex)
                        if graph[vertex][n]['weight'] > 0]
    if not possible_moves:
        return None
    scores = max((get_out_weight(graph, n), n) for n in possible_moves)
    return scores[1]

Эта функция выбирает следующую букву, используя алгоритм второго итератора.

def run_shiritori_algorithm():
    g = get_graph()
    current_letter = choice(g.nodes())
    i = 0
    while True:
        next_letter = choose_next_vertex(g, current_letter)
        if not next_letter:
            print current_letter, i
            break
        g[current_letter][next_letter]['weight'] -= 1
        i += 1
        current_letter = next_letter

И вот так происходит само моделирование: переходим от буквы к букве, пока не окажемся в тупике. Начальная буква выбирается случайно.

Независимо от начальной буквы, при каждом запуске у меня всё всегда заканчивалось на букве е с цепочкой из примерно 49 тысяч слов. Покрытие 38%.

Теперь изменим стратегию так, чтобы выбиралась вершина, из которой ходов меньше всего. Для этого нужно всего лишь заменить max на min в функции choose_next_vertex. Полностью код можно посмотреть здесь.

Тогда игра будет заканчиваться после 372–373 городов. В букве й, конечно. Судя по тому, что длина цепочки в два раза больше количества городов, начинающихся с й (чуть меньше за счет Йенбая и Йосвайняя), вся игра представляла собой танцы вокруг этой буквы. То есть ничего примечательного в таком результате нет. Интересно, могут ли быть графы, в которых проблема кратчайшего сиритори решается не так скучно.

Итог

Как и википедия, я не могу объяснить лингвистические причины, из-за которых названий на букву й так мало, кроме того, что ее вообще считают ущербной. Зато городов, которые заканчиваются ею, достаточно много благодаря множеству топонимов-прилагательных. Список из четырех тысяч названий, грепнутый из использованного словаря, я выложил сюда. Выберите оттуда штук двести городов, которые вам понравятся, и запомните до следующего раза, когда будете играть в города. Больше вам, скорее всего, не понадобится.