Hacker News new | past | comments | ask | show | jobs | submit | zeroonetwothree's comments login

> For example, it could be possible that, if we generated a random map in some way, 99% percent of the time, the three-color map coloring problem would be easy, but 1% of the time, it would be very difficult.

> This would still be NP-complete, but would make for a terrible cryptosystem - a scheme based on this problem would be easily broken 99% of the time!

I don’t think this explanation is great. We could just generate instances until we found the hard one and then use it. So the answer is more complex than just as written.


You don't know if the one you generated is hard. Graph coloring is easy for large but trivially connected graphs, and many many problem instances turn out to have structure that can be exploited to solve it efficiently. You would basically need to implement a procedure for determining the lower bound of the runtime of all known algorithms for the problem instance which is most likely very difficult, and even if possible, you don't know if your particular class of generated problems turns out to be easily solvable by a yet to be discovered algorithm.

Amateur observation, take with a grain of salt: On the other hand, I guess we are doing something similar when generating a new public/private key pair on an elliptic curve. It just turns out that finite fields have very little (known) structure to exploit compared to e.g. colored graphs, so we have more confidence in the assumption that the generated discrete logarithm problem is indeed hard.


The point is not that all NP hard problems make bad cryptosystems, but rather the NP-hardness guarantee fails to translate into a useful guarantee for a cryptosystem.

It's about the proof, not the computation.


Can you explain your usage of NP hard in your comment?

