Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

My Mathematical Regression

blog.dahl.dev

Post reply on HN
Print view View original

11–20 of 159 posts

Re: My Mathematical Regression

#11

Post by qsort »

ogogmad wrote: post #2

me@localhost:~> bc d=1; for(i=21; i I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to using for-loops instead. * - What it does contain is sine,…

You don't need space for 40!/20!, for example:

  let ans = 1
  for (let i=1; i
The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.

Re: My Mathematical Regression

#12

Post by Mainan_Tagonist »

The more i think about math these days, the more i see it as a muscle one must constantly train to achieve its potential.

Give it too long a rest and you have to go back at full blast for weeks on end to hope to ever achieve past performance.

I am very bad at math and have always been in awe of those who can do it well.

Re: My Mathematical Regression

#13

Post by purple-leafy »

Heh, this grid image is all too familiar to me right now.

I’m building a grid based game and engine, and I have a game replay format which is not video.

I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution.

Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering you can move 4 cells per second…

What’s the smallest worst-case raw compression artefact you can output for 1 player for a 1 minute game?

It’s an extremely fun problem to solve. I tried:

- encoding changes into bits eg using 2 bits for direction

- movement pattern batching (ie batching 2 moves into 3 bits)

- crowd patterns and movement prediction

- treating movement as a “projectile” and deriving intermediate states

And all sorts of other wild crap that I will write up about on game launch

Re: My Mathematical Regression

#14

Post by tux3 »

purple-leafy wrote: post #13

Heh, this grid image is all too familiar to me right now. I’m building a grid based game and engine, and I have a game replay format which is not video. I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution. Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering…

What a lot of games do is run a strictly deterministic simulation in lockstep. Then you don't save the path of every unit, you save one move command for the whole group. Then the game replays inputs, and the pathing algorithm should give the same result if there are no desyncs.

Re: My Mathematical Regression

#15

Post by purple-leafy »

tux3 wrote: post #14
purple-leafy wrote: post #13

Heh, this grid image is all too familiar to me right now. I’m building a grid based game and engine, and I have a game replay format which is not video. I hit a massive wall with compression, trying to compress unit pathing and was trying to solve a similar solution. Given an NxN grid, and the 4 cardinal directions (NSEW) you can move in, plus an extra action that makes you move 2 cells instead of 1, and considering…

What a lot of games do is run a strictly deterministic simulation in lockstep. Then you don't save the path of every unit, you save one move command for the whole group. Then the game replays inputs, and the pathing algorithm should give the same result if there are no desyncs.

Yes you are definitely onto something! Love to see more people talking about deterministic games.

My game is strictly deterministic, so I get bot movement for free - but the player has agency so I need to capture their deviations

That’s the tricky part! Right now I do capture input (actually just deviations) and can replay whole games, but I think I’m at the limits in terms of compression - talking bytes here not KB

Re: My Mathematical Regression

#16

Post by [deleted] »

Mainan_Tagonist wrote: post #12

The more i think about math these days, the more i see it as a muscle one must constantly train to achieve its potential. Give it too long a rest and you have to go back at full blast for weeks on end to hope to ever achieve past performance. I am very bad at math and have always been in awe of those who can do it well.

[deleted]

Re: My Mathematical Regression

#17

Post by ogogmad »

qsort wrote: post #11
ogogmad wrote: post #2

me@localhost:~> bc d=1; for(i=21; i I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to using for-loops instead. * - What it does contain is sine,…

You don't need space for 40!/20!, for example: let ans = 1 for (let i=1; i The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.

Good point. But what if `i` does not divide `ans` evenly? I suppose you could use floats and then round.

Re: My Mathematical Regression

#18

Post by [deleted] »

jp57 wrote: post #7

I think one of the saddest thing is that the kind of person who would recognize, "we can solve this seemingly complicated problem by just applying this formula", would often have trouble even getting recognized in many corporate environments. I managed a guy like that. He was capable of very complex thinking, but he wasn't in love with complexity, he was in love with simplicity. His solutions tended to be of the form…

[deleted]

Re: My Mathematical Regression

#19

Post by qsort »

ogogmad wrote: post #17
qsort wrote: post #11

Earlier quoted context omitted.

You don't need space for 40!/20!, for example: let ans = 1 for (let i=1; i The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.

Good point. But what if `i` does not divide `ans` evenly? I suppose you could use floats and then round.

It always divides it evenly, that's why it works.

After the i-th iteration of the for loop, ans will contain n!/((n-i)!i!) which is exactly \binom{n}{i}, an integer.

Technically "ans" can grow above the final result in my example, but even that could be fixed if one really wants (e.g. i must divide either ans or n-i, you play a bit with divmod to figure out which division you do first.)

Re: My Mathematical Regression

#20

Post by aesthesia »

ogogmad wrote: post #2

me@localhost:~> bc d=1; for(i=21; i I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to using for-loops instead. * - What it does contain is sine,…

Just noting that Python natively handles integers larger than the machine word size since version 2.5, so this would have worked in Python as well.
Post reply on HN