Файл: Теория игр. Поиск выигрышной стратегии.doc

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 09.12.2023

Просмотров: 604

Скачиваний: 12

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
...



















2












–2
2
–1
1
1
1

оценка позиции 12 равна (–2)

Решение Задания 19.

  1. Ответ: 14 (позиция с оценкой –1).

Решение Задания 20.

  1. Ответ: 7 и 13 (позиции с оценкой 2).;

Решение Задания 21.

  1. Ответ: 12 (позиция с оценкой –2).

Решение (программа, А. Кабанов)

  1. Напишем функцию, которая определяет существование выигрышной стратегии не более чем за moveWin ходов обоих игроков. Функция имеет три параметра: количество камней S, число совершённых ходов prevMoves и наибольшее возможное количество ходов moveWin.

def f( S, prevMoves, moveWin ):

if S >= 29:

return prevMoves % 2 == moveWin % 2 # 1

if prevMoves == moveWin: return 0 # 2

if (prevMoves+1) % 2 == moveWin % 2: # 3

return f(S+1, prevMoves+1, moveWin) or \

f(S*2, prevMoves+1, moveWin)

else:

return f(S+1, prevMoves+1, moveWin) and \ # 4

f(S*2, prevMoves+1, moveWin)

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

  2. Варианты, требующие большей глубины, чем moveWin, отбрасываются (метка #2).

  3. Если moveWin нечётное, то проверяется возможность победы первого игрока, для чётных победа второго игрока. При анализе следующих ходов мы исходим из принципа, что если их чётность совпадает с moveWin, то достаточно победы в одном из них (метка #3). В противном случае победа должна быть во всех случаях (метка #4).

  4. Для нахождения ответа на 19 задание найдём значение S, для которого существует выигрышная стратегия за 2 хода.

print( '19)', *[s for s in range(1,29) if f(s,0,2)] )

  1. Для нахождения ответа на 20 задание найдём значения S, для которых не существует выигрышной стратегии за 1 ход, но существует за 3 хода.

print( '20)', *[s for s in range(1,29)

if not f(s,0,1) and f(s,0,3)] )

  1. Для нахождения ответа на 21 задание найдём значение S, для которого не существует выигрышной стратегии за 2 хода, но существует за 4 хода.

print( '21)', *[s for s in range(1,29)

if not f(s,0,2) and f(s,0,4)] )

  1. Ответ:

19) 14

20) 7 13

21) 12

Решение (программа)

  1. напишем, как и в разборе задачи Р00 (см. ниже), функцию, определяющую оценку позиции в виде числа:

TARGET = 29

def gameResult( S ):

...

Константа TARGET обозначает количество камней, при котором игра заканчивается.

  1. условие окончания игры (проигрыш того, кто получил такую позицию, оценка 0):

if S >= TARGET: return 0

  1. определяем рекурсивно оценки всех возможных ходов:

nextCodes = [ gameResult(S+1), gameResult(S*2)]

  1. определяем, нет ли среди возможных ходов хода в проигрышную позицию:

negative = [c for c in nextCodes if c <= 0]

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

if negative:

res = -max(negative) + 1

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

else:

res = -max(nextCodes)

  1. вот полная функция

TARGET = 29

def gameResult( S ):

if S >= TARGET: return 0

# рекурсивно определяем коды всех возможных ходов

nextCodes = [ gameResult(S+1), gameResult(S*2) ]

negative = [c for c in nextCodes if c <= 0]

if negative:

res = -max(negative) + 1

else:

res = -max(nextCodes)

return res

  1. и основная программа, которая ее вызывает:

results = [(S,gameResult(S)) for S in range(1,TARGET)]

print( '19:', [S for S, R in results if R == -1] )

print( '20:', [S for S, R in results if R == 2] )

print( '21:', [S for S, R in results if R == -2] )

Здесь сначала определяются оценки позиции для всех возможных начальных значений S; они сохраняются в массиве кортежей (S,оценка). Затем выбираются результаты с оценкой –1 (решение задачи 19) , 2 (решение задачи 20) и –2 (решение задачи 21).

