HDTenEightyP/NetNews huggingface dataset:
From: varvel@cs.utexas.edu (Donald A. Varvel)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: 28 Sep 1992 11:51:39 -0500
Organization: U Texas Dept of Computer Sciences, Austin TX
NNTP-Posting-Host: coltexo.cs.utexas.edu

In article <23738@alice.att.com> ark@alice.UUCP () writes:
>In article <1992Sep27.161451.20136@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:

>> Consider the game 1. Nf3 Nf6 2. Ng1 Ng8 3.Nf3 Nf6 4.Ng1 Ng8 5.Nf3 Nf6
>> and so on, forever; with neither player choosing to claim a draw.  I 
>> am asking for a proof that when collapsing the game tree to determine the
>> value of the initial position, this sequence must have the value of a draw.

>We can solve the problem in at least two ways.

>1. Define it away by saying that any position from which neither player can
>   force a win is a draw.

>2. Ask why, in the situation you mention, neither player claims the draw after
>   the third repetition.  Evidently the answer must be that they both think
>   that playing indefinitely is preferable to ending the game with a draw.
>   But in that case, the game is not zero-sum, which contradicts one of the
>   conditions necessary for the theorem to apply in the first place.

I think this is precisely Mr. Hummel's point.  Win, loss, and draw
are all defined, but it is possible that a nonterminating game has
value greater than a draw for both players.  Clearly that's a nonzero-
sum game.  But identifying and exploiting positive-sum games is a
major activity of a good life.  And it seems the rules of chess
assign no value to unfinished games.

Two points of my own:

1. If an unfinished game has a value for both players greater than
   that of a draw, a draw is not a normal outcome.  In fact, constructing
   a position where both players have to settle for a draw is nontrivial.
   Many games are drawn because neither player has any winning chances.
   Clearly real players do *not* value a continuing game more than a
   draw, although that isn't written into the rules.

2. Obviously this has no effect on chess being solvable.

-- Don Varvel (varvel@cs.utexas.edu)
From: ed@cbnewsl.cb.att.com (edward.m.hummel)
Subject: Re: "Solvability" in Chess
Organization: AT&T
Date: Sat, 26 Sep 1992 13:25:08 GMT

In article <xeno.717471510@pv34ad.vincent.iastate.edu> xeno@iastate.edu (Gary L Snethen) writes:
>It is not possible for both players to have better than a draw and
>less than a win....  What one player has, the other does not.  One's
>loss is the other's win... zero sum game.
>
>How do I prove this?  The rules of chess state it quite plainly...
>If white wins, black loses.  If black loses, white wins.  A draw is
>considered a perfect 50%/50% game for each (a half-loss, half-win situation).

There is a loop hole:  the rules do not give a value to games that do
not end.

Newsgroups: sci.logic,sci.math,rec.games.chess
From: cuffell@spot.Colorado.EDU (CUFFELL TIMOTHY MICH)
Subject: Re: "Solvability" in Chess
Organization: University of Colorado, Boulder
Date: Tue, 29 Sep 1992 09:04:57 GMT

In article <xeno.717575523@pv34ad.vincent.iastate.edu> xeno@iastate.edu (Gary L Snethen) writes:
>In <1992Sep26.132508.24956@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:
>
>>In article <xeno.717471510@pv34ad.vincent.iastate.edu> xeno@iastate.edu (Gary L Snethen) writes:
>>>It is not possible for both players to have better than a draw and
>>>less than a win....  What one player has, the other does not.  One's
>>>loss is the other's win... zero sum game.
>>>
>>>How do I prove this?  The rules of chess state it quite plainly...
>>>If white wins, black loses.  If black loses, white wins.  A draw is
>>>considered a perfect 50%/50% game for each (a half-loss, half-win situation).
>
>>There is a loop hole:  the rules do not give a value to games that do
>>not end.
>
>I beg to differ, but they most certainly do!  This is called a 'draw'.  If
>it were NOT considered a 'draw' then a king vs. king position would very
>plainly fall under the category of such a loop hole.  If you then say
>'well, there is not enough of a material advantage for either side to win
>so therefore it is obviously a draw since all paths lead to draws, but in
>another example, this might not be the case' then my response is:
>
>You've added a synthetic rule to the game which states that lack of material
>advantage is a draw. (Note that this is *not* really synthetic as the rules
>of chess plainly state that such positions are draws, JUST as they state
>that indefinite loops are draws...  if you take one, you MUST take the other).
>
>If you are interested in 'rigor' then all you need do is add these two rules:
>
>(1) ANYTIME a position has been repeated three times, the game is a draw.
>
>and/OR (yes, OR...  either rule suffices)
>
>(2) If 50 moves pass with no capture, the game is a draw.
>
>
>You are accusing the rules of chess of having 'loop holes' whereby players
>can claim a condition other than win/lose/draw...  If you wish to contort
>the rules of chess to create such synthetic loop holes to support your
>argument, then at least explain it as such.  If there ARE loopholes and I
>am still confused on the issue, PLEASE try to create an example situation
>where this question would arise.
>
>Even if so, I think I can easily gain a consensus amoung the players here
>on the net that if a game lasts forever (ie., has infinite moves whether in a
>loop or not), then that game is a draw since neither side has a hope to
>win unless the other side makes a mistake.  But luckily, the accepted rules
>of play prohibit such situations from arising.
>
>Now, if you are interested in a variant of chess where these rules do not
>apply, then your argument is completely founded.  But then we are no longer
>talking about a finite game, so the previous discussions do not apply.
>
>
>---Xeno
>
The rules also describe a tournament director who can decide the outcome of
games that take too long.

