Они сказали, что это азартная игра. Они сказали, что это весело. Входит 151 команда, одна команда уходит. Сможет ли ваша стратегия противостоять лучшим?

По крайней мере, таков был план. Но Hog - это не азартная игра, это игра вероятностей. Холодная, безжалостная вероятность, где маржа 0,008% может означать разницу между сочным беконом и далеким 6-м местом.

Так как же победить Борова? На самом деле это просто: вы позволяете компьютеру делать выбор.

Что такое динамическое программирование?

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

Рассмотрим следующую функцию Фибоначчи:

def fib(n):
    if n in (0,1):
        return n
    return fib(n-1) + fib(n-2)

Хорошо право? Не совсем. Для запуска fib(34) требуется примерно секунда, что неплохо, и 2526553 года, чтобы запустить fib(100), что немного хуже.

Почему это занимает так много времени? Он делает повторяющиеся вызовы функций. В частности, запуск fib(100) вызывает fib(99) один раз, fib(98) два раза, fib(97) три раза, fib(96) пять раз, fib(95) восемь раз (видите шаблон?) И так далее, в конечном итоге вызывая fib(1) 354224848179261915075 раз. Это большая дополнительная работа, от которой мы можем избавиться, кешируя результаты.

Давайте сделаем это с мемоизацией (разновидностью DP):

stored_fib_results = [0,1]
def fib(n):
    if n < len(stored_fib_results):
        return stored_fib_results[n]
    res = fib(n-1) + fib(n-2)
    stored_fib_results.append(res)
    return res

Это дает нам небольшое улучшение производительности, позволяя запускать fib(100) примерно за 23 микросекунды. Неплохо!

(В Python также есть простой способ автоматически применить мемоизацию, добавив from functools import lru_cache и поместив декоратор @lru_cache над любой функцией, которую вы хотите запомнить. Однако на других языках это не так просто.)

Как мы можем применить это к Hog?

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

  1. Сколько кубиков вы решите бросить в этот момент
  2. Ваша вероятность выигрыша в любой будущей позиции

Вы не поверите, но это означает, что существует идеальная стратегия для правил, не связанных с соревнованиями. Давайте настроим код для определения этой стратегии:

best_choice =     [[-1]*100 for _ in range(100)]
prob_of_winning = [[-1]*100 for _ in range(100)]
def calculate_best_choice_at(score, opponent_score):
    #stuff
def calculate_chance_with(score, opponent_score, choice):
    #stuff

Давайте разберем это:

  • best_choice - это 2-й список (список списков), в котором хранится лучший выбор в каждой позиции. Мы можем получить к нему доступ как best_choice[score][opponent_score]. Он заполнен значением -1, что представляет собой невычисленное значение (помогает при отладке).
  • prob_of_winning также является 2-м списком.
  • calculate_best_choice будет вызывать calculate_chance_with для каждого выбора 0–10 и сохранять наиболее вероятный вариант в best_choice. Он также хранит вероятность выигрыша с таким выбором в prob_of_winning.
  • calculate_chance_with рассчитает вероятность выигрыша с учетом позиции и выбора и вернет ее.

calculate_chance_with работает так: набор бросков костей представлен в виде распределения вероятностей. Например, вот распределение вероятностей для броска 3 кубиков:

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

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

И как только вы набрали calculate_best_choice по всем позициям, все готово! Вы отлично умеете играть в кабана!

Шенаниганы с 8-гранными игральными костями

Конечно, соревнование Hog не было бы очень увлекательным, если бы в нем была всего лишь 151 идеальная стратегия, каждая из которых приносила ровно 50% винрейта друг против друга. Вот почему это было введено:

В дополнение к правилам игры, описанным в Hog Project, игроки будут бросать 8-гранные кубики на всех дополнительных ходах.

Это правило имеет очень важное значение: Hog больше не является идеальной информационной игрой.

Рассмотрим позицию, в которой у вас 33, а у оппонента 34, что мы можем обозначить как (33,34). У тебя дополнительный ход или нет?

Невозможно сказать - у вас могло быть (25,34) и выкинуть 8 очков (что дает дополнительный ход), или ваш оппонент мог быть на (33,33) и выбросить 1 (и вы бы не т быть на дополнительном повороте).

Однако, хотя невозможно узнать наверняка, можно приблизительно оценить вашу вероятность оказаться на дополнительном ходу. Карта вероятностей выглядит так:

Эти вероятности можно использовать в calculate_best_choice, чтобы помочь создать стратегии, которые, хотя и не идеальны, но довольно близки. Это можно сделать несколькими способами:

  • Возьмите средневзвешенное значение лучшего выбора с 6-гранными кубиками и лучшего выбора с 8-гранными кубиками.
  • Рассчитайте вероятность выигрыша на основе броска кубиков с нецелыми сторонами от 6 до 8 (n = 6 + 2p, где p - вероятность выпадения дополнительного хода)
  • Рассчитайте вероятность выигрыша как средневзвешенное значение вероятности выигрыша с 6-гранным кубиком и вероятности выигрыша с 8-гранным кубиком.

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

Альтернативный способ справиться с 8-гранными игральными костями - признать, что менее 200 позиций имеют эту неопределенность (особенно позиции (n, n + 1) и (n, n + 2)). Случайным образом меняя несколько из этих квадратов за раз, генерируя остальную часть стратегии на основе алгоритма expectiminimax и проверяя процент выигрышей по сравнению с идеальной всезнающей стратегией (той, которая знает, находитесь ли вы на дополнительном ходу), можно вносить постепенные изменения, пока стратегия не станет почти идеальной.

Обратной стороной этого альтернативного метода является то, что для его вычислений требуется время. Несколько вещей, которые можно сделать, чтобы ускорить его:

  • Только пересчет квадратов, на которые повлияло изменение. Хотя это не очень помогает для поздних квадратов, это значительно ускоряет ранние изменения квадратов.
  • Использование языка, отличного от Python. Rust - замечательный язык для этого случая использования - переход на Rust дал нам буквально 700-кратное ускорение нашего кода расчета винрейта (в среднем с 980 миллисекунд до 1,36 миллисекунды).

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

Почему потолок?

К всеобщему удивлению, конкурс в этом семестре закончился вничью. Как это случилось?

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

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

  • (57,65) может быть 2 или 9
  • (65,67) может быть 8 или 9

Неудивительно, что была 5-исходная ничья!

Независимо от исхода конкурса, надеемся, что всем было весело. Спасибо сотрудникам курса CS 61A за организацию этого конкурса!