Mathematical Go Endgames mentions that the method of playing a difference game to compare two moves in the same position can be proven mathematically. Believed, but... Has it been proven and where? Or is it a direct implication of certain definitions or theorems of CGT? Which and how?

For combinatorial games, suppose that Black can move from A to B or to B'. If either move dominates the other, how can we tell?

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Assume B dominates B' => B >= B' <=> B <= -B' <=> B - (-B') <= 0 <=> "Playing the difference game of the moves to B versus B' ". QED.


Suppose that White can move from A to B or to B'.

Assume B dominates B' => B <= B' <=> B >= -B' <=> B - (-B') >= 0 <=> "Playing the difference game of the moves to B versus B' ". QED.


EDIT

No. These sketches of proofs are insufficient for describing difference games for comparing two moves. We must also consider the following outcome classes because a difference game depends on the two cases of Black or White starting.

- The player's first move is better than the opponent's if 1) the player to continue wins the difference game and 2) the opponent to continue does not win it.
- The player's first move is worse than the opponent's if 1) the player to continue does not win the difference game and 2) the opponent to continue wins it.
- The first moves of the player and the opponent are equal if 1) the player to continue ties and 2) the opponent to continue ties.
- The player's and opponent's first moves are incomparable if 1) the player to continue wins the difference game and 2) the opponent to continue wins it.

Now, how to work out my sketches to complete the proof?

Good.

The question is if B >= B' or if B'>= B. (As you point out, there are other possibilities.)

B >= B' iff B - B' >= 0 iff Black wins the difference game, B - B', if White plays first. (OC, in CGT Black if she gets the last play to make jigo.) And vice versa. OC, if B = B' then the plays are equivalent in terms of CGT.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

If B <> B' it is still possible for the move from A to B or from A to B' to be preferable, regardless of the rest of the board, if either move reverses.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Suppose that Black can move from A (which can include any environment without kos now or later) to B or to B'. Consider their difference game compared to 0, that is, B - B' ? 0. We define

I) B > B' <=> B - B' > 0 :<=> 1) Black continues and wins the difference game AND 2) White continues and does not win it.

II) B >= B' <=> B - B' >= 0 :<=> White continues and does not win the difference game.

III) B < B' <=> B - B' < 0 :<=> 1) Black continues and does not win the difference game AND 2) White continues and wins it.

IV) B <= B' <=> B - B' <= 0 :<=> Black continues and does not win the difference game.

V) B = B' <=> B - B' = 0 :<=> 1) Black continues and ties AND 2) White continues and ties.

VI) B || B' <=> B - B' || 0 :<=> 1) Black continues and wins the difference game AND 2) White continues and wins it.

Should these be definitions or do the :<=> equivalences follow from the definitions of CGT outcome classes and why?

Does this complete the proof (whether by definition or not)?

(We call > or < "the larger dominates the smaller, and can allow equality.)

***

Please explain and show an example for "If B <> B' it is still possible for the move from A to B or from A to B' to be preferable, regardless of the rest of the board, if either move reverses".

There are no ties in CGT. Better B = B' <=> B >= B' and B' >= B.



They follow logically from the outcome classes.



Well, all you need is II).

In ONAG the >= relation is defined recursively: G >= H iff there is no H_L such that H_L >= G and there is no G_R such that G_R >= H. (H_L is a left follower of H, and G_R is a right follower of G.) The outcome classes are defined from that definition.



Now you are outside of CGT.



See viewtopic.php?p=198774#p198774

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

I see. OTOH, I do not adhere to CGT strictly and do not mind to go outside CGT by speaking of positions instead of combinatorial games. This gives me freedom to redefine / reinterpret equality, I think.



Ok, need to look into Siegel again.



Oh! As you see, I am not familiar with this fundamental CGT theory. I feel like learning algebra at university.



See viewtopic.php?p=198774#p198774 :)[/quote]

"reverse" in the go theory meaning rather than the CGT meaning? Anyway, I still do not understand why incomparable can have preference for a move.

Of course. However, 1) you then have the onus of proving your theory; 2) the definition I gave does not depend upon CGT; 3) CGT has been shown to apply to go, except for ko positions.




You don't really need ONAG to apply CGT to go. It is just that you asked about definitions.



