Principles from Basic Endgame Trees (Daniel Hu)

[RobertJasiek]

Lemma 6:

The proof is correct.

[RobertJasiek]

3.3 General case of n / introduction:

Assuming b, c, d unequal to all a_i move values may be necessary to proving but means that cases of equality demand further propositions.

What is "a difference game argument (strategy stealing)" for proving that choosing the largest depth 1 move value or play b? If something is trivial, write it down, please!

The paper claims

s_Bi+1 - s_Bi = a_2i+1 - a_2i+2 - ∆(a_2i+3,...,a_n,c) + ∆(a_2i+1,,...,a_n,c).

Let me try by applying the definition given in the paper:

s_Bi+1 - s_Bi = (a_1 - a_2 +... + a_2i+1 - b + ∆(a_2i+2,...,a_n, c) - (a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c)) =

a_1 - a_2 +... + a_2i+1 - b + a_2i+2 - a_2i+3 +... -+ a_n +- c - (a_1 - a_2 +... - a_2i + b - a_2i+1 + a_2i+2 -... +- a_n -+ c) =

a_1 - a_2 +... + a_2i+1 - b + a_2i+2 - a_2i+3 +... -+ a_n +- c
- a_1 + a_2 -... + a_2i - b + a_2i+1 - a_2i+2 +... -+ a_n +- c =

2a_2i+1 - 2b +- a_n-1 -+ 2a_n +- 2c.

I cannot confirm the paper's claim and, at least not in its way, subsequent conclusion s_Bi+1 - s_Bi >= 0.

Therefore, I am not motivated to
- try exercise 7 (What is its answer?),
- verify s_Wi+1 - s_Wi <= 0 (If it is "amazingly simple", please write down its proof!),
- verify the alleged conclusion "Hence it is correct strategy for Black after 2i moves to delay playing move b if and only if [he can gain] from doing so and White cannot stop him. That is [...,] there is [...] s_Bi+j > s_Bi but s_Wk > s_Bi for all i <= k < i+j. The correct timing to play at b is just before the increasing s_Bi and the decreasing s_Wi cross. [...A] greedy algorithm (looking only one move ahead) works."

EDIT

[RobertJasiek]

You study one local gote with both players' simple follow-ups in an environment of simple gotes without follow-ups. I studied this four years ago but still need to publish it. My study allows equalities. I found major cases depending on how the temperature compares to the two follow-up move values. For low temperature, play locally. Medium or high temperatures are rather demanding and require different alternating sums of the intermediate move values of the environment.

Later in your paper, you also speak of sente. I have still to read the remaining paper. Since it declares to study local gote endgames only, I need to see later what you mean by "sente".

[RobertJasiek]

Principle 5 says: "Don't play on b unless your opponent can get more from playing b on their next turn. Otherwise play at b."

What is "gaining more on the local reply than the first local play gains"?

In a local gote, the reply gains less. In a local sente, the first local play and its reply gain the same: the follow-up move value. If, however, the first local play (such as a self-atari) gains less than the local reply, then the first local play is a mistake!

So what shall principle 5 tell us?!

My suspicion is that you do NOT mean gain(s). Maybe you mean move values and that the opponent's reply has a larger move value than the player's first local play? That would be a local sente. However, your paper has declared to only study local gotes (decreasing move values).

So what shall principle 5 tell us?!

Is the subsequent text on 1 1/3 pages supposed to be its proof? A proof of what meaning of principle 5?


EDIT:

Oh, maybe principle 5 has a typo: "unless" -> "if". If so, it would read:

"Don't play on b if your opponent can get more from playing b on their next turn. Otherwise play at b."

Now, THIS is self-explaining:) Do you mean this? (We presume no kos now or later. In a ko fight, it can sometimes be correct to incur a local loss.)


EDIT 2:

The second sentence "Otherwise play at b." demands context. It is only a truth for low temperature. For high temperature, playing locally at b can be wrong. E.g., if the temperature is 100 but the local move values are small.

[RobertJasiek]

s_Bi+1 - s_Bi = (a_1 - a_2 +... + a_2i+1 - b + ∆(a_2i+2,...,a_n, c) - (a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c)) =

a_1 - a_2 +... + a_2i+1 - b + a_2i+2 - a_2i+3 +... -+ a_n +- c - (a_1 - a_2 +... - a_2i + b - a_2i+1 + a_2i+2 -... +- a_n -+ c) =

