Chat:Ru/2022-01-23

From CG community
Jump to navigation Jump to search

wlesavo: во, другое дело, в 10 раз где-то ускорился

wlesavo: 2кк bfs за 100ms

wlesavo: а было 200к гдето

Uljahn: что-то важное запилил, кроме советов смитси?

wlesavo: вообще по другому сделал, на сдвигах, получается что-то типа такого однострочника, в массиве кон маска соединений по каждому направлению cur = (cur&con[0])>>WIDTH | (cur&con[1])<<1 | (cur&con[2])<<WIDTH | (cur&con[3])>>1;

     cur &= ~tmp;
     tmp |= cur;

wlesavo: я думаю у YurkovAS что-то похожее

wlesavo: по количеству роллаутов bfs похоже по крайней мере

wlesavo: странно что вообще не нашел нормальных статей по этому поводу, сама идея похожая и в шахматных ускорениях и много где еще, но вот что-то в такой простой форме не видел нигде

YurkovAS: там еще когда сдвигаешь в лево/право необходимо отслеживать границы

wlesavo: у меня это в con учитывается

wlesavo: границы сразу зануляются перед сдвигом

YurkovAS: и стерны тут еще учитывать

YurkovAS: *стены

wlesavo: ну и стены в con тоже аккуратно битами активируются

YurkovAS: ну вот оно и есть. работает заметно быстрее и расстояние позволяет посчитать

Uljahn: кроме Смитса есть ещё такой плейграунд: https://tech.io/playgrounds/53455/fast-15x15-bit-grid-bfs-breadth-first-search

wlesavo: ща надо будет с шириной поэкспериментировать

wlesavo: Uljahn да, я читал, но там больно усложнено и легко не транслируется в то что нужно

YurkovAS: а если борд был бы 64bit, тогда можно через avx сразу по 2 смещения влево + 2 смещения вправо ну и and там же

YurkovAS: в итоге еще быстрее будет

YurkovAS: Uljahn этот подход тоже подойдет, тк. у нас 9х9

YurkovAS: wlesavo в итоге хуже стало?

YurkovAS: может баг где-то еще

YurkovAS: но тогда он же сразу проявится в игре - типа нетуда будешь ходить

wlesavo: не, предыдущая версия тоже так сабмится часто, плюс я в паре мест отключил учет площади. то что в бфс бага нет точно проверял, со старой версией сравнивал

YurkovAS: еще как вариант - в старой версии вывести скоринги на каждой глубине и сравнить скоринги битбордов должно совпадать, ну и локально можно

wlesavo: ща поэкспериментирую, фундаментально сломанным не выглядит по крайней мере

YurkovAS: тут еще есть тема: можно пустить волну от финиша к противнику

wlesavo: да, это как у рекара в пм

YurkovAS: и по ней тоже можно площадь взять, правда, там наверное наоборот надо

YurkovAS: у тебя же чем меньше площадь, тем лучше?

wlesavo: да

YurkovAS: у меня так же.

wlesavo: ну тут главное я наконец разобрался с ускорением, теперь хоть не так грустно, в первую очередь отключу эвристику чтобы только вдоль минимальных путей стены проверять

YurkovAS: а может оно и верно у меня для стен нет проверок, ставлю все возможные и потом по скору только отсеиваем

YurkovAS: мне уже проще забить - лучшее враг хорошего только время тратить

wlesavo: ну мне проверить сейчас легко, раньше просто это глубину убивало

YurkovAS: это да

AntonBlockchain: Добрый день. а бронзовая лига появляется сама когда народ набегает в паззл. или бронзовой лиги никогда не будет www.codingame.com/ide/puzzle/counting-tictactoe

wlesavo: вероятнее всего никогда, раньше иногда добавляли на сколько я знаю, если устраивали контест по существующей мульти

YurkovAS: это комьюнити мульти и в ней всего 3 лиги, вот тут в фильтрах все есть https://www.codingame.com/multiplayer/bot-programming/counting-tictactoe/leaderboard

YurkovAS: обогнал меня на тайпскрипте

AntonBlockchain: спасибо а то прошел до 21 места, а ачивку не дали за бронзу (

wlesavo: ну да, за cp и ачивками лучше идти в официальные игры, а не в комьюнити

AntonBlockchain: YurkovAS: ага)

YurkovAS: у меня там мктс или минимакс - типа продвинутые алгоритмы и все очень быстро работает

YurkovAS: но....

wlesavo: хаха YurkovAS, запушил тебя на первое место))

YurkovAS: :thumbsup:

wlesavo: у меня почему-то против рекара 1х1 неплохо играет

wlesavo: обратно запушил :smiley:

YurkovAS: да у него точно сильнее моего

YurkovAS: neildo вот он еще все испортил, у меня против него плохо играет и его раньше в топе небыло, а сейчас мешает

YurkovAS: и Ромку вниз опустили, хотя он был в топ5

wlesavo: да, топ вообще сильно перемешался, те против кого хорошо играли вниз ушли и теперь мешают, рекурс вообще с топ20 где-то поднялся на восьмое

Default avatar.png PavRus: Привет. Мне интересно. А кто-нибудь получал предложения по работе с этого ресурса? Какой у вас уровень был?

И может быть админы знают, в среднем какой уровень должен быть, чтобы получить рабочее предложение?

AntonBlockchain: YurkovAS: вот ты выше в counting-tictactoe - поздравляю)

YurkovAS: AntonBlockchain спс, да, улучшил немного

AntonBlockchain: PavRus: я тут всего неделю, так что не знаю. тоже интересно послушать.

wlesavo: таки был баг, чтобы маску заполнить n единицами надо делать (1<<n) - 1, а я делал 1<<(n+1)-1

wlesavo: и эта лишняя единица у меня в соединениях была, не знаю сильно влияло или нет, но как-будто бы стабильнее стал играть бот

YurkovAS: у меня нет такого

wlesavo: я для направлений инициализирую значения так

wlesavo: ладно, думаю н аэтом пора заканчивать, лучше уже не будет)

wlesavo: хотя конечно есть еще проблемы точно, когда все близко к углам начинают ловлю 6 последних мест

YurkovAS: wlesavo :thumbsup:

wlesavo: спасибо) заодно тебя красиво запушил))

Default avatar.png TTeaLL: как использовать eval в питоне?

Default avatar.png TTeaLL: уже не надо

Default avatar.png molly.pears: как разбан в мировом чате получить?

Default avatar.png molly.pears: и возможно ли это?