From: hyatt@cis.uab.edu (Robert Hyatt)
Newsgroups: sci.logic,sci.math,rec.games.chess
Subject: Re: "Solvability" in Chess
Date: 28 Sep 92 15:46:18 GMT
Article-I.D.: cis.1992Sep28.154618.26890
Organization: University of Alabama at Birmingham

In article <1992Sep25.185626.14074@ugle.unit.no> andreas@idt.unit.no (Andreas Lothe Opdahl) writes:
>In article <1992Sep25.013439.1019@cbnewsl.cb.att.com> ed@cbnewsl.cb.att.com (edward.m.hummel) writes:
>>In article <1992Sep24.170907.26780@ugle.unit.no> andreas@idt.unit.no (Andreas Lothe Opdahl) writes:
>>>The point that 3- or 50-move draws must be *claimed* to apply does
>>>not make chess insolvable.  For some position:
>> ...
>>>In this case the min/max-search graph changes:
>>>
>>>    -	from being a tree or a directed acyclic graph 
>>>    -	into being a possibly cyclic graph.
>>>
>>>Extending the min/max-algorithm to account for this must be 
>>>possible since the graph is still finite (although the resulting
>>>algorithm would possibly be NP-complete.)
>>
>>The graph may be finite, but how do you assign a value to the loops?
>>As far as I can see, they have undetermined value.  (It is tempting
>>to assign them the value of a draw, but I don't see a PROOF that they
>>must have the value of a draw.  In fact, I can see good reason why it
>>cannot be proven that the loops have the value of a draw.)  If there
>>is no way to assign a value to the loops, the value of the game (i.e.,
>>the initial position) can only be written as a function of an undeterminable
>>parameter.  That may be a solution, but it is not single-valued.
>
>This is important, thank you for pointing it out.
>
>In general, the min/max-algorithm can be used almost as is.
>The only change needed would be never to (re-)visit a node *which is
>already in the current path*.  This works allright as long as there
>is at least one exit from at least one of the nodes in every loop.
>
>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.  One example is the set of nodes representing two 
>kings only on the board.  (These nodes are all draw by the rules of 
>chess, of course.)
>
>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.)
>
>What is your reason why it can not be *proven* that closed loops have
>the value of a draw?  Perhaps we must add the *axiom* that closed loops 
>are drawn to make chess solvable?
>
>Andreas
>-- 
`

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.

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.

The rules say that three repetitions offer the side making the repeating
move the opportunity to claim a draw.  If a human wants to repeat a position
endlessly, perhaps he ought to do something about getting his elevator to
go all the way to the roof.


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