Проблема нейросетей - невозможность обучаться на единичных примерах. Справиться может табличное RL, но обучаться на данных большой размерности - иная неразрешимая сторона этой парадигмы https://habr.com/ru/post/437020/. Решение только в одном: видеть мир иерархически, где каждая его подчасть также может быть выражена иерархически.
Как здесь https://habr.com/ru/post/420219/ - сложность игры которой сокращается за счет введения небоевого состояния, подсостояниями которого являются ожидание и патрулирование.
Теперь маштабируем этот подход. На этот счет интересны рассуждения В.Турчина
И игра, и каждое из ее состояний, и каждый из классификаторов иерархии представлен какой-то отдельностью. Так видеть - естественно для человека. Но не для машины.
Вот что пишет об этом А. Карпатый https://habr.com/ru/post/439674/. Как только вы поймете «хитрость», с помощью которой работают эти алгоритмы, вы сможете понять их сильные и слабые стороны. В частности, эти алгоритмы далеко отстают от людей в построении абстрактных представлений об играх.
Так каков критерий видеть эти отдельности? Попытки представить предметы и явления как результат алгоритмов, например, свертки - лишь частный случай более фундаментального подхода.
![Р. Эшби .//Введение в кибернетику [стр 63]](https://habrastorage.org/getpro/habr/upload_files/02f/fcc/e41/02ffcce41f9e16f70d0c0604d45097ee.jpg "Р. Эшби .//Введение в кибернетику [стр 63]")
Пусть имеется мячик (синий квадрат) как в игре пинг-понг, летящий по некой траектории.
Как мы понимаем, что это отдельная сущность, а не множество синих мячей появляющихся и исчезающих в разных точках пространства? Контраст предмета синий и белого фона? А если этот предмет будет менять цвет, например на случайно выбранные синий, серый (код ниже, BALL_CHANGE_BG = True)? Вроде на фоне белого же. Но что если фоном будет случайно выбранные цвета?
Из трассировок видно, например, что из состояния (1,2) следует как состояние (1,3), так и состояния (2,3), (0,3). По этой причине невозможно (если переходы равновероятны) поймать синий мячик из этого состояния. Выигрыш не более 1/3, если основываться только на политике без учета предшествующих состояний.
Можно попытаться найти такое действие, которое бы приводило к желаемой однозначности. Им является предшествующее состояние. Тогда: (1,2) перейдет однозначно в (1,3) при действии (1,1); (1,2) перейдет только в (2,3) при действии (0,1); (1,2) перейдет только в (0,3) при (2,1).
Всегда ли можно найти однозначные преобразования, подобрав необходимые действия? Нет конечно. Но к этому нужно стремится. Ниже 4 фрагмента.
Действие неизвестно. По умолчанию оно одно (условно f). Коэффициент однозначности 0.6
Вносим неустраняемую неопределенность отскока от черного квадрата. Коэффициент будет ниже.
Выбраны верные действия. Коэффициент единица (однозначность сто процентов),. Теперь, зная граф переходов, безошибочно вычисляется куда прилетит синий мяч.
Добавляем неопределенность к верным действиям. Из состояния (1.2) она максимальна из-за черного квадрата (неопределенный отскок)
Так как же можно разглядеть явления, которые могут как влиять друг на друга, так и быть иерархически выстроены?
Ниже лабиринт (Л) - это одно из сменяемых состояний {11, 12, 14, 15} в результате действий {31, 32}. В свою очередь, состояние лабиринта ключ (11) тоже выражено сменой своих подсостояний {45, 44, 41} в результате действий {35, 36, 34}. И состояние лабиринта дверь (12) управляется ключом (11). Управляется по той причине, что состояния ключа являются действиями для двери. Когда подсостояние двери принимает значение открыто (54), агент может из лабиринта (Л) перейти в комнату (км) и найти клад (63). В отдельно взятой таблице поиск оптимального пути может осуществляться средствами RL.
Но! В начале игры агент ничего не ведает, что есть клад. Не ведает что есть эти отдельности (лабиринт, ключ, двер, комната). Он лишь наблюдает поток данных. Сначала [32, 52, .., 52, ..], затем [.., .., 44, .. 36] и т.д. Рассматривает разные гипотезы, стремясь максимизировать коэффициент однозначности. Так, рассмотрев черную гипотезу, приходит к выводу, что есть некая сущность (11), состояниями которой являются {45, 44, 41}. Обнаруживает также однозначность переходов сущности (12). И далее уже о сущности (Л) тоже мыслит как о какой-то отдельности, переходы состояний которой однозначны. По той простой причине, что для красной гипотезы (попытка понять что есть лабиринт) состояния {44, 41, 45} заменятся на (11), а состояния {52, 53, 54} заменятся на (12).
По Турчину, (11) и (12) являются классификаторами нижнего уровня для классификатора (Л) более верхнего уровня, образуя иерархию понятий.
Ниже представлен код для игры в понг, но без части максимизации однозначности и без оптимизации маршрута по графу (состояние и действие мяча, состояние и действие ловящего мяч) . Без комментариев.
# Выразить иерархически: вопрос как увидеть хамелена
from tkinter import *
import random
class Hd():
def __init__(self, graph):
self.graph = graph
def rnd_get(self, v):
return random.choice(v.split("|"))
def show(self, graph):
for x in graph:
print(x, ":", graph[x])
def get_ku(self, graph):
'''return (коэффициент однозначности, размер)'''
n = 0; u = 0
for x in graph:
for y in graph[x]:
if y[0]:
u += y[0].count("|")
n += 1
if n != 0:
return (round(1- u/(n+u), 3), n+u)
else:
return (None, None)
def get_states(self, x, f_list = [], n=11):
x_list = []
x_list.append(x)
if f_list != []:
for f in f_list:
xf = [xf for xf in g[x] if xf[1] == f]
if not xf:
x_list.append(''); f_list[len(x_list)-2] = ''
return (x_list, f_list[:len(x_list)-1])
x = self.rnd_get(xf[0][0])
x_list.append(x)
else:
for i in range(n):
if not self.graph[x]:
x_list.append(''); f_list.append('')
break
t = random.choice(self.graph[x])
f = t[1]
x = random.choice(t[0].split('|'))
x_list.append(x); f_list.append(f)
if len(f_list) == len(x_list) -1:
return (x_list, f_list)
else:
return ([], [])
def get_yfx(self, f_list, x_list, t = True):
if len(x_list) == len(f_list):
x_list.append('')
path = []
for i in range(len(f_list)):
path.append((x_list[i], f_list[i], x_list[i+1]))
if t:
return path #(x, f, next_x)
else:
p = []
for xfy in path:
if xfy[2] != '':
p.append(xfy[2]+'='+xfy[1]+'('+xfy[0]+')')
return p
def flow(self, path, rnd=False):
if not path: return []
fl = []
for p in path:
if not rnd:
fl.append(p[:-1])
else:
pr = list(p[:-1])
#random.shuffle(pr)
fl.append(tuple(pr))
fl.append(pr)
return fl
def fORx(self, flow, f=0):
'''index: f=0, x=1 or x=0, f=1'''
def add_empty():
empty = []
for k in graph:
for x in graph[k]:
z = list(set(x[0].split('|')) - set(list(graph.keys())))
if z:
empty.append(z[0])
return empty
if not flow: return []
graph = {}
fli = flow[0]
for t in flow[1:]:
if f == 0:
if fli[1] not in graph:
graph[fli[1]] = []
r = [(i, xf) for i,xf in enumerate(graph[fli[1]]) if xf[1] == fli[0]]
if r:
if t[1] not in r[0][1][0]:
x_new = r[0][1][0] + "|" + t[1]
if x_new != '':
graph[fli[1]][r[0][0]] = (x_new, r[0][1][1])
if not r:
if t[1] != '':
graph[fli[1]].append((t[1], fli[0]))
if f == 1:
if fli[0] not in graph:
graph[fli[0]] = []
r = [(i, xf) for i,xf in enumerate(graph[fli[0]]) if xf[1] == fli[1]]
if r:
if t[0] not in r[0][1][0]:
x_new = r[0][1][0] + "|" + t[0]
if x_new != '':
graph[fli[0]][r[0][0]] = (x_new, r[0][1][1])
if not r:
if t[0] != '':
graph[fli[0]].append((t[0], fli[1]))
fli = t
em = add_empty()
if em:
graph[em[0]] = []
return graph
def merge(self, g1, g2):
def find_index():
for i in range(len(graph[k])):
if graph[k][i][1] == x[1]:
return i
return -1
all_keys = set(list(g1.keys()) + list(g2.keys()))
graph = {}
for k in all_keys:
if k not in graph:
if k in g1:
graph[k] = g1[k]
else:
graph[k] = g2[k]
if k in g2:
for x in g2[k]:
ind = find_index()
if ind != -1:
if x[0] != []:
t1 = x[0].split('|')
if graph[k][ind] != -1:
t2 = graph[k][ind][0].split('|')
z = "|".join(set(t1+t2))
#xf = [z, graph[k][ind][1]]
xf = (z, graph[k][ind][1])
graph[k][ind] = xf
else:
graph[k].append(x)
return graph
class Wednesday():
def __init__(self, root, maps, ban):
self.root = root
self.maps = maps
self.ban = ban
Wednesday.time = {}
Wednesday.hierarchy = {}
Wednesday.neighbor = {}
self.init_3_dict()
def init_3_dict(self):
def is_en(yx):
if yx[0] < 0 or yx[0] > len(self.maps)-1: return
if yx[1] < 0 or yx[1] > len(self.maps[0])-1: return
if yx in self.ban: return
return True
for y in range(len(self.maps)):
for x in range(len(self.maps[0])):
Wednesday.hierarchy[(y,x)] = self.maps[y][x]
n = []
if is_en((y-1,x)):
n.append((y-1,x))
if is_en((y+1,x)):
n.append((y+1,x))
if is_en((y,x-1)):
n.append((y,x-1))
if is_en((y,x+1)):
n.append((y,x+1))
if is_en((y-1,x-1)):
n.append((y-1,x-1))
if is_en((y-1,x+1)):
n.append((y-1,x+1))
if is_en((y+1,x+1)):
n.append((y+1,x+1))
if is_en((y+1,x-1)):
n.append((y+1,x-1))
Wednesday.neighbor[(y,x)] = n
Wednesday.time[(y,x)] = 0
if (y, x) in self.ban:
lb = Label(text=" ", background = 'black')
lb.configure(text=self.maps[y][x])
else:
bg = "white"
if CHANGE_BG:
bg = random.choice(["yellow", "red", "white", "brown", "pink"])
lb = Label(text=" ", background = bg)
lb.configure(text=self.maps[y][x])
lb.grid(row=y, column=x, ipadx=15, ipady=10, padx=1, pady=1)
def update(self):
for y in range(len(self.maps)):
for x in range(len(self.maps[0])):
if Wednesday.time[(y,x)]:
Wednesday.time[(y,x)] -=1
else:
Wednesday.hierarchy[(y,x)] = self.maps[y][x]
if not (y, x) in self.ban:
bg = "white"
if CHANGE_BG:
bg = random.choice(["yellow", "red", "white", "brown", "pink"])
lb = Label(text=" ", background = bg)
lb.configure(text=Wednesday.hierarchy[(y,x)])
lb.grid(row=y, column=x, ipadx=15, ipady=10, padx=1, pady=1)
self.root.after(TIME, self.update)
class Base():
def __init__(self, root, color, node):
self.root = root
self.color = color
self.y = node[0]
self.x = node[1]
self.visit = {}
self.neighbor = {}
self.count = 0
def show(self, y, x, color):
lb = Label(text=" ", background = color)
try:
lb.configure(text=Wednesday.hierarchy[(y,x)] )
lb.grid(row=self.y, column=self.x, ipadx=15, ipady=10, padx=1, pady=1)
except:
pass
def add_neighbor(self):
try:
self.neighbor[(self.y, self.x)] = Wednesday.neighbor[(self.y, self.x)]
except:
pass
def choice(self, yx):
self.add_neighbor()
return random.choice(self.neighbor[yx])
def move(self):
yx = self.choice((self.y, self.x))
self.redraw(yx)
self.count +=1
def redraw(self, yx):
self.show(self.y, self.x, 'white')
self.y = yx[0]
self.x = yx[1]
self.show(yx[0], yx[1], self.color)
def update(self):
self.move()
self.root.after(TIME, self.update)
def env(self):
return (self.color, (self.y, self.x))
class WhoBeats(Base):
def __init__(self, root, color, node, lenYX):
super().__init__(root, color, node)
self.lenYX = lenYX
self.balls = []
def choice(self, yx):
self.add_neighbor()
if self.count % (self.lenYX[1] +PAUSE) == 0:
y = yx[0] + random.choice([-1, 0, 1])
if y < 0:
y = 0
if y > self.lenYX[0] -1:
y = self.lenYX[0] -1
dy = y-yx[0]
ball = Ball(root, "blue", (y, yx[1]), self.lenYX, dy)
self.balls.append(ball)
ball.update()
yx = list(random.choice(self.neighbor[yx]))
yx[1] = 0
return tuple(yx)
def get_balls(self):
for ball in self.balls:
pass
return self.balls
class Ball(Base):
def __init__(self, root, color, node, lenYX, dy):
super().__init__(root, color, node)
self.lenYX = lenYX
self.dy = dy
def choice(self, yx):
if BALL_CHANGE_BG:
self.color = random.choice(["grey", "blue"])
self.add_neighbor()
if yx[0] <= 0:
self.dy = 1
if yx[0] >= self.lenYX[0]-1:
self.dy = -1
try:
if (yx[0] +self.dy, yx[1] + 1) in self.neighbor[yx]:
yx = (yx[0] +self.dy, yx[1] + 1)
else:
if yx[1]+1 >= self.lenYX[1]:
yx = (yx[0], self.lenYX[1])
else:
v = []
for i in self.neighbor[yx]:
if not i in self.visit:
self.visit[i] = 0
v.append((i, self.visit[i]))
v.sort(key = lambda x: x[1], reverse = False)
v = [i for i in v if v[0][1] == i[1]]
v = random.choice(v)
self.visit[v[0]] += 1
yx = v[0]
self.dy = random.choice([-1,1])
except:
pass
return yx
class WhoСatches(Base):
def __init__(self, root, color, node, lenYX, whoBeats):
super().__init__(root, color, node)
self.lenYX = lenYX
self.whoBeats = whoBeats
self.win = 0
self.routes = []
self.route = []
self.gf = [{}, {}]
self.hdWC = Hd({})
def choice(self, yx):
self.add_neighbor()
self.neighbor[yx] = [x for x in self.neighbor[yx] if x[1] == self.lenYX[1]-1]
dy = self.action()
if (yx[0] +dy, yx[1]) in self.neighbor[(yx[0], self.lenYX[1]-1)]:
hd = Hd({})
hdF = self.tuple_str((dy,0))
hdX = self.tuple_str(yx)
hdY = self.tuple_str((yx[0] +dy, yx[1]))
path = hd.get_yfx([hdX, hdY], [hdF, ""])
gn = hd.fORx(hd.flow(path), f=0)
self.hdWC.graph = hd.merge(self.hdWC.graph, gn)
print("\nwhoСatches ku = ", self.hdWC.get_ku(self.hdWC.graph))
self.hdWC.show(self.hdWC.graph)
yx = (yx[0] +dy, self.lenYX[1]-1)
self.winner()
return yx
def action(self, choice = None):
if choice == None:
dy = random.choice([-1,0,1])
return dy
def hypothesis(self, x_list, f = None):
if f == None:
f_list = ["f"]*len(x_list)
return (f_list, x_list)
else:
f_list = x_list[:-1] #дейсвие = предыдущее состояние
x_list = x_list[1:]
return (f_list, x_list)
def tuple_str(self, v, convert = True):
if convert:
delimiter = ','
r = delimiter.join([str(x) for x in v])
else:
r = [ x for x in v.split(',')]
return r
def winner(self):
balls = self.whoBeats.get_balls()
for i, ball in enumerate(balls):
if ball.env()[1][1] == 1:
self.route = []
self.route.append(ball.env()[1])
elif ball.env()[1][1] < self.lenYX[1]-1:
self.route.append(ball.env()[1])
else:
self.route.append(ball.env()[1])
if self.route not in self.routes:
self.routes.append(self.route)
if self.x == ball.env()[1][1]:
if self.y == ball.env()[1][0]:
self.win +=1
else:
self.win -=1
root.title("win = " + str(self.win))
self.whoBeats.balls.pop(i)
if self.routes:
hd = Hd({})
for x_list in self.routes:
x_list = [self.tuple_str(x) for x in x_list]
if HYPOTHESIS:
f_list, x_list = self.hypothesis(x_list, f=True)
else:
f_list, x_list = self.hypothesis(x_list)
path = hd.get_yfx(x_list, f_list)
gn = hd.fORx(hd.flow(path), f=0)
self.gf[0] = hd.merge(self.gf[0], gn)
ku = hd.get_ku(self.gf[0])
print("\n\nball ku =", ku)
hd.show(self.gf[0])
print("\nroutes")
t = [print(x) for x in self.routes]
#--------- main ---------#
if __name__ == "__main__":
TIME = 500 #частота обновления
PAUSE = 5
HYPOTHESIS = True
CHANGE_BG = False
BALL_CHANGE_BG = False
#CHANGE_BG = True
#BALL_CHANGE_BG = True
root = Tk()
#ban=[(1,3), (1,5), (1,6), (1,7), (0,7), (1,4), (2,4), (3,4), (4,3), (4,4), (5,6), (5,7), (4,7), (3,7), (2,7)]
#M=8; N=12
ban=[(1,3)]
#ban = []
M=3; N=6
maps = [["" for i in range(N)] for j in range(M)]
def update():
#w1.update()
b1.update()
c1.update()
w1 = Wednesday(root, maps, ban)
b1 = WhoBeats(root, "red", (1,0), (M, N))
c1 = WhoСatches(root, "green", (1,N-1), (M, N), b1)
update()
root.mainloop()
