"Indefinite improvement" for AlphaZero-like engines

[moha]

I just cannot like examples without draws. I feel this is an unallowable inaccuracy when we talk about perfect go and perfect komi - why look for trouble? One limiting factor of classes and Elo performance may be exactly the fact that there is (may?) a significant prob mass at no win no lose even vs (near) perfect players. That's why I preferred (and referred to) this version:

We can do the same with draws. ... hidden fractional advantage is rounded to the nearest of -2, -1, 0, 1, 2, etc for the final observable outcome in points. Suppose it luckily happens to be the case that naturally the game "starts at" 0.51 fractional advantage - extremely close to 0.5, from white's perspective.

My 0.1-0.9 was also the momentary balance of free room before the next worse rounding (not the nominal fraction) - and OC small mistakes by the opponent can move or even flip the balance suddenly (after they change the minimax solution, so became a whole point error but now with ease to lose back, hard to win more). Unless you round away from zero or similar there is never easy to lose (a minimax point) by both sides I think. (I understand you focused on the flipfloping above.)

One more point to make clearer or stress again (not that I think anybody misunderstood) is that with the example 0.5 player of 0/1 (rarely 2) pt errors I didn't mean a player who exhibits this particular pattern from all positions and viewpoints (even though this could be a frequently observed pattern), but meant a distributed collection of all kinds of players with averages, variances, weaknesses and strengths that (in a kind of normal-ish sense) can be approximated together as summing to this imaginary player.

The last example seem to have returned to a game without draws. Almost impossible to draw before the final transform, but even a nonperfect player can beat perfect play after it. I find it hard to see this as a good model for go with perfect komi, from what we know from smaller boards, solvable positions etc. Could you change it to match a perfect komi game with several potential subpoint (CGT or other) mistakes for both sides but with integer rounding, according to your interpretation?

I'm reluctant to use it as is, but some of my doubts would translate here as: suppose the opponent is weaker, and already moved the count by a significant part of a point in their losing way (the most common occurrence). Our variance is almost negligibly small (you assumed almost constant 0.1 avg mistake - a bit doubtful imo). Can we be sure that we can perform whole classes better or worse from these winning positions than our (near or perfect) neighbours, even if our and their mistakes will almost never amount to anything near a single point, and the final granulation is whole points so some of our tiny advantage over neighbours will surely get canceled?

(Btw to me A doesn't seem to match Bill's chilled go which I interpreted as allowing fractional final scores without any rounding - thus naturally several subpoint classes. But I guess you meant chilled-then-rounded to territory or area.)

[moha]

I think that's ok. These players are nearly perfect. They'll win against almost all other players. But since they reliably beat each other, each of them should end up >= 400 points better than the previous one. Otherwise, playing against weaker opponents who you always beat would lower your ELO rating.

I don't think so. Any player can win against any other player except perfect one, but no player can win always (assuming a normal distribution and perfect komi). The difference in that tiny fraction of upset losses matters IMO, exactly because strength and performance is to be considered across all opponents and situations. Simply chain beating is not hard with some tricks about reducing randomness, for example.

I also think that while practical Elo and similar systems often round the rating points that can be gained/lost in a match to integers (so for large differences the stronger side can not gain for a win but lose for an upset), this is not necessary. So in theory you could measure the Elo distance between very far opponents by (extremely long) direct matches, based on comparing exactly that tiny fraction of upset frequency to its expectations, via the proportion of fractional rating points gained vs lost per match (not that this would be a good or reliable thing to try in practice).

[lightvector]

The last example seem to have returned to a game without draws. Almost impossible to draw before the final transform, but even a nonperfect player can beat perfect play after it. I find it hard to see this as a good model for go with perfect komi, from what we know from smaller boards, solvable positions etc. Could you change it to match a perfect komi game with several potential subpoint (CGT or other) mistakes for both sides but with integer rounding, according to your interpretation?

Yep! The game is exactly the same except now the grid is on all the integers (...-2,-1,0,1,2,...) and the game starts at 0.499999 (so with perfect play with both players always flipping zeros on cards, the game is a draw).

The flip flopping that you get is now between wins and draws, rather than wins and losses. But that's fine, in variant C it's still pretty easy to fit multiple "75%" classes within the span of the last point, much more than 2 classes.

