From: andreas@idt.unit.no (Andreas Lothe Opdahl)
Subject: Re: "Solvability" in Chess
Organization: Div. of CS & Telematics, Norwegian Institute of Technology
Date: Mon, 28 Sep 92 20:49:38 GMT


In article <1992Sep28.154618.26890@cis.uab.edu> hyatt@cis.uab.edu (Robert Hyatt) writes:
>In article <1992Sep25.185626.14074@ugle.unit.no> andreas@idt.unit.no (Andreas Lothe Opdahl) writes:
>>The problem is the existence of "closed loops" in the node graph,
>>i.e. sets of nodes from which only other nodes in the set can
>>be visited.  Such a closed node set can *not* be assigned a value by 
>>min/max-search. 
...
>>More disturbing is the following family of positions [white: Ke1, a4, 
>>b5, c4, d5, e4, f5, g4, h5; black: Ke8, a5, b6, c5, d6, e5, f6, g5, h6].
>>If neither player claims a draw, the evaluation would enter a closed
>>loop.  Obviously, a "pure" game-theoretic evaluation can not make such 
>>an assumption about players behaviour (i.e. claiming a draw.)
...
>You are missing the entire point.  A three-fold repetition can be scored
>as a draw with absolutely no problems.  If you want to not claim the draw
>for some bizarre reason, no problem...  the loop in the tree has already
>been closed and we simply treated the third repetition as a draw.  If you
>insist on playing on, the fourth repetition is also a draw.....  If you
>have some alternative to repeating for the 500'th time then you had that
>alternative before reaching this position for the first time as well and
>it has already been examined.

My initial point in joining this thread was demonstrating just that.
However, Mr. Hummel has since pointed out to me that the situation is 
slightly more subtle.  I certainly still agree that chess is solvable, 
but now argue that some additional assumptions are needed.  (See my 
previous posting.)

>As for a player intentionally not claiming a draw after three-fold (or more
>repetitions)  I fail to see what that has with the question being 
>discussed here.....  A human can wipe all the pieces off the board and
>walk away, but that isn't something that the search algorithm has to
>include along the way.

We (at least I) are talking about *theoretical solvability* rather than
practical chess.  It turns out that game-theory is not applicable in 
its "purest" form, but that minor enhancements must be made.

In article <1992Sep28.155045.27036@cis.uab.edu> hyatt@cis.uab.edu (Robert Hyatt) writes (in response to several posts):
>You apparently don't understand the minmax algorithm at all.  If you
>enter a repeating line but have a winning move, the minmax algorithm
>will find the winning move and assume that that side will opt for
>best play and play the winning move immediately, rather than repeating
>a position for a dozen times and then going for the win.  

The point here (again) is positions of above type [white: Ke1, a4, b5, 
c4, d5, e4, f5, g4, h5; black: Ke8, a5, b6, c5, d6, e5, f6, g5, h6].
Assume (white) a3-a4 was the last move played.  If neither player
claims a draw, all possible positions will eventually be repeated 
three times and the 50-move rule come into effect.  However, there
exists no "winning move" for either side.  The *min/max-algorithm*
can easily be modified to account for this, but this algorithm is
only an *implementation* of game theory, it is not the theory itself.

>Let's take this discussion back to reality.....

Hmmm, I think this has been fun and most people have probably killed
the thread a long time ago anyhow.  This may have settled things for
me, and unless something *really* provoking occurs I'll shut my 
mouth for now :-)

>!Robert Hyatt                    Computer and Information Sciences   !
>!hyatt@cis.uab.edu               University of Alabama at Birmingham !

-- 

Andreas Lothe Opdahl			Phone:	+ 47 - 5 - 54 41 15
Department of Information Science	Fax: 	+ 47 - 5 - 54 41 07
University of Bergen, Norway		Email:	andreas@ifi.uib.no
Newsgroups: sci.logic,sci.math,rec.games.chess