Правила игры:
Играют два противника. 1тур состоит из выбрасывания пальцев одной рукой. После выбрасывания игроки получают очки по следующим правилам: если выброшено больше чем у противника, игрок записывает себе количество баллов равное разнице, за исключением случая, когда разница равна 1. В этом случае противник записывает себе сумму выпавших значений. Игра ведется до 21 балла.

Во-первых, успевшие прийти ко мне в голову соображения:
предположим противник - ГСЧ. В этом случае матожидание хода "1"
MO(1)=(0+3-2-3-4)/5=-1.2 Аналогично рассчитываем остальные значения МО:
МО(2)=(-3+0+5-2-3)/5=-0.6
МО(3)=(2-5+0+7-2)/5=0.4
МО(4)=(3+2-7+0+9)/5=1.4
МО(5)=(4+3+2-9+0)/5=0
Итак, если оппонент - ГСЧ, наиболее выгодно выбрасывать 4, менее выгодно - 3, эквивалентно - 5, и невыгодно - 1 и 2. Вывод - ГСЧ как алгоритм, должен в этой игре проигрывать.
Модернизируем оппонента по-квазиБайкерски. Берем в оппоненты алгоритм в программе которого делать ход с наибольшим МО, то есть 4. Очевидно что стратегия выбрасывания троек становится победной и приносит 7 очков за бросок. Вывод - на каждую опу найдется что-то с резьбой.
К сожалению дальше мои размышления вошли в цикл.

Игра похожа на покер. Оптимальная стратегия - подстраиваться под стратегию соперника и менять свою. Кто лучше подстроится, тот и выиграет.

Неплохая стратегия - подстраиваться под стратегию оппа. Еще лучше стратегия - угадывать, что выбросит сейчас оппонент. Жаль, непонятно, как осуществлять ни второй, ни первый варианты.

Это сообщение отредактировал Izubr - 22/01/2009, 13:04

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

Идея такая: наш ход носит вероятностный характер.
Тогда под стратегией в одиночном испытании я предлагаю считать набор вероятностей для нашего хода:
X = {х1, х2, х3, х4, х5}
0 <= х(i) <= 1, i=1..5
S = х1 + x2 + x3 + x4 + x5 = 1


Матрица «A» c ожидаемыми результатами игры по сути была описана в первом посте:
А::
0, -3, 2, 3, 4
3, 0, -5, 2, 3
2, 5, 0, -7, 2
-3, -2, 2, 0, 9
-4, -3, -2, 9, 0

Тогда, в случае выбора оппонентом числа «1», наш выигрыш(проигрыш) в среднем составит:
M1 = M(1) = 0*x1 - 3*x2 + 2*x3 + 3*x4 + 4*x5
И т.д.

Или, в более общем виде:
Mj = M(j) = Сумма(Aj*X) = a1j*x1 + … + a5j*x5, j=1..5 (т.е. - для всех ходов оппонента)
Т.е. Mj – это условное матожидание нашего выигрыша

Полагаю, что если существует непроигрышная стратегия (в такой постановке), то она должна удовлетворять очевидному условию (можно доказать):
(1) Mj = 0, j=1..5 (система линейных однородных уравнений)
Интерпретация такая: какой бы ход ни сделал наш оппонент, в среднем результат будет ничейным.

Дополнительно, по условию задачи:
(2) S = х1 + x2 + x3 + x4 + x5 = 1
(3) 0 <= х(i) <= 1, i =1..5

Таким образом необходимо найти решение (если оно есть) для системы {(1),(2),(3)}
Если нет решения – то и непроигрышной стратегии нет.

Дальше я сдаюсь, потому что считать надо :-))
Простого и красивого решения изначальной задачи (поиск стратегии) я не увидел.

Ну что Вы, конечно же нет, о выигрыше никто ничего и не говорил.
Я правильно понял, что нам нужно найти некие частные вероятности очередного хода, чтобы ожидаемое МО было равным нулю при любом броске соперника? то есть, допустим у нас есть набор частных вероятностей: x(1)=0,12, x(2)=0.16,x(3)=0.22,x(4)=0.33,x(5)=0.17, при каждом очередном ходе мы встряхиваем мешок где лежат 12 бочонков "1", 16 бочонков "2", 22 бочонка "3", 33 бочонка "4", 17 бочонков "5", вытаскиваем 1 бочонок и делаем соответствующий ход, при этом на длительной дистанции наше МО должно оказаться равно 0?

Дела давно минувших дней

Больше десяти лет назад при разработке корпоративной системы подумал: в Windows есть всякие игрушки типа пасьянса, минера и т.п., а нашей системе нет. И дня за три-четыре встроил в систему игрушку Орел-Решка.

Игра проста.
Машина предлагает игроку задумать число 0 или 1 и нажать любую клавишу, игрок выполняет, машина выдает на экран предположение о задуманном, игрок вводит задуманное число, система сравнивает предположение и задуманное, выдает протокол и статистику на экран. Цикл повторяется.
Для выигрыша достаточно набрать больше 50% очков. Игрок мог завершить игру в любой момент.
Единственное условие: зачет результата игры производился лишь в том случае, если было сделано не менее 101 хода. Интерфейс простейший, поэтому эти ходы можно было сделать менее, чем за минуту.

Было реализовано четыре уровня сложности: от Новичка (по сути машиной использовался имевшийся по рукой датчик случайных чисел) до Чемпиона (с авторскими ухищрениями).


Рис.1 Меню

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

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

Чтобы показать как это выглядит реально, сыграл для примера начало партии. Числа вводил особо не задумываясь. Результат игрока после 13 ходов виден (30.77%). Нижняя строка с ником пользователя – это статистика результатов его предыдущих партий.


Рис.2 Протокол партии

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

Вчера почитал условие, показалось интересным.

Хотел предложить свою стратегию решения. Оказалось, что она практически совпадает с предложенной Зенкером.

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

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

Вопрос в том, как найти оптимальный набор бочонков?
Я думаю, надо двигаться асимптотически шаг за шагом.
То есть в качестве первого (точнее нулевого) шага взять предложенный в первом посте расчет МО. Фактически для равных вероятностей выпадения каждого из пяти чисел от 1 до 5. Вероятность этого для каждого числа равна 0,2. При этом таблица вероятностей для каждой из двух рук своя. И расчет МО для каждого тоже свой.
Далее для второй руки разрешить изменение вероятностей в пределах скажем 0,05.
При этом изменение производится таким образом, чтобы его МО стало наибольшим. После этого производится изменение первой руки с учетом изменившейся вероятности и т.д.
В процессе иттерации допустимое изменение вероятности должно постепенно уменьшаться.
При сходимости этого процесса, начиная с определенного шага эти вероятности для двух рук станут одинаковыми. Это и будет оптимальная стратегия.

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

Попробую на досуге реализовать описанную схему, если кто-то меня не опередит.

Это сообщение отредактировал magystr - 22/01/2009, 20:34

Кстати.
Второй вариант получения какого-то решения - движение от простого к сложному.

То есть сначала то же самое для двух цифр 1 и 2.

В этом случае решение очевидно.
В мешке должны находиться только бочонки (можно и один) с числом 1.

Тогда при ЛЮБОЙ стратегии оппонента мы гарантируем себе непроигрыш.

Далее перейти к трем бочонкам. И т.д.

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

Это сообщение отредактировал magystr - 22/01/2009, 20:51

Да.
Вот тут быстро прикинул.
Для чисел 1,2 и 3 НЕПРОИГРЫШНАЯ стратегия такая.
Вероятность числа 1 - 0,5
вероятность числа 2 - 0,2
вероятность числа 3 - 0,3

То есть в мешке должно находиться 5 "единичек", 2 "двойки" и 3 "тройки", извлекаемые абсолютно случайным образом.

Желающие могут попытаться оппровергнуть мою гипотезу, предложив ЗАВЕДОМО выигрышную стратегию против предложенной.

Это сообщение отредактировал magystr - 22/01/2009, 21:20

Ну что Вы, конечно же нет, о выигрыше никто ничего и не говорил.
Я правильно понял, что нам нужно найти некие частные вероятности очередного хода, чтобы ожидаемое МО было равным нулю при любом броске соперника? то есть, допустим у нас есть набор частных вероятностей: x(1)=0,12, x(2)=0.16,x(3)=0.22,x(4)=0.33,x(5)=0.17, при каждом очередном ходе мы встряхиваем мешок где лежат 12 бочонков "1", 16 бочонков "2", 22 бочонка "3", 33 бочонка "4", 17 бочонков "5", вытаскиваем 1 бочонок и делаем соответствующий ход, при этом на длительной дистанции наше МО должно оказаться равно 0?

Алексей, Вы всё абсолютно правильно поняли. Наш "мешок" (генератор случайных чисел) должен быть настроен на формирование нашего "хода" (1,2,3,4 или 5) с заранее заданными фиксированными вероятностями. Такими - чтобы все пять условных матожиданий выигрыша/проигрыша были равны нулю. Если конечно есть решение у соответствующей системы уравнений (см.выше). Именно в этом моё предположение (за правильность не ручаюсь, но чую что прав). Найдём такой набор вероятностей - получим Оптимальную Стратегию. При этом устройство "мешка" (реализация ГСЧ) - непринципиально, важно лишь, что он настраивается как нам надо.

Длительная дистанция тут ни при чём. Все "испытания" независимы и МО у них совпадает. (На то оно и МО - характеристика случайной величины).


Поправка по матрице результатов (выше я опечатался)
А::
0, -3, 2, 3, 4
3, 0, -5, 2, 3
-2, 5, 0, -7, 2
-3, -2, 7, 0, -9
-4, -3, -2, 9, 0

Для фрагмента 3х3 легко заметить, что {5;2;3} является невырожденным решением системы трёх линейных однородных уравнений.
И после нормировки получаем вероятности Х={0.5; 0.2; 0.3} - об этом совершенно справедливо написал magystr.