Let's ignore whether that many consecutive 9s is realistic as a model for Go - I'll settle for simply having exhibited a game where:
* Mistakes behave cumulatively/additively.
* The final result is a discrete integer or half-integer score in a way that seems on the larger scale to be stochastic and roughly linear in cumulative mistakes.
* The discretization of the score in this way does NOT tightly bound the number of possible "classes", in variant C (not even in the version with draws).
* Variants B and C are very hard to distinguish from only observing data from players whose error distributions are many integers wide, as they are right now for even current superhuman Go bots.
* None of it depends on any special pathologies between particular players or sets of players when matched versus each other.

Even if one doubts this is a great match for Go, because of more Go-specific details besides the above properties, isn't it fascinating that this is all explicitly possible at the same time?

As I said before many times, I don't want to try to argue this is a great match, because I don't think it is myself, at least not to this extreme. So I agree the specific numbers are doubtful, they're chosen to just make a point that this is possible in theory... and in a way still consistent with current observational evidence being too coarse to have actually ruled out!

I'm reluctant to use it as is, but some of my doubts would translate here as: suppose the opponent is a bit weaker, and already moved the count to a significant bit in their losing way (the most common occurrence). Our variance is almost negligibly small (you assumed almost constant 0.1 avg mistake - a bit doubtful imo). Can we be sure that we can perform whole classes better or worse from these winning positions than our (near or perfect) neighbours, even if our and their mistakes will almost never amount to anything near a single point, and the final granulation is whole points so some of our tiny advantage over neighbours will surely get canceled?

Yep! If you take the model at face value. Still yes, but only to a smaller degree (e.g. maybe you only squeeze in an extra 1 class) if you think the behavior is enough closer to B but still maybe could have a small component of C-like behavior, in addition to "noise" of other sorts.

I think that's ok. These players are nearly perfect. They'll win against almost all other players. But since they reliably beat each other, each of them should end up >= 400 points better than the previous one. Otherwise, playing against weaker opponents who you always beat would lower your ELO rating.

I don't think so. Any player can win against any other player except perfect one, but no player can win always (assuming a normal distribution and perfect komi). The difference in that tiny fraction of upset losses matters IMO, exactly because strength and performance is to be considered across all opponents and situations.

Oh I didn't realize you wanted to also consider vastly differently-skilled players to also measure how a model corresponds to Elo. I guess I had implicitly assumed that you meant a variety of not-too-distant players (eliminating all rock-paper-scissors effects, but still giving sane differences).

We already know that real life often increasingly deviates from Elo in the tails. And real ranking systems sometimes do use different tail models, and therefore do make orders-of-magnitude different predictions in the extremes from each other! Yet mostly it doesn't matter - there isn't a presumption that the model is supposed to be used for or should precisely match reality for estimating such tiny probabilities.

For what it's worth, the earlier example I had with normally distributed sum of errors will err on the side of the tails being *too thin*. Strong players will win *too often* against weaker players, so the rating difference as measured by strong vs vastly weaker player will actually be *even larger* than with chains of closer players. The opposite of the worry, hopefully making it more obvious that no matter how you slice it, you have more than 2 classes per point, not fewer? But if you wanted precisely Elo like tails, you could posit a logistic distribution, and if you thought that large upsets were actually more common in real life than merely logistic (plausibly true in some activities, deviating from Elo the other way), you could try a t-distribution.

[moha]

The game is exactly the same except now the grid is on all the integers (...-2,-1,0,1,2,...) and the game starts at 0.499999 (so with perfect play with both players always flipping zeros on cards, the game is a draw).

Thanks! I'm not sure how you meant your last comment? It seems variants A and B collapse immediately as it is now possible to beat perfect play, even for nonperfect players (and the game is NOT always draw even between perfect players). Variant C remains.

OC we can still look at A and B in a game theoretical sense, but note that losing the mental crutch of a deterministic minimax solution / score not only cuts ties to any board game but makes it harder to verify the model.

Anyway, let's take a reference player who (ie. the whole subset of playerbase that normally sums to him) is the smallest pointwise distance from perfect play, 1 pt weaker. To demonstrate the possibility of extra subpoint classes we need to find a player between him and perfect play, who is either more than one class away perfomance-wise from both sides, or at least the sum of these two distances is more than 2 classes. Is this possible?

