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

Что наша жизнь. ИГРА!

#Базовая постановка задачи на одну кучу#
Два игрока, Пятачок и Винни, играют в следующую игру.
Перед игроками лежит одна куча из S камней. Игроки ходят по очереди, первый ход делает Пятачок. За один ход игрок может:
- добавить в кучу a₁, a₂,...,a_k  камней (уменьшить количество камней в куче m₁, m₂,...,m_l  камней);
- увеличить количество камней в куче на в  p₁, p₂,...,p_l раз (уменьшить количество камней в куче в  p₁, p₂,...,p_l раз с окрулениес вверх/низ)
Игра заканчивается, если количество камней в куче становится не менее N  (не более N).
Игрок, сделавший последний ход:

, т.е. первым получивший такую позицию, при которой в куче будет не меньше, чем N камней (не более N).

считается победителем
считается проигравшим, то есть победа присуждается его сопернику
считается победителем, если выполнено <условие победы>, иначе считается проигравшим

Изначально количество камней в куче определяется <множеством Старта>:-

множеством простых чисел, меньших чего-то и т.п.

Вопросы могут быть интегральные, например:

выигрышная стратегия есть у Пятачка (1 число ответа)
выигрышная стратегия есть у Винни (2 число ответа)
и т.п.

Попробуем использовать модель, аналогичную "машинному обучению с подкреплением"
Первый игрок - это Агент и он стремиться к Победе
Второй игрок - это "Окружающая среда" (ОС) - сообщающая информацию о состоянии
На каждом "такте" (ходе) ОС сообщает информацию о том, куда "можно/безопасно" ходить,
а куда ходить "нельзя/запрещено"

Общая модель решения

1. Определяем параметры игры (будем использовать короткие имена, как на экзамене)
ee - множество параметров, определяющих игру ee[0] = N
G - множество позиций, которое может находиться в игре (может быть разумным)
St - множество стартовых позиций (если есть ограничения на них)
L,W - множества позиций, определяющих стратегию игры.

L - множество позиций в которые "можно" (то есть это поля, стартуя из которых Агент не имеет ВС (выигрышной стратегии)
W - множество позиций, в которые ходить "запрещено" (то есть поля, стартуя из которых Агент имеет ВС, а пойдя в них тереет ВС)

t - номер "такта" игры(получения информации) - на нечётных тактах получаем информацию от поз оициях в которые "можно" ходить (W),
а на нечетных - о "запрещенных" позициях (L)
R - промежуточный результат исследования для каждого такта
ANS - список ответов ОС (ANS[t] = R)

2. Модель решения

# Заполнение/инициализация множеств G, St, L, W и ee

t, ANS = 0, {}
while ( len(G & St) > 0 ) :
    t += 1
    R = shag (t)
    ANS[t] = R
    if t % 2 == 1 : W = W.union(R)
    if t % 2 == 0 : L = L.union(R)
#  Обработка ответов (словаря ANS)

def fp(n, p) :
  x = n*100 + n*p
  return (x+99)//100
def pi(pos):
  p, k = pos
  v =[(p+x, 1) for x in A] + [(p-x, 2) for x in B] + [(fp(p,x),3)  for x in P]
  w = set()
  for x,y in v :
    if y == k : continue
    if x < ee[0] : w.add((x,y))
    else : w.add(ee[0])
  return w
def shag(t) :
  if t%2 == 1 : return set([p for p in G if pi(p) & L])
  return set([p for p in G if pi(p) <= W])
  
# Входные данные
N, M = 15800, 500# порог окончания, минимальное к рассмотрению
A = [15, 35] #то, что можно прибавлять
B = [7] # то, что можно вычитать
P = [50] # проценты увеличения
# отбор стартовых значений
R = sieve(M, 2*M) # простые числа от P до N
ee =[N, R[0] - max(B)] # параметры игры
G = set([(x,k) for x in range(ee[1], ee[0]) for k in [1,2,3]])
St = set([(x,0) for x in R])
G = G.union(St)
L, W = set([ee[0]]), set()
ANS, t = {}, 0
while len(G & St) > 0 :
  t += 1
  R = shag(t)
  ANS[t] = R & St
  G = G - R
  #print(t, len(G), len(ANS[t]))
  if t % 2 == 1 : W = W.union(R)
  if t % 2 == 0 : L = L.union(R)
ans1 = sum([len(ANS[i]) for i in ANS if i % 2 == 1])
ans2 = sum([len(ANS[i]) for i in ANS if i % 2 == 0])
print(ans1,ans2, max(ANS))

Для решения задания подребуются подрограммы
def shag (t): - ОС исследует состояние

ee = [1581, 1584, 6]
L, W = set([ee[0]]), set([ee[1]])
G = set([(i,k) for i in range(1, ee[0]) for k in range(5)])
St =set([(i,0) for i in range(1, ee[0]) ])
def pi(pos) :
  p, k = pos  
  a = [(p+4,1),(p+5,2),(p*2,3),(p*3,4)]
  b = set()
  for x, y in a :
    if y == k : continue
    if x < ee[0] : b.add((x,y))
    elif x % ee[2] == 0 : b.add(ee[1])    
    else : b.add(ee[0])  
  return b
def shag(t):
  if t%2 == 1 : return set([p for p in G if pi(p) & L])
  return set([p for p in G if pi(p) <= W])
t, ANS = 0, {}
for t in range(1,7):
  R = shag(t)
  ANS[t] = R & St
  if t%2 == 1 : W = W.union(R)
  if t%2 == 0 : L = L.union(R)
  G = G - R
print( min([ANS[2]]))
print( min([ANS[3]]),max([ANS[3]]))
print(len(ANS[4]))

Печать