It is currently Fri Oct 22, 2021 2:30 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 59 posts ]  Go to page Previous  1, 2, 3
Author Message
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #41 Posted: Tue May 25, 2021 10:30 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
"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.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #42 Posted: Tue May 25, 2021 10:42 pm 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
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.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #43 Posted: Tue May 25, 2021 11:58 pm 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
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.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #44 Posted: Wed May 26, 2021 3:44 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
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).

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #45 Posted: Wed May 26, 2021 9:40 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
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?


Last edited by RobertJasiek on Sat May 29, 2021 9:26 am, edited 2 times in total.
Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #46 Posted: Thu May 27, 2021 10:21 pm 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
Lemma 5: |∆(A) − ∆(A ∪ {b})| ≤ b; b not in A.

What kept me from proving it was the claim that the proof would be trivial. It is not. Let me prove the more general

Lemma 5': |∆(A) − ∆(A ∪ {b})| ≤ b.

Proof:

Case u EVEN: (*E)

∆A - ∆A|b
= ∆A+ + (-1)u∆A- - ∆A+ - (-1)u(b - ∆A-) // A+ := {a ∈ A : a > b}, A- := {a ∈ A : a ≤ b}
= (-1)u∆A- - (-1)ub + (-1)u∆A-
=(*E) ∆A- - b + ∆A-
= (∆A- - b) + ∆A-
≤(*0) ∆A-
≤(*0) b.

Case u ODD:

As before and by taking the absolute.

Footnotes:

(*0) ∆A- ≤(*1)(*2) b

(*1) By my proposition "T is the maximum value of starting in an environment of simple gotes without follow-ups and largest move value T".

(*2) By definition of A-.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #47 Posted: Sat May 29, 2021 9:25 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
"s_Bi+1 - s_Bi >= 0 [...] proved"

I need to revoke this conclusion at least temporarily for the following reasons.

The paper distinguishes these two cases: c < a_2I+2 and c > a_2I+2. For the latter, I first need to understand whether and why this case can occur at all. Considering s_Bi+1 also means playing a_2(I+1) before b, that is a_2I+2 > b. By definition of local gote, we have b > c hence a_2I+2 > b > c, which contradicts occurrence of the case c > a_2I+2.

If I should have understood the above wrongly and the case can occur, we have the subcase a_2I+1 > c > a_2I+2, for which the propagrated application of lemma 6 works. However, we also have the subcase c > a_2I+1 > a_2I+2, which the paper misses and for which I prove -∆a_2I+3|c + ∆a_2I+1|c <= 0 instead of the needed >= 0.

Daniel, please explain!

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #48 Posted: Mon May 31, 2021 1:17 pm 
Lives with ko

Posts: 291
Liked others: 39
Was liked: 245
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
Hi Robert,

Thank you for taking the time to understand and communicate. I appreciate all the feedback. I apologise for my own lack of response, my todo list has been overly backlogged lately. Hence I'm not sure if/when I will update that pdf (more than linking to this thread), rather than writing on other topics.

by "basic", I generally mean that they are the easiest problems/generalisations that I (am aware of | can think of) that go beyond standard theory. Even here, computations are a little awkward. As go trees grow exponentially, it gets awkward to apply principles in the same way, but perhaps we can hope for something similar to how just 4 axioms can prove all true statements in propositional calculus (edit: I wrote predicate logic here before, silly me). I tend to think (hope) that there must be a better way to view all this, but in practice, it seems better for my sanity to only expect small steps of progress.

by phase space below, I will mean the space of gains (a_i, b,c,d etc)

from post26:

exercise 1: Ok, I can agree the general case is not that easy. I think I can prove it based on difference games (see 3.3 below), and also induction based on ∆ manipulations. Perhaps I meant "problem to think about" instead of exercise, given that it's not necessarily easier than (3.3) the main problem I am trying to solve.
Proving my example with depth 1 however seems much easier.