Presumably I have made a mistake here. In 3.3, c is not specified. However, now, I guess that c is assumed to be like in lemma 6. That is, it need not occur after a_n. The paper should clarify the presuppositions for 3.3, in particular for c. So we have:

s_Bi+1 - s_Bi = (a_1 - a_2 +... + a_2i+1 - b + ∆(a_2i+2,...,a_n, c) - (a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c)) =

a_2i+1 - b + ∆(a_2i+2,...,a_n, c) - b + ∆(a_2i+1,...,a_n,c) =

-2b + a_2i+1 + a_2i+2 - ∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c).

Instead, the paper writes

a_2i+1 - a_2i+2 - ∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c).

Still somebody must have made a transformation mistake:)

we do not further transform the alternating sums but apply lemma 6 directly to them. Ok, but first let us clarify which transformation is right!

[RobertJasiek]

On pages 5+, I expected a proof of something before but find a new study. I see. However, I am unsure what is being studied there.

The first sentence there suggests a study of generalisation to games of larger depth. What shall have larger depth? Only b? Also any a_i? In the subsequent study, I do not recognise generalisation to games of larger depth. Now I wonder whether the first sentence there stands on its own and is entirely unrelated to the subsequent study on pages 5+, or whether that study is meant for generalisation to games of larger depth. Please clarify!

In the book Combinatorial Game Theory, Aaron N. Siegel, chapter VII and other CGT literature, one finds the topics of stop, score, rich environment, orthodoxy, sentestrat and (without rich environment) orthodox accounting. They study generalisation to games of larger depth but the error of an approximation in a thin environment can be T/2 (half the temperature).

You presume an irregular environment and want optimal scores and correct first moments of playing locally. For that, generalisation to games of larger depth still appears to be too hard. For an environment of simple gotes without follow-ups (you would say depth 1) and one local gote endgame of depth 2 with the initial move value b and simple follow-ups of both players (whose move values you call c and d), a complete analysis is possible. As I have said, I have done it. My guess is that, on pages 5+, you also try to do it, although still without equalities.

Daniel, please confirm that, on pages 5+ except for page 5 sentence 1, you study an environment of simple gotes without follow-ups (you would say depth 1) and one local gote endgame of depth 2 - or tell us what you mean to study there!

As long as this is unclear and I am not convinced of all now applied earlier results, I do not study every detail on pages 5+. Nevertheless, I have noticed some things during my earlier readings as follows.

What justifies that the following conditions determine optimal play?

s_Wi-1 > s_Bi > s_Wi

s_Bi+1 > s_Wi > s_Bi

My own study has been different: I have studied the cases Black starts or White starts separately. Instead, you seem to combine and relate both cases so I want to see your justification why you may do so and why these inequations express the right last / first moments.

You are on track when mostly the intermediate parts A_| of alternating sums remain.

In your case analysis (cases 1 to 4), you compare a_2i+1 to c and d. You do so because you concentrate your study on the verge between the last moment of playing in the environment and the first moment of playing locally. My own study instead compares the (dynamically changing) temperature T (which you might call a_1) to c and d (for which I use different letters;) ). Basically, my cases are the same but I also allow equality:

Case 1: T >= c, d AND NOT T = c = d
Case 2: c > T > d
Case 3: d > T > c
Case 4: c, d >= T (including T = c = d here is easier)

Furthermore, you are also on track that some values are multiplied by 2 but others aren't.

In my study, the notation greatly differs from yours but the necessity to fight against signs is familiar:) Therefore, I cannot say yet whether (except for equality, which you postpone) your results agree to mine for an environment of simple gotes without follow-ups and one local gote endgame of depth 2.

[RobertJasiek]

s_Bi+1 - s_Bi = (a_1 - a_2 +... + a_2i+1 - b + ∆(a_2i+2,...,a_n, c) - (a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c)) =

a_2i+1 - b + ∆(a_2i+2,...,a_n, c) - b + ∆(a_2i+1,...,a_n,c) =

-2b + a_2i+1 + a_2i+2 - ∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c).
[...]
Still somebody must have made a transformation mistake:)

Me, of course:) Indices must be substituted i -> i+1 properly and carefully! Since the inserted index term is multiplied by 2, signs keep their parities. Let me try 3.3 / introduction again:

s_Bi+1 - s_Bi =

(a_1 - a_2 +... - a_2(i+1) + b - ∆(a_2(i+1)+1,...,a_n, c) - (a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c)) =

(a_1 - a_2 +... - a_2i+2 + b - ∆(a_2i+3,...,a_n, c) - (a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c)) =