OK. Black can move from A to B or from A to B'. B and B' are incomparable. However, suppose that B' reverses to C. Now if C >= B, then the play from A to B' is preferable to the play from A to B; likewise, if B >= C, then the play from A to B is preferable to the play from A to B'.

Edit: The relation between B and B' does not depend upon A. But whether either of them reverses does depend upon A. Considering reverses then, gives us more information upon which to base the choice between moves.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Thanks to all of you for your kind thoughts, and for your friendship over the years.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

Ok, thank you for the clarification!

On the Hempel's Raven Paradox and the weakness of confirmatory evidence

This is not about go, but the current discussion on evidence of cheating at go by using a bot ( viewtopic.php?f=10&t=15538 ) prompted this.

When I was a kid I read an article in Scientific American by Martin Gardner about the Hempel's Raven Paradox. Briefly, here it is, more or less as Gardner presented it. Logically, the proposition that all ravens are black is equivalent to the proposition that all non-black things are not ravens. Therefore, a red dress is evidence that all ravens are black. That is counterintuitive (a paradox). Do we really think that a red dress is evidence that all ravens are black? That's crazy!

The resolution of the paradox that Gardner presented is that, yes, a red dress is evidence that all ravens are black, but it is much, much weaker evidence than a black raven, because there are many, many more non-black things than ravens.

I have mentioned how I was fortunate, as an undergraduate, to spend an afternoon with L. J. Savage talking statistics. He was very generous with his time and attention. He did not convert me to Bayesianism, which was out of favor in those days, but our discussion showed me that I actually was one. That is, that I believed in the probability of hypotheses.

I also studied Keynes's Treatise on Probability, which takes a kind of Bayesian viewpoint, but also discusses the problems with Bayesianism. Keynes regards Bayesian probability as a form of logic. I got the problem with the probability of the sunrise from Keynes.

In my twenties, with that background I took another look at Hempel's Raven. There is a problem with the contrapositive to "all ravens are black", expressed as "all non-black things are not ravens". Where does things come from? Expressed more precisely, a la Quine, "all ravens are black" becomes "whatever X may be, X is a raven only if X is black". X is not a thing, it is a logical pronoun, a placeholder. And the contrapositive becomes "whatever X may be, X is not black only if X is not a raven". Again, that says nothing about things. But what kind of, ahem, thing could X be?

But we can also express "all ravens are black" with this statement, "given that X is a raven, X is black". Or, in terms of Bayesian probability, P("X is black"|"X is a raven") = 1. The "given" I got from Keynes. Keynes also points out that that is not quite right. It should be P("X is black"|"X is a raven", b) = 1, where the comma means "and" and "b" stands for our background knowledge. Note that this is not a proposition in first order predicate logic. The logical formulation of Quine is not about ravens, it is about everything ("whatever"). The probability statement is about ravens. A red dress is not evidence that all raven are black because it is not a raven. The dress is irrelevant.

More to come.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

On the Hempel's Raven Paradox and the weakness of confirmatory evidence, II

In my forties I revisited Hempel's Raven. It was in the back of my mind when I was studying negation. What is a non-raven? A red dress, plainly. How about a purple cow? Purple cows do not exist, but they could. "Whatever X may be"! Since I was interested in Bayesian logic, a la Keynes, the question comes up. Suppose that we have a 2x2 table with the numbers of black ravens, non-black ravens, black non-ravens, and non-black non-ravens. If we include imaginary non-ravens, it affects the numbers. (Not a problem for "given a raven, it's black", but we have other statistical questions to ask.) It's really a question of what is our universe, and there is no obvious answer.

Around the same time I ran across a brief paper about Hempel's Raven from a Bayesian standpoint which came to the same conclusion that Gardner had. Non-black non-ravens are evidence that all ravens are black, but very weak, because there are many more of them than there are of black ravens. To reach their conclusion they held the marginal totals of their 2x2 table constant. Now, one of the things that Savage had told me that afternoon was that you didn't have to do that. OC, holding those totals constant was standard practice, but, given the go ahead, I played around with not doing so. Eventually I concluded that, if you are going to test for association, then it's a good idea. And that was the standard test. So the question the paper was really addressing was whether there is an association between ravenness and blackness. Obviously, there is, and obviously, a red dress is evidence of that association.

But my solution, which ignored the contrapositive, bothered me. If we know what our universe is, then we know the numbers, and the contrapositive is statistically well defined. We should be able to find the probability of "given that X is not black, it is not a raven" and if probability is a form of logic, that probability should be the same as the probability of "given that X is a raven, it is black". Obviously we cannot guarantee that. Back to the drawing board.

