задача С3 ЕГЭ Информатика -игра в камушки.

[eugrita]

задача С3 ЕГЭ Информатика -игра в камушки.
-------------------------------------------
Правила: в куче N камней
2 (несколько)игроков ходят по очереди у каждого есть свой конечный набор ходов
(индивидуальный или общий)- где - количество забираемых камней из кучи. (куч может быть тоже несколько)
Выигрывает тот кто сделал последний ход.
------------------------------------------------------------------------------
Я написал на эту тему несколько программ в порядке усложнения (используют рекурсию).
1)прохождение по листьям дерева, счет кол-ва выигрышей 1-го и 2-го игрока (при всех вариантах развития)
2)Нахождение выигрышных позиций 1 и 2 игрока
3)Разработка интерактивной игры компьютер играет по стратегии 1 ход вперед.
(Т.е. просмотр вершин следующего уровня переход к выигрышной и уклонение от проигрышной в случ их наличия.
Полезно на бумаге построить несколько деревьев игры например для N=30 m1=4, m2=3
или N=40, m1=5,m2=4 Выигрышные позиции 1 игрока заштриховать красным, а 2-го-чернвм.
В текущем узле предварительно просматривается все узлы следующего уровня: если для 1-го есть красная вершина - идти туда, если есть черная - не идти. В случае отсутствия красных и черных вершин стратегия пока не уточняется-можно по random. (Возможны и более тонкие стратегии.)
Внизу общего дерева игры могут быть красные и черные поддеревья различной высоты. (какой?)

1)Очень хотелось бы [b]классификации данной задачи с т.зрения теории игр и математического обобщения - типа выбора из конечного числа альтернатив каждого шага. Как понимаю ,эта игра относится к классу многошаговых позиционных игр.
2) нахождение реальных экономических игровых задач под эту модель игра с выбором постоянных альтернатив без случайности, с возможностью компьютерного просмотра дерева игры, выигрышных позиций [и выбором стратегий/b].
нужен другой критерий выигрыша-проигрыша -не количественный после каждого хода, а некий глобальный (аналог-в куче кончились камни).
Некоторые примеры я нашел в интернете Сайт
Однако разобранные там деревья очень малы чтобы допускать компьютерную обработку.
Нужны достаточно многошаговые задачи или с сильным ветвлением (конечно не с сложностью типа шазмат)

[folk]

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

2) нахождение реальных экономических игровых задач под эту модель игра с выбором постоянных альтернатив без случайности, с возможностью компьютерного просмотра дерева игры, выигрышных позиций [и выбором стратегий/b].

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

[eugrita]

Source of the post
Могу ошибаться, но для данной задачи должна по идее выигрышная стратегия которая строится от конечного результата.

2) нахождение реальных экономических игровых задач под эту модель игра с выбором постоянных альтернатив без случайности, с возможностью компьютерного просмотра дерева игры, выигрышных позиций [и выбором стратегий/b].

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

Я понял пока так, что то ,что меня интересует, отдаленно похожее на описанную игру называется
детерминированная задача теории принятия решений (ТПР),т.е с функциональной зависимостью исходов от альтернатив или позиционная игра с полной информацией. хочу найти подходящуютакую модель в задачах микроэкономики.
Я также не хочу скатываться к задаче динамического программирования хотя именно она наиболее близка к данной.Задача динамического программирования использует просчитываемый критерий и решается с конца -там все известно как в игре в камни.В своей задаче я хотел бы иметь детерминированную модель но с воздействием неизвестного игрокам фактора. Т.е. стратегии должны быть адаптивными, приспосабливающимися к неизвестно-как изменяющимся условиям.
Наверное, придется взять за основу классическую задачу оптимизации производственной программы предприятия.
$$max Ï=\sum_{i=1}^{n}{(p_i-c_i)x_i}-\sum_{j=1}^{m}{q_jy_j}$$
c ограничениями по объему потребления ресурсов. т.е. задачу линейного или квадратичного программирования но рассматриваемую многоэтапно.
При этом цены единицы продукции и единиц сырья (удельных затрат) могут зависеть от номера этапа каким-то неизвестным игрокам но функциональным способом . Прибыль полученная от к-этапа идет на расширение производства, но с учетом меняющихся от к ограничений.
Правда в такой модели я что-то альтернатив не вижу - оптимизация - да, есть да еще на каждом этвпе.
Альтернатива -необходимый элемент задачи ТПР. (рылся в лаботаторных и курсовых по ТПР для студентов) - там тоже - говорят красивые слова об ТПР, альтернативах, а потом скатываются к условной оптимизацииили симплекс-методу
Уже самим фактом принятия модели оптимизации производственной программы предприятия я отошел от понятия игры (пусть даже игры с природой) к понятию пошаговой оптимизации
Ближе к игре наверное задача конкуренции 2 или нескольких производителей одного (нескольких) видов товаров одного назначения