Разгадывание вражеских боевых планов, по одному пикселю за раз
В эти выходные состоится восьмая и последняя Битва за Страну Загадочников, организованная FiveThirtyEight. Первый был проведен еще в 2017 году. Мне он нравится, потому что я выиграл второй и третий, за что получил вызов за 18-е место в четвертом. Это был мой высший балл, хотя я и занял 10-е место в шестом заезде. Естественно, я ищу любое преимущество, которое я могу получить в восьмом раунде, и это история о том, как моя неустанная погоня за таким преимуществом привела меня к преобразованию значений RGB в огромное количество стратегической информации.
Позволю Заку Висснеру-Гроссу, руководящему соревнованием, объяснить правила:
В далекой, истерзанной войной стране есть 10 замков. Есть два военачальника: вы и ваш заклятый враг. Каждый замок имеет свою стратегическую ценность для будущего завоевателя. В частности, замки приносят 1, 2, 3, …, 9 и 10 победных очков. У вас и у вашего врага есть по 100 солдат, которых можно распределить любым способом, чтобы они сражались в любом из 10 замков.
Тот, кто отправляет больше солдат в данный замок, завоевывает этот замок и получает свои победные очки. Если каждый из вас отправляет одинаковое количество войск, вы делите очки. Вы не знаете, какое распределение сил выбрал ваш противник, пока не начнутся бои. Кто наберет больше очков, тот и выиграет войну.
Те, кто знаком с теорией игр, могут признать это игрой Полковника Блотто. Вы отправляете стратегию, список из 10 целых чисел, сумма которых равна 100, а затем ваша стратегия сражается со всеми стратегиями, представленными другими людьми. Вот некоторые отдельные результаты предыдущего прогона, чтобы дать вам представление (они появятся снова).
При принятии решения о том, какую стратегию представить, очень полезной является информация о том, какие стратегии были отправлены ранее. Стратегии для первых пяти раундов есть на GitHub, но не для шестого или седьмого раундов. Для наших целей важны только раунды 1–4 и 7; В 5-м раунде было 13 замков, поэтому эти стратегии не переносятся, а в 6-м раунде разрешались уничтоженные солдаты — то есть вы могли назначать своих солдат юнитами по 0,1 — так что эти стратегии тоже не помогут.
Это означает, что нам не хватает только одного раунда данных, но это самые свежие данные из раунда 7. У нас есть 10 лучших стратегий из этого раунда выше (вместе со стратегиями, занявшими 112-е и 266-е места, потому что они показали хорошие результаты в нокаут-рейтинге). турнир проходил в этом раунде). Единственное, что у нас есть, — это опубликованная Заком тепловая карта: Как и в предыдущие годы, я создал тепловую карту (с более темным оранжевым, представляющим больше фаланг) со всеми 432 стратегиями, организованными по тому, насколько хорошо каждый подход показал себя в этом предварительный этап.
Моя цель — реконструировать эту тепловую карту, чтобы восстановить стратегии.
Вопрос 1: Какие пиксели мы должны читать?
Сразу же мы видим, что это представление будет враждебным. То, что я представляю, когда-то аккуратное и чистое представление данных было искажено, чтобы соответствовать любым размерам, которые FiveThirtyEight настаивает на своей графике. Замки, по крайней мере, не так уж плохи. При средней ширине 52,3 пикселя места для работы предостаточно. Стратегии были сжаты или сплющены в среднем до 2,85 пикселя по вертикали. Эти нецелочисленные размеры будут проблемой, и будет непросто взять образцы из каждой стратегии ровно один раз.
При увеличении правого верхнего угла изображения также можно заметить ужасающую (по крайней мере, для наших целей) интерполяцию:
Каким-то образом мы должны избегать чтения интерполированных строк как их собственных стратегий. Тем не менее, кажется, что каждая из 10 лучших стратегий получает две строки пикселей и отделена друг от друга одной интерполированной строкой. На рисунке ниже справа я включил масштабированную часть тепловой карты, которая должна соответствовать первой десятке.
Поковырявшись в GIMP, я вижу, что кодирование Top 10, по крайней мере, довольно приятное. Каждая из этих стратегий представлена двумя вертикальными рядами пикселей, при этом эти двухпиксельные полосы отделены друг от друга одной интерполированной строкой. Мы можем сэмплировать замки, начиная со значения x 110 и увеличивая его с шагом 53; эти сегменты достаточно широки, чтобы иметь много места для маневра.
import numpy as np
from PIL import Image
image = Image.open("heatmap.png")
image = image.convert("RGB")
data = np.array(image)
# Top 10 strategies, RGB values
data_top_10 = data[69:97:3, 110:598:53]
# Define the ground truth matrix
ground_truth_mat = np.matrix([
[ 1, 3, 8, 13, 11, 24, 5, 28, 3, 4],
[ 0, 0, 7, 11, 12, 23, 3, 4, 6, 34],
[ 0, 0, 8, 11, 13, 22, 3, 4, 5, 34],
[ 0, 1, 8, 11, 16, 21, 2, 4, 4, 33],
[ 3, 5, 6, 7, 12, 1, 27, 31, 4, 4],
[ 0, 6, 7, 11, 12, 22, 3, 26, 6, 7],
[ 0, 1, 11, 0, 1, 1, 23, 27, 1, 35],
[ 1, 1, 2, 14, 3, 3, 22, 24, 26, 4],
[ 2, 1, 8, 1, 1, 1, 25, 27, 1, 33],
[ 0, 0, 8, 12, 14, 22, 3, 3, 6, 32]])
Мы еще не придумали, что делать ниже Топ-10, и я вернусь к этому ближе к концу, а пока давайте двигаться дальше.
Вопрос 2: Что даже измерять?
Можно сделать много ошибок, отвечая на этот вопрос, и я, конечно, сделал. Сначала я попытался измерить расстояние между цветами пикселей и оранжевым цветом. Но какой оранжевый? Затем я попытался найти «лучший» апельсин для этого и обнаружил, что даже «лучший» апельсин все еще не очень хорошо соответствует данным.
Моя первая хорошая идея заключалась в том, что вместо того, чтобы измерять, насколько цвета близки к оранжевому, я должен измерить, насколько они далеки от серого. В первой десятке есть несколько нулей, поэтому значения RGB соответствующих пикселей послужат хорошей привязкой. К счастью, эти значения RGB идентичны (229, 229, 299).
Используя этот цвет в качестве привязки, мы заменим все наши цветовые данные их расстоянием от этого цвета.
gray_rgb = np.array([229, 229, 229]) dist_top_10 = np.apply_along_axis(lambda x: np.linalg.norm(x - gray_rgb), axis=-1, arr=data_top_10)
Вопрос 3: Как перевести на счет солдат?
Вместо того, чтобы совершить ошибку, которую я изначально сделал, давайте проявим смекалку и начнем с графика, сравнивая расстояние до серого пикселей (из 10 лучших стратегий) с их истинными значениями на диаграмме Зака.
import matplotlib.pyplot as plt
# Flatten the distance and ground_truth_mat arrays for plotting
dist_top_10_flat = dist_top_10.flatten()
ground_truth_flat = ground_truth_mat.A1
# Create a scatter plot
plt.scatter(dist_top_10_flat, ground_truth_flat)
plt.xlabel('distance from gray')
plt.ylabel('ground truth')
plt.show()
Лучшее, что мы могли ожидать, это прямая линия. Нам почти повезло.
Этот график показывает, что все большие (31 и выше, по крайней мере) значения истинности земли были уменьшены, но кроме этого, расстояние до серого имеет хорошую линейную зависимость от фактического количества солдат. Это имеет смысл. Если бы Зак не сократил эти значения до того, как сгенерировал тепловую карту, в ней доминировал бы чувак, который поместил 100 солдат в замок 1. Забавный факт: это своего рода выигрыш.
Теперь мы исключаем эти большие наземные значения истинности и находим связь между расстоянием от серого и количеством солдат для значений, где эта связь является линейной.
# Filter the arrays to exclude points where the fit won't work mask = ground_truth_flat <= 30 dist_top_10_filtered = dist_top_10_flat[mask] ground_truth_filtered = ground_truth_flat[mask] # Reshape data for lstsq A = dist_top_10_filtered.reshape(-1, 1) b = ground_truth_filtered # lstsq returns several values, we only care about the first one slope, residuals, rank, s = np.linalg.lstsq(A, b, rcond=None)
Мы получаем наклон 0,15679897 и остатки всего 0,14377823. Мы знали, что подгонка будет хорошей, и остатки говорят нам, что она хорошая, но давайте все равно построим ее, чтобы насладиться ее точностью.
line_y = slope * dist_top_10_flat
plt.plot(dist_top_10_flat, line_y, color='red')
plt.scatter(dist_top_10_flat, ground_truth_flat)
plt.xlabel('distance from gray')
plt.ylabel('ground truth')
plt.show()
Вопрос 4: Как восстановить большие значения?
Линейное соответствие между расстоянием до серого и количеством солдат прекрасно работает, пока мы не достигнем цвета RGB (222, 120, 72) на расстоянии 191,32778707 от серого. Этот цвет представляет все значения от 30 и выше.
Если в стратегии есть уникальная запись не менее 30, мы можем увеличить эту запись, чтобы учесть, сколько солдат пропало после округления значений до целых. Но если в стратегии есть несколько входов не менее 30, мы ничего не можем сделать. Я предпочту разделить пропавших без вести солдат поровну между этими позициями, но я не восстанавливаю эти стратегии точно.
def recover_strategy(dist_vec):
# Given a vector of distances-to-gray, recover the strategy.
estimated_values = [slope[0] * dist for dist in dist_vec]
strategy = np.rint(estimated_values).astype(int).tolist()
# What will cut-off values look like?
max_rgb = np.array([222, 120, 72])
max_dist = np.linalg.norm(max_rgb - gray_rgb)
max_rounded = np.rint(slope[0] * max_dist).astype(int)
# Get the indices of possibly-cut-off values.
max_indices = np.where(strategy == max_rounded)[0]
# Deal with extra soldiers if any.
extra = 100 - sum(strategy)
if extra:
# There are missing soldiers. Do the best we can.
if len(max_indices) > 1:
print(f"Missing soldiers and multiple max entries, so have to guess.")
elif not len(max_indices):
print(f"Missing soldiers but no max entries, so not fixing.")
if len(max_indices):
each_extra = extra // len(max_indices)
remainder = extra % len(max_indices)
# Distribute the extra soldiers
for i in max_indices:
strategy[i] += each_extra
for i in range(remainder):
strategy[max_indices[i]] += 1
return strategy
Чтобы проверить это, мы можем применить его к Топ-10.
>>> recovered_top_10 = np.apply_along_axis(recover_strategy, axis=1, arr=dist_top_10)
>>> recovered_top_10 - ground_truth_mat
matrix([[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0]])
Мы отлично восстановили первую десятку. На дно 422!
Вопрос 5: Какие строки включить?
Стратегии получают в среднем 2,85 пикселя по вертикали, и они (иногда) разделены рядами интерполированных пикселей. Мы не можем надеяться на то, что будем брать пробы через равные промежутки времени, даже несмотря на то, что нам повезло попасть в Топ-10.
Во-первых, чтобы со всем было проще работать, я конвертирую в расстояний к серому, а затем проверю, сколько уникальных строк у нас есть.
# Convert to distance-to-gray vectors. dist_data = np.apply_along_axis(lambda x: np.linalg.norm(x - gray_rgb), axis=-1, arr=data[69:1302:1, 110:598:53]) # Number of unique rows. unique_rows = set(map(tuple, dist_data)) len(unique_rows) # Should return 732.
Выполнение этого кода показывает, что у нас есть 732 уникальные строки, что намного больше, чем 432 стратегии, которые мы пытаемся восстановить.
По крайней мере, из данных Top 10, которые мы рассмотрели, кажется, что по крайней мере два ряда пикселей представляют каждую стратегию. С другой стороны, интерполированные ряды пикселей не должны быть похожи ни на один ряд, к которому они примыкают. Мы начинаем с фильтрации предполагаемых интерполированных строк и проверки того, сколько уникальных строк осталось.
# Zero out all rows that are not equal to an adjacent row.
zero_vec = np.zeros_like(dist_data[0])
filtered_dist_data = dist_data.copy()
for i in range(1, dist_data.shape[0] - 1):
if not np.array_equal(dist_data[i], dist_data[i - 1]) and not np.array_equal(dist_data[i], dist_data[i + 1]):
filtered_dist_data[i] = zero_vec
unique_rows = set(map(tuple, filtered_dist_data))
len(unique_rows) # Should return 419.
Теперь он говорит, что у нас есть только 419 уникальных строк. Один — это нулевой вектор, поэтому у нас есть 418 уникальных стратегий. Это должны быть все уникальные стратегии в наборе данных, хотя некоторые из них были отправлены более одного раза. Оставшаяся задача состоит в том, чтобы восстановить эти стратегии нужное количество раз.
Начнем с первоначального выбора 432-строчных индексов из filtered_dist_data. Затем мы изменяем эти индексы, чтобы гарантировать, что все окончательные индексы соответствуют ненулевым строкам и что у нас никогда не будет двух смежных строк. Код ниже делает это и оставляет нас с selected_matrix.
# Select 432 row indices, as equally spaced as possible, from filtered_dist_data.
# Note that filtered_dist_data has length 1233; I played around with where this
# np.linspace starts and stops to get 418 unique nonzero rows.
selected_indices = np.round(np.linspace(0, 1231, 432)).astype(int)
# We will restrict to the nonzero rows.
nonzero_rows = np.unique(np.nonzero(filtered_dist_data)[0])
# Initialize a list to store the final selected indices.
final_indices = []
# To be selected, a row must be nonzero and not adjacent to another selected row.
# If a member of selected_indices fails one of these conditions, replace it with the
# nearest index that does not fail the conditions.
for idx in selected_indices:
if idx not in nonzero_rows or (len(final_indices) > 0 and abs(final_indices[-1] - idx) <= 1):
# This index must be replaced.
nearest_rows = nonzero_rows[np.abs(nonzero_rows - idx).argsort()]
for nearest_row in nearest_rows:
if len(final_indices) > 0 and abs(final_indices[-1] - nearest_row) <= 1:
continue
else:
final_indices.append(nearest_row)
break
else:
final_indices.append(idx)
# Stop if we have selected 432 rows.
if len(final_indices) >= 432:
break
selected_matrix = filtered_dist_data[final_indices, :]
Проверяем, чтобы убедиться, что мы не потеряли ни одной стратегии.
unique_rows = set(map(tuple, selected_matrix)) len(unique_rows) # Should return 418.
Комментарий к коду, создающему selected_matrix, объясняет, что нужно было немного повозиться, чтобы получить ровно 418 уникальных стратегий (количество, которое нам нужно). Это немного о том, как часто некоторые из стратегий появляются в наборе данных, но они есть все, и я считаю, что они представлены с довольно точной частотой.
Остается только преобразовать эти векторы расстояний в стратегии.
recovered_strategies = np.apply_along_axis(recover_strategy, axis=1, arr=selected_matrix)
Так как recover_strategy() печатает сообщения, когда встречает пропавших без вести солдат, он не может разместить их уникальным образом. Я могу сказать вам, что из рядов, выбранных process_data(), было 47 с пропущенными солдатами и несколькими максимальными записями, а в 11 были пропущенные солдаты и их некуда было поместить.
Более того, эта матрица recovered_strategies соответствует всем строкам таблицы Top 10 + #112 + #266, которой поделился Зак.
>>> recovered_strategies[[*range(10), 111, 265]]
array([[ 1, 3, 8, 13, 11, 24, 5, 28, 3, 4],
[ 0, 0, 7, 11, 12, 23, 3, 4, 6, 34],
[ 0, 0, 8, 11, 13, 22, 3, 4, 5, 34],
[ 0, 1, 8, 11, 16, 21, 2, 4, 4, 33],
[ 3, 5, 6, 7, 12, 1, 27, 31, 4, 4],
[ 0, 6, 7, 11, 12, 22, 3, 26, 6, 7],
[ 0, 1, 11, 0, 1, 1, 23, 27, 1, 35],
[ 1, 1, 2, 14, 3, 3, 22, 24, 26, 4],
[ 2, 1, 8, 1, 1, 1, 25, 27, 1, 33],
[ 0, 0, 8, 12, 14, 22, 3, 3, 6, 32],
[ 1, 1, 9, 15, 12, 16, 8, 7, 8, 23],
[ 5, 0, 14, 19, 5, 6, 8, 8, 18, 17]])
Конечный результат
Один из способов измерить успех этой операции — вычислить записи восстановленных стратегий и сравнить их с результатами, опубликованными Заком. Вот что я получаю, когда делаю это:
Это не совсем согласуется с результатами Зака. Наиболее вероятным виновником является то, что я фактически отказался от 47 стратегий с пропавшими без вести солдатами и более чем одной большой записью, к которой они могли быть отнесены. Можно было бы представить себе использование записей о ничьих выигрышах и проигрышах, которые опубликовал Зак, чтобы сделать более обоснованный выбор того, где использовать этих дополнительных солдат (скажем, сформулировав назначение этих 47 наборов недостающих солдат как задачу программирования с ограничениями), но я буду сопротивляться этому искушению.
Хотя это показывает, что я не полностью восстановил все стратегии, я вполне доволен извлеченным набором данных, по крайней мере, для планирования моей стратегии для восьмой битвы за нацию Загадочников. Осталось только сохранить стратегии в файл CSV.
import pandas as pd
df = pd.DataFrame(recovered_strategies)
df.columns = ["Castle " + str(i) for i in range(1, 11)]
df.to_csv("castle-solutions-7.csv", index=False)
А потом выложить их на GitHub для всех.
