Hacker News Reader

Comment by dmurray | Hacker News Reader

> They gave the system 100 games from each of about 3000 known players, and 100 fresh games from a mystery player. To make the task harder, they hid the first 15 moves of each game. The system looked for the best match and identified the mystery player 86% of the time...A non-AI method was only 28% accurate.

This sounds incredible, to pick the right player out of 3000 candidates 86% of the time.

I am not sure that pruning the first 15 moves is enough to eliminate the information you get from choice of opening (which is presumably the intention of the restriction). For example, if a player religiously plays the Najdorf Sicilian as Black, you can immediately rule out many(most? ) positions that started with a French or a Ruy Lopez.

I'd like to see what the best results are from a model that just looks at the position after move 15, and use that as a baseline.

View on HN

> I'd like to see what the best results are from a model that just looks at the position after move 15, and use that as a baseline.

Reading the paper, they have an "opening baseline" which consists of frequency analysis on a player's first 5 moves. That model has 93% accuracy!

The mapping of first-five-move sequences to the positions obtained after them is almost a bijection (there are some transposition, but a small effect) so that's similar to my proposal.

I can't tell whether the 15-move cutoff is 15 half-moves, so 7-8 moves per player, or 15 moves each which is how every chess player would read the sentence.

Either way, I haven't completely read the paper yet, but I don't think it addresses the rebuttal of "I will just change my openings and the machine won't detect me".

Yeah, that means it extracts roughly 12 bits of information from observing a game after move 15. It takes 33 bits to pick out one human from everyone alive. You get at least 3 bits just knowing someone plays chess, so you're halfway there?

Good point about baseline.

From observing 100 games after move 15, I think you mean.

Oh, I thought the 100 applied only to training. But the article agrees with you -- thanks.

Where can one learn more about this technique of equating bits to pieces of information? I get that it's used in various contexts like cryptography, randomness, compression, games of Guess Who, etc. but basically just nod in fake agreement when someone formally describes a system this way. Like what first principles did you use to make this statement:

It takes 33 bits to pick out one human from everyone alive

Is it basically just 2^33 > ~8 billion humans, therefore that's the minimum information context to identify a single individual? But then what counts as an information bit - any valid Yes/No question? And how do you calculate the bit value of a piece of info (i.e. 3 bits for the knowledge of playing chess)?

It's any valid question at all, it needn't be yes or no. Humans have, at minimum, red, black, brown, blonde, dyed, grey, white, and no hair. Learning what colour hair a person has eliminates the other categories.

The way to think about the information content of a problem or of something you learn is exactly what you're suggesting. If you numbered every living person on earth, it'd take more than 32 bits and not quite fill the 33rd bit.

If you then learn a person's gender, you can eliminate all the people with the incorrect gender, which is going to leave you either 31.x bits (assuming binary gender) or 25-27 bits of remaining entropy (assuming some non-binary gender and, say, a 1-3% incidence rate).

When the parent you're responding to says you get 3 bits for knowing someone plays chess, they're guessing that 1/(2^3) = 1/8 of people, in an undifferentiated sense, play chess. Of course if we knew someone's age or gender or country of origin, the conditional information value in knowing they play chess could be greater or lesser. And realistically no one is ever trying to identify a human among all humans (partially because it seems highly unlikely that there are many questions that could equally implicate the president of the United States and a six year old on the Marshall Islands in their answer). Each bit of information represents a halving of the entropy of the target surface.

I think you got to within 1 bit of the answer from first principles ;)

It's a rough estimation technique. If every choice/factor divides the number of candidates in half (on average), you can choose between 2^N candidates with N yes/no questions (on average).

I'd assume that they are estimate that 1/8 of the human population plays chess, which feels like an over-estimate to me (but not absurdly, depending on your threshold of "plays"; by a similar process I'd estimate that at least 1/8 of humans alive are under 10 years old).

> feels like an over-estimate

That's why I said at least 3 bits. If chess players are rarer, then knowing someone is a chess player is a stronger filter. (By the same token, knowing that they're not is a weaker one; but that's not the case we're discussing.)

It's the field of information theory.

https://en.m.wikipedia.org/wiki/Information_theory

It seems really impressive.

I wonder how a chess GM would do at this test (although we’d have to restrict it to other top GMs that are active at the same time as them).

Does anyone good religiously play the same opening as black?

I don’t know chess but that sounds like a bad idea

> that sounds like a bad idea

Why? If you like it, you like it

I would assume black is more reactive. Like your opening may easily become an obviously terrible choice to white’s moves.

Ah, right. You can’t play the same moves in response to all of your opponent’s moves. (This is true for both white and black). I assumed the person you were responding to meant that they play the Najdorf Sicilian whenever white allows them to enter that line.

For example, you can’t play any kind of Sicilian, whether Najdorf or otherwise, against 1. d4 (white’s second most popular first move, behind 1. e4).

Usually when you play the opening as Black you are responding to White's move which takes the initative out of your hands somewhat. There is such a thing as transposing https://en.wikipedia.org/wiki/Transposition_(chess), where you can reach the same position from different sequence of openings. So you can reach positions you are familiar with from a number of different openings.

As far as top players I think you need to be able to have variation in your repertoire if you play the same thing stubbornly you would risk becoming predicable and your opponent can prepare lines against you specifically. It might work for one tournament but afterwards people would have studied the games and developed counters.

Reply on news.ycombinator.com