a_2i+1 - a_2i+2 - ∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c)),

as the paper states.

Now (see the paper for the detailed case analysis c > a_2i+2 or c < a_2i_2) lemma 6 implies

-∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c)) >= a_2i+1 - a_2i+2 >= 0 so

s_Bi+1 - s_Bi = (a_2i+1 - a_2i+2) + (-∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c)) >= 0 + 0 = 0.

[RobertJasiek]

Conjecture s_Wi+1 - s_Wi <= 0. Proof:

s_Wi+1 - s_Wi =

(a_1 - a_2 +...+ a_2(i+1)+1 - b + ∆(a_2(i+1)+2,...,a_n,d)) - (a_1 - a_2 +...+ a_2i+1 - b + ∆(a_2i+2,...,a_n,d)) =

(a_1 - a_2 +...+ a_2i+3 - b + ∆(a_2i+4,...,a_n,d)) - (a_1 - a_2 +...+ a_2i+1 - b + ∆(a_2i+2,...,a_n,d)) =

(a_1 - a_2 +...+ a_2i+3 + ∆(a_2i+4,...,a_n,d)) - (a_1 - a_2 +...+ a_2i+1 + ∆(a_2i+2,...,a_n,d)) =

-a_2i+2 + a_2i+3 + ∆(a_2i+4,...,a_n,d) - ∆(a_2i+2,...,a_n,d) =

// We have d < b < a_2i+3.

-a_2i+2 + a_2i+3 + ∆(a_2i+4,...,a_n,d) - a_2i+2 + a_2i+3 - ∆(a_2i+4,...,a_n,d) =

-2a_2i+2 + 2a_2i+3 <= 0.

[RobertJasiek]

The changes in scores are also described by the following more general proposition of combinatorial game theory for enriched scores of a local position P comprising one or several local endgames, which can be iterative, in a rich environment. We presume no kos now or later. B means Black starts, W means White starts, the index is the temperature.

For two real numbers T > S > 0, we have
T - S ≥ B_S(P) - B_T(P) ≥ 0,
T - S ≥ W_T(P) - W_S(P) ≥ 0.
In particular, B_T decreases in T, W_T increases in T and each is continuous in T.

[RobertJasiek]

Exercise 7:


"if and only if": I do not buy this. E.g., equality can also mean a_1 = a_2 =... = a_n = b = c = d including an ambiguous local endgame or some subset of such equalities.


"If max (c, a_2i+2) >= a_2i+1 => s_Bi+1 = s_Bi": Proof:


Case max (c, a_2i+2) = c:

Study s_Bi+1 = s_Bi <=> b - a_2i+1 + c = a_2i+1 - b + c
because these might differ but played in either stated order.

By definition of b and c, we have b >= c.
By definition of a_2i+1 and a_2i+2, we have a_2i+1 >= a_2i+2.
By the initial and case assumptions, we have c >= a_2i+1.
Hence b >= c >= a_2i+1 >= a_2i+2.
In the second played order, we also have a_2i+1 >= b.
Hence b = c = a_2i+1.
Hence b - a_2i+1 + c = a_2i+1 - b + c.


Case max (c, a_2i+2) = a_2i+2:

Study s_Bi+1 = s_Bi <=> b - a_2i+1 + a_2i+2 = a_2i+1 - b + a_2i+2
because these might differ but played in either stated order.

By definition of a_2i+1 and a_2i+2, we have a_2i+1 >= a_2i+2.
By the initial and case assumptions, we have a_2i+2 >= a_2i+1.
Hence a_2i+2 = a_2i+1.
In the second played order, we also have a_2i+1 >= b >= a_2i+2.
Hence a_2i+1 = b = a_2i+2.
Hence b - a_2i+1 + a_2i+2 = a_2i+1 - b + a_2i+2.

[RobertJasiek]

"Hence it is correct strategy for Black after 2i moves to delay playing move b if and only if [he can gain] from doing so and White cannot stop him. That is [...,] there is [...] s_Bi+j > s_Bi but s_Wk > s_Bi for all i <= k < i+j. The correct timing to play at b is just before the increasing s_Bi and the decreasing s_Wi cross. [...A] greedy algorithm (looking only one move ahead) works."

After having studied the paper more, I sort of expect this, or something close, to be true. However, it should be stated carefully as a proposition and proved to be a corollary of the earlier findings.

[RobertJasiek]

In (3.1), the paper claims

s_Bi - s_Wi = 2b - a_2i+1 - ∆(a_2i+1,...,a_n,c) - ∆(a_2i+2,...,a_n,d),