Newsgroups: sci.logic
From: fulk@cs.rochester.edu (Mark Fulk)
Subject: Re: A question in Recursion Theory
Keywords: recursion
Organization: Computer Science Department University of Rochester
Date: Tue, 29 Sep 1992 17:55:54 GMT

In article <1992Sep29.161016.19533@ghost.dsi.unimi.it> chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) writes:
>A question for Recursion Theorists.
>
>If you take a partial recursive function phi and two sets I and J such that
> dom(phi) contains I and range(phi) is included in J, you can define an
> obvious set-theoretic function f:I->J.
>
>The question is: does EVERY surjective f admit a section, i.e. a g:J->I
> obtained in the same way from a partial recursive function, say psi, such
> that
>	for each j in J    f(g(j))=j       ?
>
>People-who-know will see I'm actually defining a category and asking "does
> every good (i.e surjective) epi split?"
>
>I suspect this to be false, but I can't manage to find a counter-example; the
> difficulties arise from the clumsiness of restricting arbitrarily the domain
> of a partial recursive function.

Thanks for the nice problem.  If I is recursively enumerable, there is
such a section.  In general, there is not, by the following finite-injury
priority argument.

Let f be the left projection function for some pairing function.
Let J be the set of natural numbers.

Note: the range of f is N, so the range of any section of f must be infinite.

We construct I by deleting elements from N; note that this makes I co-r.e.
In the construction, we will refer to certain requirements R_i:

R_i: range phi_i is finite or there is y in N such that phi_i(y) not in I.

We will also restrain some numbers into I for certain requirements.  These
restraints can be broken for higher-priority (lower-numbered) requirements,
but the standard finite-injury argument will establish that every requirement
gets met.

Stage s:
   Search for s steps for i such that requirement i is not met, and there
   are x,y such that phi_i(x) = y, f(y)=x, and y is not held in I for any
   requirement i'<i.  Let i0 be the least i so found; let x0 and y0 be
   corresponding values of x and y.

   Delete y from I.
   Find y'>y, not yet deleted from I (there will always be such), and
   restrain y' into I for requirement i0.

   Mark requirement i0 as being met.
   Unmark all requirements i with i>i0.
End state s.

I will leave the verification up to the reader.  The basic structure of
the proof is that every requirement will be met, either by default
(phi_i has finite range) or by being met in the construction.  The
latter will happen to each requirement at most a finite number of times
(2^(i-1) will do it).  Then note that meeting every requirement is enough
to establish that f|I has no section.

Mark
-- 
Mark A. Fulk			University of Rochester
Computer Science Department	fulk@cs.rochester.edu
Newsgroups: sci.logic
From: hyatt@cis.uab.edu (Robert Hyatt)
Subject: Re: "Solvability" (long & pedantic)
Organization: University of Alabama at Birmingham
Date: Wed, 30 Sep 1992 01:39:41 GMT

In article <22964@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:
>In article  <lcf2ctINN2te@coltexo.cs.utexas.edu> Donald A. Varvel writes:
>]First of all, it is not necessary to visit every node in the game tree.
>]Period.  Alpha-beta pruning yields the same result as min-max, provided
>]each works with the same assumptions.  That is, an alpha-beta search
>]of the entire game tree yields the same result as min-max, while cutting
>]of many branches without analysis.  That's a minor point, though, since
>]A-B doesn't promise an easy solution either.
>
>It's been some time since I looked at this stuff, but as I recall,
>search strategies that are still guaranteed to find the optimal
>solution cannot be asymptotically better than breadth-first search
>with the same cost function.  So alpha-beta pruning will do no better
>than remove a polynomial number states from an exponential search
>space.
>-- 
>					David Gudeman