More to come.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

On the Hempel's Raven Paradox and the weakness of confirmatory evidence, III

During all of these cogitations I realized that there is another form of the proposition, "all ravens are black", namely, "Whatever X may be, X is black or X is not a raven". Confirming instances include everything that is black and everything that is not a raven. So a black dress is evidence that all ravens are black, and doubly so, being both black and a non-raven. BTW, this was what Hempel originally said, so screw you, Martin Gardner. Given Hempel's original formulation, why did Gardner and others, including the authors of the paper I had read, ignore the confirming evidence of black dresses? Anyway, in our 2x2 table, if we see a non-black raven we have disproven the hypothesis that all ravens are black, and if we see anything in any of the other three boxes, that is confirmatory evidence.

But what goes in the table? How about a piece of yellow cheese, a non-black non-raven? OK. Let me cut that piece in two, so that there are two pieces of yellow cheese. That's more evidence that all ravens are black, right? The more pieces I cut, the more likely it is that all ravens are black! Wow! Science is fun!

No, that has to be wrong. But it shows that our scientific universe is not the universe of things. What else can we count to get our statistics? I cannot claim to have solved the problem of the statistical universe, but that question would not have bothered Keynes too much, because he did not believe that all probabilities are numbers.

For scientific purposes, I think that the proper universe is that of observations. There is no set way of defining observations, but we can operationalize them, and that's good enough, I think, even though others might operationalize them differently. Cutting up pieces of cheese is not part of our operational definition of observing ravens. But we cannot eliminate observations of non-ravens, at least not easily, because a raven or non-raven is not an operation. But we should define our operations to make observing a raven as likely as we reasonably can. So just looking around my room, in which I do not expect to see a raven, should not be included in our observational universe.

Even so, in our 2x2 table our most frequent box will probably be that of non-black non-ravens, with black non-ravens coming next, and then black ravens, and then non-black ravens, if any. And making a new observation does not take away any other observation, so our margins can change.

OK, under these conditions, how much does a new observation that is not that of a non-black raven alter the odds that all ravens are black? Well, as we might expect, it does not alter them much. Confirmatory evidence is weak. But, to my surprise, it does not matter which of the three boxes the observation falls into, the effect is the same. The observation of a black dress has the same effect as the observation of a black raven. Logically, that makes sense, as every observation that is not one of a non-black raven has the same logical status. Hempel might be pleased. (I doubt if he was a Bayesian.)

So yes, there is a counter-intuitive result (paradox). All observations of non-ravens or non-black things are very, very weakly confirmatory, if at all.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

I don't really think the original result (observing the red dress provides confirmation that all ravens are black) is a paradox. Instead, I think it shows that humans are really, really bad at intuitively grasping the implications of very large numbers. If I have seen one black raven and was able to observe every non-black thing in the universe, then of course I would confirm that all ravens are black. The problem is that the set of non-black things in the universe is uncountably large, so I don't really learn much by any particular observation.

Your idea of defining an observational universe helps a lot with this problem. Let's say I'm sitting down to play a game of go, and my opponent hands me a bowl that is (apparently) filled with black stones. My working hypothesis is that "All go stones in this bowl are black." Making observations outside of the bowl doesn't add to my knowledge about the situation. But if I catch a glimpse of white in the bowl, only to realize that an errant piece of paper had fallen inside, it does add (some) information to support my hypothesis. Of course, you're right that it's weak evidence. I won't know for sure that there are no white stones buried in the bowl until I have examined every stone in the bowl.

The use of a statistical epistemology makes more sense in this limited universe, too. If I know there are only 180 go stones in the bowl and I have observed 179 of them to be black, that would increase my confidence in the hypothesis that all of the stones are black. Contrast this putting my hand into a bowl and pulling out a single stone at random: that doesn't tell me a whole lot about the makeup of the bowl. (Unless, of course, I allow my previous knowledge that go players tend to keep their stones separated by color to inform my hypothesis. )

By the way, Hempel's basic hypothesis was wrong: there are (rarely) white ravens.

