Establishing a player's identity

[Gobang]

How should I proceed if I wanted to establish a "fingerprint" of a player's style?

Has anyone ever reliably done this? Are you willing to put in the amount of work needed to achieve this? If you do it thoroughly I imagine that the amount of work might be comparable to a significant portion of the work involved in putting together a dissertation for a doctorate. (If that is your plan, to incorporate this in a dissertation or some form of scientific paper, the best of luck to you).

Assuming this has successfully been done, where will you be? You can say that using methodology X, Y and Z you have evidence that there is an X% probability that the player who was supposed to be playing was not playing. What good will that do? Does it prove anything? Are you ready to put in the work it will take to refute the refutations of your method?

All I am saying is that you should carefully consider what you will achieve, or if you will in fact achieve anything before you embark on a course of action.

Don't get me wrong, I would like nothing more than a method that can conclusively prove that player X is lying when he says he played a certain game. I suspect it will be much easier to prove that player X did not play a game, rather than to prove that player Y, or computer program Z did in fact play it.

[Bill Spight]

How should I proceed if I wanted to establish a "fingerprint" of a player's style?

Has anyone ever reliably done this? Are you willing to put in the amount of work needed to achieve this? If you do it thoroughly I imagine that the amount of work might be comparable to a significant portion of the work involved in putting together a dissertation for a doctorate. (If that is you plan, to incorporate this in a dissertation or some form of scientific paper, the best of luck to you).

It is easier, and more practical for purposes of detecting when one specific player has played instead of another, to decide between the two.

Edit: This kind of thing has already been done with the authorship of certain of the Federalist Papers. There were three possible authors.

[Fede]

How should I proceed if I wanted to establish a "fingerprint" of a player's style?

Has anyone ever reliably done this? Are you willing to put in the amount of work needed to achieve this? If you do it thoroughly I imagine that the amount of work might be comparable to a significant portion of the work involved in putting together a dissertation for a doctorate. (If that is your plan, to incorporate this in a dissertation or some form of scientific paper, the best of luck to you).

Assuming this has successfully been done, where will you be? You can say that using methodology X, Y and Z you have evidence that there is an X% probability that the player who was supposed to be playing was not playing. What good will that do? Does it prove anything? Are you ready to put in the work it will take to refute the refutations of your method?

All I am saying is that you should carefully consider what you will achieve, or if you will in fact achieve anything before you embark on a course of action.

Don't get me wrong, I would like nothing more than a method that can conclusively prove that player X is lying when he says he played a certain game. I suspect it will be much easier to prove that player X did not play a game, rather than to prove that player Y, or computer program Z did in fact play it.

Please, this thread should be used to give ideas and to try develop them. I don't give interviews

I will repeat what I have already said: I know that it may be impossible to show whether the accusation has merit or not. I am not pursuing only this approach. I think that it is my duty to try.
I'll add that some players have a unique style that is easier to recognize (think of Takemiya Masaki, for example). And that, in my opinion, many players can recognize their own games because they know how they play. So I don't consider this hopeless.

Now, please, let's use this thread for what it was intended. Pretty please.

[Fede]

Federico,
Have you checked games for program usage?
It is much easier, only 1 player is involved, and it coincides with availability of programs.
If those games started in this year's league, then you have only few programs to check.

I thought a little more about this. Yes, I will use AIs to examine the games, as they may help show whether a game was one sided or not. Having someone repeatedly beat a stronger opponent in a one sided game would be increasingly unlikely and a strong AI will make it simpler (and I hope more objective) to judge whether the game is one sided or not.

Edit: I consider this as another approach that I will add to the analysis, not related to the identity question.

[Gobang]

And that, in my opinion, many players can recognize their own games because they know how they play.

I play a lot, and if you gave me some random game I played a year or two ago I could not positively identify that it was me playing. It would help me a lot to really know how I play. I might be able to change my play in a positive direction.

[pnprog]

Hi, just a quick update:

I made some cleaning in my list of SGF games: I removes games with very weak bots that would play almost randomly, and also remove some clones bots of the two I selected. In the end, I ended with ~600 games for each.