3.1:
- It is based on the preceding diagram. The simple gotes are a_i, and the depth 2 tree is b{c,d}.

- "boundary" refers to the paragraph in introduction around "position and shape of the boundary". It means boundary in phase space between different strategies.

- Principles: yes, sure. I guess I am still wondering about the theory of what a principle is, how to construct it from solved situations, and how general they are.
principle 4: yes, I meant all else being equal.

3.2:
prop3: "telescoping terms". I think I just made it up but the similarity to telescoping series is fairly superficial. I guess it is most similar to the alternating series test.

Prop 4: annotation: interesting

Lemma5: The || means absolute value in this case.
Following your calculations, you reach (-1)u2∆A- - (-1)ub
We are done as ∆A<=max(A)<=b

3.3:
Equality cases: As far as I can tell, equality cases are the boundary in phase space of different (at least 2) optimal strategies. So strategically it only leads to degeneracy in optimal strategies. Hence for the purpose of strategy, they don't require more investigation (hopefully), just more explanatory words.

Difference game argument: I plan to clarify this in another write-up. I mean that playing in a simple gote of size g is always at least as good as playing in a simple gote of size h when g>=h. I accept this is much less trivial than it sounds.

s_Wi+1 - s_Wi <= 0 is by symmetry in black and white (from the above statement)


Last edited by dhu163 on Tue Jun 01, 2021 1:08 pm, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #49 Posted: Mon May 31, 2021 1:18 pm 
Lives with ko

Posts: 291
Liked others: 39
Was liked: 245
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
post34:
No!
Apologies for confusion. I blame my double negative, my use of "otherwise", and "more" (for whom?). The principle says that you should delaying play in b (locally) until the last moment.

I should say
"Play on b if you get a better result from it than if you play in the environment and your opponent plays on b the next turn. Otherwise play a_1"

re: EDIT: I do not mean 'if', re: EDIT2: yes, but this is encapsulated in the above.

Principle 5 refers to the preceding paragraph. Subsequent writing is to develop the boxed formula at the start of p7.

by "get", I don't mean gain, but the overall SUOP.

It means compare what happens to the SUOP (score under optimal play) if you play b now (you call this playing locally) to the SUOP (score under optimal play) if you play a simple gote (what you call the environment at temperature T?) and your opponent plays b (locally) next. Now in the latter case, the move at b might not be optimal, which is what gives this principle its information content.

However, in this particular situation (of one depth 2 tree and several simple gotes), the principle as written above holds. Perhaps it is less a principle and more a summary in words of the previous paragraph's result, answering "what is optimal play".

The next page or so then computes what the SUOP is.

post 35: "The paper should clarify". ok, perhaps

post 36:
"For that, generalisation to games of larger depth still appears to be too hard.": agreed with some caveats (hopefully to be written up)

Quote:
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!


Ok. Yes, that is what I am studying in this write up. I based everything on the diagram at the end of page 2.

"What justifies that the following conditions determine optimal play?": I hope to write more on this in another write up.

"I have studied the cases Black starts or White starts separately." This seems strange to me as the way I have set it up is completely symmetric. (just need to switch c and d)

"Basically, my cases are the same": that's reassuring.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #50 Posted: Mon May 31, 2021 1:18 pm 
Lives with ko

Posts: 291
Liked others: 39
Was liked: 245
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
post 37: yes, thanks.
Your last 2 lines have a mistake. The inequalities are actually tighter than that. Lemma 6 only gives us
-∆(a_2i+3,...) + ∆(a_2i+1, ...) >= a_2i+2 -a_2i+1
but still
s_Bi+1 - s_Bi = (a_2i+1 - a_2i+2) + (-∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c)) >= 0.

post 38: Not quite right as per post 37, but by "similar", I meant its true by symmetry.

post 39: sounds like thermographs

post 40: not sure what you mean by "Study s_Bi+1 = s_Bi <=> ..."
I stand by my "if and only if". By equality, I meant of the preceding inequality.