OC we may find cases of chain-beating players. For example P1-P2-P3 may be increasingly stronger by a smaller half of classes, but have styles that play into the weakness of the previous when matched directly, while P3 may still be strong enough to beat P1 (maybe even by a wider than expected margin). But again strength difference does not equal direct results between (or a small subset of) players.

Your almost-constant almost-perfect players did a bit more than this, even allowing to consider performance vs a few more players in the immediate vicinity. But can they demonstrate their class advantage/differences over each other against the -1 pt player?

[Bill Spight]

FWIW, here is an easy game. Not completely irrelevant, I think.

There are some stacks of chips on the table; each stack has some number of Red chips or Blue chips. Black plays first. On her turn Black can take one stack of Blue chips off the table, or take the top chip from one stack of Red chips, and White on his turn can take one stack of Red chips or the top chip from a Blue stack. OC, play stops when there are no more chips on the table. Each player's score is the number of chips she has collected from the table. The game can be played with komi or reverse komi.

[Mike Novack]

The number of chips in these stacks might be relevant?

In the degenerate case where the stack size is 1, it does not matter which action the player takes as top chip and entire stack the same. And when the game ends, each will have taken exactly the same number.

[lightvector]

The game is exactly the same except now the grid is on all the integers (...-2,-1,0,1,2,...) and the game starts at 0.499999 (so with perfect play with both players always flipping zeros on cards, the game is a draw).

Thanks! I'm not sure how you meant your last comment? It seems variants A and B collapse immediately as it is now possible to beat perfect play, even for nonperfect players (and the game is NOT always draw even between perfect players). Variant C remains.

Sure, just focus on C then, ignore A and B.

But can they demonstrate their class advantage/differences over each other against the -1 pt player?

Oh, I think I see what you're getting at, and why you've been insistent on adding draws. Yes, you're right about this objection. I hadn't considered enough the difference between draws and drawless games, thanks for pushing on this detail.

The issue is no *single* intermediate player who wins strictly more than 75% against both endpoints if you count draws as 1/2, even though there are potentially a very large number of "tiers" of 75%s in between. In that example, if you randomly pick almost *any* sequence of two or more intermediate players between the perfect player and the 1 point, if the standard deviation of performance is not too large for "natural" players, then they will highly likely form a chain that adds up to >= 2 classes of difference end to end. It's not really that the players have particular styles that exploit each other in ways that fail to generalize to most other players, because it would happen for almost any random sequence of natural players. But if you only look at one player alone, then that player is not separated by more than one class from each end.

So I guess what you have here is that by nature of the game itself, the Elo model itself isn't very good here. Depending on exactly what population of players you select, even very generic and varied populations, I agree now the Elo range from fitting a model will be constrained by the fact that players near the ends of the range will still only 75% each other, exactly how constrained and what ratings you get from attempting to fit a model could vary based on many details simply because the model as a whole is a poor fit - there isn't a consistent way to assign ratings here.

In the real world, if losses almost never happened beyond a certain level of skill, and wins and draws were about equally split depending on color like this, then in terms of evidence about which player was "stronger", strangely draws (as, say, white) would be almost like losses - drawing as white would be a clear bit of evidence suggesting black was stronger rather than equal, and vice versa. Also, amusingly, adjusting the komi off of the game theoretic optimum by half a point would increase the Elo range greatly (the example still should work fine for non-integer komi), despite none of the game, the strategy, or the players being otherwise any different than before.

So I guess with draws you can try to squeeze in more classes than 2 in this only in a "nontransitive" way if everything else behaves linearly enough. And importantly because it doesn't depend on player's special styles or rock-paper-scissors effects, but rather works for all players, it causes the naive Elo model itself to break down and become a not so great model, for all players.

Thoughts?

[Bill Spight]

The number of chips in these stacks might be relevant?

Indeed it might.

In the degenerate case where the stack size is 1, it does not matter which action the player takes as top chip and entire stack the same. And when the game ends, each will have taken exactly the same number.

Yup.

BTW, you can chill this game by making the player pay one chip for each move, from what he has taken. In that case the game might end with an odd number of 1 chip stacks on the table. As usual, play in the chilled game is also correct in the unchilled game, with the proviso that you should take that last odd chip.

