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: при ходе уже
