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

Направленные игры c запретами на команды

Играют два игрока А и Б. Ходы по очереди.
Правила

прибавить из списка 1
или умножить/разделить на число из списка 2
запрещается повторять команду соперника
стартовые позиции - натуральные числа не превосходящие N
Проиграл тот, кто не может сделать ход

Способ решения - метод "раскраски" BFS

Определяем piA(pos, swin) - программа, определяющая для ходов игрока A:
есть ли выход за пределы или ход в множество X
возвращает подходящие позиции с указанием команд
Определяем piA(pos) - программа, которая для ходов игрока Б. проверяет,
что все ходы ведут в множество X:
возвращает определившиеся позиции
Определяем step(S, X, t) - S - множество позиций для обработки, X - множество для сравнений , t - такт хода
возвращает множество значений и S которых "подходят" для заданного такта
Основная программа - определяет/инициализирует словари/множества для работы

G - Множество позиций, появление которых в игре разрешено
(пока совпадает с множество исследуемых вершин)
LW = {0:set(), 1:set()} - словарь обработанных позиций, где ключ 1 соответствует "выигрышным позициям",
а ключ 0 "проигрышным"
swin - набор параметров, определяющих игру ("правила завершения")
R - промежуточный результат
Ans - словарь для хранения ответов (при заполнении может пересекаться с множеством "стартовых" фигур

Обработка может вестись несколько тактов, может до окончания "стартовых позиций"
При решении немного оптимизирована используемая память и быстродействие "алгоритма"

from time import process_time as prt
def pi(poss, V):
    pos, k = poss
    ss = set()
    xx = [ (pos + 2, 'a'),(pos + 5, 'b'),(pos + 12, 'c'),(pos * 2, 'd')]
    ss = set([x for x in xx if (x[0] in V ) and (x[1] != k)])
    return sorted(ss)    
def game(st,V):
    track.append(st)
    tt[0] += 1
    for x in pi(st, V) :
        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 = 21
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,'s'),V)
    if fl  :
        kk += 1
        print(f'{start=} {pi((start,'s'), V)} ...  ans={fl} {track} {tt} ')
print(f'{kk=} time={prt() - t0} {n=}')

#заготовка 2 в прошлое
from time import process_time as prt
def piA(pos, swin, X):
  y = [pos - 3, pos - 4, pos // 3]
  for p in y : 
    if p < swin or p in X : return True
  return False
def piB(pos, X):
  y = [pos + 1, pos + 2, pos * 2 ]
  for p in y :
    if (p in X) == False : return False
  return True  
def step(S, X, swin, t):
  if t % 2 == 1 :
    return set([p for p in S if piA(p, swin, X)])
  return set([p for p in S if piB(p, X)])
tm0 =prt()
swin = 13
LW = {0: set(), 1 : set(range(swin, swin*2 + 1))}
G = set(range(swin, 1000))
Ans = {}
t = -1 
while t < 6:
  t += 1
  R = step(G, LW[t % 2], swin, t)
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R)
  G = G - R
  Ans[t] = R
  print(f'{t=} {len(R)} {R}')
print(f'{len(Ans)=} time={prt()-tm0}')

Печать