На стене выключатель. Нажатие которого иногда приводит к цели, иногда нет. Что означает, что выключателем может быть не то, что мы предполагаем.
Вопрос можно поставить абстрактно. Пусть имеется множество {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)
bvv2311 Автор
Насколько знаю, нет моделирования игр для недетерминированного конечного автомата.