#prog #math #gamedev

How I Found A 55 Year Old Bug In The First Lunar Lander Game

(thanks @itpgchannel)

#prog #math #video

Больше всего меня удивило следующее:

Первые решения автора использовали скорость перемещения каретки в качестве выходного параметра (ещё для первой части с уравновешиванием одинарного маятника). В качестве fitness function использовалась очень простая вещь: единица счёта начислялась за каждую секунду симулированного времени, во время которой конец маятника находился достаточно высоко. С таким подходом ему удалось сконструировать решение, но для получения эстетически удовлетворительных результатов — без лишней дёрганности — ему пришлось модифицировать fitness function, чтобы она штрафовала решения за ненулевую угловую скорость маятника и за отклонение от серединного положения.

В комментариях к первому видео автора справедливо заметили, что использование скорости в качестве выходного параметра фактически означает бесконечное ускорение и потому нефизично и нереалистично. В конце второго видео автор попробовал подход, при котором в качестве выходного параметра используется ускорение каретки вместо скорости — разумеется, скорость каретки пришлось добавить в качестве входного параметра для нейросети. В итоге получилось рабочее и при этом не дёрганное решение — и для его достижения было достаточно первой, самой простой формы fitness function.

#algo #math #video

О том, как вывести формулу, описывающую распределение ещё не отсортированной части массива при сортировке пузырьком.

youtu.be/Gm8v_MR7TGk

#math #meme

#math #article

(thanks @sv9t_channel)

#math #video

How good is advantage in D&D?

Видео, которое со всех сторон рассматривает статистические эффекты преимущества и помехи на броски в Dungeons&Dragons — в частности, пытается прикинуть, каким модификатором их можно заменить. Если вам непонятны термины выше — спокойно, у видео есть вводная, которая это всё объясняет.

Тут, оказывается, биг дил случился. Доказали, что BB(5) = 47,176,870. Практического смысла в Busy Beaver не очень много, прямо скажем, но всё равно интересно.
- Тут можно почитать хорошую статью с деталями, историей и т.п.
- Тут само объявление об успехе
- А тут хорошие посты про это же, но кратко и прямо в телеге

#cs #math #science

Напомнило, кстати, про #prog #math #article Turns are Better than Radians, которая аргументирует, что использование радианов для тригонометрических функций не особо осмысленно. В качестве одного из аргументов автор приводит тот факт, что одна из реализаций синуса для AVX (как и "pretty much every fast trig library", но тут уже предлагается верить автору на слово) первым шагом в вычислениях фактически делит аргумент на π, что зачастую является немедленной отменой умножения на π на вызывающей стороне.

#math #article

Breaking CityHash64, MurmurHash2/3, wyhash, and more...

<...>

As a teaser, this article explains how you can generate strings such as these, thousands per second:

cityhash64("orlp-cityhash64-D-:K5yx*zkgaaaaa") == 1337
murmurhash2("orlp-murmurhash64-bkiaaa&JInaNcZ") == 1337
murmurhash3("orlp-murmurhash3_x86_32-haaaPa*+") == 1337
farmhash64("orlp-farmhash64-/v^CqdPvziuheaaa") == 1337

I also show how you can create some really funky pairs of strings that can be concatenated arbitrarily such that when concatenating k strings together any of the 2^k combinations all have the same hash output, regardless of the seed used for the hash function:

a = "xx0rlpx!xxsXъВ"
b = "xxsXъВxx0rlpx!"
murmurhash2(a + a, seed) == murmurhash2(a + b, seed)
murmurhash2(a + a, seed) == murmurhash2(b + a, seed)
murmurhash2(a + a, seed) == murmurhash2(b + b, seed)

a = "!&orlpՓ"
b = "yǏglp$X"
murmurhash3(a + a, seed) == murmurhash3(a + b, seed)
murmurhash3(a + a, seed) == murmurhash3(b + a, seed)
murmurhash3(a + a, seed) == murmurhash3(b + b, seed)

(thanks @daily_ponv)

#math #лингво #meme, видимо

Будем считать, что это #math #meme

#prog #abnormalprogramming (а на самом деле #math)

How to Optimize your Rust Program for Slowness
Write a Short Program That Finishes After the Universe Dies

Aside: Practical concerns about running a program beyond the end of the universe are outside the scope of this article.

#math #meme

#math #meme

(thanks одной девушке, которая увлекается карандашами, котами и кодом)

#math #meme

(thanks @furthunivers)

#math #game

