Тихі поєдинки — Побудова рішення, частина 2 || Математика ∩ Програмування
Попередні публікації в цій серії:
Тихі поєдинки та старий папір Restrepo. Тихі поєдинки — Розбір конструкції. Тихі поєдинки — Побудова рішення, частина 1
Відколи це було три роки з останнього допису в цій серії, і причина затримки полягає в тому, що я повністю застряг на реалізації. Я публікую цю чернетку статті як частковий прогрес, поки не знайду час попрацювати над нею знову.
Якщо ви не читали останній пост, прочитайте. Репо коду. Папір я працюю. У цій публікації я досягаю прогресу в реалізації загальної конструкції оптимальних стратегій з паперу, але в кінці перший серйозний тестовий приклад провалюється. Зрештою я застряг і не знаю, що робити далі, щоб це виправити.
Рефакторинг
Давайте почнемо з рефакторингу безладу коду з минулого допису. Зараз гарний час для цього, тому що наші роботи в останньому дописі вселили впевненість, що ми розуміємо основні механізми. Центральні функції для побудови загального рішення містяться в цьому файлі, станом на цю фіксацію.
Ми використовуємо Sympy для представлення функцій і обчислення інтегралів, і це допомагає правильно називати типи. Зауважте, я буду використовувати анотації типів python у коді, але типи не перевіряються через відсутність заглушок у sympy. Назвіть це простором для вдосконалення.
from sympy import Lambda
SuccessFn = NewType('SuccessFn', Lambda)
@dataclass
class SilentDuelInput:
'''Class containing the static input data to the silent duel problem.'''
player_1_action_count: int
player_2_action_count: int
player_1_action_success: SuccessFn
player_2_action_success: SuccessFn
Тепер переходимо до виходу. Нагадаємо, стратегія — це розбиття $(0,1)$ на $n$ інтервалів, де $n$ — кількість дій, указаних у вхідних даних, з розподілом ймовірностей для кожної частини розбиття. Це говорить про природну поломку
@dataclass
class Strategy:
'''
A strategy is a list of action distribution functions, each of which
describes the probability of taking an action on the interval of its
support.
'''
action_distributions: List(ActionDistribution)
І ActionDistribution визначається як:
@dataclass
class ActionDistribution:
'''The interval on which this distribution occurs.'''
support_start: float
support_end: float
'''
The cumulative density function for the distribution.
May be improper if point_mass > 0.
'''
cumulative_density_function: Lambda
'''
If nonzero, corresponds to an extra point mass at the support_end.
Only used in the last action in the optimal strategy.
'''
point_mass: float = 0
t = Symbol('t', nonnegative=True)
def draw(self, uniform_random_01=DEFAULT_RNG):
'''Return a random draw from this distribution.
Args:
- uniform_random_01: a callable that accepts zero arguments
and returns a uniform random float between 0 and 1. Defaults
to using python's standard random.random
'''
if self.support_start >= self.support_end: # treat as a point mass
return self.support_start
uniform_random_number = uniform_random_01()
if uniform_random_number > 1 - self.point_mass - EPSILON:
return self.support_end
return solve_unique_real(
self.cumulative_density_function(self.t) - uniform_random_number,
self.t,
solution_min=self.support_start,
solution_max=self.support_end,
)
Ми представляємо розподіл ймовірностей як інтегральну функцію щільності $F
class SilentDuelOutput:
p1_strategy: Strategy
p2_strategy: Strategy
Я також вирішив створити невелику структуру даних, щоб допомогти підтримувати спільний прогрес створення розділу та нормалізації констант для кожного гравця.
@dataclass
class IntermediateState:
'''
A list of the transition times computed so far. This field
maintains the invariant of being sorted. Thus, the first element
in the list is a_{i + 1}, the most recently computed value of
player 1's transition times, and the last element is a_{n + 1} = 1.
This value is set on initialization with `new`.
'''
player_1_transition_times: Deque(Expr)
'''
Same as player_1_transition_times, but for player 2 with b_j and b_m.
'''
player_2_transition_times: Deque(Expr)
'''
The values of h_i so far, the normalizing constants for the action
probability distributions for player 1. Has the same sorting
invariant as the transition time lists.
'''
player_1_normalizing_constants: Deque(Expr)
'''
Same as player_1_normalizing_constants, but for player 2,
i.e., the k_j normalizing constants.
'''
player_2_normalizing_constants: Deque(Expr)
@staticmethod
def new():
'''Create a new state object, and set a_{n+1} = 1, b_{m+1}=1.'''
return IntermediateState(
player_1_transition_times=deque((1)),
player_2_transition_times=deque((1)),
player_1_normalizing_constants=deque(()),
player_2_normalizing_constants=deque(()),
)
def add_p1(self, transition_time, normalizing_constant):
self.player_1_transition_times.appendleft(transition_time)
self.player_1_normalizing_constants.appendleft(normalizing_constant)
def add_p2(self, transition_time, normalizing_constant):
self.player_2_transition_times.appendleft(transition_time)
self.player_2_normalizing_constants.appendleft(normalizing_constant)
Тепер, коли ми встановили типи, переходимо до конструкції.
Будівництво
У конструкції є три частини:
- Обчислення правильних $\alpha$ і $\beta$.
- Знаходження моментів переходу та нормалізації констант для кожного гравця.
- Використовуйте вищезазначене для побудови вихідних стратегій.
Побудова вихідної стратегії
Ми почнемо з останнього: обчислення результату за правильних значень. Конструкція є симетричною для кожного гравця, тому ми можемо мати одну функцію, що викликається з різними входами.
def compute_strategy(
player_action_success: SuccessFn,
player_transition_times: List(float),
player_normalizing_constants: List(float),
opponent_action_success: SuccessFn,
opponent_transition_times: List(float),
time_1_point_mass: float = 0) -> Strategy:
Ця функція обчислює конструкцію Restrepo.
Одна з труднощів полягає у вираженні переривчастих розривів. Визначення $f^*$ є добутком $b_j > t$, але якщо $b_j$ лежить всередині інтервалу дії, це призведе до розриву. Я не знаю простого способу виразити добуток $f^*$ буквально так, як це написано в sympy (дайте мені знати, якщо ви знаєте краще), тому замість цього я вирішив побудувати функцію по частинах вручну, яку sympy добре підтримує.
Це призводить до наступної функції для створення остаточного $f^*$ для однієї дії для одного гравця. Покускова функція полягає в тому, щоб розбити інтервал дії на частини відповідно до розривів, внесених переходами опонента, які лежать у тому самому інтервалі.
def f_star(player_action_success: SuccessFn,
opponent_action_success: SuccessFn,
variable: Symbol,
opponent_transition_times: Iterable(float)) -> Expr:
'''Compute f^* as in Restrepo '57.
The inputs can be chosen so that the appropriate f^* is built
for either player. I.e., if we want to compute f^* for player 1,
player_action_success should correspond to P, opponent_action_success
to Q, and larger_transition_times to the b_j.
If the inputs are switched appropriately, f^* is computed for player 2.
'''
P: SuccessFn = player_action_success
Q: SuccessFn = opponent_action_success
'''
We compute f^* as a Piecewise function of the following form:
(prod_{i=1}^m (1-Q(b_i))) * Q'
(prod_{i=2}^m (1-Q(b_i))) * Q'
(prod_{i=3}^m (1-Q(b_i))) * Q'
.
.
.
(1) * Q'
'''
non_product_term = diff(Q(variable), variable) / (Q(variable)**2 * P(variable))
piecewise_components = ()
for i, b_j in enumerate(opponent_transition_times):
larger_transition_times = opponent_transition_times(i:)
product = 1
for b in larger_transition_times:
product *= (1 - Q(b))
term = product * non_product_term
piecewise_components.append((term, variable < b_j))
# last term is when there are no larger transition times.
piecewise_components.append((non_product_term, True))
return Piecewise(*piecewise_components)
Частичні компоненти є щільністю ймовірності, тому ми можемо їх інтегрувати по частинах, щоб отримати кумулятивну щільність. Тут є кілька помічників для роботи з кусковими функціями. Спочатку ми визначимо a mask_piecewise щоб змінити внутрішнє представлення sympy кускової функції, щоб вона мала вказані значення за межами фіксованого інтервалу (інтервал, на якому відбувається дія). Для pdf це має бути нуль, а для cdf має бути 0 перед інтервалом дії та 1 після. Є також деякі нюанси, до яких приховані виклики expr.simplify() дозволяють інтеграції відбуватися набагато швидше, ніж інакше.
def compute_strategy(
player_action_success: SuccessFn,
player_transition_times: List(float),
player_normalizing_constants: List(float),
opponent_action_success: SuccessFn,
opponent_transition_times: List(float),
time_1_point_mass: float = 0) -> Strategy:
'''
Given the transition times for a player, compute the action cumulative
density functions for the optimal strategy of the player.
'''
action_distributions = ()
x = Symbol('x', real=True)
t = Symbol('t', real=True)
# chop off the last transition time, which is always 1
opponent_transition_times = (
x for x in opponent_transition_times if x < 1
)
pairs = subsequent_pairs(player_transition_times)
for (i, (action_start, action_end)) in enumerate(pairs):
normalizing_constant = player_normalizing_constants(i)
dF = normalizing_constant * f_star(
player_action_success,
opponent_action_success,
x,
opponent_transition_times,
)
piece_pdf = mask_piecewise(dF, x, action_start, action_end)
piece_cdf = integrate(piece_pdf, x, action_start, t)
piece_cdf = mask_piecewise(
piece_cdf,
t,
action_start,
action_end,
before_domain_val=0,
after_domain_val=1
)
action_distributions.append(ActionDistribution(
support_start=action_start,
support_end=action_end,
cumulative_density_function=Lambda((t,), piece_cdf),
))
action_distributions(-1).point_mass = time_1_point_mass
return Strategy(action_distributions=action_distributions)
def compute_player_strategies(silent_duel_input, intermediate_state, alpha, beta):
p1_strategy = compute_strategy(
player_action_success=silent_duel_input.player_1_action_success,
player_transition_times=intermediate_state.player_1_transition_times,
player_normalizing_constants=intermediate_state.player_1_normalizing_constants,
opponent_action_success=silent_duel_input.player_2_action_success,
opponent_transition_times=intermediate_state.player_2_transition_times,
time_1_point_mass=alpha,
)
p2_strategy = compute_strategy(
player_action_success=silent_duel_input.player_2_action_success,
player_transition_times=intermediate_state.player_2_transition_times,
player_normalizing_constants=intermediate_state.player_2_normalizing_constants,
opponent_action_success=silent_duel_input.player_1_action_success,
opponent_transition_times=intermediate_state.player_1_transition_times,
time_1_point_mass=beta,
)
return SilentDuelOutput(p1_strategy=p1_strategy, p2_strategy=p2_strategy)
Зауважте, що «Lambda» — це внутрішня анонімна функція sympy, яку ми використовуємо тут для визначення функціональності. Лямбда також підтримує нотацію виклику функції шляхом перевантаження __call__. Це дозволяє розглядати подальший розподіл дій як функцію.
Знаходження моментів переходу
Далі ми переходимо до обчислення часу переходу для даного $\alpha, \beta$. Цей крок здебільшого такий самий, як і в попередній публікації цієї серії, але ми оновлюємо код, щоб він став простішим і загальнішим.
Зовнішній цикл створить об’єкт проміжного стану та обробляє процес, який Restrepo описує: «взяття більшого параметра», а потім обчислення наступних $a_i, b_j$ з використанням попередньо збережених параметрів. Є одне застереження, яке Рестрепо пропускає, коли пише: «для певності ми припускаємо, що $a_n > b_m$…на наступному кроці…обчислюється новий $b_m$…використовуючи єдиний параметр $a_n^*$». Наскільки я можу сказати (і експериментуючи із симетричними прикладами), коли обчислені часи переходу рівні, збереження лише одного та сумлінне дотримання алгоритму Restrepo призведе до непослідовного результату. Наскільки я можу сказати, це незначна помилка, і якщо часи переходу однакові, ви повинні зберегти їх обидва, а не перераховувати один, використовуючи інший як параметр.
def compute_as_and_bs(duel_input: SilentDuelInput,
alpha: float = 0,
beta: float = 0) -> IntermediateState:
'''
Compute the a's and b's for the silent duel, given a fixed
alpha and beta as input.
'''
t = Symbol('t0', nonnegative=True, real=True)
p1_index = duel_input.player_1_action_count
p2_index = duel_input.player_2_action_count
intermediate_state = IntermediateState.new()
while p1_index > 0 or p2_index > 0:
# the larger of a_i, b_j is kept as a parameter, then the other will be repeated
# in the next iteration; e.g., a_{i-1} and b_j (the latter using a_i in its f^*)
(a_i, b_j, h_i, k_j) = compute_ai_and_bj(
duel_input, intermediate_state, alpha=alpha, beta=beta
)
# there is one exception, if a_i == b_j, then the computation of f^* in the next
# iteration (I believe) should not include the previously kept parameter. I.e.,
# in the symmetric version, if a_n is kept and the next computation of b_m uses
# the previous a_n, then it will produce the wrong value.
#
# I resolve this by keeping both parameters when a_i == b_j.
if abs(a_i - b_j) < EPSILON and p1_index > 0 and p2_index > 0:
# use the average of the two to avoid roundoff errors
transition = (a_i + b_j) / 2
intermediate_state.add_p1(float(transition), float(h_i))
intermediate_state.add_p2(float(transition), float(k_j))
p1_index -= 1
p2_index -= 1
elif (a_i > b_j and p1_index > 0) or p2_index == 0:
intermediate_state.add_p1(float(a_i), float(h_i))
p1_index -= 1
elif (b_j > a_i and p2_index > 0) or p1_index == 0:
intermediate_state.add_p2(float(b_j), float(k_j))
p2_index -= 1
return intermediate_state
Залишається обчислити окрему пару $a_i, b_j$ з проміжним станом. Ми переробили тіло циклу з останньої публікації в загальну функцію, яка працює як для $a_n, b_m$ (які потребують доступу до $\alpha, \beta$), так і для нижчих $a_i, b_j$. За винятком “simple_f_star”, тут не відбувається нічого нового.
def simple_f_star(player_action_success: SuccessFn,
opponent_action_success: SuccessFn,
variable: Symbol,
larger_transition_times: Iterable(float)) -> Expr:
P: SuccessFn = player_action_success
Q: SuccessFn = opponent_action_success
non_product_term = diff(Q(variable), variable) / (Q(variable)**2 * P(variable))
product = 1
for b in larger_transition_times:
product *= (1 - Q(b))
return product * non_product_term
def compute_ai_and_bj(duel_input: SilentDuelInput,
intermediate_state: IntermediateState,
alpha: float = 0,
beta: float = 0):
'''
Compute a pair of a_i and b_j transition times for both players,
using the intermediate state of the algorithm computed so far.
This function also computes a_n and b_m when the intermediate_state
input has no larger transition times for the opposite player. In
those cases, the integrals and equations being solved are slightly
different; they include some terms involving alpha and beta. In all
other cases, the alpha and beta parameters are unused.
'''
P: SuccessFn = duel_input.player_1_action_success
Q: SuccessFn = duel_input.player_2_action_success
t = Symbol('t0', nonnegative=True, real=True)
a_i = Symbol('a_i', positive=True, real=True)
b_j = Symbol('b_j', positive=True, real=True)
p1_transitions = intermediate_state.player_1_transition_times
p2_transitions = intermediate_state.player_2_transition_times
# the left end of the transitions arrays contain the smallest
# (latest computed) transition time for each player.
# these are set to 1 for an empty intermediate state, i.e. for a_n, b_m
a_i_plus_one = p1_transitions(0)
b_j_plus_one = p2_transitions(0)
computing_a_n = a_i_plus_one == 1
computing_b_m = b_j_plus_one == 1
p1_fstar_parameters = list(p2_transitions)(:-1) # ignore b_{m+1} = 1
p1_fstar = simple_f_star(P, Q, t, p1_fstar_parameters)
# the a_i part
if computing_a_n:
p1_integrand = ((1 + alpha) - (1 - alpha) * P
p1_integral_target = 2 * (1 - alpha)
else:
p1_integrand = (1 - P
p1_integral_target = 1 / intermediate_state.player_1_normalizing_constants(0)
a_i_integrated = integrate(p1_integrand, t, a_i, a_i_plus_one)
a_i = solve_unique_real(
a_i_integrated - p1_integral_target,
a_i,
solution_min=0,
solution_max=a_i_plus_one
)
# the b_j part
p2_fstar_parameters = list(p1_transitions)(:-1) # ignore a_{n+1} = 1
p2_fstar = simple_f_star(Q, P, t, p2_fstar_parameters)
if computing_b_m:
p2_integrand = ((1 + beta) - (1 - beta) * Q
p2_integral_target = 2 * (1 - beta)
else:
p2_integrand = (1 - Q
p2_integral_target = 1 / intermediate_state.player_2_normalizing_constants(0)
b_j_integrated = integrate(p2_integrand, t, b_j, b_j_plus_one)
b_j = solve_unique_real(
b_j_integrated - p2_integral_target,
b_j,
solution_min=0,
solution_max=b_j_plus_one
)
# the h_i part
h_i_integrated = integrate(p1_fstar, t, a_i, a_i_plus_one)
h_i_numerator = (1 - alpha) if computing_a_n else 1
h_i = h_i_numerator / h_i_integrated
# the k_j part
k_j_integrated = integrate(p2_fstar, t, b_j, b_j_plus_one)
k_j_numerator = (1 - beta) if computing_b_m else 1
k_j = k_j_numerator / k_j_integrated
return (a_i, b_j, h_i, k_j)
Вам може бути цікаво, що відбувається з «simple_f_star». Дозвольте мені залишити це на кінець публікації, оскільки це пов’язано з тим, наскільки я зараз застряг у розумінні конструкції.
Двійковий пошук альфа і бета
Нарешті, нам потрібно виконати двійковий пошук бажаного результату $a_1 = b_1$ як функції $\alpha, \beta$. Відповідно до заяви Рестрепо, ми спочатку обчислюємо $a_1, b_1$ за допомогою $\alpha=0, \beta=0$. Якщо $a_1 > b_1$, то ми шукаємо $\beta > 0$, і навпаки для $\alpha$.
Щоб полегшити двійковий пошук, я вирішив реалізувати абстрактну процедуру бінарного пошуку (яка працює лише для доменів із плаваючою комою). Ви можете побачити код тут. Важливою частиною є те, що він абстрагує тест (чи знайшов?) і відповідь (ні, надто низька), тому ми можемо зробити, щоб ядром цього тесту було обчислення $a_1, b_1$.
Спочатку біти недвійкового пошуку:
def optimal_strategies(silent_duel_input: SilentDuelInput) -> SilentDuelOutput:
'''Compute an optimal pair of corresponding strategies for the silent duel problem.'''
# First compute a's and b's, and check to see if a_1 == b_1, in which case quit.
intermediate_state = compute_as_and_bs(silent_duel_input, alpha=0, beta=0)
a1 = intermediate_state.player_1_transition_times(0)
b1 = intermediate_state.player_2_transition_times(0)
if abs(a1 - b1) < EPSILON:
return compute_player_strategies(
silent_duel_input, intermediate_state, alpha=0, beta=0,
)
# Otherwise, binary search for an alpha/beta
searching_for_beta = b1 < a1
<snip>
intermediate_state = compute_as_and_bs(
silent_duel_input, alpha=final_alpha, beta=final_beta
)
player_strategies = compute_player_strategies(
silent_duel_input, intermediate_state, final_alpha, final_beta
)
return player_strategies
Наведене вище спочатку перевіряє, чи потрібен пошук, і в будь-якому випадку використовує наші раніше визначені функції для обчислення стратегій виведення. Частина бінарного пошуку виглядає так:
if searching_for_beta:
def test(beta_value):
new_state = compute_as_and_bs(
silent_duel_input, alpha=0, beta=beta_value
)
new_a1 = new_state.player_1_transition_times(0)
new_b1 = new_state.player_2_transition_times(0)
found = abs(new_a1 - new_b1) < EPSILON
return BinarySearchHint(found=found, tooLow=new_b1 < new_a1)
else: # searching for alpha
def test(alpha_value):
new_state = compute_as_and_bs(
silent_duel_input, alpha=alpha_value, beta=0
)
new_a1 = new_state.player_1_transition_times(0)
new_b1 = new_state.player_2_transition_times(0)
found = abs(new_a1 - new_b1) < EPSILON
return BinarySearchHint(found=found, tooLow=new_a1 < new_b1)
search_result = binary_search(
test, param_min=0, param_max=1, callback=print
)
assert search_result.found
# the optimal (alpha, beta) pair have product zero.
final_alpha = 0 if searching_for_beta else search_result.value
final_beta = search_result.value if searching_for_beta else 0
З’єднайте все разом
Проведемо повну конструкцію на кількох прикладах. Я додав пару операторів print у код і перевантажив __str__ про класи даних, щоб допомогти. Спочатку ми можемо перевірити, що отримуємо той самий результат, що й у попередньому симетричному прикладі:
x = Symbol('x')
P = Lambda((x,), x)
Q = Lambda((x,), x)
duel_input = SilentDuelInput(
player_1_action_count=3,
player_2_action_count=3,
player_1_action_success=P,
player_2_action_success=Q,
)
print("Input: {}".format(duel_input))
output = optimal_strategies(duel_input)
print(output)
output.validate()
# output is:
Input: SilentDuelInput(player_1_action_count=3, player_2_action_count=3, player_1_action_success=Lambda(_x, _x), player_2_action_success=Lambda(_x, _x))
a_1 = 0.143 b_1 = 0.143
P1:
(0.143, 0.200): dF/dt = Piecewise((0, (t > 0.2) | (t < 0.142857142857143)), (0.083/t**3, t < 0.2))
(0.200, 0.333): dF/dt = Piecewise((0, (t > 0.333333333333333) | (t < 0.2)), (0.13/t**3, t < 0.333333333333333))
(0.333, 1.000): dF/dt = Piecewise((0, (t > 1) | (t < 0.333333333333333)), (0.25/t**3, t < 1))
P2:
(0.143, 0.200): dF/dt = Piecewise((0, (t < 0.2) | (t < 0.142857142857143)), (0.083/t**3, t < 0.2))
(0.200, 0.333): dF/dt = Piecewise((0, (t > 0.333333333333333) | (t < 0.2)), (0.13/t**3, t < 0.333333333333333))
(0.333, 1.000): dF/dt = Piecewise((0, (t > 1) | (t < 0.333333333333333)), (0.25/t**3, t > 1))
Validating P1
Validating. prob_mass=1.00000000000000 point_mass=0
Validating. prob_mass=1.00000000000000 point_mass=0
Validating. prob_mass=1.00000000000000 point_mass=0
Validating P2
Validating. prob_mass=1.00000000000000 point_mass=0
Validating. prob_mass=1.00000000000000 point_mass=0
Validating. prob_mass=1.00000000000000 point_mass=0
Це збігається: гравці мають однакову стратегію, а час переходу становить 1/7, 1/5 і 1/3.
Далі замініть Q = Lambda((x,), x**2)і мають лише одну дію для кожного гравця. Для цього має знадобитися двійковий пошук, але це буде легко перевірити вручну. Я додав зворотний виклик, який друкує межі під час кожної ітерації бінарного пошуку для спостереження. Також зауважте, що інтеграція sympy досить повільна, тому цей бінарний пошук займає хвилину або дві.
Input: SilentDuelInput(player_1_action_count=1, player_2_action_count=1, player_1_action_success=Lambda(_x, _x), player_2_action_success=Lambda(x, x**2))
a_1 = 0.48109 b_1 = 0.42716
Binary searching for beta
{'current_min': 0, 'current_max': 1, 'tested_value': 0.5}
a_1 = 0.37545 b_1 = 0.65730
{'current_min': 0, 'current_max': 0.5, 'tested_value': 0.25}
a_1 = 0.40168 b_1 = 0.54770
{'current_min': 0, 'current_max': 0.25, 'tested_value': 0.125}
a_1 = 0.41139 b_1 = 0.50000
{'current_min': 0, 'current_max': 0.125, 'tested_value': 0.0625}
a_1 = 0.48109 b_1 = 0.44754
{'current_min': 0.0625, 'current_max': 0.125, 'tested_value': 0.09375}
a_1 = 0.41358 b_1 = 0.48860
{'current_min': 0.0625, 'current_max': 0.09375, 'tested_value': 0.078125}
a_1 = 0.41465 b_1 = 0.48297
{'current_min': 0.0625, 'current_max': 0.078125, 'tested_value': 0.0703125}
a_1 = 0.48109 b_1 = 0.45013
{'current_min': 0.0703125, 'current_max': 0.078125, 'tested_value': 0.07421875}
a_1 = 0.41492 b_1 = 0.48157
{'current_min': 0.0703125, 'current_max': 0.07421875, 'tested_value': 0.072265625}
a_1 = 0.48109 b_1 = 0.45078
{'current_min': 0.072265625, 'current_max': 0.07421875, 'tested_value': 0.0732421875}
a_1 = 0.41498 b_1 = 0.48122
{'current_min': 0.072265625, 'current_max': 0.0732421875, 'tested_value': 0.07275390625}
a_1 = 0.48109 b_1 = 0.45094
{'current_min': 0.07275390625, 'current_max': 0.0732421875, 'tested_value': 0.072998046875}
a_1 = 0.41500 b_1 = 0.48113
{'current_min': 0.07275390625, 'current_max': 0.072998046875, 'tested_value': 0.0728759765625}
a_1 = 0.48109 b_1 = 0.45098
{'current_min': 0.0728759765625, 'current_max': 0.072998046875, 'tested_value': 0.07293701171875}
a_1 = 0.41500 b_1 = 0.48111
{'current_min': 0.0728759765625, 'current_max': 0.07293701171875, 'tested_value': 0.072906494140625}
a_1 = 0.41500 b_1 = 0.48110
{'current_min': 0.0728759765625, 'current_max': 0.072906494140625, 'tested_value': 0.0728912353515625}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.0728759765625, 'current_max': 0.0728912353515625, 'tested_value': 0.07288360595703125}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288360595703125, 'current_max': 0.0728912353515625, 'tested_value': 0.07288742065429688}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288360595703125, 'current_max': 0.07288742065429688, 'tested_value': 0.07288551330566406}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288551330566406, 'current_max': 0.07288742065429688, 'tested_value': 0.07288646697998047}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288646697998047, 'current_max': 0.07288742065429688, 'tested_value': 0.07288694381713867}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288646697998047, 'current_max': 0.07288694381713867, 'tested_value': 0.07288670539855957}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288670539855957, 'current_max': 0.07288694381713867, 'tested_value': 0.07288682460784912}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288670539855957, 'current_max': 0.07288682460784912, 'tested_value': 0.07288676500320435}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288670539855957, 'current_max': 0.07288676500320435, 'tested_value': 0.07288673520088196}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288673520088196, 'current_max': 0.07288676500320435, 'tested_value': 0.07288675010204315}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288675010204315, 'current_max': 0.07288676500320435, 'tested_value': 0.07288675755262375}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288675755262375, 'current_max': 0.07288676500320435, 'tested_value': 0.07288676127791405}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288675755262375, 'current_max': 0.07288676127791405, 'tested_value': 0.0728867594152689}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288675755262375, 'current_max': 0.0728867594152689, 'tested_value': 0.07288675848394632}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288675755262375, 'current_max': 0.07288675848394632, 'tested_value': 0.07288675801828504}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288675801828504, 'current_max': 0.07288675848394632, 'tested_value': 0.07288675825111568}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288675825111568, 'current_max': 0.07288675848394632, 'tested_value': 0.072886758367531}
a_1 = 0.41501 b_1 = 0.48109
{'current_min': 0.07288675825111568, 'current_max': 0.072886758367531, 'tested_value': 0.07288675830932334}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288675830932334, 'current_max': 0.072886758367531, 'tested_value': 0.07288675833842717}
a_1 = 0.48109 b_1 = 0.45099
{'current_min': 0.07288675833842717, 'current_max': 0.072886758367531, 'tested_value': 0.07288675835297909}
a_1 = 0.48109 b_1 = 0.48109
a_1 = 0.48109 b_1 = 0.48109
P1:
(0.481, 1.000): dF/dt = Piecewise((0, (t > 1) | (t < 0.481089134572278)), (0.38/t**4, t < 1))
P2:
(0.481, 1.000): dF/dt = Piecewise((0, (t > 1) | (t < 0.481089134572086)), (0.35/t**4, t < 1)); Point mass of 0.0728868 at 1.000
Validating P1
Validating. prob_mass=1.00000000000000 point_mass=0
Validating P2
Validating. prob_mass=0.927113241647021 point_mass=0.07288675835297909
Це проходить перевірку розумності вихідних розподілів із масою ймовірності 1. P2 також має мати точкову масу в кінці, оскільки розподіл P2 є $f(x) = x^2$, який має меншу вагу на початку та різко зростає в кінці. Це дає P2 недолік і збільшує ймовірність їх дій до кінця. Згідно з теоремою Рестрепо, було б оптимально чекати до кінця приблизно 7% часу, щоб гарантувати ідеальний удар. Ми можемо опрацювати приклад вручну та перетворити результат на модульний тест.
Зауважте, що ми не перевіряли правильність цього прикладу вручну. На даний момент ми просто розглядаємо деякі перевірки розумності.
Де розвалюється
У цей момент я почувався досить добре, а потім наступний приклад показує, що моя реалізація не працює:
x = Symbol('x')
P = Lambda((x,), x)
Q = Lambda((x,), x**2)
duel_input = SilentDuelInput(
player_1_action_count=2,
player_2_action_count=2,
player_1_action_success=P,
player_2_action_success=Q,
)
print("Input: {}".format(duel_input))
output = optimal_strategies(duel_input)
print(output)
output.validate(err_on_fail=False)
Вихідні дані показують, що отриманий розподіл ймовірностей не має загальної ймовірнісної маси 1. Тобто це не розподіл. ой ой
Input: SilentDuelInput(player_1_action_count=2, player_2_action_count=2, player_1_action_success=Lambda(_x, _x), player_2_action_success=Lambda(x, x**2))
a_1 = 0.34405 b_1 = 0.28087
Binary searching for beta
{'current_min': 0, 'current_max': 1, 'tested_value': 0.5}
a_1 = 0.29894 b_1 = 0.45541
{'current_min': 0, 'current_max': 0.5, 'tested_value': 0.25}
a_1 = 0.32078 b_1 = 0.36181
{'current_min': 0, 'current_max': 0.25, 'tested_value': 0.125}
a_1 = 0.32660 b_1 = 0.34015
{'current_min': 0, 'current_max': 0.125, 'tested_value': 0.0625}
a_1 = 0.34292 b_1 = 0.29023
{'current_min': 0.0625, 'current_max': 0.125, 'tested_value': 0.09375}
a_1 = 0.33530 b_1 = 0.30495
{'current_min': 0.09375, 'current_max': 0.125, 'tested_value': 0.109375}
a_1 = 0.32726 b_1 = 0.33741
{'current_min': 0.09375, 'current_max': 0.109375, 'tested_value': 0.1015625}
a_1 = 0.32758 b_1 = 0.33604
{'current_min': 0.09375, 'current_max': 0.1015625, 'tested_value': 0.09765625}
a_1 = 0.32774 b_1 = 0.33535
{'current_min': 0.09375, 'current_max': 0.09765625, 'tested_value': 0.095703125}
a_1 = 0.33524 b_1 = 0.30526
{'current_min': 0.095703125, 'current_max': 0.09765625, 'tested_value': 0.0966796875}
a_1 = 0.33520 b_1 = 0.30542
{'current_min': 0.0966796875, 'current_max': 0.09765625, 'tested_value': 0.09716796875}
a_1 = 0.32776 b_1 = 0.33526
{'current_min': 0.0966796875, 'current_max': 0.09716796875, 'tested_value': 0.096923828125}
a_1 = 0.32777 b_1 = 0.33522
{'current_min': 0.0966796875, 'current_max': 0.096923828125, 'tested_value': 0.0968017578125}
a_1 = 0.33520 b_1 = 0.30544
{'current_min': 0.0968017578125, 'current_max': 0.096923828125, 'tested_value': 0.09686279296875}
a_1 = 0.32777 b_1 = 0.33521
{'current_min': 0.0968017578125, 'current_max': 0.09686279296875, 'tested_value': 0.096832275390625}
a_1 = 0.32777 b_1 = 0.33521
{'current_min': 0.0968017578125, 'current_max': 0.096832275390625, 'tested_value': 0.0968170166015625}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.0968017578125, 'current_max': 0.0968170166015625, 'tested_value': 0.09680938720703125}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.0968017578125, 'current_max': 0.09680938720703125, 'tested_value': 0.09680557250976562}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.0968017578125, 'current_max': 0.09680557250976562, 'tested_value': 0.09680366516113281}
a_1 = 0.33520 b_1 = 0.30544
{'current_min': 0.09680366516113281, 'current_max': 0.09680557250976562, 'tested_value': 0.09680461883544922}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680366516113281, 'current_max': 0.09680461883544922, 'tested_value': 0.09680414199829102}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680366516113281, 'current_max': 0.09680414199829102, 'tested_value': 0.09680390357971191}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680366516113281, 'current_max': 0.09680390357971191, 'tested_value': 0.09680378437042236}
a_1 = 0.33520 b_1 = 0.30544
{'current_min': 0.09680378437042236, 'current_max': 0.09680390357971191, 'tested_value': 0.09680384397506714}
a_1 = 0.33520 b_1 = 0.30544
{'current_min': 0.09680384397506714, 'current_max': 0.09680390357971191, 'tested_value': 0.09680387377738953}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384397506714, 'current_max': 0.09680387377738953, 'tested_value': 0.09680385887622833}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384397506714, 'current_max': 0.09680385887622833, 'tested_value': 0.09680385142564774}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384397506714, 'current_max': 0.09680385142564774, 'tested_value': 0.09680384770035744}
a_1 = 0.33520 b_1 = 0.30544
{'current_min': 0.09680384770035744, 'current_max': 0.09680385142564774, 'tested_value': 0.09680384956300259}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384770035744, 'current_max': 0.09680384956300259, 'tested_value': 0.09680384863168001}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384770035744, 'current_max': 0.09680384863168001, 'tested_value': 0.09680384816601872}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384770035744, 'current_max': 0.09680384816601872, 'tested_value': 0.09680384793318808}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384770035744, 'current_max': 0.09680384793318808, 'tested_value': 0.09680384781677276}
a_1 = 0.32777 b_1 = 0.33520
{'current_min': 0.09680384770035744, 'current_max': 0.09680384781677276, 'tested_value': 0.0968038477585651}
a_1 = 0.33520 b_1 = 0.30544
{'current_min': 0.0968038477585651, 'current_max': 0.09680384781677276, 'tested_value': 0.09680384778766893}
a_1 = 0.33520 b_1 = 0.33520
a_1 = 0.33520 b_1 = 0.33520
deque((0.33520049631043414, 0.45303439059299566, 1))
deque((0.33520049631043414, 0.4897058985296734, 1))
P1:
(0.335, 0.453): dF/dt = Piecewise((0, t < 0.335200496310434), (0.19/t**4, t < 0.453034390592996), (0, t > 0.453034390592996))
(0.453, 1.000): dF/dt = Piecewise((0, t < 0.453034390592996), (0.31/t**4, t < 0.489705898529673), (0.4/t**4, t < 1), (0, t > 1))
P2:
(0.335, 0.490): dF/dt = Piecewise((0, t < 0.335200496310434), (0.17/t**4, t < 0.453034390592996), (0.3/t**4, t < 0.489705898529673), (0, t > 0.489705898529673))
(0.490, 1.000): dF/dt = Piecewise((0, t < 0.489705898529673), (0.36/t**4, t < 1), (0, t > 1)); Point mass of 0.0968038 at 1.000
Validating P1
Validating. prob_mass=0.999999999999130 point_mass=0
Validating. prob_mass=1.24303353980824 point_mass=0 INVALID
Probability distribution does not have mass 1: (0.453, 1.000): dF/dt = Piecewise((0, t < 0.453034390592996), (0.31/t**4, t < 0.489705898529673), (0.4/t**4, t < 1), (0, t > 1))
Validating P2
Validating. prob_mass=1.10285404591706 point_mass=0 INVALID
Probability distribution does not have mass 1: (0.335, 0.490): dF/dt = Piecewise((0, t < 0.335200496310434), (0.17/t**4, t < 0.453034390592996), (0.3/t**4, t < 0.489705898529673), (0, t > 0.489705898529673))
Validating. prob_mass=0.903196152212331 point_mass=0.09680384778766893
Чим принципово відрізняється цей приклад? Головне, що я можу сказати, це те, що це найпростіший приклад, коли гравець 1 виконує дію, яка має час переходу гравця 2 посередині. Це така дія:
(0.453, 1.000): dF/dt = Piecewise((0, t < 0.453034390592996), (0.31/t**4, t < 0.489705898529673), (0.4/t**4, t < 1), (0, t > 1))
...
Validating. prob_mass=1.24303353980824 point_mass=0 INVALID
Тут фактично має значення розрив $f^*$. У попередньому прикладі або була лише одна дія, і за задумом часи початку діапазонів дій однакові, або ж гра була симетричною, тож гравці мали однакові кінцеві точки діапазону дій.
У моїй першій реалізації я фактично повністю проігнорував розриви, і оскільки гра була симетричною, це не вплинуло на розподіл вихідних даних. Це те, що зараз міститься в коді як “simple_f_star”. Переходи дій жодного гравця не потрапляли в межі будь-якого діапазону дій іншого гравця, тому я не помітив, що розрив був важливим.
У будь-якому випадку, за три роки, відколи я вперше працював над цим, я не зміг зрозуміти, що я зробив не так. Можливо, я деякий час не повертатимуся до цієї проблеми, а тим часом, можливо, у якогось доброго читача вистачить терпіння розібратися в цьому. Ви можете побачити журнал моєї плутанини в цій проблемі GitHub, а також деякі дивні обхідні шляхи, які я намагався змусити його працювати.