post 41: I was hoping this was clear enough from the monotonicity, though I was thinking of doing a separate write-up of optimal play in a more general case where monotonicity doesn't hold that I call a laddertree, inspired by Bill's converging inequalities.

post 46: correct proof. It took me a few minutes for me to understand your proof format, but having done so, it is very clear.

post 47: "Considering s_Bi+1 also means playing a_2(I+1) before b, that is a_2I+2 > b."
No,
1) the whole point of my write-up was to figure out when to play in a tree of depth 2 compared to a tree of depth 1. As you well know, comparing gains is good but not perfect.
2) s_Bi+1 is defined as SUOP under the assumptions of playing a_2i+1 before b, regardless of whether this is optimal or not. I felt this was a more general space to work in, probably because I started thinking about laddertrees.

"for which I prove -∆a_2I+3|c + ∆a_2I+1|c <= 0 instead of the needed >= 0."
Yes and no, see my comment on post 37. I stand by my monotonicity result.

_

posts 42-44, there is quite a bit here, and I still need to read it and check my own working too, as well as Bill's corresponding formula (which seems to assume d=0, though that's equivalent to subtracting a constant to everything if c>d). Lots to do!

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #51 Posted: Mon May 31, 2021 2:15 pm 
Lives with ko

Posts: 291
Liked others: 39
Was liked: 245
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
post 42:
I think I have made a typo here. It should say d, a2i+1 < a2i. I do mean positive sign.

Proof is by summing the equations, incrementing i, and taking symmetry between Black and White. For example
"max(c,a2i+2)>=a2i+1 is false" is the same as saying "c,a2i+2 < a2i+1"

This typo would affect case 3,4, and yet I do consider all cases there, so this is probably not the reason for the discrepancy.

post 43:
"No lower bound is needed!". Yes if the question is should you play locally now, but I guess I was curious about "when should you play locally" and the lower bound was cheap, coming with the rest of the calcuations.

hmm, as far as I can tell, my formulae are correct, but our notation is causing a discrepancy when the a_2i+1 is included in your ∆. With your notation, the result is written much more concisely.

case 4: Yes, sure. I guess I left it for readers to realize that 2b>c+d always holds, so always play b.

post 44:
Thank you for explaining your work. I am tempted to just redirect to this post rather than rewriting this paper.

I am curious as to how you proved your formula if you didn't go via monotonicity.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #52 Posted: Mon May 31, 2021 3:57 pm 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
dhu163 wrote:
I am curious as to how you proved your formula


By learning from Bill's techniques:) You need to wait some weeks or months for it.

Now, I need to proceed with my own work. Maybe I can reply to some of your other statements later.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #53 Posted: Tue Jun 01, 2021 12:27 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
dhu163 wrote:
post 37: yes, thanks.
Your last 2 lines have a mistake. The inequalities are actually tighter than that. Lemma 6 only gives us
-∆(a_2i+3,...) + ∆(a_2i+1, ...) >= a_2i+2 -a_2i+1
but still
s_Bi+1 - s_Bi = (a_2i+1 - a_2i+2) + (-∆(a_2i+3,...,a_n, c) + ∆(a_2i+1,...,a_n,c)) >= 0.


Right, thanks, very nice!

Quote:
s_Wi+1 - s_Wi <= 0 is by symmetry in black and white


With this, you suggest the following simple proof:

s_Bi+1 - s_Bi >= 0 <=> -s_Wi+1 - (-s_Wi) >= 0 <=> s_Wi+1 - s_Wi <= 0.

However, such a proof relies on

s_Bi = -s_Wi.

You defined

for the starting player sB,i = a1 − a2 + · · · − a2i + b − ∆(a2i+1, · · · , an, c) and
for the second moving opponent sW,i = a1 − a2 + · · · + a2i+1 − b + ∆(a2i+2, · · · , an, d).

