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

Bloom Filters for the Perplexed

sagi.io

Post reply on HN
Print view View original

41–46 of 46 posts

Re: Bloom Filters for the Perplexed

#41

Post by Retric »

notgood wrote: post #27
jason_slack wrote: post #16

Can anyone tell me about a use case in game design?

This link[0] has an example; so basically almost anything in a game where it has to lookup massive amounts of data (e.g. logs), the example in the article is to quickly check if the user has already seen an item (in a game with thousands of items [e.g because those were pseudo-randomly generated, think RPGs]). But it's easy to think further applications: quickly check if the player already played this chess game befo…

It's not clear to me that the added complexity aka risk of bugs is worth it in your case for any reasonable game design.

In the chess example, knowing it's possible to lose from X positions is almost meaningless most of the time. The issue is search space sizes are either to large to be useful or small enough for brute force.

Re: Bloom Filters for the Perplexed

#42

Post by notgood »

Retric wrote: post #41
notgood wrote: post #27

Earlier quoted context omitted.

This link[0] has an example; so basically almost anything in a game where it has to lookup massive amounts of data (e.g. logs), the example in the article is to quickly check if the user has already seen an item (in a game with thousands of items [e.g because those were pseudo-randomly generated, think RPGs]). But it's easy to think further applications: quickly check if the player already played this chess game befo…

It's not clear to me that the added complexity aka risk of bugs is worth it in your case for any reasonable game design. In the chess example, knowing it's possible to lose from X positions is almost meaningless most of the time. The issue is search space sizes are either to large to be useful or small enough for brute force.

You can always use it things that are not critical for the game to work; and a good coder would make it in a separate class/container so most possible bugs are isolated as well.

In the chess example the most importan thing its not for the machine to win (or lose); is so the user feels its not the same game they already played; or -dare I say- think that the enemy is "learning"

Re: Bloom Filters for the Perplexed

#43

Post by Retric »

notgood wrote: post #42
Retric wrote: post #41

Earlier quoted context omitted.

It's not clear to me that the added complexity aka risk of bugs is worth it in your case for any reasonable game design. In the chess example, knowing it's possible to lose from X positions is almost meaningless most of the time. The issue is search space sizes are either to large to be useful or small enough for brute force.

You can always use it things that are not critical for the game to work; and a good coder would make it in a separate class/container so most possible bugs are isolated as well. In the chess example the most importan thing its not for the machine to win (or lose); is so the user feels its not the same game they already played; or -dare I say- think that the enemy is "learning"

Even cellphones can run chess programs powerful enough to beat any human. The normal way to tone them down is to make them more random which prevents games from repeating in the first place. Making this a non issue.

Even ignoring that and assuming you wanted to do a lookup vs all games played with someone that's a tiny dataset so looking it up has no real downside.

Re: Bloom Filters for the Perplexed

#44

Post by hikarudo »

vertex-four wrote: post #37
hikarudo wrote: post #35

Earlier quoted context omitted.

It seems you're talking about the IO monad specifically, not about monads in general. Other monads, like Maybe and List, absolutely occur in programs written by "most developers in other languages", whether they perceive them as monads or not. For instance, a pointer type in C is like a "Maybe a" in Haskell, because a pointer can always be null (Nothing).

So how does knowing that Maybe is a monad solve a problem for anybody not programming Haskell?

I guess it helps in two ways.

First, if you realize you have a computation that can either return a value or a "special" value that means it failed, you can model this using a Maybe-like data structure.

Second, if in some part of your program you are already using a data structure that is isomorphic to Maybe, you might stand to gain from using the same interface used with the Maybe monad in Haskell (or any other monad), namely 'bind' and 'return', or similar forms.

Re: Bloom Filters for the Perplexed

#46

Post by hvidgaard »

notgood wrote: post #27
jason_slack wrote: post #16

Can anyone tell me about a use case in game design?

This link[0] has an example; so basically almost anything in a game where it has to lookup massive amounts of data (e.g. logs), the example in the article is to quickly check if the user has already seen an item (in a game with thousands of items [e.g because those were pseudo-randomly generated, think RPGs]). But it's easy to think further applications: quickly check if the player already played this chess game befo…

That is not a good usecase for bloomfilters. With a bloomfilter you can tell if something has not been added/done. But you cannot tell if the opposite is true. In technical terms, false negatives are not possible, but false positives absolutely are, and should be expected. It can tell you: "This is not in the set", or "This is possibly in the set".

With that in mind, bloomfilters should be used for things where you are only interested to know if it is not in the set, or when you can tolerate a given false positive rate and size it accordingly.

For the first example will give false positives and be hostile to players that have not attacked. That might be okay, but not what you expect, and you might as well use probability for that. The second example I suppose you can use it to only try things you haven't tried before, but it seems weird.

That said, the link you provided is actually a good post about the topic, and include some good insight. It's not trying to hide that bloom filters are No or Maybe.

Post reply on HN