Блог

Там n стопок монет. Каждая стопка содержит монеты k_i, и монеты в определенной стопке имеют разные значения. В каждый ход вы можете выбрать одну монету из верхней части любой стопки, а ваш противник может выбрать одну монету из нижней части любой стопки. Выигрывает тот, у кого больше всего монет.

Какова была бы оптимальная стратегия для этой игры?

Я думаю, что это должен быть какой-то жадный алгоритм в сочетании с ответом оппонентов и, возможно, разделение каждого стека пополам для сравнения значений, может быть?

Значение для четных стеков

В качестве особого случая рассмотрим, все ли стеки ровные.

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

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

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

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

Значение для общих стеков

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

В Python это может быть записано как:

 def compute_value(stacks):  t=0  middle=[]  for S in stacks:  n=len(S)  n2,r = divmod(n,2)  t  = sum(S[:n2]) - sum(S[n2 r:])  if r:  middle.append(S[n2])  middle.sort(reverse=True)  for i,m in enumerate(middle):  if i%2==0:  t  = m  else:  t -= m  return t  

Оптимальная стратегия

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

Обратите внимание, что это эффективно, потому что вам нужно продумать только один ход вперед, вам не нужно исследовать целое дерево ходов.

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

Сначала давайте попробуем найти, какие драгоценные камни будут взяты, если оба игрока будут играть оптимально. Вместо стека давайте предположим, что драгоценные камни предположим, что драгоценные камни были расположены в ряд, и игроки ставят отметку рядом с выбранными ими драгоценными камнями.

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

Гипотеза, основанная на интуиции, состоит в том, что если оба игрока будут играть оптимально, то в конечном итоге они будут собирать драгоценные камни только со своей половины. Мы сравниваем только две стопки из всех стопок. Таким образом, мы получим 3 случая:

Случай 1: Четный и четный

Давайте возьмем несколько двух стеков с драгоценными камнями $2m$ и $2n$, и пусть драгоценные камни будут пронумерованы как $a_1, a_2,…, a_{2m} $ и $b_1, b_2,…, b_{2n}$ слева направо соответственно, и игрок 1 выбирает слева, а игрок 2 справа.

Интуитивно мы ожидаем, что игроки разделят каждый стек совершенно равномерно между собой. Итак, давайте предположим обратное, что в конце концов игрок 1 выбрал драгоценные камни $a_1,a_2,…,a_m,…,a_{m k}$ и $b_1,b_2,…,b_{n-k}$, а игрок 2 выбрал оставшиеся драгоценные камни в этих двух стопках.

Из леммы 5.1 мы знаем, что любой игрок мог принудительно разделить, но поскольку они этого не сделали, мы можем предположить, что сумма значений драгоценных камней из $a_{m 1},…, a_{m k}$ и из $b_{n-k 1},…, b_n$ равна, потому что в противном случае это означало бы, что игроки играли не оптимально. Возможно, что значения равны, но когда мы играем, мы можем разделить их поровну для простоты.

Случай 2: Нечетное и нечетное

Давайте сделаем то же самое, что и раньше, но две стопки с драгоценными камнями по 2 миллиона долларов 1 доллар и 2 миллиона долларов 1 доллар. Таким образом, в центре большинства драгоценных камней находятся $a_{m 1}$ и $b_{n 1}$.

Давайте снова предположим, что в конце концов игрок 1 выбрал драгоценные камни $a_1,a_2,…,a_{m 1},…,a_{m 1 k}$ и $b_1,b_2,…,b_{n 1-k}$, а игрок 2 выбрал оставшиеся драгоценные камни в этих двух стопках. Как и в предыдущем случае, сумма значений драгоценных камней из $a_{m 2},…,a_{m 1 k}$ и из $b_{n 1-k 1},…,b_{n 1}$ должна быть равной, поскольку предполагается, что оба игрока играют оптимально. Единственная разница в том, что в этом случае игрок, который пойдет первым, может выбрать больший из драгоценных камней между $a_{m 1}$ и $b_{n 1}$. Поэтому мы можем разделить стопки поровну, и нам нужно только сравнить центральные драгоценные камни.

Случай 3: Четное и нечетное

Давайте сделаем то же самое, что и раньше, но две стопки, содержащие 2 м и 2n 1 драгоценных камней. Таким образом, центральным камнем для стека B является b_(n 1). Давайте предположим, что игрок 1 выбирает первым.

Давайте предположим, что в конце концов игрок 1 выбрал драгоценные камни $a_1,a_2,…,a_m,…,a_{m k}$ и $b_1,b_2,…,b_{n 1-k}$, а игрок 2 выбрал оставшиеся драгоценные камни в этих двух стопках. Как и в предыдущем случае, сумма значений драгоценных камней из $a_{m 1},…,a_{m k}$ и из $b_{n 1-k 1},…,b_{n 1}$ должна быть равной.

Аналогично, если в конце игрок 1 выбрал драгоценные камни $a_1, a_2,…, a_{m-k}$ и $b_1,b_2,…, b_{n 1},…, b_{n 1 k}$, а игрок 2 выбрал оставшиеся драгоценные камни, то сумма значений драгоценных камней из $a_{m-k 1},…,a_m$ и из $b_{n 2},…,b_{n 1 k}$ должна быть равной. Поэтому мы можем просто разделить каждую стопку пополам для простоты.

Поэтому оптимальной стратегией (для обоих игроков) было бы разделить каждую стопку с четным количеством драгоценных камней пополам и упорядочить все стопки с нечетным количеством драгоценных камней по убыванию в зависимости от значения их центральных драгоценных камней, а затем 1-я стопка будет разделена таким образом, что игрок 1(предположим, что игрок 1 начинает) получит центральный драгоценный камень, а 2-я стопка будет разделена таким образом, что игрок 2 получит центральный драгоценный камень, а $(2n-1) — й$ стек с нечетным количеством драгоценных камней разделится, когда игрок 1 получит центральный драгоценный камень, и стек $(2n) — й$ с нечетным количеством драгоценных камней разделится, и игрок 2 получит центральный драгоценный камень.

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

Давайте отсортируем и пронумеруем все стопки с нечетным количеством драгоценных камней по убыванию, в зависимости от их центрального камня, от 1 до $k$.

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

Оценка игрока 1 = сумма значений всех драгоценных камней в верхней половине всех стеков с четным количеством драгоценных камней сумма значений всех драгоценных камней в верхней половине стеков с нечетным количеством драгоценных камней { включая центральный драгоценный камень, если стек пронумерован нечетным числом, и исключая центральный драгоценный камень, если стек пронумерован четным числом}

Счет игрока 2 = сумма значений оставшихся драгоценных камней

Я думаю, что это результат, если оба игрока будут играть с (как я думаю) наиболее оптимальной стратегией.