Главная страница
Навигация по странице:

  • Решение (построение таблицы).

  • Решение Задания 19. Ответ: 14 (позиция с оценкой –1). Решение Задания 20.

  • TARGET = 29 def

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

  • else

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

    		•

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


    Скачать 0.73 Mb.
    НазваниеТеория игр. Поиск выигрышной стратегии
    Дата01.04.2022
    Размер0.73 Mb.
    Формат файлаdoc
    Имя файлаege1921.doc
    ТипДокументы
    #434706
    страница2 из 7
    1   2   3   4   5   6   7

    Пример задания:


    P-01(демо-2022).Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит

    куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в два раза. Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 29. Победителем считается игрок, сделавший последний ход, т.е. первым получивший кучу, в которой будет 29 или больше камней.

    В начальный момент в куче было S камней, 1 ≤ S ≤ 28.

    Задание 19.

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

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

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

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

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

    Задание 21

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

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

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

    Решение (построение таблицы).

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

    2. очевидно, что при всех S ≥ 15 Петя выигрывает свои первым ходом, увеличив количество камней в куче вдвое; это позиции с оценкой 1 (выигрыш в один ход):

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











































      1
      1
      1

    3. все возможные ходы из позиции 14 (это 15 и 28) ведут в позиции с оценкой 1, то есть 14 – проигрышная позиция с оценкой –1: проигрыш за один ход (Петя, начинающий игру, может ходить любым способом, но Ваня своим первым ходом сразу сможет выиграть):

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








































      –1
      1
      1
      1

    4. гарантированный выигрыш за 2 хода возможен для тех позиций, из которых есть ход в позицию с оценкой –1, то есть, из позиций 13 и 7; оценка этих позиций – 2:

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



















      2















      2
      –1
      1
      1
      1

    5. дальше определяем все позиции, откуда все ходы ведут в позиции с оценкой 1 или 2 (все они уже заполнены в таблице); определяем, что это только позиция 12 (возможные ходы – 13 с оценкой 2 и 24 с оценкой 1):

    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. напишем, как и в разборе задачи Р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).
    1   2   3   4   5   6   7

    написать администратору сайта