Use Letterpest to win at Letterpress • Hacker News Board

Re: Use Letterpest to win at Letterpress

#21

Post by buss » Fri, Nov 23, 2012, 10:02 PM UTC

buss wrote: post #15

zwily wrote: post #8

Earlier quoted context omitted.

I think I'd have used a bloom filter for something like Letterpress.

I'm not seeing how a bloom filter would help you here. The only application of a bloom filter that I can see is checking whether or not the word candidate you generated is in a dictionary. All n-choose-k sets is enormous and you'd spend a very long time just generating the candidates. A prefix trie, as the GP mentioned, seems like a very good and obvious approach. You avoid most of the work generating non-words becau…

On further thought, you could use a bloom filter to test if a given set of letters has any valid words, then look up that set in a normal hash table (or use an associate bloom filter).

I haven't done any calculations or experiments, but it doesn't seem like you'd save much computation time with the bloom filter vs just using a hash table that maps (letter sets) -> (words). I could see this being faster than a trie, though, since you aren't trying to do spelling suggestions and you lose a lot of time traversing the trie for all possible permutations of the letters.

Re: Use Letterpest to win at Letterpress

#22

Post by baddox » Sat, Nov 24, 2012, 12:38 AM UTC

pwthornton wrote: post #20

baddox wrote: post #17

Earlier quoted context omitted.

A timer alone wouldn't help much. One could still take a screenshot of the game board during the first turn, upload it here, then have a list of good words to use for the rest of the game.

Would there be a way for these lightning rounds to disqualify someone if they put the app into a background process? You would have to be locked into the app in the foreground for the entire match.

I've never done iPhone development, but activities in Android have an onPause method that can be overridden and gets called whenever the activity gets temporarily hidden. There would probably be problems with getting disqualified for getting a phone call, etc. but I'm certain that something can be done in iPhone.

Re: Use Letterpest to win at Letterpress

#23

Post by baddox » Sat, Nov 24, 2012, 12:40 AM UTC

buss wrote: post #15

zwily wrote: post #8

Earlier quoted context omitted.

I think I'd have used a bloom filter for something like Letterpress.

I'm not seeing how a bloom filter would help you here. The only application of a bloom filter that I can see is checking whether or not the word candidate you generated is in a dictionary. All n-choose-k sets is enormous and you'd spend a very long time just generating the candidates. A prefix trie, as the GP mentioned, seems like a very good and obvious approach. You avoid most of the work generating non-words becau…

I suspect zwily was talking about the word verification for the Letterpress app itself, not the cheating app.

Re: Use Letterpest to win at Letterpress

#24

Post by MrScruff » Sat, Nov 24, 2012, 10:17 AM UTC

gojomo wrote: post #9

MrScruff wrote: post #5

I don't really understand this - has someone really gone to all this trouble to help people cheat at a free word game?

It's the interesting problem -- letter recognition, dictionary search, constrained ranking -- that likely motivates the author(s). The practical use in helping cheaters is just a bonus for bringing added attention to the engineering achievement. Still, the Letterpress board is so fixed in its layout/fonts that I'm surprised they need a 'neural network' recognizer, and prefer a certain color scheme. Advanced assignmen…

I understand why some might be motivated to solve it as a problem, but it doesn't seem a particular impressive technical achievement to me. It's just like how everyone and his dog was writing soduku solvers a few years back.

Except in this case it's basically contributing to ruining a game, or at least the 'play with strangers' component. I would have thought a blog post outlining the approach taken to solve the problem would have sufficed.

Re: Use Letterpest to win at Letterpress

#25

Post by gojomo » Sat, Nov 24, 2012, 4:03 PM UTC

MrScruff wrote: post #24

gojomo wrote: post #9

Earlier quoted context omitted.

It's the interesting problem -- letter recognition, dictionary search, constrained ranking -- that likely motivates the author(s). The practical use in helping cheaters is just a bonus for bringing added attention to the engineering achievement. Still, the Letterpress board is so fixed in its layout/fonts that I'm surprised they need a 'neural network' recognizer, and prefer a certain color scheme. Advanced assignmen…

I understand why some might be motivated to solve it as a problem, but it doesn't seem a particular impressive technical achievement to me. It's just like how everyone and his dog was writing soduku solvers a few years back. Except in this case it's basically contributing to ruining a game, or at least the 'play with strangers' component. I would have thought a blog post outlining the approach taken to solve the prob…

There were already cheap apps in the App Store for Letterpress cheating, so showing off open-source code (or a web service) doesn't change a cheater's prospects much. On the other hand it does serve as practice/illustration of the techniques involved.

Re: Use Letterpest to win at Letterpress

#26

Post by gojomo » Sat, Nov 24, 2012, 4:09 PM UTC

pwthornton wrote: post #20

baddox wrote: post #17

Earlier quoted context omitted.

A timer alone wouldn't help much. One could still take a screenshot of the game board during the first turn, upload it here, then have a list of good words to use for the rest of the game.

Would there be a way for these lightning rounds to disqualify someone if they put the app into a background process? You would have to be locked into the app in the foreground for the entire match.

That might help, or other techniques used by some apps ('SnapChat'?) that purport to prevent the taking of screengrabs. But, it's also not that hard to type in 25 letters manually, to a nearby computer. Cheaters gonna cheat... you ultimately have to play with people you trust, or choose to trust.

Re: Use Letterpest to win at Letterpress

#27

Post by zwily » Thu, Dec 06, 2012, 12:07 AM UTC

baddox wrote: post #23

buss wrote: post #15

Earlier quoted context omitted.

I'm not seeing how a bloom filter would help you here. The only application of a bloom filter that I can see is checking whether or not the word candidate you generated is in a dictionary. All n-choose-k sets is enormous and you'd spend a very long time just generating the candidates. A prefix trie, as the GP mentioned, seems like a very good and obvious approach. You avoid most of the work generating non-words becau…

I suspect zwily was talking about the word verification for the Letterpress app itself, not the cheating app.

Right - just for verification in Letterpress. The occasional false positive wouldn't be so bad, and you can tune your bloom filter so that it's really rare.