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

Вопрос можно поставить абстрактно. Пусть имеется множество {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+u) 
		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)

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