Chat:Ru/2021-03-14

From CG community
Jump to navigation Jump to search

MadKnight: uljahn

MadKnight: srochno

Uljahn: я понял, что кодить ты это сам не будешь

tutubalin: короче, на сях заполнить вектор с 3 миллионами комбинаций у меня получается 120 мс. а надо за 50

wlesavo: tutubalin так а первая секунда на что?

tutubalin: а разве дают? вроде не написано

wlesavo: дают дают, странно что не написано

tutubalin: turnMaxTime = 50ms и всё. я на это и ориентировался

wlesavo: сорян :slight_smile:

tutubalin: не, ну если целая секунда есть, я там такое забабахаю!

vrabosh: мне кароче можно самбитить, может и 100% возьму, уже 90%..

vrabosh: tutubalin я учел, то что ты сказал, что для 9 и 10 не учитывать коров, и убрал кусок скрипта.. стало быстрей работать.

vrabosh: блин, всеволишь 2 теста не стработало

vrabosh: жалко не видно, с ошибкой сработало, по таймауту или ходы закончелись

vrabosh: еее ... я завершил задачу

vrabosh: на 54 месте

vrabosh: теперь надо учить си)

vrabosh: а может я еще таймы не прально проверяю, какой самый лучший способ время проверять?

MadKnight: уровень на 8 в Bulls and Cows 2 тут прошёл за 6 ходов

MadKnight: наконец нормально понял алгоритм

vrabosh: на питоне пишешь?

Hariton1500: а где вы нашли игру быки и коровы?

MadKnight: https://www.codingame.com/ide/puzzle/bulls-and-cows-2

MadKnight: vrabosh а что?

vrabosh: для питона это классный результат.. раскажи, что за алгоритм

MadKnight: вручную пошаговый подбор

MadKnight: чё там писать-то? 5-10 строк шагов

tutubalin: ого. на моём новом компе считается за 57мс

tutubalin: закон мура таки что-то делает

MadKnight: а на старом как было?

MadKnight: и насколько старый?

tutubalin: на старом 170. он 2008 года. на CG 120.

MadKnight: ага, они заметно мощнее стали

MadKnight: а чё за код такой?

tutubalin: быки и коровы через битмаски

tutubalin: надо поставить чо-нить тяжёлое посчитать )

MadKnight: а как ты выбираешь следующее число для теста?

tutubalin: пока никак. это чисто генерация начальных перестановок

tutubalin: я думаю, тут размера кэша свою роль сыграл

MadKnight: каких начальных?

MadKnight: для какого-то уже стартового кейса?

MadKnight: или общих для всех игр?

tutubalin: 1234567890 1234567809 1234567980

tutubalin: для N=10

MadKnight: а собираешься как выбирать?

MadKnight: ход

tutubalin: вариант 1: среди возможных комбинаций выбирать ту, которая даст больше информации

tutubalin: вариант 2: среди возможных комбинаций выбирать вообще любую, так как есть подозрение, что они все равнозначные

tutubalin: но вот мне надо провести эксперимент, чтобы проверить вариант 2

vrabosh: tutubalin это на си за 120мс делает? Ну впринципе даже с таким результтам можешь уже хорошо в топ войти

vrabosh: вместо 6 ходов макс 8 ходов будет.. на 2 хода дольше будешь делать при худших вариантах

MadKnight: vrabosh а ты собираешься на питоне пилить?)

vrabosh: я уже сделал, 49 место

vrabosh: потом может на си перепишу.

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

miklla: я начал в 2048, но что-то мой первый алгоритм даёт лишь 66ое место, неужели бимсёрч тут так необходим?

wlesavo: miklla у тебя со змейкой?

wlesavo: брутфорсом на глубину семь у меня в районе 22М было вроде

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

miklla: я хотел делать змейку, топ результат у меня с число пустых клеток -> самая большая ли в углу, но почему-то когда я добавил проверку, что вторая по величине соседствует с тем углом, то всё стало работать заметно хуже