Alpha-beta with good move ordering reduces the size of the minimax
tree to nearly the square root of the size of the minimax tree.  alpha
beta does not guarantee to find the shortest path to a win, but it will
find the best score.  If you make the path length part of the scoring
function, then even this complaint fades away.  breadth-first is not
appropriate to alpha-beta.....  it works with minimax DEPTH-FIRST game
trees only.  

Bob Hyatt

-- 
!Robert Hyatt                    Computer and Information Sciences   !
!hyatt@cis.uab.edu               University of Alabama at Birmingham !
Newsgroups: sci.logic,sci.math,rec.games.chess
From: xeno@iastate.edu (Gary L Snethen)
Subject: Re: "Solvability" in Chess
Organization: Iowa State University, Ames IA
Date: Sat, 26 Sep 1992 05:49:15 GMT

In <1992Sep26.014734.15691@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:

>In article <1992Sep25.220728.26568@unixg.ubc.ca> ramsay@unixg.ubc.ca (Keith Ramsay) writes:
>>As an aside, I'd like to point out that the problem with repeated
>>positions is not an essential problem, so long as there are only
>>finitely many possible positions. ...
>>
>>For large enough n, W_n and B_n have to stabilize.  The remaining
>>positions are ones in which neither can force a win, i.e., either can
>>in principle guarantee a draw. 

>The point is that even though either can guarantee a draw, it cannot
>be proven that the value of the position is a draw.  At least, I haven't
>heard a proof, or seen one posted here.  So, if there are a finite
>number of such positions, and the values (although indeterminate) are
>constant, then chess is solvable, BUT we don't know the value of the
>initial position.  (We know it as a function of a finite number of
>undetermined constants.) 

I am apparently missing the point over these 'loops'.
Why do you feel that they must be assigned a value other than a draw?
It seems clear to me that these loops are drawn according to the accepted
rules of chess.  If neither side is willing or capable of making an
alternative move, the game is clearly drawn, and should be valued as such.
To determine whether an alternate move should be made is simply a matter
of using the mini-max approach as previously mentioned...

If you want to start assigning values other than 'drawn' 'won' and 'lost'
then you could, I suppose, also start saying that white lost, but 'not by
much'...  But this complicates the game...  The goal is (usually) to win,
not to stomp your opponent as hard into the ground as you possibly can.

---Xeno











Newsgroups: sci.logic
From: rz@mips.complang.tuwien.ac.at (Richard Zach)
Subject: Logic Textbooks
Followup-To: poster
Reply-To: zach@csdec1.tuwien.ac.at
Organization: Technische Universit"at Wien
Date: Tue, 29 Sep 1992 19:31:20 GMT

I will hold an informal information get-together
with freshmen logic majors. Basic logic education is
pretty poor and disorganized in Vienna, and
I'd like to give the kids there tips on what to
read as introduction to logic. It should
be modern (ie not Hilbert-Ackermann), it
should have a slight proof-theoretic bias
(ie contain sequent calculus, natural deduction,
cut elimination etc., preferably also
resolution), and preferably it should be in
print (ie not Shoenfield). Pointers to sections *in*
books and survey articles etc. appreciated as well.
Please email me, I'll post a summary.

-- 
Richard Zach                      [zach@csdec1.tuwien.ac.at]
Technische Universitaet Wien, Institut fuer Computersprachen
Resselgasse 3/185.2,     A-1040 Vienna,       Austria/Europe
From: sbloch@silver.cs.umanitoba.ca (Stephen Bloch)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: 1 Oct 92 18:34:51 GMT
Organization: Computer Science, University of Manitoba, Winnipeg, Canada

ed@cbnewsl.cb.att.com (edward.m.hummel) writes:
>Consider the game 1. Nf3 Nf6 2. Ng1 Ng8 3.Nf3 Nf6 4.Ng1 Ng8 5.Nf3 Nf6
>and so on, forever; with neither player choosing to claim a draw.

And, presumably, neither player choosing to break out of the loop by doing
something else.

