HDTenEightyP/NetNews huggingface dataset:
From: fsmgs@camelot.acf-lab.alaska.edu (Michael Schmahl [Black-Robe Mage])
Subject: Re: "Solvability" in Chess
Organization: University of Alaska Computer Network
Date: Thu, 1 Oct 1992 20:39:35 GMT

Lars Roennow writes
> 
> In article <1992Sep25.205258.25317@cs.rochester.edu> fulk@cs.rochester.edu (Mark  
Fulk) writes:
> >Actually, the FIDE rules go a bit farther: if there have been 50 moves
> >without a capture, the game is drawn unless one player can demonstrate a
> >forced mate (this allows the use of the KBN vs. K mate).

Actually, there are a few positions which allow extensions to the 50-move rule,  
since the quickest forced mate is longer than 50 moves.  An example is K+N+N vs  
K+P.
From: cxm7@po.CWRU.Edu (Colin Mclarty)
Newsgroups: sci.logic
Subject: Re: A question in Recursion Theory
Date: 29 Sep 1992 19:28:30 GMT
Organization: Case Western Reserve University, Cleveland, OH (USA)
Reply-To: cxm7@po.CWRU.Edu (Colin Mclarty)
NNTP-Posting-Host: slc12.ins.cwru.edu


In a previous article, chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) says:

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

	Surely it is true, unless I misunderstaood the question.  Given 
sets I and J and a partial recursive psi that maps I onto J here is an
algorithm for a section g:

	to find gn for n in J, start evaluating psi for each m in I.
Of course you can not just start with the first m in I and evaluate 
psi for it, since psi might be undefined for it.  So take a few steps 
on the first element of I, then a few on the second, then a few more 
on the first, a few more on the second and a few on the third, then a
few more on the first....  This way we would eventually find the value 
of psi for each element of I where it is defined.  Since psi maps I 
onto J we will eventually finish evaluating psi on some element of I 
that gives n.  Define gn to be that element.  

	This algorithm may work for values of n not in J.  Indeed
it can not be defined precisely on J unless J is r.e.  But it is
defined for all of J.

Colin McLarty
From: burt@aupair.cs.athabascau.ca (Burt Voorhees)
Newsgroups: sci.logic
Subject: Re: The Mathematical Universe
Keywords: inconsistent multiplicities
Date: 3 Oct 92 16:50:49 GMT


  It seems to me that the existance theorem for the inverse limit takes care of
all this rather nicely.
Xref: sparky sci.logic:1610 sci.math:12391 rec.games.chess:8278
From: ronnow@iesd.auc.dk (Lars Roennow)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: 29 Sep 92 09:49:39 GMT
	<1992Sep25.185626.14074@ugle.unit.no>
	<1992Sep25.205258.25317@cs.rochester.edu>
	<1992Sep28.025846.7309@ucsu.Colorado.EDU>
Organization: Mathematics and Computer Science, Aalborg University


In article <1992Sep25.205258.25317@cs.rochester.edu> fulk@cs.rochester.edu (Mark Fulk) writes:
>Actually, the FIDE rules go a bit farther: if there have been 50 moves
>without a capture, the game is drawn unless one player can demonstrate a
>forced mate (this allows the use of the KBN vs. K mate).


Are you sure ? It is well known that KBN vs K is a forced mate in
about 37 moves (worst). But anyone have the right to test your
opponents technique. Therefore I am nearly sure thet one have to
demonstrate a mate *within* the 50 moves.

/ronnow
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: sci.logic
Subject: Re: A set cannot contain itself as a member
Date: 6 Oct 92 08:23:53 GMT
Organization: U of Arizona CS Dept, Tucson

In article  <Oct05.201328.96457@yuma.ACNS.ColoState.EDU> Steven Arnold writes:
]
]	The proposition to be proven is: A set can never contain
]itself as a member.
]	Suppose X is an arbitrary set which contains itself as a
]member.  All other members within the set can be symbolized as
]'g'; therefore,
]
]		X = {g,X}		(1)

