BorisZ: magaiti в той схеме надо будет мапать пару х у в четыре индекса
BorisZ: одной точке х у соответствуют 4 позиции в массиве - строки столбцы и две диагонали
BorisZ: то есть хотим поставить или убрать крестик - надо его в 4х местах править
wlesavo: у меня в крестиках вместо досок сразу хеш ключи в которые крестик добавляешь например так += 1<<5, а дальше все что нужно по ключу достаешь из таблицы предрасчитанной
Uljahn: а большая таблица?
wlesavo: 512 же всего
Uljahn: а, "стандартный" LUT детекта вина для крестиков
wlesavo: отдельно ключи крестиков, отдельно ноликов и отдельно общая
wlesavo: ну да, не то что бы это я сам придумал, это чатиковые идеи большинство
Uljahn: а чем ключи отличаются?
wlesavo: ну ключ ничем, просто по полному ключу достаешь только свободные клетки, а из ключей для крестиков и ноликов победы
wlesavo: или ты не об этом, тогда ключ это просто двоичное 9ти битное число
Uljahn: а, ключ - это стейт борды отдельно для крестиков и ноликов
wlesavo: ну да
wlesavo: и главное что это даже не хеш а индекс в таблице сразу
Uljahn: надо профилировать LUT vs bitshift, меня вот это "сразу" как-то настораживает
Uljahn: причём, если используются и другие LUT (логарифм, обратный корень), то с кэшами будет всё весело
wlesavo: ну бит шифт во всяком случае намного быстрее возведения в степень. а так у тебя 512 стейтов и если без багов то мапится все 1в1, другое дело если ты в одно место дважды единицу поставишь, это да
YurkovAS: += 1<<5 - это установка 5-го бита? через плюс не тестил скорость, делаю через или
wlesavo: да, ну вообще я тоже не тестил, первое что в готлову пришло
amurushkin: думаете что есть разница?
wlesavo: ну существенной точно нет, но разница может быть
amurushkin: асм отличается 1 инструкцией
Uljahn: я про LUT vs вычисление вин-стейта на битшифтах, но там и сам стейт немного сложнее
https://www.youtube.com/watch?v=5t5jzkO0t7w
YurkovAS: есть таблицы, в которых указаны скорости инструкций, найти для intel haswell
Uljahn: у меня подозрение, что LUT на 512 элементов будет вытесняться из кэша, так как у нас роллауты чередуются с селекшном :/
amurushkin: не получается найти
amurushkin: Uljahn: вроде не вытесняется. там же несколько килобайт нам доступно. по крайней мере профилировщик не показывает миссы вроде
Uljahn: понятно
wlesavo: я правильно понимаю что CodinGame Sponsored Contest это пакман на минималках?
Uljahn: возможно :)
wlesavo: у них какая то нездоровая любовь к пакману :slight_smile:
tutubalin: мне почему то казалось, что там стрелять можно
tutubalin: но версия с пэкменом мне нравится больше
amurushkin: я со всех спойлеров и намеков в чате сделал вывод что там пакман. но сам не кодил еще кроме рандома
wlesavo: ну я давно хотел, вот только добрался. но я только по хинтам догадался больше ничего не слышал про него
amurushkin: на 2048 уже все забили?
tutubalin: я сам с нуля разобрался, что там по лабиринту бегаешь и видишь, что находится сверху, слева, справа, внизу. и кроме тебя бегают ещё четверо
tutubalin: но что это пэкмэн даже в голову не пришло. мне показалось, что там 5 мужиков друг в друга стреляют
wlesavo: ну я из хинтов про направления понял, до того как-то совсем в другую сторону думал, дальше уже понятно
wlesavo: tutubalin ты навекрное в первый дум переиграл :slight_smile:
tutubalin: и в первый, и во второй :)
во втором двустволка появилась. это прям имба была
tutubalin: в универе не очень поощрялось играть в компьютерных классах, потому что компов было мало, а людей много. и если палят, что играешь, занимая комп, в то время как кому-то надо решать задачки - могли зобанить на денёк-другой.
tutubalin: и компы все были без HDD, только сетевой диск на 1 мегабайт и виртуальный диск в памяти на 4 мегабайта.
tutubalin: но мы всё равно играли в Doom. как?
wlesavo: а сколько дум сам весил?
tutubalin: 16 мегабайт дискового пространства
wlesavo: хм, как?
tutubalin: 1. отредактировали файлы оригинального дистрибутива, вырезав оттуда всё, что не требовалось для сетевой игры: уровни, монстров, текстуры.
осталось примерно 3.8 мегабайта
tutubalin: это всё равно слишком много, чтобы поместить на сетевой диск
tutubalin: 2. заархивировали и разбили на несколько частей по ~800 кб каждый. распределили эти части между несколькими людьми, каждый хранил у себя частичку дума
tutubalin: 3. расшарили папки с этими частичками. разумеется, использовали всякие шифрования и прочие трюки, чтобы не запалили админы
tutubalin: 4. для запуска дума нужно было разархивировать его из этих кусочков на виртуальный диск (4мб, так что туда он влезал)
tutubalin: из-за отсутствия текстур, они были заполнены случайным мусором из памяти. выглядело очень психоделично. людям с эпилепсией смотреть на такое нельзя
tutubalin: tutubalin, пожалуйста, не нужно флудить
wlesavo: неплохо :slight_smile:
Lobs: а каким образом кодить
gsomix: Я до сих пор в дум играю. Но чаще всего с модами. :)
Uljahn: ion fury понравилась из последнего дум-подобного
wlesavo: блин, у них в этом пакмане тоже телепорты есть, охренеть
wlesavo: ктобы мог подумать
wlesavo: лол, в тесте с телепортами можно бесконечно бегать до лимита ходов
wlesavo: о, изи топ200
wlesavo: за 160 строк, норм, можно даже посильней ужать
amurushkin: не мы в дум играли в общаге по ночам по соплям ))
amurushkin: даже на монохромном монике :)
amurushkin: у меня первый комп был сборный чуть ли не с пол общаги ))
amurushkin: где то моник взял. где то клаву. мышь. корпус. сам купить мать проц и память :)
amurushkin: постепенно собрался чисто мой )
amurushkin: а потом уже когда работал то купил полностью новый и моник и системник. а тот пошел на свалку истории
wlesavo: хм, если восстановить карты для пакмана можно уже неплохую симу прикрутить, для многих тестов точно возможно почти полностью восстановить, вопрос в том валидаторы отличаются или нет
wlesavo: ух ты, выяснил что один уровень полностью зачищаю и что можно выйграть съев все пелетки
BorisZ: каждый хранил у себя частичку дума :open_mouth:
BorisZ: wlesavo ну ты монстр просто - за несколько часов на 150 место
wlesavo: ну там когда понятно что это пакман сильно проще, тем более играл же уже в пакмана
BorisZ: я помню что несколько дней только голову ломал что за игра
BorisZ: правда хинтов вроде не было тогда, хотя может и были - не помню )
wlesavo: ну у меня тоже не первый подход. я просто хинты не читал
wlesavo: ну вот да, я вообще долго думал что это лифты какие-то
wlesavo: незнаю почему но про 4 направления в голову не пришло
wlesavo: BorisZ ты не знаешь там карты в валидаторах такие же как в тестах или нет?
BorisZ: вроде карты такие же но разные не то стартовые позиции не то поведение врагов
BorisZ: несколько месяцев назад обсуждали, вроде с mykeich
BorisZ: по названию карт видно - там 2 буквы это карта а другие две буквых - хз что
wlesavo: но когда догадался про карту почему то сразу про пакмана подумал, наверное потому что раньше еще заметил что проигрываешь когда твои координаты сталкиваются с другими координатами то проигрываешь
wlesavo: прикольно что призраки не умеют в телепорты
wlesavo: и пытаются идти по манхетену
BorisZ: да, там ключ к высокому скору - предсказать как ходят призраки, у них разные алгоритмы
wlesavo: а, прикольно
amurushkin: wlesavo: незнаю почему но про 4 направления в голову не пришло, а я и не знал даже :))
wlesavo: ух наконецто все карты восстановил
wlesavo: добавил полную информацию и стало в разы хуже играть)
wlesavo: потому что флудфильная оценка теперь руинится
wlesavo: надо пробовать симу делать, но я так и не понял до конца как они движутся. в целом понятно, но некоторые моменты я не могу объяснить
Uljahn: а ты имплементил алгоритмы из оригинальной игры?
Uljahn: там 4 разных пасфайндинга вроде
Uljahn: https://habr.com/ru/post/109406/
wlesavo: не, ты чо, у меня там примитивнейшая оценка была, просто без карты ничего лучше особо не придумаешь, а теперь уже можно думать. за привидений спасибо, гляну, выглядит правдоподобно
wlesavo: ща проверю включается у них разбегание или нет
wlesavo: хм, тяжело сказать, в целом общие правила похоже что работают и что один преследователь есть реально, вот с остальными не очень понятновпринципе разбегание можно задетектить в теории
wlesavo: интересно, получается не всегда все типа приведений могут быть, а разные наборы
Uljahn: наборы с несколькими одинаковыми что ли?
Uljahn: я-то сам не пилил детект
Uljahn: да и вообще не сразу про инпуты врагов сообразил))
Lobs: а каким образом кодить
