Life In 19x19

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?

RobertJasiek wrote: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?

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?

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.

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.

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".

RobertJasiek wrote: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.

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

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?

They follow logically from the outcome classes.

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

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.

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

Now you are outside of CGT.

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".

See viewtopic.php?p=198774#p198774

Bill Spight wrote: There are no ties in CGT. Better B = B' <=> B >= B' and B' >= B.

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.

They follow logically from the outcome classes.

Ok, need to look into Siegel again.

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.

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

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".

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.

RobertJasiek wrote:

Bill Spight wrote: There are no ties in CGT. Better B = B' <=> B >= B' and B' >= B.

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.

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.

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.

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

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

RobertJasiek wrote: 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".

See viewtopic.php?p=198774#p198774

"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.

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.

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

Bill Spight wrote: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.

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.

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.

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.