A minor nit-pick: the above notation restricts X to be a two-element
set of which one element is the set g and the other set is X.  I
believe what you want is

  X = g union {X}

](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''!

This can only prove something about the particular representation
you use for the set.  In other words, assuming that your "therefore"
is correct, you have only proven that a set that contains itself
cannot be represented by an infinite expansion of the sort you give
above.

And your "therefore" itself is on shaky ground.  Rather than try to
approach it directly, let me propose a related falacy due to Zeno:

Suppose that you are at point A and want to move in a straight line to
point B, say 10 feet away.  Before you can get to B, you have to get
to C, halfway between A and B.  But before you can get to C, you have
to get to D, halfway between A and C.  You can see that this regress
is infinite, but that each segment is finite and takes a finite amount
of time to cross.  Moving an infinite number of finite distances
requires an infinite amount of time, so movement is impossible.
-- 
					David Gudeman
gudeman@cs.arizona.edu
From: oz@nexus.yorku.ca (Ozan Yigit)
Newsgroups: sci.logic
Subject: Re: FAQ
Date: 30 Sep 92 02:35:38 GMT
Article-I.D.: yorku.oz.717820538
Organization: York University

zeleny@husc9.harvard.edu (Michael Zeleny) writes:
 
>When writing articles for this forum, I can reasonably expect everyone to
>be familiar with TeX conventions (if they aren't, they damn well ought
>to be).

Actually, this "forum" has been around long enough and populated with
enough many people to make that assumption somewhat baseless. Just as
an example, there are those of us who cut teeth with troff long before
"TeX" was a meaningful [leaving aside a particular italian comic book
cowboy, that is] word. I will, however, cheerfully admit that "Andr\'e"
is much easier to read and type than "Andr\o'e\(aa'", so I guess you
could say that there are a few advantages to a document compiler that
came about only a decade after troff.

oz
---
In seeking the unattainable, simplicity | internet: oz@nexus.yorku.ca
only gets in the way. -- Alan J. Perlis | phone: 416 736 2100 x 33976
Newsgroups: sci.logic,sci.math,rec.games.chess
From: gudeman@cs.arizona.edu (David Gudeman)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" (long & pedantic)
Date: 29 Sep 92 07:11:43 GMT
Followup-To: sci.logic
Organization: U of Arizona CS Dept, Tucson

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
gudeman@cs.arizona.edu
From: markh@csd4.csd.uwm.edu (Mark)
Newsgroups: sci.logic
Subject: Re: Church's Heresy and the Unsolveability of chess
Date: 6 Oct 1992 20:23:34 GMT
Organization: Computing Services Division, University of Wisconsin - Milwaukee
NNTP-Posting-Host: 129.89.7.4

I expound on The Church's Heresy:
>   The strong version of Church's Heresy: the set of all functions that have
>been, are being, ever will be, or ever could be computed is a finite subset
>of the recursive functions bounded above in size by 2-to-the-256.

>Corollary: Every computable function can be represented uniquely by 32 bytes.
>Theorem:   This 32-byte coding is not computable, but is finite and recursive.

In article <1992Oct6.112819.16016@odin.diku.dk> torbenm@diku.dk (Torben AEgidius Mogensen) writes:
>No. It is only the size of the functions that can be represented in 32
>bytes. The functions themselves needs 2^256 bytes.

There are 2^256 32 byte integers.  Therefore there is a one-to-one
correspondence between 32 byte integers and computeable functions (which
there are less than 2^256 of).

Furthermore, this mapping is finite, therefore it is a recursive function.
It's just not computeable.
From: zeleny@husc9.harvard.edu (Michael Zeleny)
Newsgroups: sci.logic
Subject: Re: FAQ
Date: 30 Sep 92 23:57:46 GMT
Article-I.D.: husc3.1992Sep30.195747.15980
Organization: The Phallogocentric Cabal

In article <oz.717820538@yorku.ca> oz@nexus.yorku.ca (Ozan Yigit) writes:

>zeleny@husc9.harvard.edu (Michael Zeleny) writes:

MZ:
>>When writing articles for this forum, I can reasonably expect everyone to
>>be familiar with TeX conventions (if they aren't, they damn well ought
>>to be).

OY:
>Actually, this "forum" has been around long enough and populated with
>enough many people to make that assumption somewhat baseless. Just as
>an example, there are those of us who cut teeth with troff long before
>"TeX" was a meaningful [leaving aside a particular italian comic book
>cowboy, that is] word. I will, however, cheerfully admit that "Andr\'e"
>is much easier to read and type than "Andr\o'e\(aa'", so I guess you
>could say that there are a few advantages to a document compiler that
>came about only a decade after troff.

Point well taken; however at this moment TeX has the advantage of being the
de facto worldwide math typesetting standard in the academic circles.  So
on the net which is fairly biased towards an academic audience, it is well
suited to doing the work of lingua franca for mathematically oriented
newsgroups.

>oz
>---
>In seeking the unattainable, simplicity | internet: oz@nexus.yorku.ca
>only gets in the way. -- Alan J. Perlis | phone: 416 736 2100 x 33976

cordially,
mikhail zeleny@husc.harvard.edu
"Nous donnons la mort, nous saurons la subir."
Newsgroups: sci.logic,sci.math,rec.games.chess
From: converse@cs.uchicago.edu (timoshenko)
Subject: practical solvability
Organization: University of Chicago Computer Science
Date: Sun, 27 Sep 1992 08:21:06 GMT


I've made another posting on this topic that makes a similar point, but 
I hope that this one will be more fun.

There have been a number of posts about the solvability of chess that
argue that:

	i)  chess is theoretically solvable (i.e. assuming no time or
memory limitations, a computer could play perfect chess, simply by
exhaustive search of the game tree).

	ii) chess is practically insoluble (i.e. given what we know
about physics and the size and age of the universe, exhaustive search
of the game tree cannot be done).  