miklla: а блин, в ней была опечаткаааааа

miklla: (в проверке)

wlesavo: miklla короче снейк эвал и будет тебе счастье

MadKnight: wlesavo miklla а вы уже все мульти сделали?)

MadKnight: tutubalin протестил эти свои эксперименты по варианту 2 ?

miklla: нет, я просто думал что бы мне поделать, и нам ум пришла 2048

miklla: жаль, конечно, что тут она отличается от оригинальной двумя аспектами, поэтому я чуть не отказался, но всё-таки попробую ещё

MadKnight: чё за аспекты такие?

miklla: во-первых в 2048 следующая плитка появляется рандомно и надо принимать решение по матожиданию, во-вторых в оригинале вероятность увидеть 4 равна 10%, а не как тут 50%

miklla: спокойной

tutubalin: MadKnight протестил

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

tutubalin: можно проверять рандомные и выбирать из них лучшую

MadKnight: но хоть для чего-то они могут быть полезны?

MadKnight: tutubalin

tutubalin: конечно! просто некоторые дают, например, 1.888 бит, а некоторые 1.889 бит

MadKnight: я так и не уверен что они битами называют

tutubalin: информация измеряется в битах

MadKnight: под что там так много бит если даже строку с числом можно записать в меньше битт?

tutubalin: это не тыщи. это одна целая, 888 тысячных

MadKnight: ааа

MadKnight: это под что столько информации?

tutubalin: ну вот есть неопределённость: какая из комбинаций загадана

tutubalin: делаешь попытку, получаешь быков и коров

tutubalin: отсеиваешь варианты, которые не подходят

tutubalin: чем больше вариантов отсеилось, тем больше информации получили

tutubalin: log2(было_вариантов/стало_вариантов) - это полученная информация

tutubalin: а теперь хитрее: мы ещё не задали вопрос и не получили ответ, но хотим узнать, сколько информации нам принесёт вопрос

MadKnight: аааа

MadKnight: так этож просто степень

tutubalin: ну!

MadKnight: зачем определение степени так сложно завернули?

MadKnight: и для чего они использую эту информацию?

MadKnight: для чего нужно это значение?

MadKnight: это типа максимум сколько можно сократить?

MadKnight: не доверяй флоатам

MadKnight: юзай точные данные

tutubalin: https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%8D%D0%BD%D1%82%D1%80%D0%BE%D0%BF%D0%B8%D1%8F#%D0%9E%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%BF%D0%BE_%D0%A8%D0%B5%D0%BD%D0%BD%D0%BE%D0%BD%D1%83

MadKnight: так это скорее степерь влияния/важности 1 бита информации на размер данных

MadKnight: и тут у нас уже есть применение

MadKnight: у нас некоторые биты информации могут давать 0 изменений, но в сумме они могут сильно сократить информацию

MadKnight: ну или дополнить её

tutubalin: если неопределённости стало меньше - значит информация получена

tutubalin: это может быть 0.0001, но не ноль

MadKnight: ну так я о том и говорю

MadKnight: это получается не константа

tutubalin: если получено 0 бит информации, значит ничего нового мы не узнали и неопределённость осталась та же

MadKnight: а степень влияния данной информации

tutubalin: блин, в топ10 пока не попал )

tutubalin: в топ11 только )

MadKnight: потому что биты информации не осилил

tutubalin: просто там рандом. надо искать удачный сабмит

MadKnight: сделай просто более умный экстрактор бит информации

tutubalin: в 50 миллисек умнее уже некуда

tutubalin: алгоритм почти оптимальный

MadKnight: ты часть тонн массивов можешь заменить на range()

tutubalin: не могу

tutubalin: во-первых, у меня нет массивов, только вектора

MadKnight: вот потому и не успевает в 50мс лол

tutubalin: во-вторых, в них хранятся комбинации в пожатом битмаповом виде. ренджом никак не заменить

MadKnight: а как фильтруется это всё потом?

MadKnight: при ходе уже