s_Wi-1 - s_Bi = -2b + a_2i + ∆(a_2i+1,...,a_n,c) + ∆(a_2i,...,a_n,d).

Proof:

s_Bi - s_Wi = a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c) - (a_1 - a_2 +...+ a_2i+1 - b + ∆(a_2i+2,...,a_n,d)) = 2b - a_2i+1 - ∆(a_2i+1,...,a_n,c) - ∆(a_2i+2,...,a_n,d).

s_Wi-1 - s_Bi = a_1 - a_2 +...+ a_2(i-1)+1 - b + ∆(a_2(i-1)+2,...,a_n,d) - (a_1 - a_2 +... - a_2i + b - ∆(a_2i+1,...,a_n,c)) = -2b + a_1 - a_2 +...+ a_2(i-1)+1 + ∆(a_2(i-1)+2,...,a_n,d) - (a_1 - a_2 +... - a_2i - ∆(a_2i+1,...,a_n,c)) = -2b + a_1 - a_2 +...+ a_2i-1 + ∆(a_2i,...,a_n,d) - (a_1 - a_2 +... - a_2i - ∆(a_2i+1,...,a_n,c)) = -2b + a_2i + ∆(a_2i,...,a_n,d) + ∆(a_2i+1,...,a_n,c).

******************************************************************************************

The paper claims that for

s_Bi - s_Wi = 2b - a_2i+1 - ∆(a_2i+1,...,a_n,c) - ∆(a_2i+2,...,a_n,d) and

s_Wi-1 - s_Bi = -2b + a_2i + ∆(a_2i+1,...,a_n,c) + ∆(a_2i,...,a_n,d)

both to have the same (positive) sign, by exercise 7, we have d < a_2i+1 < a_2i.

Sketch:

By definition of a_2i+1 and a_2i, we have a_2i+1 < a_2i.

Exercise 7 gives max (c, a_2i+2) >= a_2i+1 => s_Bi+1 = s_Bi.

How to (use exercise 7 and) show that d < a_2i+1 < a_2i and so

0 < 2b - a_2i+1 - ∆(a_2i+1,...,a_n,c) - ∆(a_2i+2,...,a_n,d) and

0 < -2b + a_2i + ∆(a_2i+1,...,a_n,c) + ∆(a_2i,...,a_n,d)?

In particular, for b >> c, d, we have very small -2b. So how could possibly the second inequation hold?

The paper must prove its claim.

Is "the same (POSITIVE) sign" a typo for "the same (NEGATIVE) sign"? Even so, a proof is needed.

[RobertJasiek]

The paper claims that the environment's head and tail drop out and only the intermediate part A_| remains. In my own research, I proved this. The paper, however, needs to prove this (possibly for all four cases) for the sake of its research.

In various inequations, the paper has a 2b, which occurs as 2M (for the move value M of the local endgame) in mine. Although I have not verified the paper's inequations yet, this term must be good.

The paper's case 3 must be worked out.

The paper's case 4 fears double sente and suspects a necessity for close values. Neither should be an issue. Case 4 should be the simplest of all. Allowing equalities would help.

The paper must also study all possible equalities.

******************************************************************************************

I do not study the paper's details of signs yet but peek at the structures of the cases' concluding inequations. For this purpose, I use my own approach with the temperature T replacing a_2i+1 and, due to its dynamic nature, ignoring the lower bounds depending on a_2i. Instead, I use pairs of inequations >= and <=, which include the equalities. Below, I only annotate the > for simplicity. I abbreviate ∆ := ∆(A_|) and have b = M. See above for the paper's shortcomings.


Case 1 (simplified, T > c, d): The paper and my research agree:

2(b - T) > +-c +- d +- 2∆.


Case 2 (simplified, c > T > d): The paper and my research agree:

2b > c +- d + 2∆.

Remark: I write this as 2b - c > 2∆_d because the d continues ∆.


Case 3 (simplified, d > T > c):

The paper suggests: 2(b - T) > +-c + d - 2∆.

My research has: 2b - d > 2∆_c because the c continues ∆.

The paper's inequation guesses 2b, +-c, d and the factor 2 of ∆ correctly but wrongly guesses -T and the - sign of 2∆. To agree to my proved research, the paper must write:

Corrected paper: 2b > +-c + d + 2∆.


Case 4 (simplified, c, d > T):

The paper suggests: 2b > c + d.

My research has: Always start locally.

