Chat:Ru/2022-01-13

From CG community
Jump to navigation Jump to search

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: еще грубо достаточно оцениваю могу ли закрыть противника так чтобы у него площадь была меньше чем у меня, и если могу то за это большой бонус