[moha]

About the drawless version: doesn't variant A and B collapse there as well? Or are you ok with nonperfect players beating perfect play with BOTH colors? And - I didn't realize this at first - version C is pure illusion, a swindle. It rounds away from zero, exactly as I mentioned earlier, which is both a logical no-no usually, and in this case a no-op: you are not rounding at all. Game result remains the high res result - and naturally you don't get any class-bounding effect of nonexistent rounding.

Back to the "complete" version with draws: What makes apart a rock-paper-scissors, a chain-beating phenomenon (where the best still beats the worst), either arised naturally or artifically, and real (in any sense) subpoint classes? My first hunch would be to look at the AVERAGE performance vs the COMPLETE playerbase. This is what strength (and Elo) is about. You might want to exclude players too far away to be meaningful - it's ok. You might also want to exclude [-1] as too far - this would raise an eyebrow. But maybe you also want to exclude players around [-0.1] who have unusually high sd? And how would you relate such almost-constant players to a sequence of 100-0 Alphazeros with NN symmetry and other randomization turned off, deterministic players always choosing the same move in a given position? They could still have decent sd (and correct and close Elo if tested vs a rich playerbase), yet may form a natural chain-beating among themselves, from not exploring each other's complete distribution (cf. behavior in all rounding cases).

In the real world, if losses almost never happened beyond a certain level of skill, and wins and draws were about equally split depending on color like this, then in terms of evidence about which player was "stronger", strangely draws (as, say, white) would be almost like losses - drawing as white would be a clear bit of evidence suggesting black was stronger rather than equal, and vice versa.

Yes this is just how I expect the perfect komi game to turn out - some tenth or two of point advantage for W or B, easier/harder to draw like in chess (and maybe differently for area and territory).

[lightvector]

moha, I'm actually not sure what you're arguing about any more? I did indeed overlook the effect that draws would have on direct comparisons between further players, so basically I agree with you that with draws seem that they do cap Elo range (cool!), or else if you try to violate that, you still can a little, but seemingly only in a way the Elo model heavily breaks down and simply fails to be a good model at all any more, so in practice there is a cap if you're talking about Elo still being practical and meaningful.

And also I think it's pretty clear now that the drawless version should actually have theoretically no limit to the Elo depth for practical player populations, despite having linear and discrete scores, so long as the game mechanically behaves in a particular way - one that is slightly quirky, but would also appear similarly linear for players with error distributions many points wide. Which also makes a lot of sense too - without draws taking a big chunk of the possiblity space, the line between win/loss can be arbitrarily thin with the right mechanics.

And - I didn't realize this at first - version C is pure illusion, a swindle. It rounds away from zero, exactly as I mentioned earlier, which is both a logical no-no usually, and in this case a no-op: you are not rounding at all. Game result remains the high res result - and naturally you don't get any class-bounding effect of nonexistent rounding.

Not sure what you mean. "Choose the nearest discrete increment to a given continuous value" is definitely a well-defined operation and is certainly not a no-op. And usually people use the word "rounding" to describe this operation?

My first hunch would be to look at the AVERAGE performance vs the COMPLETE playerbase. This is what strength (and Elo) is about.

I would normally consider Elo as a useful approximation to the real world. The most basic model is that players have ratings such that the expected win chance between any two players is a logistic in the of the difference in their ratings. Surprisingly often given a population of players, this will produce reasonable rankings and predictions of future results between pairs of players. This is because usually the population of human players, or the population of humans and bots that arise "naturally" via attempts to learn and play the game well, are transitive enough and don't contain "weird" behaviors.

Once have too many pathological players in the population (The player that plays like AlphaZero except it resigns if you open on the 1-1 point, the player that plays uniformly randomly 50% of games and like Lee Sedol 50% of games, the player who is pro level but if they see a distribution of moves that are high-probabiilty for an average human DDK in the first 100 moves, will let them win but otherwise will play their best, etc.), it can easily stop making good predictions, since the model simply is not a reasonable fit for the data any more. And I guess as we found, the structure of a game itself may force the model to be poor, even without specific attempt to create pathological players. You could obviously speculate about what an Elo model would produce if fed games for "all possible probabilistic finite state machines" or some other crazy "complete" population, but I think nobody has any idea whether any particular variant of the Elo model will produce anything sane with such data.