s_Bi = -s_Wi is (usually) false!

I think that my sketch of a proof is still needed:

Conjecture s_Wi+1 - s_Wi <= 0. Sketch of 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.

Quote:
post 38: Not quite right as per post 37, but by "similar"


So you think that I need to check my sketch of a proof above WRT applying lemma 6? The joke is: I have thought that proving s_Wi+1 - s_Wi <= 0 is simpler in the sense of not needing lemma 6 at all. Can we double check?

Quote:
post 39: sounds like thermographs


Thermography, but does not need thermographs.

Quote:
post 47: "Considering s_Bi+1 also means playing a_2(I+1) before b, that is a_2I+2 > b." [...]
2) s_Bi+1 is defined as SUOP under the assumptions of playing a_2i+1 before b, regardless of whether this is optimal or not.


Ah.



dhu163 wrote:
post 42:
I think I have made a typo here. It should say d, a2i+1 < a2i. I do mean positive sign.

Proof is by summing the equations, incrementing i, and taking symmetry between Black and White. For example
"max(c,a2i+2)>=a2i+1 is false" is the same as saying "c,a2i+2 < a2i+1"

This typo would affect case 3,4, and yet I do consider all cases there, so this is probably not the reason for the discrepancy.


We need to reflect this.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #54 Posted: Wed Jun 02, 2021 2:07 am 
Lives with ko

Posts: 291
Liked others: 39
Was liked: 245
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
re: many general criticisms regarding strength of principles, format, more proofs required
I accept these criticisms as valid. I feel a mix of {I will try harder next time | I probably had bad reasons such as laziness etc. | gratitude | dread}

Quote:
With this, you suggest the following simple proof:

s_Bi+1 - s_Bi >= 0 <=> -s_Wi+1 - (-s_Wi) >= 0 <=> s_Wi+1 - s_Wi <= 0.

However, such a proof relies on

s_Bi = -s_Wi.


Yes to the first half. No to the second half. The problem set up is symmetric in black and white (say under c->d, d->c, s_Bi->-s_Wi, s_Wi->-s_Bi+1, n->n+1, ... for example). Hence, every line in the proof for s_Bi+1 - s_Bi >= 0 can be replaced by the mirror version to obtain a proof for s_Wi+1 - s_Wi <= 0. We can say this without even having a proof.

A bit like a difference game compares G-H rather than G+H, I am not saying

Proof of (W):
1) given t1
2) proof of (B): t1=>(*1)t2=>...=>(*n)tn+1
3) apply mirror to reach conclusion tn+1 => ?

but instead saying

let m(x) be mirror of x, some nice transformation

Proof of (W):
1) given m(t1)
2) mirror proof of (B): m(t1)=>(m(*1))m(t2)=> ... => m(tn+1)


I am saying that the problem is essentially self-symmetric so m(x) is merely relabelling free variables on the givens and the conclusion. Hence I claim that
any proof of t1=>t2 also proves m(t1)=>m(t2). Admittedly I don't actually know how to prove this even in propositional calculus.

Quote:
Can we double check?

Post 38: I didn't read it in detail the first time. But I object to "// We have d < b < a_2i+3." for the same reason as in my comment to post 47.
Whether or not lemma 6 is used, the problems are symmetric, so they have exactly the same difficulty.
__
Note for readers: we are losing generality with the assumption b>c,d
__

I have written up notes on domination, difference games and a proof of exercise 1 here if you are interested.
https://dhu163go.files.wordpress.com/20 ... tion-1.pdf

I don't know if it is well known to others, but exercise 1 means that
"“hotstrat”, the strategy of always playing the move with the highest gain (in miai counting) is the optimal strategy among unary trees that satisfy the sente-gote axiom. The only time when you should “duck” and play a move of lower gain is to fight for tedomari, when the situation is asymmetric.