>I am asking for a proof that when collapsing the game tree to determine the
>value of the initial position, this sequence must have the value of a draw.
>As far as I can see, such a sequence (or the node corresponding to
>one of the positions in the sequence) has indeterminable value.  This
>does not mean that chess is unsolvable.

Under the assumption that both players are playing optimally (under the
assumption that their opponents are playing optimally, under the
assumption...), I can prove this.  If either player could force a win by
breaking out of the loop, one or the other would have done so before the
loop completed EVEN ONCE.  If neither player can force a win, and if
neither player is daring enough to break out of the loop into a possibly-
losing situation on the assumption that the opponent will make a mistake,
the game is effectively drawn whether either player "claims" it or not.

If you insist on a formal claim, I have to make the additional assumption
that at least one of the players prefers a draw to an infinite game.  If
you grant me that, said player will follow the above reasoning, conclude
that the best (s)he can hope for is a draw, claim a draw, and get on with
the rest of life.

-- 
					Stephen Bloch
				sbloch@silver.cs.umanitoba.ca
Newsgroups: sci.logic
From: chinnici@ghost.dsi.unimi.it (roberto riccard chinnici)
Newsgroups: sci.logic
Subject: A question in Recursion Theory
Summary: Sections of recursive functions
Keywords: recursion
Date: 29 Sep 92 16:10:16 GMT
Article-I.D.: ghost.1992Sep29.161016.19533
Organization: Computer Science Dep. - Milan University

A question for Recursion Theorists.

If you take a partial recursive function phi and two sets I and J such that
 dom(phi) contains I and range(phi) is included in J, you can define an
 obvious set-theoretic function f:I->J.

The question is: does EVERY surjective f admit a section, i.e. a g:J->I
 obtained in the same way from a partial recursive function, say psi, such
 that
	for each j in J    f(g(j))=j       ?

People-who-know will see I'm actually defining a category and asking "does
 every good (i.e surjective) epi split?"

I suspect this to be false, but I can't manage to find a counter-example; the
 difficulties arise from the clumsiness of restricting arbitrarily the domain
 of a partial recursive function.

Thanks in advance, and feel free to e-mail me!!

----------------------------------------------------------------------
	Roberto R. Chinnici	<chinnici@hp2.sm.dsi.unimi.it>

	Dipartimento di Scienze dell'Informazione
	Universita' degli studi di Milano

	"but now
	 she stands upon southampton dock
	 with her handkerchief
	 and her summer frock clings
	 to her wet body in the rain
	 in quiet desperation knuckles
	 white upon the slippery reins
	 she bravely waves the boys goodbye again"

				southampton dock, Pink Floyd
----------------------------------------------------------------------
Newsgroups: sci.logic,sci.math,rec.games.chess
From: ed@cbnewsl.cb.att.com (edward.m.hummel)
Subject: Re: "Solvability" in Chess
Organization: AT&T
Date: Mon, 28 Sep 1992 01:03:35 GMT

xeno@iastate.edu (Gary L Snethen) writes:
>But I propose that we will always either take the draw option or continue
>out of the loop using the following reasoning:
>One of the assumptions we make is that our opponent, when given the
>chance to force a win, will, and if not, will force a draw if possible...

Well, of course!  Once you ASSUME this, the rest is trivial.  The point
was that an additional assumption is NEEDED.

>Consensus has everything to do with it...  We must have rules before we
>may prove or disprove the solvability of chess...  and since the rules
>of FIDE and USCF (to my knowledge) do not cover what happens in an
>'infinite' game, we should set this rule down before we can continue with
>the analysis.  Since humans are interested in finite-length games of
>chess (when playing each other), I think we could arrive at a consensus
>that any position that is repeated infinitely constitutes a forced draw.

Perhaps you are giving up too easily.  There is still a lot of interesting
analysis that can be done without adding to the set of rules.  Once you
decide to add to the rules, there are lots of ways to do it.  Whether
a consensus is used, or an edict from a Federation, it doesn't much
matter.  The point has very little practical value anyway.  The 
argument has been about whether the current rules allow for chess to
be solved.  I think it has been proven well enough that the game
is solvable.  My point has been that the rigorous solution is not as
"simple" as some people have been claiming.

>But I'll try to contain my analysis to the case where this rule does not
>apply, since I think I can show solvability on your ground.

Please do.  If you look through the previous posts you will find
the proof.  I have not been claiming that chess is insolvable, just that
the solution is a function of a large (but finite) number of
undetermined parameters.
Newsgroups: sci.logic
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: sci.logic
Subject: Re: "Solvability" (long & pedantic)
Date: 30 Sep 92 18:41:49 GMT
Organization: U of Arizona CS Dept, Tucson

