Hacker News Reader

Comment by notgood | Hacker News Reader

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 before (all pieces where in the same position) to make sure the enemy does something smarter this time (because that time the enemy lost), and such.

[0] https://blog.demofox.org/2015/02/08/estimating-set-membershi...

View on HN

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.

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.

This is a great application and something I can actually learn and use now. What a way to motivate learning :-)

Reply on news.ycombinator.com