В сфере настольных ролевых игр наиболее известной и популярной игрой, безусловно, является Dungeons & Dragons пятой редакции. Сказать, кто стоит на втором месте, проблематично, но, по разным оценкам, следующей по популярности игрой в этой нише является Pathfinder второй редакции. Это — разные игры, но общего у них довольно много (что неудивительно, учитывая, что обе игры прослеживают свою родословную от D&D 3.5).

Одна из этих общих частей — пошаговые бои, в рамках которого участники действуют каждый в свою очередь в пределах установленного в начале боя порядке. Ещё одним общим моментом является использование хитов/очков жизни (hit points) для отслеживания физического благосостояния живых существ, включая персонажей под управлением игроков. Существа в обеих системах обычно умирают, когда число хитов опускается до нуля, но это не касается персонажей игроков. Вместо этого они валяются в бессознательном состоянии и каждый ход делают проверки, по итогам которых персонаж может стабилизироваться, то есть остаться без сознания, но без угрозы для жизни. Детали этих проверок уже разнятся между этими двумя играми, но они схожи тем, что характеристики персонажей на эти проверки не влияют, а также тем, что при получении хитов персонажи автоматически перестают умирать.

В D&D 5e правила следующие:
- Когда персонаж впервые падает без сознания (= опускается до 0 хитов), он начинает умирать и отслеживать провалы и успехи спасбросков от смерти. Поначалу число и тех, и тех равно нулю.
- В начале каждого хода, когда персонаж умирает, он делает спасбросок от смерти. Это означает, что игрок кидает куб кость d20 (икосаэдр, с 20 гранями) и сравнивает выпавшее число с 10. Если число равно или больше 10, то персонаж получает один успех. Если число меньше 10, то персонаж получает один провал.
- Если персонаж получает три успеха спасброска смерти, он стабилизируется, перестаёт умирать и больше не делает спасброски от смерти. Если он получает три провала, то умирает окончательно.
- 1 и 20 на кости имеют особое значение. Значение 20 означает, что персонаж получает 1 хит (= перестаёт умирать), приходит в сознание и может действовать на этом ходу. Значение 1 означает, что персонаж получает два провала вместо обычного одного.

Прежде чем объяснить правила в Pathfinder 2e, нужно сначала объяснить, как там делаются проверки. И в DnD, и в PF для этого кидается кость d20, прибавляются уместные модификаторы и результат сравнивается с заранее заданным целевым порогом, численно характеризующим сложность задачи. Значение равно или больше порогу — успех, меньше — провал. PF2 отличается тем, что проверка также может окончиться критическим успехом и критическим провалом. Критический успех получается, если число на кубе после модификаторов превосходит порог на 10 или более. Аналогично критический провал получается, когда результат на 10 или более меньше порога. Числа 20 и 1 имеют особый эффект: 20 увеличивает степень успеха на одну, а 1 степень успеха на одну уменьшает (на практике для типичных задач, когда сложность не является очень высокой или очень низкой, это означает, что 20 на кубе является критическим успехом и 1 критическим провалом).

В Pathfinder 2e правила следующие:
- Когда число хитов персонажа опускается до нуля, он начинает умирать и получает состояние dying 1 (обычно, при некоторых обстоятельствах это значение может быть выше).
- В начале каждого хода, когда персонаж умирает, игрок делает recovery check. Для этого игрок кидает кость d20 и сравнивает значение с порогом, равным 10 + текущее значение dying. Успех уменьшает значение dying на 1, провал увеличивает значение dying на 1. Критические успех и провал меняют значение на 2 в ту же сторону.
- Когда значение dying увеличивается до dying 4 или выше, персонаж умирает насовсем. Если значение dying уменьшается до dying 0 или меньше, персонаж теряет состояние dying и стабилизируется.

#prog #math #article

Ideal divisors: when a division compiles down to just a multiplication

The division instruction is one of the most expensive instruction in your CPU. Thus optimizing compilers often compile divisions by known constants down to a multiplication followed by a shift. However, in some lucky cases, the compiler does not even need a shift. I call the corresponding divisors ideal.

#math #video

Every PROOF you've seen that .999... = 1 is WRONG

TL;DR: распространённые "доказательства" опираются на манипуляции бесконечными числовыми записями без строгого обоснования их смысла и корректности операций над ними

#math #video

Видео о замысловатой математической задаче, двух различных подходах к её решению и о том, как в анимэ Assassination classroom использовали эти два подхода для того, чтобы раскрыть двух персонажей и их различия.

youtube.com/watch?v=64ZjFXrFBqE