Ещё пример задания:


P-00(демо-2021).Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней. В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.

Задание 19.

Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
В задачах такого типа «неудачным» считается такой ход Пети, после которого

  1. он проиграет, хотя мог бы выиграть, ИЛИ...

  2. он проиграет быстрее (за меньшее число ходов) чем мог бы, если бы старался затянуть игру.


Задание 20.

Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:

− Петя не может выиграть за один ход;

− Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.

Найденные значения запишите в ответе в порядке возрастания.

Задание 21

Найдите минимальное значение S, при котором одновременно выполняются два условия:

– у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;

– у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.

Решение (программа, А. Кабанов)

  1. Напишем функцию, которая определяет существование выигрышной стратегии не более чем за moveWin ходов обоих игроков. Функция имеет четыре параметра: количество камней в первой куче a, количество камней во второй куче b, число совершённых ходов prevMoves и наибольшее возможное количество ходов moveWin.

def f( a, b, prevMoves, moveWin ):

if a + b >= 77:

return prevMoves % 2 == moveWin % 2 # 1

if prevMoves == moveWin: return 0 # 2

h = [ f(a+1, b, prevMoves+1, moveWin), # 3

f(a, b+1, prevMoves+1, moveWin),

f(a*2, b, prevMoves+1, moveWin),

f(a, b*2, prevMoves+1, moveWin)]

return any(h) if (prevMoves+1) % 2 == moveWin % 2 \ # 4

else all(h)


  1. Если moveWin нечётное, то проверяется возможность победы первого игрока, для чётных победа второго игрока. (метка #4).

  2. При анализе следующих ходов мы исходим из принципа, что если их чётность совпадает с moveWin, то достаточно победы в одном из них. В противном случае победа должна быть во всех случаях (метка #4).

  3. Для удобства можно составить список из значений функций для следующих ходов. Для проверки условий можно использовать any и all (метка #4).

  4. Для выполнения 19 задания создадим функцию f1 аналогичную f, кроме замены последней строки на

return any(h)

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

print('19)', min(s for s in range(1,70) if f1(7,s,0,2)) )

  1. Для нахождения ответа на 20 задание найдём значения S, для которых не существует выигрышной стратегии за 1 ход, но существует за 3 хода.

print('20)', *[s for s in range(1,70)

if not f(7,s,0,1) and f(7,s,0,3)])

  1. Для нахождения ответа на 21 задание найдём значение S, для которого не существует выигрышной стратегии за 2 хода, но существует за 4 хода.

print('21)', min(s for s in range(1,70)

if not f(7,s,0,2) and f(7,s,0,4)))

  1. Ответ:

19) 18

20) 31 34

21) 30

Решение Задания 19.

  1. возможно, что есть несколько значений S, которые удовлетворяют условию; нас интересует минимальное из них;

  2. при минимальном подходящем значении S общее количество камней в двух кучах увеличивается максимально быстро до значения 77 или большего;

  3. поскольку удвоение увеличивает количества камней в куче быстрее, чем добавление одного камня, можно сделать вывод, что для минимального подходящего значения S игроки своими ходами дважды удвоили бОльшую из двух куч;

  4. предположим, что бОльшая куча имеет 7 камней, и S = 7; тогда наибольшее число камней, которое можно получить после одного хода каждого игрока – 7 + 7*2*2 = 35; так как 35 < 77, игра не окончена и этот вариант не подходит; делаем вывод, что S > 7

  5. таким образом, дважды была удвоена вторая куча; условие окончания игры

7 + S*2*2  77,

откуда получаем S  17,5; это значит, что Smin = 18

  1. Ответ: 18.

Решение Задания 20.

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

  2. рассмотрим такие (проигрышные) позиции; при удвоении второй (бОльшей) кучи в сумме должно получаться 76 камней (недостаточно для выигрыша):

Смотрите также файлы