I prepared the data, and had a first try at training a network.
I used 80 games from each bots, so 40 games each (because that what I was planning to use for Fede's case).
And I split both set in 40 games for training, and 40 games to check for over-fitting.
So totally 15574 entries for training, and 14831 entries to check for over-fitting.

With that, the network is able to converge (it's simple error back propagation algorithm) but, unfortunately, the network is over-fitting: the error on the training set decreases to low value, but the error on the control group just decrease a little bit

Ok, I am not a machine learning specialist in any way, so I will play a bit more with what I have to see if I did not messed up something, but then I will upload the training data so that others can have a try at it as well. But... yeah, I am not quite optimistic this would work. Maybe with more data? But it would not be useful for Fede's case then.

[Fede]

Hi, just a quick update:

I made some cleaning in my list of SGF games: I removes games with very weak bots that would play almost randomly, and also remove some clones bots of the two I selected. In the end, I ended with ~600 games for each.

I prepared the data, and had a first try at training a network.
I used 80 games from each bots, so 40 games each (because that what I was planning to use for Fede's case).
And I split both set in 40 games for training, and 40 games to check for over-fitting.
So totally 15574 entries for training, and 14831 entries to check for over-fitting.

With that, the network is able to converge (it's simple error back propagation algorithm) but, unfortunately, the network is over-fitting: the error on the training set decreases to low value, but the error on the control group just decrease a little bit

Ok, I am not a machine learning specialist in any way, so I will play a bit more with what I have to see if I did not messed up something, but then I will upload the training data so that others can have a try at it as well. But... yeah, I am not quite optimistic this would work. Maybe with more data? But it would not be useful for Fede's case then.

Please bear in mind that I have only a vague idea of how neural networks work, so my questions may be a bit stupid.

How large is the error on the control group?
What is the bottleneck at the time being? The games played by A or the games for which we need to establish whether the player was A or B?

If it's the former, I'm still searching new games to use to train the network for A, so the number of games available could increase. It would be nice to have an idea on how many would be needed.

[pnprog]

How large is the error on the control group?

First, a word on the error:
For one training entry, the output should be (1,0) for game played by player A, or (0,1) for games played by player B. And I defined the error simply as the average error for each output. So if the network output (x,y) instead of (1,0), the error is (abs(1-x)+abs(0-y))/2
Then, I defined the error on the training group or control group simply as the average error for all training entries.

Usually, I would use the quadratic error for each training entry. But since one can expect to have a lot of duplicate entries for both player A and player B (all the games they start by hoshi in top corner...) I don't want to give to much weight than necessary to those entries. So simple average.

So in my last run, the training group reached 3% average error, and the control group was at 43%

What is the bottleneck at the time being? The games played by A or the games for which we need to establish whether the player was A or B?
If it's the former, I'm still searching new games to use to train the network for A, so the number of games available could increase. It would be nice to have an idea on how many would be needed.

I am not sure in fact. I guess more training data will make it harder for the network to over-fit. But it might just make it impossible to converge as well.

I started a run with 2x400 training games and 2x400 control games. It's very slow on my computer, so I will let it run this night. If it over-fits, then I don't know what to do. If it does not converge, I will try with bigger network sizes (more layers).

If it converges but don't over-fit, bingo

In any case, I will share the training data (or the way to generate them from SGF) to let specialists have a try.

[Bill Spight]

So in my last run, the training group reached 3% average error, and the control group was at 43%

A reduction of the average error from an expected 50% to 43% by training on only 40 games is not bad, IMO.

One thing you can try is to train on all but one game and use it for testing. Then include it in the training set and take out another game for testing. Train on the new set and test on that game. Do this 80 times and you get an estimate of the error rate for training on 79 games.

[moha]

A reduction of the average error from an expected 50% to 43% by training on only 40 games is not bad, IMO.

There may also be huge random variance since the test set is small. And I'm afraid you are underestimating the amount of training data required for answers of this complexity. How would a human perform on this task - if he didn't know go before?

[Tryss]

If your training set has 3% error and your test set has 43%, you're overfitting way too much : it doesn't work.

So you either need more data or an other network configuration

[Bill Spight]

A reduction of the average error from an expected 50% to 43% by training on only 40 games is not bad, IMO.

There may also be huge random variance since the test set is small. And I'm afraid you are underestimating the amount of training data required for answers of this complexity. How would a human perform on this task - if he didn't know go before?

I doubt if I am underestimating the amount of training data required. I was quite surprised that training on only 40 games did so well.

Anyway, the question is required for what. To help is all that I require.

[pnprog]

I started a run with 2x400 training games and 2x400 control games. It's very slow on my computer, so I will let it run this night.

The training is still ongoing (performed 98 iterations), but it showing signs of over-fitting already: 27.8% vs 39.7%

Still, it is better than before.

[moha]

There is always some difference between the training set and the test set, depending on amount of training (if you couldn't heavily overfit the training with infinite iterations that would mean a problem with the net or the data, esp. with small training sets - oc in practice you stop much earlier).

I'd be more worried about the test results - what does it learn, and how reliably it generalizes in the long run and against different (unseen) opponents? My guess would be simple statistics like average distance from opponents move, tenuki percentage, second and third line move frequency, number of ko captures etc. Which could appear to work in one case, but could also fail in another. Did you also have move number as input?

[Tryss]

A possible idea :

Step 1 : Start by training a level x policy network on games of players with level x. This network is reusable.

Step 2 : Add another couple layers at the end and train the last couple layers to discriminate between player A and not player A (you can further train the whole network when your last layers are well trained)


By building on a network that already "know" something, it may take much less training data than by starting with a fresh network

Obviously, this is just an idea and testing is needed (and I'm not able to try this experiment before a couple weeks)