Last edited by dhu163 on Thu Jun 03, 2021 4:43 pm, edited 1 time in total.
Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #55 Posted: Thu Jun 03, 2021 1:21 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
dhu163 wrote:
The problem set up is symmetric in black and white (say under c->d, d->c, s_Bi->-s_Wi, s_Wi->-s_Bi+1, n->n+1, ... for example). Hence, every line in the proof for s_Bi+1 - s_Bi >= 0 can be replaced by the mirror version to obtain a proof for s_Wi+1 - s_Wi <= 0.


I do not buy this for the following reason.

A proof of s_Bi+1 - s_Bi >= 0 relies on the definition of s_Bi with b played after 2i moves.

Now, for substituting i->i+1, we get b played after 2(i+1) = 2i + 2 moves, which is still even.

However, for White's moves and proving s_Wi+1 - s_Wi <= 0, we need b played after an odd number of moves!

Therefore, a copy&paste proof "by symmmetry / substitution" does not work.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #56 Posted: Thu Jun 03, 2021 2:02 am 
Lives with ko

Posts: 291
Liked others: 39
Was liked: 245
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
Well spotted.
However, i maintain the problem about sBi+1-sBi is symmetric under the right transformation.

E.g. I claim that strategy is only dependent on the current game state not previous ones.
We can delete a1 for example when we apply the symmetry transformation.

Or, using the same variables I used, the SUOPs of sW and sB are shifted by a1. But as we only care about differences in SUOP between nodes, we are fine.

Or we could relabel so that an>...>a2>a1 which would make induction more natural, say since taking a1=0 would be allowed. I think a direct copy paste still needs some steps though.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #57 Posted: Thu Jun 03, 2021 3:06 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
Write down your would-be proof in detail. Meanwhile, I try to correct mine.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #58 Posted: Thu Jun 03, 2021 4:54 am 
Judan

Posts: 5502
Liked others: 0
Was liked: 744
Proposition

S_W,I+1 - S_W,I ≤ 0.

Proof

S_W,I+1 - S_W,I =
(A_1 - A_2 +... + A_2(I+1)+1 - b + ∆A_2(I+1)+2|d) - (A_1 - A_2 +... + A_2I+1 - b + ∆A_2I+2|d) =
(A_1 - A_2 +... + A_2I+3 - b + ∆A_2I+4|d) - (A_1 - A_2 +... + A_2I+1 - b + ∆A_2I+2|d) =
-A_2I+2 + A_2I+3 + ∆A_2I+4|d - ∆A_2I+2|d =
(-A_2I+2 + A_2I+3) + (∆A_2I+4|d - ∆A_2I+2|d) ≤(*) 0.

Footnote

*) By lemma 6, ∆A_2I+4|d - ∆A_2I+2|d ≤ A_2I+2 - A_2I+3.

Top
 Profile  
 
Offline
 Post subject: Re: Principles from Basic Endgame Trees (Daniel Hu)
Post #59 Posted: Sat Jun 05, 2021 3:53 pm 
Lives with ko

Posts: 291
Liked others: 39
Was liked: 245
Rank: UK 2d Dec15
KGS: mathmo 4d
IGS: mathmo 4d
I agree with that proof.

re: principle 4 - I've no idea what I was thinking when I wrote that down. I agree it seems blatantly wrong.
re: symmetry proof - I have little inclination to do this atm.

I have corrected some of my difference games write up instead (I incorrectly thought A>=B was equivalent to LEFT and RIGHT getting a better score in A than in B, luckily I didn't depend on that in the rest, (I think!)) + add more theory. Wordpress changes the url after a reupload, so here is the link to the page I put them: https://dhu163go.wordpress.com/game-tree/

I have skim read quite a bit more of Bill's writings on L19 over the last few years. Writing up on Laddertrees is my next target but I still hope to return to tree construction. I guess it depends on what I think I am making progress on.

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 59 posts ]  Go to page Previous  1, 2, 3

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: Harleqin and 1 guest


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group