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

BFS для игровой стратегии

Придумаем игру с достаточно сложными правилами для реализации
Вначале рассмотрим одну кучу
Два игрока, Алиса и Боб играют в следующую игру .
Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Алиса.
За один ход игрок может:

добавить в кучу 1 или 5 камней (то есть применить операцию сложения)
увеличить количество камней в два или три раза (то есть применить операцию умножения)
игрок не может повторять операцию хода соперника
(то есть, если Алиса применила сложение, то Боб должен делать умножение и наоборот)

Игра завершается, когда количество камней в куче становиться не менее 100.
Если при этом количества камней кратно 4 , то победителем считается игрок, сделавший последний ход,
а если количество камней некратно 4, то этот игрок считается проигравшим и считается, что его соперник сделал ход.

Способ решения bfs - метод "раскраски"
Для решения от множества вершин перейдем к позициям/ребрам.
Каждая позиция - (вершина, команда выхода) - для таких вершин и будем производить раскраску
После завершения раскраски - анализ и разбиение вершин на две доли (выигрышные, проигрышные)
Для выигрышных определим возможные "команды выхода" (для проигрышных - это все)
Для решения задачи определимся с переменными для описания задачи и хранения результатов.

swin - параметр завершения игры (в примене swin = 100)
G - множество стартовых вершин (в примере G =set(range(1,swin)
H - множество ходов/наборов ходов. (в примере можно считать, что
H = { 'a':['x+3', 'x + 5'], 'b':['x * 2', 'x * 3']} )
E - множество "выходящих ребер" (декартовое произведение G на H}
также определим словарь для хранения "выигрышных" и "проигрышных" вершин
LW = {0 : {'W'} , 1:{L'}} 'W' - это "кружок", в который ходить не надо, "L" - это "прямоугольник", в который надо стремиться
создаем словарь для промежуточных ответов Rez
создадим словарь для вершин (к какой доли относятся, возможные выходы)

Для решения потребуются подпрограммы:

def fz - будет получать множество значений
def piA - определять является ли позицая "хорошей" для игрока A ("кружок")
def piB - определять является ли позицая "хорошей" для игрока B ("прямоугольник")
def step - поиск "кружков" на нечётных тактах и определение "прямоугольников" на четных

# Пока только настройка и получение смежных вершин
def fz(x, k, H, swin): #получение окружения 
  # x - вершина, k - команда, H - словарь команд, 
  if not (k in H) : return set() #команда неприменима
  A = [eval(s) for s in H[k]] # список фактических переходов
  sw, m = swin # параметры игры - можно исследовать снаружи
  for i in range(len(A)): #преобразование "внешних позиций в L/W
    y = A[i]
    if y >= sw and (y % m) == 0: A[i] = 'L' # это "прямоугольник" - хотим попасть
    elif y >= sw and (y % m)!=0 : A[i] = 'W' # это "кружок" - не хотим попадать
  return set(A)    
# Основная настройка
swin = (100, 4) #для проверки финальных состояний
G = set(range(1, swin[0])) #множество стартовых вершин (для удобства)
H = {'a':('x + 1', 'x + 5'), 'b':('x * 2', 'x * 3')} # словарь команд
x = int(input())
for k in H :
  z = fz(x, k, swin, H)
  print(f' {x=} {k=} {z}')

Дописываем остальное. Стараемся все реализовать в самом общем варианте.
Пока реализуем, для получения информации по ребрам
(подпрограмму fz убираем с экрана)

def piA(poss, swin, X, H): # проверка ребра(позиции) на "выигрышность"/"кружок"
    # X - множество "прямоугольников"
    pos, kp = poss #распаковка pos - вершина, kp - команда выхода
    r = fz(pos, kp, H, swin) # значение "стоков"
    for p in r : # поиск "выигрышного стока"
      js = len([(p,k) for k in H if (k !=kp) and not ((p,k) in X)]) # всех возможных выходы в "прямоугольник"
      if js == 0 : #нашли сток, из которого нет хода в "прямоугольник" 
        return True
    return False #"прямоугольник не нашли"
def piB(poss, X, H): # проверка ребра(позиции) на "проигрышность"/"прямоугольность"
    # X - множество "кружков"
    pos, kp = poss
    r = fz(pos, kp,H, swin)
    for p in r: #проверка, что все стоки "кружки"
      js = len([(p,k) for k in H if (k !=kp) and ((p,k) in X)]) # всех возможные выходов в кружок
      if js == 0 : # у соперника есть ход, из которого нельзя попасть в "кружок"
        return False
    return True #все ответы соперника дают возможность перехода в "кружок"
def step(S, X, swin, t, H): #организация ходов по очереди
  if t % 2 == 1 : #в нечетные такты ищем "кружки", в четные определяем "прямоугольники"
    return set([p for p in S if piA(p, swin, X, H)])
  return set([p for p in S if piB(p, X, H)])
    
swin = (30,4) #упрощаем, чтобы все ответы "поместились"
G = set(range(1, swin[0]))
H = {'a':('x + 1', 'x + 5'), 'b':('x * 2', 'x * 3')}
E = set([(a,k) for k in H for a in G])
#LW -словарь для хранения "прямоугольников" (ключ 1) и "кружков" (ключ 0)
LW = {0: set([('W',k) for k in H]), 1 : set([('L',k) for k in H])}
Rez = {} # промежуточные результаты
t = 0 # номер такта
while len(E) > 0 : #пока есть необработанные ребра
  t += 1 # переход хода
  R = step(E, LW[t % 2], swin, t, H)
  # R - найденные кружки(t%2 == 0) или "прямоугольники" (t%2 == 1)
  LW[(t + 1) % 2] = LW[(t + 1) % 2].union(R)
  E = E - R # выводим "раскрашенные" ребра из обработки
  Rez[t] = R # фиксация результата
  print(f'{t=} {len(R)=} {len(E)=} {sorted(R)}')

Пока получена раскраска ребер.
Теперь надо решить с раскраской вершин.
Если из вершины идет хотя бы одно "выигрышное ребро", то вся вершина выигрышная
То есть, если вершина есть Rez[i] при нечетных i, то вершина "выигрышная"
Аналогично - вершина проигрышная, если все её ребра в R[i] с четными номерами
Оформим решение в подпрограмму, возвращающую Rez иопределим
словарь Ans с ключом <вершина> и значениям = <номер такта появления, вершина, команд выхода, Выигрышная/проигрышная)

# Настройка параметров
swin = (30, 4)
G = set(range(1, swin[0]))
H = {'a':('x + 1', 'x + 5'), 'b':('x * 2', 'x * 3')}
E = set([(a,k) for k in H for a in G])
LW = {0: set([('W',k) for k in H]), 1 : set([('L',k) for k in H])}
Rez = solve(E, LW, swin, H)
print(f'{len(Rez)=} {len(E)=} {len(LW[0])=} {len(LW[1])=}')  
Ans = {} # словарь по вершинам
for i in range(1, len(Rez), 2): #Отбираем "выигрышные позиции" (они на нечетных тактах)
  for poss in Rez[i] : #poss исходящее ребро <вершина, команда выхода>
    pos, k = poss #распаковка ребра
    if not(pos in Ans): #это новый "кружок"
      Ans[pos] = [i, pos, k, True]
    else : # обновляем данные о "кружке" 
      Ans[pos][2] += k # добавляем команду выхода, возможно не оптимальную
for i in range(2, len(Rez), 2): #Отбираем "проигрышные позиции"
  for poss in Rez[i] :
    pos, k = poss #распаковка ребра
    if not(pos in Ans): #новый "прямоугольник
      Ans[pos] =[i, pos, k, False]
    elif Ans[pos][3] == False:
      Ans[pos][0] = i #выбираем самое "долгое" сопротивление
      Ans[pos][2] = k + Ans[pos][2] # в порядке сопротивления 
#Словарь по тактам 
Takt = {}    
ss=['False', 'True']
for i in range(1, len(Rez)):
  Takt[i] = (ss[i%2], sorted([Ans[p][1] for p in Ans if Ans[p][0] == i]))
  print(f'takt={i} {Takt[i][0]}/{len(Takt[i][1])} = {Takt[i][1]}')
print(Ans[10])

"Уберем" получение Ans в подпрограмму solvе и попробуем немного изменить условие задачи
"Нельзя повторять команду соперника" вместо "Нельзя повторять операцию команды соперника"
Для решения достаточно изменить только словарь команд H

# Настройка параметров
swin = (30, 4)
G = set(range(1, swin[0]))
H = {'a':('x + 1',), 'b':('x + 5',), 'c':('x * 2',), 'd':('x * 3',)}
E = set([(a,k) for k in H for a in G])
LW = {0: set([('W',k) for k in H]), 1 : set([('L',k) for k in H])}
Ans, tt = solve(E, LW, swin, H)
#Словарь по тактам 
Takt = {}    
ss=['False', 'True']
for i in range(1, tt + 1):
  Takt[i] = (ss[i%2], sorted([Ans[p][1] for p in Ans if Ans[p][0] == i]))
  print(f'takt={i} {Takt[i][0]}/{len(Takt[i][1])} = {Takt[i][1]}')
v = int(input())
print(f'{v=} {Ans[v]=}')

Можно проверить решение.
Так для вершины 3 Ans[3] покажет, что нужно выполнить переход по команде d, то есть в вершину 9
Из вершины 9 соперник может перейти в (а = 10, b = 14, c = 18)
Из 18 переход возможен по b или a (b=23, a = 19) откуда соперник или проиграет (умножением) или сложением перейдет в число кратное 4
Из 14 переход по a в 15 - соперник или проигрывает умножением, или сложением перейдет в число 16, далее умножем
Из 10 переход по b в 15 - соперник или проигрывает умножением или сложением перейдет в число 16, далее умножаем

Печать