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

Направленные игры без запретов

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

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

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

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

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

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

#заготовка 1 в будущее
from time import process_time as prt
def piA(pos, swin, X):
  y = [pos + 1, pos + 2, 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 * 3]
  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 = 140
LW = {0: set(), 1 : set()}
G = set(range(1,swin))
Ans = {}
t = 0 
while t < 6 > 0:
  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)} {sorted(R)}')
print(f'{len(Ans)=} time={prt()-tm0}')

#заготовка 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}')

Печать