wlesavo: не исключено что нейронка конечно, раз он до сих пор интерес не потерял
aangairbender: я себе визуализатор сделал, стало намного проще искать проблемы
aangairbender: оказалось в моей tree of chambers их достаточно)
Uljahn: эйлер как-то объяснял алгоритм быстрого расчёта заполнения, даже картинку нарисовал https://i.imgur.com/sVqAcue.png
wlesavo: у меня там была очень простая эвристика которая количество своих клеток рядом с головой учитывает, чем больше тем лучше, вроде адекватно работает
aangairbender: вот так мой визуализатор выглядит
https://imgur.com/a/bRl644U
aangairbender: правда там я сейчас в процессе фикса, поэтому тупики не считает отдельными комнатами
wlesavo: ух, круто
aangairbender: вот в этой ситуации оба говорят праивильно сколько ходов проживут
https://imgur.com/a/UTA5a80
aangairbender: ну и заполняют всё без дырок
wlesavo: у меня последний крупный баг был интересный достаточно
я изолированных соперников почти полностью игнорирую: в начале хода считаю полную площадь и грубо считаю что они проживут по количеству клеток. и это же количество использовал как счетчик для обратного отсчета на удаление соперника
wlesavo: и потом в процессе случайно обнулял для них счетчик и противники удалялись на втором ходу поиска
wlesavo: ну и изза того что это только на втором ходу происходило некорректных движений в игре никогда не возникало, поэтому очень поздно заметил
aangairbender: текущая версия выигрывает YurkovAS если начинать в противоположных углах (и когда хожу первый, и когда второй)
aangairbender: жаль что в мультиплеере не так)
aangairbender: сейчас wlesavo c тобой проверяю
YurkovAS: ты там завязывай с этим и заифай мой ник в друзья :)
aangairbender: wlesavo тоже выигрываю не смотря на первенство хода
aangairbender: YurkovAS ты писал что у тебя оценка это разница неких оценок для себя и оппонента
aangairbender: а когда несколько оппонентов то как
YurkovAS: 1на1 мало боев - даже не заметишь
aangairbender: 1на1 мало это жаль конечно)
YurkovAS: у меня оценка такая:
(vorMy - vorAllOps) * 1000 + movesCountMy + (bordersCountMy == 2 ? 1500 : 0)
и нормализуется к диапазону от 0-1
0 - если умер
YurkovAS: bordersCount - кол-во занятых клеток в текущей позиции
YurkovAS: и так для каждого игрока заполняю и потом в backpropagation-е проставляется в мктс нодах
aangairbender: хорошо вы там, конечно, заняли места:joy:
wlesavo: aangairbender у меня 1x1 очень слабый бот, часто два поражения ловит если условия стартовые примерно равные, так что со мной смысла тестировать нет особого)
aangairbender: всё, я устал от трона, вернусь в другой раз:joy:
aangairbender: не нашли еще новую игру?
aangairbender: у меня в fal challenge 2020 золото, это надо исправить
YurkovAS: я переключусь в неспешный режим и поразбираюсь в битовых манипуляциях для othello
YurkovAS: но это не точно, просто найду что-то максимально легкое, как всегда
YurkovAS: у тебя отличный результат в троне!
там совсем немного надо улучшить и дойдет до 10-ки, то вот что... :)
aangairbender: есть 2 варианта
1) улучшить функцию оценки (умней учитывать результат оппонентов, ведь результат каждого считается довольно точно, а вот совместить - беда)
2) поменять алгоритм для большей глубины
aangairbender: бывают ситуации часто когда мой вороной упирается в вороной оппонента и я не иду в сторону оппонента, но если внимательно посмотреть, то у оппонента и без меня много места в другую сторону (его вороной упирается в другого соперника помимо меня)
YurkovAS: большую глубину как раз даст alpha-beta против ближайшего, там еще и отсечения могут помочь.
ветвистость точно будет меньше
aangairbender: думал best first search with uct попробовать
aangairbender: смесь mcts и minimax
YurkovAS: я пытался урезать кол-во ходов у противников и он сразу начал их терять, дерево не переиспользуется и играет хуже
aangairbender: мне конечно нравится maxn (как минимум потому что он уже написан:sweat_smile: ), но другие алгоритмы тоже попробовать бы
aangairbender: мне кажется в троне нет прям киллер ходов, чтоб минимакс был лучше других
aangairbender: или я что-то упускаю?
YurkovAS: мне трудно сказать, при то что у меня был минимакс, который для противников выбирал по 1 лучшему и тоже доходил до 30 места
aangairbender: ну вот у меня примерно так, 1-2 хода каждого
aangairbender: для 4ех игроков 5ply (то есть каждый по ходу а потом я еще раз)
YurkovAS: а ты пробовал прунинг?
YurkovAS: правда там написано, чтобы суммарная оценка в максН всегда была одинаковая
в той книге = 10
aangairbender: не пробовал, я подумал суммарную оценку 600 сделать, но не уверен насколько хорошо оно будет отсекать
aangairbender: вообще я думаю даже с лучшим прунингом максимум еще 1 круг ходов добавлю
aangairbender: что не сильно поможет
aangairbender: мне кажется важно делать поиск на уровне макро игры, например к какому оппоненту идти (если несколько смежных вороных)
YurkovAS: можно сложить оценки всех, а потом оценку каждого делить на эту суммарную
всегда будет от 0-1 диапазон
aangairbender: вот например тут
https://imgur.com/a/RL0a8dT
можно ведь как-то оценить макро стратегию
aangairbender: полезная конечно штука визуализатор, без него tree of chambers я бы не отдебагал, ошибок была куча
YurkovAS: у меня была такая идея: разбить на комнаты + корридоры
настроить между ними связи
после бфс-ов мы знаем в каких комнатах мы побывали и откуда начали.
запустить дфс по этому графу и найти максимальный (по размеру комнаты и корридора)
YurkovAS: и типа потом в его бфс-е убрать лишние комнаты и корридоры
и дальше воронов
YurkovAS: а начать с тупиков, потом корридоры и т.д
точнее дальше не дошел, что-то лень это делать
YurkovAS: если заполнение комнат будет быстро работать
думаю это может улучшить: т.к. в воронове не будет лишней информации
aangairbender: вот у меня похожее делается
aangairbender: звучит как tree of chambers
aangairbender: только я вместо корридоров делаю много комнат размера 1, так проще)
aangairbender: по этому графе в итоге перебор (я знаю начальную позицию и пытаюсь набрать максимальный путь в графе)
aangairbender: *по этому графу
YurkovAS: дфс?
YurkovAS: быстро работает?
aangairbender: да дфс с back tracking
aangairbender: вроде быстро, там не так много ветвлений, я еще кеширование думал сделать, но и без него норм
YurkovAS: т.е. у тебя все так сейчас и играет?
aangairbender: с помощью этого считается для состояния длительность жизни всех игроков
YurkovAS: а т.е. для вороного не применяешь?
YurkovAS: когда игрок еще не заблочен - не применяешь?
aangairbender: https://imgur.com/a/giVBqd0
aangairbender: разные цвета - комнаты (комната делится по разделению вороного, это можно заметить между красным и розовым игроком)
aangairbender: кружки - articulation points
aangairbender: белые линии - ребра в графе комнат
aangairbender: каждого игрока начальную позицию кладу в отдельную комнату (с размером 0)
YurkovAS: так комнаты же должны быть большими и полностью заполнены
по ним и перебор потом будет быстрый
aangairbender: получается я для каждой комнаты считаю upper bound с помощтю checkers эврестики
YurkovAS: а черное что?
aangairbender: это хвосты игроков (по сути стены)
aangairbender: решил не красить в цвета как на кг, а то сливаются
YurkovAS: а пробовал комнаты по воронову не разделять?
aangairbender: в дереве комнат могут быть комнаты, где есть касание к чужому вороному, тогда я также считаю что в эту комнату зайти и заполнить только если по пути ничего не заполнял, а быстро шел
YurkovAS: т.е. там получается всего 2 комнаты
aangairbender: и как тогда считать кол-во клеток, которые я смогу посетить?
YurkovAS: вот справа чел, он в итоге куда пойдет?
YurkovAS: в моем случае он пойдет в верхнюю большую комнату, т.к. она большая
YurkovAS: или там справа сверху не чел?
aangairbender: вверху справа двое - розовый и оранжевый
aangairbender: и сейчас ход розового
aangairbender: клетки с игроками имеют толстую внутреннюю черную границу
aangairbender: розовый пойдет вправо, а потом вверх, так как если сразу пойти вверх то клетку справа уже сложно посетить (она становится тупиком)
YurkovAS: выглядит очень круто!
aangairbender: работает по сути за O(N*M), но там думаю константа большая
aangairbender: выглядит то прикольно, но хз как нормально применить
aangairbender: вот пример двух игроков с разных углов
https://imgur.com/a/pFVoGvd
сейчас ход оранжевого и он идет вниз
YurkovAS: получается в моем представлении справа 2-е пойдут вверх - т.к. там одна большая комната
YurkovAS: только фиолетовый другого может задавить, но это не важно, т.к. глубиной просчитается
aangairbender: оранжевый не может пойти вверх в игре с 4 игроками, так как там нет ребра вверх (как вороной не позволяет, это означает, что розовый успеет занять ту клетку первей)
aangairbender: там ведь ход розового
aangairbender: он просто вправо пойдет и все
YurkovAS: да я просто рассуждаю, как работало бы то, что придумал изначально, когда комнаты по воронову не разделяются. а каждый пойдет только в макс путь
aangairbender: на самом деле в той игре розовый пойдет вверх, так как если пойдет вправо, то потеряет часть верхней комнаты красному игроку
YurkovAS: розовый или фиолетовый? что-то не пойму немного.
там в центре еще красный (на розового похож)
Uljahn: сиреневый)
Uljahn: наверное, ему ещё выгодно идти вверх, чтобы дырочку к границе с оранжевым оставить
aangairbender: я скопировал rgb цвета из codingame
aangairbender: там есть оранжевый, красный, розовый и синий
aangairbender: Uljahn это да, но я пока это не учитываю, хотя думаю, что при 4 игроках это довольно важно
aangairbender: типа победить ближнего, оставить к нему проход и когда он умрет, то бегом на его территорию
YurkovAS: там оранжевого созжрут красный и синий
aangairbender: что найти игроков в визулизаторе достаточно найти квадратики с белыми линиями из центра, но без круга в середине
YurkovAS: тут бы солвер по этой закраске сделать - макро ходы
aangairbender: сожрут всмысле после смерти?
YurkovAS: да, он же снизу пришел
YurkovAS: потом исчезнет, т.к. заперт
aangairbender: вот такая картина спустя какое-то время
https://imgur.com/a/PEFnvep
aangairbender: добыча синего видимо)
aangairbender: кстати тут обычный вороной для синего учтет проход вправо в оценку, но tree of chambers - нет
aangairbender: еще здесь можно заметить важную проблему, синий боится далеко отходить от верхней левого угла (там конфронтация с красным), но на самом деле красный не пойдет в тот коридор 99% и синий может спокойно отойти
aangairbender: то есть хорошо бы, как ты YurkovAS говорил, запустить алгоритм, найти макро решения для всех и потом это использовать
YurkovAS: это сложно сделать
aangairbender: например можно пока есть время искать макро решения для каждого, используя решений предыдущих, тогда синий когда-то поймет, что красный не будет пытаться идти в его комнату и сможет выбрать стратегию получше
YurkovAS: там же надо убить самого слабого, а потом понять где будут находиться другие через эти Н ходов и опять все перекрасить
YurkovAS: а может проблема в максН? пробовал выключить этот алгоритм и посмотреть профит. может надо сделать apha-beta и будет круто играть
aangairbender: пока другие алгоритмы поиска не пробовал...
YurkovAS: а почему у тебя у синего не закрашена зона коричневая слева сверху?
YurkovAS: ведь это же его тема
aangairbender: на каком скрине?
YurkovAS: https://imgur.com/a/giVBqd0
YurkovAS: а, потому что туда красный быстрее может пройти
YurkovAS: тогда это может территория красного? ох туплю, я еще и считать не люблю, приблизительно всегда смотрю
aangairbender: да, там красный по корридору может пройти и отобрать
YurkovAS: а у него потом синий возвращаясь назад не отхватит другой кусок в центре? где сейчас красный
YurkovAS: т.е. ты красному присвоил ту коричневую комнату?
aangairbender: да, комнаты присваиваются по вороному
aangairbender: то что синий может отобрать с другой стороны не учитывается (разве что алгоритм поиска это как-то найдет)
aangairbender: именно поэтому идея описанная выше может сработать, если красный выберет одну из комнат, синий заберет другую
Uljahn: красный зачем-то перекрыл границу с розовым
aangairbender: хотя если синий будет стоять на месте, но красный все свое может посетить по циклу)
YurkovAS: красный туда не пойдет - как мне кажется
aangairbender: получается вороной мешает правильно оценить
aangairbender: Uljahn перекрыл так как не видит пользы не перекрывать (пока что)
Uljahn: наверное, надо повышать ценность путей к границе со слабым соперником
wlesavo: слишком геморно в оценке это держать
wlesavo: я пробовал делать разные оценки в зависимости от расстояния/количества игроков которые могут дойти в эту точку, но так ничего и не завелось, лучше всего просто оценка по вороному играет. плюс у меня там неольшой бонус за полную площадь доступную, в надежде на то что кто-то ошибется и можно будет урвать больше чем дает вороной
wlesavo: еще грубо достаточно оцениваю могу ли закрыть противника так чтобы у него площадь была меньше чем у меня, и если могу то за это большой бонус
