From: hyatt@cis.uab.edu (Robert Hyatt)
Subject: Re: "Solvability" in Chess
Organization: University of Alabama at Birmingham
Date: Wed, 30 Sep 1992 01:26:36 GMT

In article <717712154.101@mailbox.bison.mb> edward.m.hummel@mailbox.bison.mb.ca (edward.m.hummel) writes:
>Organization: AT&T
>
>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:
>>    1.	make a new node the first time the position is encountered,
>>    2.	make a new node the second time the position is encountered,
>>    3.	make a new node the third time the position is encountered, and
>>    4.	return to the third node every time the position is reencountered.
>>From the third time on, a draw can always be claimed.  From a 
>>game-theoretic perspective the positions are therefore equivalent.
>> ...
>>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.
>

The reason you can assign a loop the "draw" value is simple.  If, with
best play, the loop is the "best" I can do, then I can force the loop
to occur as long as I want, unless you make a move that breaks the loop.
However, since the loop was best for you also, you just made an
inferior move.  This move will either lead to a forced win for me,
or to another drawn line.  The point is, I can force the repeated
position and then claim it if I choose.  As long as you don't blunder,
that's the best I can hope for.  In proving that a game is won or lost
from the opening position, if I can force a win with your best play, I
can CERTAINLY force a win if you play less than optimal moves.  However,
If I can't force a win, but I can force a draw, then your "less than
optimal" moves will either lose the game for you, or lead to another
draw (how you evaluate a draw in 20 moves vs a draw in 100 moves is
up for grabs.  In cray blitz, we would go for the draw in 100 for the
very reason everyone has been point out -- give the opponent as much
time as possible to "blunder" while keeping a forced draw as the worst
that we can possible do.  However, for proving the opening position  as
won or lost or drawn, sub-optimal play makes no sense as it merely
hastens the inevitable.....

Bob Hyatt

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