In article  <1992Sep30.013941.1664@cis.uab.edu> Robert Hyatt writes:
]In article <22964@optima.cs.arizona.edu> gudeman@cs.arizona.edu (David Gudeman) writes:

]>It's been some time since I looked at this stuff, but as I recall,

Then don't post without refereshing your memory.

]>search strategies that are still guaranteed to find the optimal
]>solution cannot be asymptotically better than breadth-first search
]>with the same cost function.  So alpha-beta pruning will do no better
]>than remove a polynomial number states from an exponential search
]>space.

Breadth-first search doesn't even use cost functions, you dimwit.
Don't post before your morning caffeine fix either.

]Alpha-beta with good move ordering reduces the size of the minimax
]tree to nearly the square root of the size of the minimax tree...

Still, that doesn't reduce the complexity of an _exponential_
function.  So if the size of the tree is intractable, it will remain
intractable after pruning those nodes.

I think what I was getting at (although I'm posting pre-caffeine
again) is that an NP-hard search space cannot be made subexponential
though clever search strategies (unless P = NP).  But since (to my
knowledge) chess has not been proven NP-hard, my whole point was
rather pointless.  So never mind.
-- 
					David Gudeman
gudeman@cs.arizona.edu
Newsgroups: sci.logic
From: nik@scs.leeds.ac.uk (Nik Silver)
Subject: Re: A set cannot contain itself as a member
Keywords: recursion
Organization: The University of Leeds, School of Computer Studies
Date: Tue, 6 Oct 1992 11:02:21 GMT

In article <Oct05.201328.96457@yuma.ACNS.ColoState.EDU>, sa114984@longs.lance.colostate.edu (Steven Arnold) writes:
> [...some of proof deleted...]
>
>		X = {g,X}		(1)
>
>(Of course, g may be the empty set.)
>	Eq. 1 can be expanded as follows:
>
>		X = {g, X'}
>		        /\
>		       {g,X''}
>		          /\
>			 {g,X'''}
>
>...and so on forever.  (The ' symbol is merely meant to
>distinguish an X of one iteration from that of another.)  X'',
>for example, is equivalent to {g,X'''}; X''' is equivalent to
>{g,X''''}, etc etc.
>	The number of X's below X'' is infinite; nonetheless, it
>is certainly true that X' contains X'' as well as all the X's
>contained by X''; therefore X' contains one more X than X''!  It [...]

(I'm ignoring the fact that g should not be a single element, for we could
quite easily replace it by g1,...,gn with out affecting the rest.)

I think one mistake you've made here (and unfortunately it only takes one
to render a proof invalid :-) is saying:
	X' contains X'' as well as all the X's contained by X''
If we expand X (partially) using formal notation rather than your tree
diagram we get:
	X = {g, {g, {g, {g, X}}}}
	                -X'''-
	            -----X''---
	        --------X'------
	    --------X------------

So it is true that X' contains X'' but it does not contain X'''. What is
true is that X'' contains X'''. So by saying X(m) contains any X(n) (where
(X(p) is X with p dashes) is not true unless n=m+1). So you can't then go
on to say that X' contains more than one copy of X.

--
Nik ``nik@scs.leeds.ac.uk'' Silver
Xref: sparky sci.logic:1619 sci.math:12429 rec.games.chess:8300
From: elkies@ramanujan.harvard.edu (Noam Elkies)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Go-Moku solved? [thankfully not Re: "Solvability" in Chess]
Keywords: Go-Moku, Qubic
Date: 29 Sep 92 17:17:08 GMT
Article-I.D.: husc3.1992Sep29.131709.15945
Organization: Harvard Math Department

In article <1992Sep29.093031.14242@cs.rulimburg.nl>
allis@cs.rulimburg.nl (Victor Allis) writes:
>The only solved non-trivial games so far are Connect-Four (1988)
>Qubic (1980, 1991) and Go-Moku (1992).
>                       ^^^^^^^

This is news to me.  Was this with or without the constraint that
the first player may not win by 3&3 unless forced to by a direct
threat?  Who found the solution?  Does this mean Pente is also
solved or nearly solved?

--Noam D. Elkies (elkie@zariski.harvard.edu)
  Dept. of Mathematics, Harvard University

P.S. And what's the meaning of the curious date "1980, 1991" for
the solution of Qubic?  Was a hole in the 1980 argument found and
patched a decade later?