The corollary that is usually implicitly drawn is:

	iii) optimal chess cannot practically be played.

I would like to propose a game that is similar to chess in both (i)
and (ii) above, but that can practically be played optimally.   
Call it, um, Integer-chess.

Here are the rules of Integer-chess:

   Assume that X is some odd number that is greater than the number of possible 
   chess positions.  (say 10^200+1, if that is in fact large enough).

	1) White starts the game by choosing some number greater than
   0 and less than or equal to X.

	2) Thereafter, players alternate in choosing integers which
   are greater than 0, and less than or equal to X.  No number that
   has been chosen once by either player can be chosen again.

	3) Either player wins if:
	    3a) if he or she chooses a number which is less than a number
                     previously chosen by the opponent, or if
            3b) the opponent cannot make a legal move

Here is a game of Integer-chess, played optimally by both sides:

	White:  1
	Black:  2
	White:  3
	Black:  4
	[..]
	White:  X
	Black:  (concedes)

Since the "game-tree" of this game is as large as that of chess, the 
optimal game cannot be practically played by (dumb) game-tree search (ii).
It's also true that its game-tree is finite, so it is theoretically
solvable (i).  Finally, it should be clear that optimal Integer-chess
_can_ be practically played.  

My question is:  how can we conclude that (iii) is true of chess if it
is not true of Integer-chess?

	--tim
--
-------------------------------------------------------------------------------
Tim Converse  U. of Chicago CS Dept.  converse@cs.uchicago.edu  (312) 702-8584
From: amnell@klaava.Helsinki.FI (Marko Amnell)
Newsgroups: sci.logic
Subject: Re: A set cannot contain itself as a member
Keywords: recursion
Date: 6 Oct 92 08:27:50 GMT
Organization: University of Helsinki

In article <Oct05.201328.96457@yuma.ACNS.ColoState.EDU> sa114984@longs.lance.colostate.edu
(Steven Arnold) writes:

>	I am not an expert in set theory or the predicate
>calculus, but I was leafing through a book on the subject and the
>following informal "proof" occured to me.  Could any of you experts out
>there tell me if this contains a major flaw -- and if so, what it
>is?  Thanks.
>
>	The proposition to be proven is: A set can never contain
>itself as a member.
>	Suppose X is an arbitrary set which contains itself as a
>member.  All other members within the set can be symbolized as
>'g'; therefore,
>
>		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
>follows that X' != X'', for X' contains an X not contained in X''. 
>By the same reasoning, X != X', because X contains one more X
>than does X'.  Therefore, for any arbitrary set X, X cannot
>contain itself as a member.
>
>Steve

What you have just described is, I believe, what is called the
`unfolding' of the set x={x}.  It is a typical non-well-founded set.
A _non-well-founded set_ is a set that need not have an epsilon-minimal
element.  There will exist an infinite "descending" chain of the
epsilon-relation.  This is why it is called a non-well-founded set.  It
is not built out of pre-existing elements. The set x={x} can also be
represented by an infinite tree with a set assigned to each node.  
It would look like this, with an arrow indicating membership.

x-->x-->x-->x-->...

The existence of non-well-founded sets can be made into an axiom, the
Anti Foundation Axiom (AFA).  The resulting theory is very interesting
mathematically and has practical and theoretical applications.  See

Peter Aczel, _Non-Well-Founded Sets_.  CSLI Lecture Notes 14, (1988).

-- 
Marko Amnell
amnell@klaava.helsinki.fi
Graduate Student in Philosophy
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: Mon, 28 Sep 1992 05:49:59 GMT

In <1992Sep28.030130.18379@afit.af.mil> wbralick@afit.af.mil (Will Bralick) writes:

>In article <xeno.717639078@pv34ad.vincent.iastate.edu> xeno@iastate.edu (Gary L Snethen) writes:
>>
>>If all moves lead to a forced loss, claim a draw.
>>   reasoning:  We cannot assume our opponent will make a mistake.  Our best
>>               option is therefore to claim a draw.

>Huh?  If _all_ moves lead to a forced loss then our opponent cannot
>possibly make a mistake.  Resign.

Very sorry for the confusion...  Let me restate it more clearly.

If currently both players are in a loop, and the third repetition has
occured, then:

If all (alternative) moves lead to a forced loss, claim a draw.
   reasoning:  We cannot assume our opponent will make a mistake.  Our best
               option is therefore to claim a draw.

A similar situation happens all the time in 'go' in local positions...
Ever hear of a 'seki'?  Whoever attacks, loses.  This can happen in chess
too...  Whoever exits the loop first, can be forced to lose.  Thus, in this
situation, the game is a draw (the loop will never be exited).

>Regards,

>-- 

>Will Bralick					wbralick@afit.af.mil

---Xeno

Xref: sparky sci.logic:1574 sci.math:12292 rec.games.chess:8153
From: ts@cup.portal.com (Tim W Smith)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: Sun, 27 Sep 92 13:22:24 PDT
Organization: The Portal System (TM)
  <xeno.717323625@pv34ad.vincent.iastate.edu>
  <19s2bbINNcqi@agate.berkeley.edu>

> BUT!  If it can be proven that there is no possible way to represent
> the tree of all possible chess positions (really a graph, not a tree)
> because of its size and the Uncertainty Principle, I contend that chess 
> is not solvable by this method.  Conversely, if it can be proven that 
> there exists a way, however impractical, to represent this graph, then 
> chess is solvable by this method.  
> 
> I do not advance a proof for either side; I am merely pointing out
> what I feel is a flaw in your logic.

Do you also reject Euclid's (and others) proofs that there are an infinite
number of primes?  They contain the same "flaw" of logic. 

Besides, it is easy to represent the tree: Let T be the tree of all
possible chess games...

--Tim Smith
From: cxm7@po.CWRU.Edu (Colin Mclarty)
Newsgroups: sci.logic
Subject: Re: A question in Recursion Theory
Date: 30 Sep 1992 14:56:28 GMT
Organization: Case Western Reserve University, Cleveland, OH (USA)
Reply-To: cxm7@po.CWRU.Edu (Colin Mclarty)
NNTP-Posting-Host: slc12.ins.cwru.edu


In a previous article, fulk@cs.rochester.edu (Mark Fulk) says:

>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       ?
>>
>
>Thanks for the nice problem.  If I is recursively enumerable, there is
>such a section.  In general, there is not, 

	Well, I walked right into that one (with my alleged algorithm
for findng the section, which began by sneaking in an enumeration 
of I).

Colin McLarty
Xref: sparky sci.logic:1636 sci.math:12525 rec.games.chess:8393
From: peter@.engr.trinity.edu (Peter Vafeades)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: 30 Sep 92 19:04:52 GMT
Article-I.D.: ringer.1992Sep30.190452.11586
Organization: Trinity University

I have an interesting anecdote to relate:
Several years ago a group of amateur Greek chess players came up with a game we called "anti-chess".  The idea was quite simple: if you got your opponent to take
your king you won.  The basic simplifying rule was that if any material was offered to be taken you had to take it - if several pieces could be taken at certain move you could choose among the alternatives.  We played anti-chess for more than a year and had developed several scenarios where white lost if he played a set of first moves.  However, we had not "solved" the problem of anti-chess.  
At an international tournament some Greek players showed this game of anti-chess to some Russians.  We found out months later that "anti-chess" had been solved: white moves first, black always wins!
Granted, anti-chess is not as elaborate as chess and the rule about having to capture material really limits choice and renders a lesser probability tree, however, the solution was anything but trivial.  
My experience with antichess makes me believe that chess is "solvable": the 
question of whether it is "practically solvable", however, is a different matter.
Peter Vafeades
Xref: sparky sci.logic:1569 sci.math:12271 rec.games.chess:8134
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: practical solvability (correction)
From: converse@cs.uchicago.edu (timoshenko)
Date: Sun, 27 Sep 1992 09:13:13 GMT
Organization: University of Chicago Computer Science


In article <CONVERSE.92Sep27022106@sloth.uchicago.edu> converse@cs.uchicago.edu (timoshenko) writes:

   Here are the rules of Integer-chess:

      Assume that X is some odd number that is greater than the number of possible 
      chess positions.  (say 10^200+1, if that is in fact large enough).

	   1) White starts the game by choosing some number greater than
      0 and less than or equal to X.

	   2) Thereafter, players alternate in choosing integers which
      are greater than 0, and less than or equal to X.  No number that
      has been chosen once by either player can be chosen again.

	   3) Either player wins if:
	       3a) if he or she chooses a number which is less than a number
			previously chosen by the opponent, or if
	       3b) the opponent cannot make a legal move

   [..]
   Since the "game-tree" of this game is as large as that of chess, the 
   optimal game cannot be practically played by (dumb) game-tree search (ii).
   It's also true that its game-tree is finite, so it is theoretically
   solvable (i).  Finally, it should be clear that optimal Integer-chess
   _can_ be practically played.  

Whoops, a follow-up correction:  The optimal strategy I gave before
probably cannot be practically played, since it results in _extremely_
long games.  :-)  But I think that is easily addressed by making the
smart strategy result in short games.  For example, set X = 2^300, and
replace rule (3) with

	   3) Either player wins if 
		1) he or she chooses a power of two which is less than the
                      opponent's previous move, or if
		2) he or she chooses a power of two, when the
                      opponent's previous move was not a power of two.
     
Optimal play:
	White:  1
	Black:  2
	White:  4
	Black:  8
	[..]
	White:  2^300
	Black: concedes

	The point is just that the tree of legal games is _very_
large, yet an optimal strategy is clear.

	--tim


--
-------------------------------------------------------------------------------
Tim Converse  U. of Chicago CS Dept.  converse@cs.uchicago.edu  (312) 702-8584
Newsgroups: sci.logic,sci.math,rec.games.chess