The paper does not seem to recognise this simplest strategy because, besides the immediate truth 2b > c + d in a local gote endgame, the paper also tries to consider a lower bound creating unnecessary conditions and trouble. No lower bound is needed! Since we have the truth, it is always correct to play locally!


All cases:

Since the paper makes mistakes for cases 3 and 4, I expect its summarising formulas to be wrong but have not studied them closely.

I will study some details of signs and inequations in the paper later.

[RobertJasiek]

For cases 1 and 2, and later the other cases, the paper must derive explicitly the case-specific (in)equations from the general (in)equations. I lack time to do that work (I need not do it because I have done it in my own research). I forgo related remarks and the informal principle 6 in the paper. Let me, however, study the interesting signs.


Case 2: 2b > c + (-1)^u_dd + 2∆.

d succeeds the head having an even number of values and intermediate part ∆, which therefore starts with a + sign. If also ∆ has an even number of values, d has a + sign, else - sign. u_d counts the number of values preceding d. Therefore, (-1)^u_dd notates d with its correct sign.


Case 1: 2(b - T) > -(-1)^u_cc + (-1)^u_dd + (-1)^{min(u_c,u_d)+1[d>c]}2∆,

where c is the starting (black) player's follow-up move value, d is the opponent's follow-up move value, and we have the indicator function 1[d>c] = 1 (if d>c) or 0 (if d<c).

In my research, which now I restrict in scope to exclude equalities to meet that restriction of the paper, I define:

The parity is that of the number of the environment's move values that are larger than the larger value of c and d.
∆_cd is the alternating sum of a) the larger value of c and d, b) twice the move values of the intermediate part and c) the smaller value of c and d. The alternating sum starts with the following sign:
• minus if c is larger and the parity is odd,
• plus if c is larger and the parity is even,
• plus if d is larger and the parity is odd,
• minus if d is larger and the parity is even.

Instead, the paper does not include c and d in the alternating sum so ∆ starts one move later (after the larger value of c and d). Accordingly, it must start with the following sign to be also expressed by its formula:
• plus if c is larger and its parity is odd, (-1)^u_c+0
• minus if c is larger and its parity is even, (-1)^u_c+0
• minus if d is larger and its parity is odd, (-1)^u_d+1
• plus if d is larger and its parity is even. (-1)^u_d+1

However, the paper gets the signs wrong. They would be right if it included the larger value of c and d.

-(-1)^u_cc + (-1)^u_dd are written as if applying to both cases of either c or d being the larger value. This can't be right with different leading signs. Some indicator function is missing for both.

I suggest simplification as I use: include c and d in ∆_cd as defined above. Accordingly, the paper should write:

2(b - T) > (-1)^{min(u_c,u_d)+1[d>c]}∆_cd.


EDIT delete factor 2 (now included in the definition).

[RobertJasiek]

CONCLUSION

The paper contains some new facts and mistakes at other places. Its major part about one local gote with both players' simple follow-ups in an environment is unfinished but can only duplicate my related finished (although still unpublished) work. The terms should be replaced by common terms. Facts without proofs or too fast transformations demand proofs, regardless of whether others provide proofs or could not do so yet. Informal conjectures need formal notation and proofs, or else might better be deleted. The following mentions the facts or conjectures I consider useful and new.

Proposition 4 (proved; inserting one unique value in an alternating sum).

Conjecture "Lemma 5" (still needing a proof; inserting one unique value in an alternating sum changes the score by at most the value).

Lemma 6 (proved; impact of inserting two unique values in an alternating sum).

Conjectures: Explain whether and, if yes, why the conditions s_Wi-1 > s_Bi > s_Wi or s_B+1 > s_Wi > s_Bi determine optimal play.

Propositions: s_Bi+1 - s_Bi >= 0 and s_Wi+1 - s_Wi <= 0. These proved monotonicities are remarkable because either condition allows any simple environment instead of a rich environment, which combinatorial game theory would presume.

These informal conjectures should be decomposed, formalised and, if possible, proven or related to propositions: "Hence it is correct strategy for Black after 2i moves to delay playing move b if and only if [he can gain] from doing so and White cannot stop him. That is [...,] there is [...] s_Bi+j > s_Bi but s_Wk > s_Bi for all i <= k < i+j. The correct timing to play at b is just before the increasing s_Bi and the decreasing s_Wi cross. [...A] greedy algorithm (looking only one move ahead) works."

Who can prove some of the still unproved conjectures above?

What do others think of the mathematics in the paper?