Also, I found a really great guide to Bayes rule and its implications. The final page on the path I followed was on Bayesian scientific virtues, and I think it sheds light on why so many people feel uncomfortable with the Carlos decision. I don't have time to outline all of that right now (and this thread probably isn't the place), but at the very least there was not testing of the advance prediction that similarity to Leela's top three moves would be highly correlated with cheating.

Right. When I rethought Hempel's Raven in my forties, I realized that the theory of evolution should predict non-black ravens with high probability, both albino ravens and non-black varieties. A web search quickly revealed that both have been observed.

BTW, I have mentioned Bayesians who influenced me, including Savage, Good, and Keynes. The Bayesian revival of the late 20th century is interesting, because most of the people were raised on anti-Bayesian statistics, and many are unaware of the problems with Bayesianism that Keynes and others grappled with. A giant, IMO, of the Bayesian renaissance is Judea Pearl, whose writings I highly recommend. Some modern Bayesians think that the problem of the sunrise is simply solved by Cox's theorem and Bayesian updating (because that is their theory of knowledge). Earlier 20th century Bayesians knew better. Good hypothesized different levels of probability distributions, but I don't think that that really solves the problem. (Not that he claimed that it did, AFAIK.) Pearl I don't think addressed that problem explicitly, but he pointed out that certain kinds of knowledge can make other kinds of knowledge irrelevant. Then it is clear that if we know that the earth revolves on its axis, the fact that the sun rose yesterday and today is irrelevant to whether it will rise tomorrow, and that makes Bayesian updating irrelevant, as well.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

I think most paradoxes like this are born from tricky ommissions from the problem setting, and/or any role of infinity (like two envelopes or the St. Petersburg lottery). The ravens seem no exception.

1. "all ravens are black" -> among ravens, there is no non-black
2. "all non-blacks are non-raven" -> among non-blacks, there is no raven
3. "all things are black or non-raven" -> among all things, there is no non-black raven

As a heresy I think the first form is not completely equivalent to the second. One slight difference is in worlds without ravens (makes the latter true but the former somewhat ill-defined IMO, even if theory says otherwise). And while the refutation is the same (a single non-black raven), the three forms do also carry a gradually broadening feeling (they refer the key cell from different slices of the 2x2 table, which may come into effect if the rules or the sample set of observations is not fixed).

Some information that seems missing is how many Xs are there, and how were they selected? In a world with only three instances in total, one of them not being a non-black raven is a lot of evidence, regardless of what it is. In a world with millions of ravens but only two non-black instances, a red dress is more evidence than a black raven. Even without prior knowledge of such totals, it may be important to guess whether an observed raven may have more easily been non-black, than a red dress a raven.

And just looking for the statistical probability of the existence of a non-black raven assumes no deeper logic in the assignment of labels "raven" and "black", and also that the sample set is static. But even after observing all samples the question may be extended: what if further samples were found, or what about birds born later? In this sense the minimal evidence (one less potential refutation) offered by all three cells is not the end of the story. It is knowledge of the sample generator algorithm (or the likelihoods of potential algorithms) that allows calculation of the real probability of a statement.

Which seem to imply that observation of a black raven is also very weakly confirmatory, if at all?

Indeed. For scientific purposes I think that Jaynes is right. Start with finite models and take them to the limit.



Yes, since the scope of negation could be infinite.



I address those questions by trying to define the universe of observations in such a way as to include all ravens, but to exclude as many non-ravens as possible.



So it would seem, and that is a popular view, among those for whom the question makes sense. Gardner suggested it, and I bought it, but eventually I came around to Hempel's view. All that matters is whether we observe a non-black raven or something else. Including a black dress.




You betcha!

When I calculated the posterior odds of the existence of a non-black raven, I was quite surprised to find that they were the same, regardless of whether the new observation was of a non-black non-raven, a black non-raven, or a black raven. OC, that cannot happen if you are asking about the association between ravenhood and blackness. You have to ignore the margin totals to avoid that.

And if you ignore the margin totals, what point is a 2x2 table? You might as well have a 1x2 table, with one cell for non-black ravens and the other cell for everything else.

_________________
The Adkins Principle:
At some point, doesn't thinking have to go on?
— Winona Adkins

Visualize whirled peas.

Everything with love. Stay safe.

If the problem is narrowed down as a finite sequence of independent samples of four types A-B-C-D, then it's not surprising that the probability of the existence of a D sample depends only on the number of seen/unseen samples. But I'm not sure if this is the same as the original raven problem.