НКА: игры без знания о замыслах других

На стене выключатель. Нажатие которого иногда приводит к цели, иногда нет. Что означает, что выключателем может быть не то, что мы предполагаем.

Вопрос можно поставить абстрактно. Пусть имеется множество {a, b, c, d}. Некоторые из элементов могут быть состояниями, некоторые действиями.

Предположим, что действиями будут {a, b}, состояниями {c, d}. Пусть имеем: с|d=a(c), с|d=b(c), c=a(d), с|d=b(d).

Здесь «|» означает «либо». Так с|d=b(d) означает: из состояния d при действии b следует либо c, либо d.

Попробуем иначе интерпретировать. Предполагаем: действия {a, c}, состояния {b, d}. Пусть имеем: b=a(b), b|d=c(b), d=a(d), b=c(d).

Разница, если ее оценить количественно, в более однозначном поведении второй гипотезы. В первом случае коэффициент однозначности, взятый как отношение как если бы все переходы были бы однозначны к всем случившимся переходам,  будет равен 4/7. Во втором случае он будет равен 4/5. Или, другими словами, мы имеем почти детерминированное пространство состояний. Для которого уже можно делать предсказания с приемлемой точностью.

Это было вступление. Теперь собственно к статье. Есть объект исследования (пространство состояний), однозначность которого достаточно высока. И есть несколько агентов, целью которых является достичь целевые состояния. Которые, в частности, могут и совпадать. Оговорюсь, что эти агенты не ведают о других агентах. Поэтому их ходы обусловлены только своими QL-картами, которые агенты формируют в результате исследования пространства состояния.

В противоположность  играм, допускающих частичное или полное знание QL-карт других участников. Следствие — возможность оптимизировать маршрут при чередовании ходов, включая вариант эмпатии. Возможно, эта тема будет рассмотрена в дальнейшем.

Теперь к технической стороне описания. Загружаем сгенерированные графы load_file. В качестве демонстрации в игре участвуют три агента. Цель каждого — достичь состояния=9. Состояние=10 следует избегать.

Второй агент с загруженным graph_b — это возможность передвигаться только по черным стрелкам. Из состояния=4 имеем неоднозначность, т.к. при действии 11 может следовать либо состояние=5, либо состояние=1. Из состояния=3 ее нет, т.к действия 11 отлично от действия 13. Вызов g2.get_ku() вернет коэффициент однозначности 0.917=11/12.

Третий агент с graph_w — возможность передвигаться как по черным, так и по синим стрелкам. Для сравнения: g3.get_ku() вернет 0.933. Первый же агент с graph_w1 имеет возможности как у graph_w за исключением перехода 9=12(2), т.е перехода в 9 из 2 при действии 12 для него нет. Его коэффициент однозначности равен 0.929

{ "1": [["2", "11"], ["10", "15"]],  "2": [["3", "11"]],  "3": [["4", "11"], ["2", "13"], ["6", "12"]],  "4": [["5|1", "11"]],  "5": [["6", "11"]],  "6": [["7", "11"]],  "7": [["8", "11"], ["5", "12"]],  "8": [["9", "11"]],  "9": [],  "10":[["5", "15"]] }  { "1": [["2", "11"], ["10", "15"]],  "2": [["3", "11"]],  "3": [["4", "11"], ["2", "13"]],  "4": [["5|1", "11"]],  "5": [["6", "11"]],  "6": [["7", "11"]],  "7": [["8", "11"]],  "8": [["9", "11"]],  "9": [],  "10":[["5", "15"]] }  { "1": [["2", "11"], ["10", "15"]], "2": [["3", "11"], ["9", "12"]],  "3": [["4", "11"], ["2", "13"], ["6", "12"]],  "4": [["5|1", "11"]],  "5": [["6", "11"]],  "6": [["7", "11"]],  "7": [["8", "11"], ["5", "12"]],  "8": [["9", "11"]],  "9": [], "10":[["5", "15"]] }

Сформируем список агентов [[g1, {e: 5, b: -6}, s, e, 1], [g2, {e: 5, b: -6}, s, e, 1], [g3, {e: 5, b: -6}, s, e, 1]]. Зададим количество игр k=1.

Здесь первый игрок who=0 сформирует QL-карту, по которой будет проложен маршрут [1,2,3,6,7,8,9]. Второй агент проходит последовательно все состояния. Третьему агенту доступен самый короткий маршрут.

При чередовании ходов маршрут до цели выглядит иначе. Маршрут представлен кортежами (агент, состояние). Из начального состояния=1 агент who=0 переходит в состояние=2. Далее who=1 переходит в состояние=3. Затем who=2 согласно своей QL-карте возвращается назад в состояние=2 (именно так выглядит его оптимальный путь). Первый агент из состояния=2 выбирает состояние=3, т.к это единственный путь к цели в его представлении.

