Теория:
Для решения заданий определим понятия: выигрышная стратегия, выигрышная позиция, проигрышная позиция, правильный ход, неправильный ход, дерево игры.
По определению теория игр — это раздел математической экономики, изучающий оптимальность стратегий. Оба участника в рассматриваемых задачах, назовём их Первый и Второй, знают, кто при правильно выбранной стратегии придёт к выигрышу, а кто — к проигрышу.
Ходы, реализующие оптимальную стратегию, называют правильными.
Позицию, из которой хотя бы один ход ведёт в выигрышную позицию, называют проигрышной.
Позицию, из которой все ходы ведут в проигрышную позицию, называют выигрышной.
Игрок, создающий позицию, из которой у другого игрока есть ходы только в проигрышные позиции, обладает выигрышной стратегией.
Ход, который максимально увеличивает, например, одну из куч, называют сильным ходом. Соответственно, слабый ход — ход, при котором увеличение минимально.
Как правило, для анализа игры создаётся графическая модель — дерево игры, в которой рассматриваются все ходы участников и определяется оптимальная стратегия.
Или таблица, которая также отображает дерево игры.
Пример
Два игрока играют в следующую игру. Перед ними лежат две кучки камней, в первой из которых — \(3\), а во второй — \(2\) камня. У каждого игрока неограниченно много камней. Игроки ходят по очереди. Ход состоит в том, что игрок увеличивает в \(2\) раза число камней в одной из куч или добавляет \(3\) камня в одну из куч. Выигрывает игрок, после хода которого в одной из куч становится не менее \(18\) камней. Кто выигрывает при правильной игре? Каким должен быть первый ход выигрывающего игрока?
Решение
Запишем коротко условия ходов и выигрышную ситуацию:
\(*2\),
\(+3\),
\(>=18\).
Построим таблицу, отображающую дерево игры.
Изобразим в ней все возможные ходы Первого игрока.
Кон | П |
\(3\), \(2\) | \(6\), \(2\) |
\(6\), \(2\) | |
\(3\), \(4\) | |
\(3\), \(5\) |
Дополним таблицу возможными ходами Второго игрока. Так как два первых хода одинаковые (\(6\), \(2\)), будем рассматривать только один из них.
Кон | П | В |
\(3\), \(2\) | \(6\), \(2\) | \(12\), \(2\) |
\(6\), \(4\) | ||
\(9\), \(2\) | ||
\(6\), \(5\) | ||
\(3\), \(4\) | \(9\), \(4\) | |
\(3\), \(8\) | ||
\(6\), \(4\) | ||
\(3\), \(7\) | ||
\(3\), \(5\) | \(9\), \(5\) | |
\(3\), \(10\) | ||
\(6\), \(5\) | ||
\(3\), \(8\) |
Ход Первого игрока (\(6\), \(2\)) будет выигрышной позицией, так как все ходы Второго игрока в этом случае ведут к проигрышу.
Из позиции (\(12\), \(2\)) Первый игрок сделает (\(24\), \(2\)) и выиграет; также из позиции (\(9\), \(2\)) сделает (\(18\), \(2\)) — это выигрыш.
Позиции (\(6\), \(4\)) и (\(6\), \(5\)) приведут к выигрышу через ход.
В | П | В | П |
\(6\), \(4\) | \(6\), \(7\) | \(12\), \(7\) | \(24\), \(7\) |
\(6\), \(14\) | \(6\), \(28\) | ||
\(9\), \(7\) | \(18\), \(7\) | ||
\(6\), \(10\) | \(6\), \(20\) | ||
\(6\), \(5\) | \(6\), \(8\) | \(12\), \(8\) | \(24\), \(8\) |
\(6\), \(16\) | \(6\), \(32\) | ||
\(9\), \(8\) | \(18\), \(8\) | ||
\(6\), \(11\) | \(6\), \(22\) |