[lightvector]

@moha - also by the way thanks for the discussion. This was actually pretty fun to think about and explore. And also from playing around with the numbers also have a better quantitative feel for things too now - e.g. the logarithmic way that things need to scale to fit Elos within ranges different numbers of points wide (not just sub-points), some of Bill's thoughts on how chilled scores relate to outcomes in Go, and under what conditions to expect more or fewer "levels of skill" in a game, the way that the sigmoid naively imposed by Elo actually deviates from linear when you try to stack classes, etc. I think I'm pretty satisfied with things at this point.

It might be interesting to try to mathematically work out how a "complete" set of players would behave if one tried to fit an Elo model anyways (e.g. via maximum likelihood), but that at first glance seems really hard to gain any traction on, so if you actually figure out how this could work, I guess it would be interesting.

[moha]

Thanks from me too, and sorry, didn't want to keep arguing (not about the draw version at least), just wrote my thoughts on how I interpret your phenomenon from Elo and other strength metric viewpoint. I also learned new things (also about Bill's chilled scores indeed), and even got a fun idea from your seemingly-narrow variances - will try to post later.

[About the drawless version:] .. And - I didn't realize this at first - version C is pure illusion, a swindle. It rounds away from zero, exactly as I mentioned earlier, which is both a logical no-no usually, and in this case a no-op: you are not rounding at all. Game result remains the high res result - and naturally you don't get any class-bounding effect of nonexistent rounding.

Not sure what you mean. "Choose the nearest discrete increment to a given continuous value" is definitely a well-defined operation and is certainly not a no-op. And usually people use the word "rounding" to describe this operation?

I think it is implied that we take the sign of the final score (komi included) as THE result [-1, 0, +1]. For score rounding to become anything other than no-op, it must differ in some way from no-score-rounding. This means it has to change the sign for at least SOME fractional values. Rounding 0.11 to 0, for example, is an operation with consequences. Rounding 0.22 to 0.5 is not, it is no-op (in this context).

Games that decide by the sign of a fractional, unrounded score won't have limits on number of classes exactly because of the lack of a "smallest scoring unit" from where those bounds could arise from. With normal distributions on a continuous score scale, any performance can be exceeded by arbitrary extent (except 100% which however is unreachable). We know games like this, and drawless/C, which simply passes through the sign of the fractional untouched seems one of them.

[lightvector]

With normal distributions on a continuous score scale, any performance can be exceeded by arbitrary extent (except 100% which however is unreachable). We know games like this, and drawless/C, which simply passes through the sign of the fractional untouched seems one of them.

Yep. The clever "swindle" is to show that in theory one can have observed outcomes matching the outcomes Go has with half-integer komi, that also behave roughly additively and linearly, where so long as the best players so far still cumulatively make large and numerous errors, they can't tell the difference from other ways that don't allow as much Elo depth. You do this by having the discretization be a "no-op" on the sign. And maybe by some chance Go with half-integer komi could have some partial element of this - or not, it's hard to tell right now since the best players aren't good enough. So I think everything is resolved on the object level, I'm happy if you prefer to use different words.

even got a fun idea from your seemingly-narrow variances - will try to post later

[moha]

maybe by some chance Go with half-integer komi could have some partial element of this - or not, it's hard to tell

But there IS actual, meaningful rounding in go. As I wrote earlier, there is no real half point komi in integer games. Chinese with 7.5 komi is actually komi 7 with W winning ties. What happens here is that we play the game, THEN the score gets rounded (with ties retaining their prob mass), THEN we add the komi (which is integer), THEN we decide to treat final draws as W wins. Order matters.

If we would decide to round board scores to 100 or 1000 points (even using half point komi which is a hack) the game and the class count would drastically reduce - unlike when we try this in drawless/C, which in reality does no rounding at all.

[moha]

Btw doesn't CGT fail here? If I understood Bill correctly a chilled score of 6.8 could be seen as better than 6.7 (and it actually is if we stop chilled), but two chilled scores of 6.6 are the same. But since the rounding direction will matter for territory (an insanely lot at these levels), chilled 6.6 with W to move is different to chilled 6.6 with B to move - exactly what CGT wanted to avoid (with the principle that correct chilled play = correct territory play).