Видно, что из состояния=4 третий агент попадает в состояние=1 (в силу неоднозначности выбора из состояния=4). Маршрут зацикливается. И только со второй попытки третий агент попадает в состояние=5. Далее последовательно до состояния=9 с чередованием ходов. В выигрыше оказывается агент who=0.

Теперь сгенерируем 100 игр. Результат ниже.

Для второго агента оказалось, что маршрута до цели не существует по результату последней игры. Так вышло, потому что из состояния=3 до состояния=4 ql=1.57, а до состояния=2 ql=2.39. Иначе говоря, состояния 2 и 3 зацикливаются. Почему так QL-карта сформировалась? Следствие (косвенное) неоднозначности при переходе из состояния=4.

Увеличим количество ходов=4 за раз для второго агента.

Видно, что в последней игре он последовательно выбирает [3, 4, 1, 2]. В выигрыше из 100 игр три таком порядке ходов оказывается в большинстве случаем третий агент.

Код ниже. Каких-то сложностей не несет.

import random, pickle, json  class GenGraph(): def __init__(self, f_list, x_list, n=4): '''f_list - список действий, x_list - список состояний' Целесобразность в списке действий возникает, если соеденять графы''' self.n = n self.graph = self.initG(f_list, x_list)  def rnd_get(self, v): return random.choice(v.split("|"))  def show(self): for x in self.graph: print(x, ":", self.graph[x])  def return_graph(self): return self.graph  def get_ku(self): '''return (коэффициент однозначности, размер)''' n = 0; u = 0 for x in self.graph: for y in self.graph[x]: u += y[0].count("|") n += 1 if n != 0: return (round(1- u/(n+u), 3), n)  else: return (None, None)  def initG(self, f_list, x_list): rnd_dict = dict() r = len(x_list) rnd_list = x_list[:]  for x in rnd_list: min21 = random.randint(0, len(rnd_list)//self.n) min22 = random.randint(0, len(rnd_list)//self.n)  if min21 <= min22: k=random.randint(min21, min22) rnd_x = list(set(random.choices(rnd_list, k=k)))  rnd_fx = [(x, random.choice(f_list)) for x in rnd_x] else:  k=random.randint(min22, min21) rnd_x = list(set(random.choices(rnd_list, k=k))) rnd_fx = [(x, random.choice(f_list)) for x in rnd_x] rnd_dict[x] = rnd_fx  return rnd_dict  def add_uncertainty(self, u=0): '''Добавлем неоднозначность''' for i in range(u): w = random.choice(list(self.graph.keys()))  if self.graph[w] != []: x = random.choice(self.graph[w]) add = random.choice(list(self.graph.keys()))  if add not in x[0].split('|'): x0 = x[0] + '|' + add ind = self.graph[w].index(x) self.graph[w][ind] = [x0, x[1]]  class Ql(GenGraph): def __init__(self, f_list, x_list): super().__init__(f_list, x_list)  self.visited = {} self.ql = {} self.gamma = 0.9  def training(self, target, current=None, depth=1, epochs=1): '''Получаем QL-карту: помечаем состояния с дисконтом от цели''' ls = sorted(list(target.items()), key = lambda t: t[1], reverse = True) if ls[0][0] not in self.graph or current not in self.graph: return  for epoch in range(1, epochs+1): if current == None: current = random.choice(list(self.graph))  if current not in self.visited:  self.visited[current] = 1  self.ql[current] = 0   n = depth while n > 0: if current in target: self.ql[current] = target[current]  if self.graph[current] == []: vs = sorted(self.visited.items(), key = lambda t: t[1]) vs = [x for x in vs if vs[0][1] == x[1]] vq = [x for x in vs if self.ql[x[0]] == 0] if vq: current = vq[0][0] else: current = random.choice(vs)[0] self.visited[current] +=1  neighbors = [random.choice(x[0].split('|')) for x in self.graph[current]]  if not neighbors: n -=1  continue  for x in neighbors: if x not in self.visited: self.visited[x] = 0 self.ql[x] = 0  ql_sort = sorted([(x, self.ql[x]) for x in neighbors], key = lambda t: t[1], reverse=True) ql_max = random.choice([x for x in ql_sort if ql_sort[0][1] == x[1]])  if current not in target: self.ql[current] = round(self.gamma*ql_max[1], 2)  visited_sort = sorted([(x, self.visited[x]) for x in neighbors], key = lambda t: t[1]) visited_min = random.choice([x for x in visited_sort if visited_sort[0][1] == x[1]]) self.visited[visited_min[0]] +=1 current = visited_min[0]  n -=1  return current  def get_ql_path(self, current, target, depth=100): '''маршрут до цели''' path = [current] while depth > 0: if current == None or target not in self.graph: return [] if current == target: return path  mx = 0 neighbor_mx = None neighbors = [random.choice(x[0].split('|')) for x in self.graph[current]]  for neighbor in neighbors: #if neighbor in self.ql and neighbor not in path: if neighbor in self.ql: if self.ql[neighbor] >= mx: mx = self.ql[neighbor] neighbor_mx = neighbor else: continue  current = neighbor_mx path += [current] depth -=1  return []  def save_file(self, name, t_data, t='pickle'): f = open(name, 'wb') if t == 'pickle': if t_data == 'graph': pickle.dump(self.graph, f) if t_data == 'visited': pickle.dump(self.visited, f) if t_data == 'ql': pickle.dump(self.ql, f) if t == 'json': if t_data == 'graph': json.dump(self.graph, open(name, 'w')) if t_data == 'visited': json.dump(self.visited, open(name, 'w')) if t_data == 'ql': json.dump(self.ql, open(name, 'w')) f.close()  def load_file(self, name, t_data, t='pickle'): f = open(name, 'rb') if t == 'pickle': if t_data == 'graph': self.graph = pickle.load(f) if t_data == 'visited': self.visited = pickle.load(f) if t_data == 'ql': self.ql = pickle.load(f) if t == 'json': if t_data == 'graph': self.graph = json.load(open(name)) if t_data == 'visited': self.visited = json.load(open(name)) if t_data == 'ql': self.ql = json.load(open(name)) f.close()  class Game(): def __init__(self, agents, depth=100): self.agents = agents #список агентов self.depth = depth #глубина поиска  def run(self): cur_agent = [None]*len(self.agents) for i in range(len(self.agents)): cur_agent[i] = self.agents[i][2]  for i in range(self.depth): for j in range(len(self.agents)): who = i%len(self.agents) next_who = (i+1)%len(self.agents)  cur = agents[who][0].training(agents[who][1], current=cur_agent[who], depth=1, epochs=1) cur_agent[who] = cur  for i in range(len(agents)): who = i%len(self.agents) next_who = (i+1)%len(self.agents) print() print("who = ", who, " ql = \n", agents[who][0].ql) print("who = ", who,  " path = ", agents[who][0].get_ql_path(agents[who][2], agents[who][3], depth=100))  agents[who][0].show() print()  win = [(None, agents[0][2])]  for i in range(self.depth): who = i%len(self.agents) next_who = (i+1)%len(self.agents)  for step in range(1, agents[who][4]+1): path = agents[who][0].get_ql_path(agents[who][2], agents[who][3], depth=100) if path: cur = path[1]  if cur == agents[who][3]:  win.append((who, cur)) return (who, win)  if step == agents[who][4]: agents[next_who][2] = cur win.append((who, cur)) break else: agents[who][2] = cur win.append((who, cur)) else: win.append((who, "pass")) self.agents[next_who][2] = self.agents[who][2] break  return (-1, win) #никто не выигал   if __name__ == "__main__": agents_won = [] #кто сколько выиграл k = 1 #количество игр  #Списки по состояниям и действиям выбраны произвольно. Применительно #к этой игре роли не играют. Действия имеют значение, если соединять графы for i in range(1, k+1): g1 = Ql([str(f) for f  in range(10, 20)], [str(x) for x  in range(70, 90)]) g2 = Ql([str(f) for f  in range(10, 20)], [str(x) for x  in range(70, 90)]) g3 = Ql([str(f) for f  in range(10, 20)], [str(x) for x  in range(70, 90)])  g1.load_file('graph_w1.json', t_data = 'graph', t='json') g2.load_file('graph_b.json', t_data = 'graph', t='json') g3.load_file('graph_w.json', t_data = 'graph', t='json')  # s - начальное состояние, e - конечное состояние, b - нежелательное состояние s = '1'; e = '9'; b = '10' # последний элемент в списке каждого агента - количество ходов за раз agents = [[g1, {e: 5, b: -6}, s, e, 1], [g2, {e: 5, b: -6}, s, e, 1], [g3, {e: 5, b: -6}, s, e, 1]]  if len(agents_won) != len(agents): agents_won = [0]*len(agents)  gm = Game(agents, depth=100) r = gm.run()  if r[0] > -1: print("agent ", r[0], " won:  ", r[1]) if r[0] == 0: agents_won[0] +=1 if r[0] == 1: agents_won[1] +=1 if r[0] == 2: agents_won[2] +=1 else: print("agents won: ", [])  print("\n  The agents won:  ", agents_won)