A problem being NP-hard is one of the two requirements of being in NP-complete (the other being that it's NP). If I remember correctly, problems that are NP-hard without being NP are undecidable, so in contexts like "what problems can we base cryptography on?", it's basically the same as saying NP-complete, since we aren't able to base cryptography on undecidable problems.

https://en.wikipedia.org/wiki/NP-hardness


Not undecidable, it's just not possible to verify if an answer is correct in polynomial time. There are problems know to be decidable, known to be NP-hard and outside of NP. (E.g. in NEXPTIME)

how do you know if an instance you picked is hard?

Another problem with your suggestion: Do we even know that a 1/polynomial sized fraction of 3-coloring instances are hard? (Else you'll never sample one). (NP-Hardness certainly does not give such a guarantee, even though it sounds weak)


RSA is kind of shaky like this. You generate key and then run some tests hoping it’s “good”. Most of the time it isn’t so you try again. Many products have failed because they were not.

this mostly isn't true. for much smaller keys there were risks of "weak primes", but as general purpose factoring algorithms got better and pushed keys bigger a higher and higher percent of primes end up safe. with 2048 bit primes, the odds of your prime being significantly weaker than average drop to something like 1 in 2^1024

What is a "weak prime" here (i.e. by which properties is such a prime number characterized)?

Suppose that p-1 has no large prime factors, eg suppose p-1 divides 10000!, then you can factor N by calculating something like x = random() ^ (10000!) % N. Then x will be 1 mod p (or rarely 0, if x was) but probably not mod q unless q has the same property. Then gcd(x-1,N) = p, and you've factored N. A similar trick works with Lucas sequences if p+1 has no large prime factors. So instead of attacking your key with a very expensive algorithm that doesn't care about special properties of p,q, they might gamble that your key is weak and try a cheaper algorithm first. So folks would avoid keys where p+1 or p-1 was "smooth" in this way.

However, we don't care much about this attack anymore for two reasons. One is that N must now be big enough to resist attack by the Number Field Sieve (and not just the Quadratic Sieve). At least if there are only two primes in the RSA key, this means that p,q must be big enough for these attacks to be very unlikely to work. But just as importantly, it turns out that you can do the above attack with exponentiation on a random elliptic curve instead of regular exponentiation / Lucas sequences. This is how most math libraries implement factor(). It's slightly slower but since the random elliptic curve will have a random order instead of exactly p+1 or p-1, it is equally likely to work with any p,q of a given size, regardless of special properties they might have.

In other words, an attacker can re-randomize how weak or strong a key is by using elliptic curves. So there's not much point in avoiding ones that look weak at first glance.


A prime pair that’s easily factorable

I'd also note that zero-knowledge proofs (which are considered a branch of cryptography) often do rely on NP-complete problems like the three-color maps.

That's completely unrelated, the reliance there is because you want to be able to prove "any statement in NP" in zero knowledge. It then suffices to give a protocol for just 3-colorings, because "any statement in NP" can then be reduced to a 3-coloring.

How do you know which ones are the hard ones? I don't think it's easy to figure that out.

Consider that you are a shareholder of the employer, or a customer of the employer, or a fellow employee. Wouldn’t you prefer that the employer hire the best candidate for the job regardless of their background?

It’s unfortunate that Cody had a rough life, but it’s not the job of his employer to help his. They aren’t a charity after all.

I also don’t know where racism played into your example at all so it’s weird you bring it up. It seems to be entirely about SES.


I imagine some government agencies do use git so the answer is likely yes.

Did you also complain when they made these changes in the first place?

If I’m buying one thing then it’s much faster to self checkout than have to wait in line.

I agree with you for large purchases.


Slow news day?


Seemingly tiny, inconsequential stories like this can add up.

This sends a signal, and could hint at things to come.


This. If the timing were different, I'd agree with the "slow day" sentiment.

But, given we're not two weeks out of inauguration, it's a signal that at least some oligarchs are convinced that physical proximity to Trump will help them achieve their Machiavellian ends. It will be interesting to see who else follows along. Bezos has had a place here for a while.

It's a good time to be a realtor who specializes in Kalorama, that's for sure.


https://www.realtor.com/news/trends/trump-sends-d-c-s-luxury...

I haven't followed this closely throughout history but I bet we're going to see cycles of people with power cycling in and out of the area based on who is in office and what they need to influence the government on.


Right? I am more surprised he doesn't already have an apartment in DC for when he needs to be there.


He probably does. Or at least I assume a furnished apartment is always available. Buying "property" (and I assume in Zuckerberg terms, that means a large home or a piece of land) implies a more substantial investment and possibly a commitment to spend a much larger percentage of his time in DC.


In DC you rent an apartment to spend time at the halls of power. You need someplace to sleep and keep your stuff. Not just lobbyists, but also senators and representatives do this.

You buy a home to entertain powerful guests.

The Conways famously purchased an 8 million dollar mansion during the Trump administration, IIRC. This stuff goes on all the time. If you pay attention to these stories, you can start to understand how power really works in the US.


Bill gates in his recent interview with WSJ said one of his past mistakes he regrets is not having a Microsoft office in DC sooner.


Jeff Bezos has owned an opulent mansion on a huge piece of land at the top of the hill in Georgetown for over a decade


He likely stays in a lot of hotels/airbnbs.


The risk of a hidden camera or microphone in an Airbnb/hotel would be reason enough to buy your own place, if you were a public company CEO with this much power.


Slow news hour.


I remember my father saying something like “if this is all they got for news, it means pretty much everything is okay in the world”.


Is it “thinking” or is it regurgitating analysis of the problem it found somewhere on the internet?


Are you "thinking" or are you regurgitating analysis of the problem based on what you read on the internet, too?

This one is funny because for something like leet code, nearly everyone just reads the best answers, learns them and learns how to regurgitate them in an interview environment.


It seems like all the algorithms post 2000 or so do not have that property as much. For example: https://web.eecs.umich.edu/~pettie/papers/jacm-optmsf.pdf


Meh, I agree in spirit but in practice it’s quite hard to get enough unique names using descriptive terms. I also think there’s some benefit in learning history that comes from naming things after people.


In practice, the most it gets is people thinking "I guess some guy named Fenwick was involved somewhere along the way", if even that. I think there's a lot of benefit to learning the history of how things were discovered, but that should be done consciously by making it part of the teaching material. The names make barely any difference.

It's not trivial to come up with descriptive names, but the difficulty is often overstated because people underestimate its importance. The names don't have to be perfectly descriptive, we don't need twenty syllable names like organic chemical compounds, but every step taken towards making it descriptive helps a lot. The reality is that the names get chosen basically arbitrarily in journals or textbooks, with hardly any thought given to how it will affect generations of students, working professionals, and even future researchers in remembering the concept and looking it up in their mind among the hundreds or thousands of other things they've learnt.


I don’t find this “super good”. It’s mostly giving 2 clues which is the most basic level of competence. The paper 4 clue is reasonable but a bit lucky (eg Jack is also a good guess). I also don’t see it actually using tactics properly, which I would consider part of being “super good”. The game isn’t just about picking a good clue each round!

Now obviously it’s still pretty decent at finding the clues. Probably better than a random human who hasn’t played much. Just I find the post’s level of hype overstated. It feels like the author isn’t very experienced with Codenames.

It would be interesting to compare AI:human vs human:human games to see which does better. It seems like AI:AI will overstate its success.


Ok, we've taken supergoodness out of the title now. Presumably the post is still interesting!

(Submitted title was "I got OpenAI o1 to play the boardgame Codenames and it's super good".)


Can you elaborate on some of the more advanced tactics?

When I play, it's mostly about getting a good 2 clue each time. Then if you can opportunistically get a 3 or 4, that's awesome.

Some tactics come in for choosing the right pairs of 2's so you don't end up mismatched, or leaving clues that might be ambiguous with your opponent's... But that's mostly it.

It'll be fun for multiplayer! Just like how in other online games you can add in a AI to play as one of the players.


If you really want to get good, your goal is not so much to get as many tiles as possible, but rather to get the tiles that are semantically distinct from your opponent’s. A single mistake that triggers your opponent’s tile is generally enough to lose the game. And even if they don’t do it, having them uncover the tiles from their side that are semantically similar to your own team is also useful.

If you want to get nasty, you learn to abuse the fact that the tile layouts follow rules and that you can rule out certain tiles without considering the words.


Memorizing the tile layouts is too much for me haha (imo against the spirit of the game). I usually play online now anyway so I hope they don't follow those same patterns as the physical version.


Online specifically avoids this by randomising the grids, except in some modes like mirrors where you can't do much to preserve symmetry.


> you learn to abuse the fact that the tile layouts follow rules and that you can rule out certain tiles without considering the words.

Can you clarify? Isn't the card placement random?


There are 40 setup cards with 4 possible rotations that specify agent placements, so it's theoretically possible to do some kind of memorization.

Personally I'd find that kind of play style very unfun, and would rather switch to fully randomized boards if I played enough that it became a problem.

https://danluu.com/codenames/


It’s randomish. There are facts about the possible layouts you can memorize.

I don’t know most of these rules but there’s never 5 in a row; or even 4 in a row if you’re the team with one fewer (second team to play).

Edit: because the game layout is determined by choosing one of a few dozen possible layout cards and randomly rotating it


Other advanced tactics involve giving a broad clue that matches 3-4 of your own and just one other (either your opponents or a civilian). Your team can pick up all the matches across several turns and the one off doesn't hurt as much as the plus four helps


The S-tier tactic: When that high-number clue is cut short by a turn-ending mistake, the guessers tell their clue giver to inflate the number given during the totally unrelated next clue by however many remained from the truncated turn for which they don't need additional information to locate (and therefore it would be wasteful for a future clue to re-group those) so the stated number of that next clue must allow for its own cards plus the prior cards.

Example: The clue is "places 4" and the guessers choose 1 correctly and then 1 wrong answer, but they had achieved consensus about 2 others (and are confused about only the remaining 1). So the turns ends but they inform the clue giver to inflate by 2 next turn. That clue giver (after the other team goes) will then say the clue is "people 5" and the guessers will know that they shall select 2 places and 3 people.

This can cascade beyond just a pair of turns.


I don't think this sort of communication from guessers to clue giver is in the spirit of the game (at least in my play group). However, inflating later clues is a reasonable approach! It's just that I don't think you're allowed to communicate the amount of inflation. Guessers must determine whether people 5 has slack to allow additional guesses on previous clues.


You're free to add additional prohibitions on communication as a house rule I guess, but the only prohibition in the rule book I've seen is that the clue giver's speech must consist exclusively of clues (and private consultation with the other clue giver). The clue giver is free to adjust their clue in reaction to anything they hear, and guessers can speak freely.

Important: the clue giver cannot acknowledge the instruction during gameplay. That would certainly extend beyond giving a clue! The guessers must know that their clue giver can play this way prior to the game commencing.

Edit: I just consulted the rules and this is the most relevant section:

> If you are a field operative, you should focus on the table when you are making your guesses. Do not make eye contact with the spymaster while you are guessing. This will help you avoid nonverbal cues.

> When your information is strictly limited to what can be conveyed with one word and one number, you are playing in the spirit of the game.

The author's use of the pronoun "you/your" switches from field ops in that first paragraph to spymasters in that second paragraph, confusingly. With that in mind, it boils down to this: field ops cannot seek non-clue information from spymasters, and spymasters cannot convey non-clue information. The strategy I'm suggesting involves neither!


If you take this idea of communication restrictions to the limit, you could imagine the guessers identifying N sets of cards by a single word each as they discuss their guess. The clue giver listens, then uses the clue that identifies the correct set of N cards.

You really just need an algorithm to generate unique sets of 8 or 9 from the whole board, and identifies those sets by a word.


Yeah it's interesting to take these ideas to the extreme... even at the lower end I don't like it, I think zero communication outside of clues is the best way to follow the spirit of the game. But a little bit of banter and "kibitzing" is what makes it fun too.


I played in a Codenames tournament at CGE's stand at GenCon, and they forbid guessers from communicating at all. Officially, its supposed to be just the clue and number and nothing else.

Of course, I never play this way in my own games


How do guessers arrive at a consensus about what card to touch, if they are forbidden from communicating at all?


officially its a 4 player only game, at least at the tournament. I never do it this way myself though


The communication is only necessary/important if people haven't set this as a convention in the first place. I'll say that prior to ever looking at my clues: "I will give you higher numbers than what I said if you miss by more than 1. THe number I pick will always be high enough as to allow you to, with the +1 guess you get for free, make guesses on all the words I was hinting at.

There's also all kinds of not necessarily intended communicaton from the guessers in the fact that you can listen to which words they were considering and didn't pick. Nothing in the game attempt to say that you should not consider, say, whether they were going in the right or wrong direction in their guessing, but it sure can make a difference in how to approach later clues. If they were being very wrong, there might be a need to double up on words that you intended, and that your guessers missed.

In the same fashion, nothing in the game saying that I cannot listen to those guesses as a member of the other team, whether guesser or spymaster, and then change behaviors to make sure we don't hit words they considered as candidate words without very good reasons. Let them double dip on mistakes, or not make their difficult decisions easier. It's not as if the game demands that everyone that isn't currenly guessing should wear headphones to be sure they disregard what the other team says or does.


You can of course play however you want (and I certainly think this is clever), but imo this is likely against the spirit, and perhaps letter, of the rules.

The rule on giving clues is:

"If you are the spymaster, you are trying to think of a one-word clue that relates to some of the words your team is trying to guess. When you think you have a good clue, you say it. You also say one number, which tells your teammates how many codenames are related to your clue." (emphasis mine).

The rule states that the number should be the number of words related to the clue. There is later provisions allowing you to use zero and infinity, but outside of these carve-outs (and imo the "allowed" language is telling here, since it implies any other number not equal to the number of words is not allowed) I don't think this is legal.


We always allow any number when we play, because part of the thinking is we cannot be sure what the spy master has in mind. Of course, the number is related to the clue but possibly also to the game history up to that point. The teammates and opponents might interpret it wrong, and that’s OK. Infinity is typically used when there is enough info in principle to finish the game and a high risk if you dont; zero is super rare. We do tend to have very aggressive bids with tenuous connections, and 4 or 5 for a clue word are used in most games. Often, they don’t all work out in a single round, but on some lucky boards or in spousal teams, they occasionally work well.


You have a valid point, to which I'll concede. The rule book gives an example (spanning pages 4-5) where a guesser uses prior clues to select a card while the count is still within the number stated by the spymaster, but I suppose an allowance for guessers to deviate in this way does not also imply that spymasters may deviate in this way. Mea culpa!

Taking this a step further, given that it's well-known that a clue is deemed invalid when it pertains to cards in certain non-definitional ways (sounds-like, number of letters, etc.), it seems extremely reasonable to call a clue followed by N invalid if it doesn't pertain to N cards in a definitional way.


Indeed, a good Codenames-playing bot should know how to do all of this, in addition to using its LLM to generate great clues.


Yeah, in fact we tend to play without a limit on the number of guesses, just to avoid this sort of loophole. In variants like Codenames Duet I think there's also no limit on the number of guesses.

Another thing the guessers can do if unsure about one of the tiles from the last round, is to tell the clue giver which tile they think it was. The clue giver then tries to give a clue that either tenuously links to it or clearly excludes it. That can give the clue more scope for linking to several other words. It risks giving information to the other team though so is more of an final turn play.


> the one off doesn't hurt as much as the plus four helps

Doesn’t the turn end if you hit the opponents word?


Yes, but they can go back for those words in future rounds


I find the game more about reading the people on your team (and the other team) to understand how they think.

You have to give entirely different clues depending on the people you play with.

Sometimes you can also play adversarial and introduce doubt into the opposing team by giving topic-adjacent clues that cause them to avoid one of their own cards. It works better if someone on the other team tends to be a big doubter. It also can work when the other team constantly goes back and tries to pick n+1 cards that they think they missed from the last round, which gives you a lot of room to psychologically mess with them.

Sometimes you have a clue that only really matches 2, but because only 1 of the wrong matches is a neutral card and you could match 2 more by a massive stretch, you say “4.” Worse case, they get 2 right but then they pick the neutral card but in the best case, you stand to gain 4 for a clue that should only match 2.

I like Codenames because they are many meta ways to play the game. What makes Codenames unique is that, unlike a lot of other games (Catan, Secret Hitler, CAH, etc.), it’s an adversarial team game where the team dynamics and discussions are not secret so you can use them to your advantage.


experienced players who know their teammates well can reliably get 3-4s. if you only go for safe 2s against these opponents you will lose every time.


They should at least play with two different AI models.


Join us for AI Startup School this June 16-17 in San Francisco!

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: