Статья Автор: Лебедев Дмитрий Алексеевич

Игры с запретами

Рассмотрим следующую модель игры для двух игроков

Играют два игрока Петя и Ваня (Петя всегда ходит первым)
Задано V - множество чисел допустимых в игре
Каждый игрок имеет свой набор команд
Запрещено использовать/получать числа, которые уже были использованы в игре
Проигравшим считается игрок, который не сможет сделать ход

Пример игры
Правила игры

Множество игровых чисел - натуральные числа, меньшие N = 30
start - натуральное число, меньшее N
Петя может преобразовать числа a по одному из следующих правил
- увеличить или уменьшить на 2
- увеличить или уменьшить в 2 раза (деление целочисленное)
- "приписать к числу" слева или справа цифру 2
Ваня может преобразовать числа a по одному из следующих правил
- увеличить или уменьшить на 3
- увеличить или уменьшить в 3 раза (деление целочисленное)
- "приписать к числу" слева или справа цифру 3
Оба игрока не могут получать числа, которые уже использовались

Задание
Для заданного start определить, у кого из игроков есть ВС (выигрышная стратегия)

Для решения задания надо определить подрограммы

piA(x, V), piB(x, V) - подпрограммы получения возможных ходов игроками
(без учета траекторий)
Подпрограмма шага (рекурсия, обход в глубину)
game(st,V, track, tt) - где:
- st - вершина входа
- V - множество разрешенных вершин
- track - путь до st (запретные позиции)
- tt - служебный список ( tt[0] - такт работы, tt[1] - максимальная длина track)

from time import process_time as prt
def piA(n,V, a = 3):
    ss = set()
    sn = str(n)
    a1, a0 = int(str(a)+ sn), int(sn + str(a))
    xx = (n//a, n * a, n - a, n + a, a1, a0)
    ss = set([x for x in xx if (x in V ) and (x != n)])
    return sorted(ss)    
def piB(n,V, a = 2):
    ss = set()
    sn = str(n)
    a1, a0 = int(str(a)+ sn), int(sn + str(a))
    xx = (n//a, n * a, n - a, n + a, a1, a0)
    ss = set([x for x in xx if (x in V ) and (x != n)])
    return sorted(ss)    
def pi(n, V, j) :
    if j % 2 == 1 :
        return piA(n,V)
    return piB(n,V)
def game(st,V):
    track.append(st)
    tt[0] += 1
    trk = set(track)
    for x in pi(st, V, tt[0] % 2) :
        if x in trk : continue
        fl = game(x,V)
        if fl == False :
          if len(track) >  tt[1]:
            tt[1] =len(track)
            tt[2] = tuple(track)
          return True 
        while track[-1] != st :
            track.pop()
            tt[0] -=1
    return False
        
t0 = prt()
n = 32
V = set([i for i in range(1,n+1)])
kk = 0
for start in range(1,n):
    track = []
    tt = [0, 0, None]
    fl = game(start,V)
    if fl  :
        kk += 1
        print(f'{start=} {pi(start, V, 1)} ...  ans={fl} {track} {tt} ')
print(f'{kk=} time={prt() - t0} {n=}')

from time import process_time as prt
#from sympy import isprime
def piA(n,V, a = 3):
    ss = set()
    sn = str(n)
    a1, a0 = int(str(a)+ sn), int(sn + str(a))
    xx = (n//a, n * a, n - a, n + a, a1, a0)
    #xx = (n * a, n + a, a1, a0)
    ss = set([x for x in xx if (x in V ) and (x != n)])
    return sorted(ss)    
def piB(n,V, a = 2):
    ss = set()
    sn = str(n)
    a1, a0 = int(str(a)+ sn), int(sn + str(a))
    xx = (n//a, n * a, n - a, n + a, a1, a0)
    #xx = (n * a, n + a, a1, a0)
    ss = set([x for x in xx if (x in V ) and (x != n)])
    return sorted(ss)    
def pi(n, V, j) :
    if j % 2 == 1 :
        return piA(n,V)
    return piB(n,V)
def game(st,V):
    track.append(st)
    tt[0] += 1
    trk = set(track)
    for x in pi(st, V, tt[0] % 2) :
        if x in trk : continue
        fl = game(x,V)
        if fl == False :
          if tt[0] % 2 == 0 and len(track) >=  tt[1]:
            tt[1] =len(track)
            tt[2] = tuple(track)
          return True 
        while track[-1] != st :
            track.pop()
            tt[0] -=1
    return False
        
t0 = prt()
n = 31
V = set([i for i in range(1,n+1)])
kk = 0
for start in range(1,n+1):
    track = []
    tt = [0, 0, None]
    fl = game(start,V)
    if fl == True :
        kk += 1
        print(f'{start=} {pi(start, V, 1)} ...  ans={fl} {track} {tt} ')
print(f'{kk=} time={prt() - t0} {n=}')

Печать